1/*
2 * schedulingExample.cpp
3 * @brief hard scheduling example
4 * @date March 25, 2011
5 * @author Frank Dellaert
6 */
7
8#define ENABLE_TIMING
9#define ADD_NO_CACHING
10#define ADD_NO_PRUNING
11#include <gtsam_unstable/discrete/Scheduler.h>
12#include <gtsam/base/debug.h>
13#include <gtsam/base/timing.h>
14
15#include <algorithm>
16
17using namespace std;
18using namespace gtsam;
19
20size_t NRSTUDENTS = 12;
21
22bool NonZero(size_t i) {
23 return i > 0;
24}
25
26/* ************************************************************************* */
27void addStudent(Scheduler& s, size_t i) {
28 switch (i) {
29 case 0:
30 s.addStudent(studentName: "Young, Carol", area1: "Controls", area2: "Autonomy", area3: "Mechanics", advisor: "Fumin Zhang");
31 break;
32 case 1:
33 s.addStudent(studentName: "Erdogan, Can", area1: "Controls", area2: "AI", area3: "Perception", advisor: "Mike Stilman");
34 break;
35 case 2:
36 s.addStudent(studentName: "Arslan, Oktay", area1: "Controls", area2: "AI", area3: "Mechanics", advisor: "Panos Tsiotras");
37 break;
38 case 3:
39 s.addStudent(studentName: "Bhattacharjee, Tapomayukh", area1: "Controls", area2: "AI", area3: "Mechanics", advisor: "Charlie Kemp");
40 break;
41 case 4:
42 s.addStudent(studentName: "Grey, Michael", area1: "Controls", area2: "AI", area3: "Mechanics", advisor: "Wayne Book");
43 break;
44 case 5:
45 s.addStudent(studentName: "O'Flaherty, Rowland", area1: "Controls", area2: "AI", area3: "Mechanics", advisor: "Magnus Egerstedt");
46 break;
47 case 6:
48 s.addStudent(studentName: "Pickem, Daniel", area1: "Controls", area2: "AI", area3: "Mechanics", advisor: "Jeff Shamma");
49 break;
50 case 7:
51 s.addStudent(studentName: "Lee, Kimoon", area1: "Controls", area2: "Autonomy", area3: "Mechanics", advisor: "Henrik Christensen");
52 break;
53 case 8:
54 s.addStudent(studentName: "Melim, Andrew Lyon", area1: "Controls", area2: "AI", area3: "Perception", advisor: "Frank Dellaert");
55 break;
56 case 9:
57 s.addStudent(studentName: "Jensen, David", area1: "Controls", area2: "Autonomy", area3: "HRI", advisor: "Andrea Thomaz");
58 break;
59 case 10:
60 s.addStudent(studentName: "Nisbett, Jared", area1: "Controls", area2: "Perception", area3: "Mechanics", advisor: "Magnus Egerstedt");
61 break;
62 case 11:
63 s.addStudent(studentName: "Pan, Yunpeng", area1: "Controls", area2: "Perception", area3: "Mechanics", advisor: "Wayne Book");
64 break;
65// case 12:
66// s.addStudent("Grice, Phillip", "Controls", "None", "None", "Wayne Book");
67// break;
68// case 13:
69// s.addStudent("Robinette, Paul", "Controls", "None", "None", "Ayanna Howard");
70// break;
71// case 14:
72// s.addStudent("Huaman, Ana", "Autonomy", "None", "None", "Mike Stilman");
73// break;
74 }
75}
76
77/* ************************************************************************* */
78Scheduler largeExample(size_t nrStudents = NRSTUDENTS, bool addStudents=true) {
79 string path("../../../gtsam_unstable/discrete/examples/");
80 Scheduler s(nrStudents, path + "Doodle2013.csv");
81
82 s.addArea(facultyName: "Harvey Lipkin", areaName: "Mechanics");
83 s.addArea(facultyName: "Jun Ueda", areaName: "Mechanics");
84 s.addArea(facultyName: "Mike Stilman", areaName: "Mechanics");
85// s.addArea("Frank Dellaert", "Mechanics");
86 s.addArea(facultyName: "Wayne Book", areaName: "Mechanics");
87// s.addArea("Charlie Kemp", "Mechanics");
88
89 s.addArea(facultyName: "Patricio Vela", areaName: "Controls");
90 s.addArea(facultyName: "Magnus Egerstedt", areaName: "Controls");
91 s.addArea(facultyName: "Jun Ueda", areaName: "Controls");
92 s.addArea(facultyName: "Panos Tsiotras", areaName: "Controls");
93 s.addArea(facultyName: "Fumin Zhang", areaName: "Controls");
94 s.addArea(facultyName: "Ayanna Howard", areaName: "Controls");
95 s.addArea(facultyName: "Jeff Shamma", areaName: "Controls");
96
97 s.addArea(facultyName: "Frank Dellaert", areaName: "Perception");
98 s.addArea(facultyName: "Henrik Christensen", areaName: "Perception");
99
100 s.addArea(facultyName: "Mike Stilman", areaName: "AI");
101// s.addArea("Henrik Christensen", "AI");
102// s.addArea("Ayanna Howard", "AI");
103 s.addArea(facultyName: "Charles Isbell", areaName: "AI");
104// s.addArea("Tucker Balch", "AI");
105 s.addArea(facultyName: "Andrea Thomaz", areaName: "AI");
106
107 s.addArea(facultyName: "Ayanna Howard", areaName: "Autonomy");
108 s.addArea(facultyName: "Charlie Kemp", areaName: "Autonomy");
109
110// s.addArea("Andrea Thomaz", "HRI");
111 s.addArea(facultyName: "Karen Feigh", areaName: "HRI");
112// s.addArea("Charlie Kemp", "HRI");
113
114 // add students
115 if (addStudents)
116 for (size_t i = 0; i < nrStudents; i++)
117 addStudent(s, i);
118
119 return s;
120}
121
122/* ************************************************************************* */
123void runLargeExample() {
124
125 Scheduler scheduler = largeExample();
126 scheduler.print();
127
128 // BUILD THE GRAPH !
129 size_t addMutex = 3;
130 SETDEBUG("Scheduler::buildGraph", true);
131 scheduler.buildGraph(mutexBound: addMutex);
132
133 // Do brute force product and output that to file
134 if (scheduler.nrStudents() == 1) { // otherwise too slow
135 DecisionTreeFactor product =
136 *std::dynamic_pointer_cast<DecisionTreeFactor>(r: scheduler.product());
137 product.dot(name: "scheduling-large", keyFormatter: DefaultKeyFormatter, showZero: false);
138 }
139
140 // Do exact inference
141 // SETDEBUG("timing-verbose", true);
142 SETDEBUG("DiscreteConditional::DiscreteConditional", true);
143//#define SAMPLE
144#ifdef SAMPLE
145 gttic(large);
146 DiscreteBayesNet::shared_ptr chordal = scheduler.eliminate();
147 gttoc(large);
148 tictoc_finishedIteration();
149 tictoc_print();
150 for (size_t i=0;i<100;i++) {
151 auto assignment = sample(*chordal);
152 vector<size_t> stats(scheduler.nrFaculty());
153 scheduler.accumulateStats(assignment, stats);
154 size_t max = *max_element(stats.begin(), stats.end());
155 size_t min = *min_element(stats.begin(), stats.end());
156 size_t nz = count_if(stats.begin(), stats.end(), NonZero);
157// cout << min << ", " << max << ", " << nz << endl;
158 if (nz >= 13 && min >=1 && max <= 4) {
159 cout << "======================================================\n";
160 scheduler.printAssignment(assignment);
161 }
162 }
163#else
164 gttic(large);
165 auto MPE = scheduler.optimize();
166 gttoc(large);
167 tictoc_finishedIteration();
168 tictoc_print();
169 scheduler.printAssignment(assignment: MPE);
170#endif
171}
172
173/* ************************************************************************* */
174// Solve a series of relaxed problems for maximum flexibility solution
175void solveStaged(size_t addMutex = 2) {
176
177 bool debug = false;
178
179 // super-hack! just count...
180 SETDEBUG("DiscreteConditional::COUNT", true);
181 SETDEBUG("DiscreteConditional::DiscreteConditional", debug); // progress
182
183 // make a vector with slot availability, initially all 1
184 // Reads file to get count :-)
185 vector<double> slotsAvailable(largeExample(nrStudents: 0).nrTimeSlots(), 1.0);
186
187 // now, find optimal value for each student, using relaxed mutex constraints
188 for (size_t s = 0; s < NRSTUDENTS; s++) {
189 // add all students first time, then drop last one second time, etc...
190 Scheduler scheduler = largeExample(nrStudents: NRSTUDENTS - s);
191// scheduler.print(str(boost::format("Scheduler %d") % (NRSTUDENTS-s)));
192
193 // only allow slots not yet taken
194 scheduler.setSlotsAvailable(slotsAvailable);
195
196 // BUILD THE GRAPH !
197 scheduler.buildGraph(mutexBound: addMutex);
198
199 // Do EXACT INFERENCE
200 gttic_(eliminate);
201 DiscreteBayesNet::shared_ptr chordal = scheduler.eliminate();
202 gttoc_(eliminate);
203
204 // find root node
205 DiscreteConditional::shared_ptr root = chordal->back();
206 if (debug)
207 root->print(s: ""/*scheduler.studentName(s)*/);
208
209 // solve root node only
210 size_t bestSlot = root->argmax();
211
212 // get corresponding count
213 DiscreteKey dkey = scheduler.studentKey(i: NRSTUDENTS - 1 - s);
214 DiscreteValues values;
215 values[dkey.first] = bestSlot;
216 double count = (*root)(values);
217
218 // remove this slot from consideration
219 slotsAvailable[bestSlot] = 0.0;
220 cout << scheduler.studentName(i: NRSTUDENTS - 1 - s) << " = " << scheduler.slotName(s: bestSlot) << " (" << bestSlot
221 << "), count = " << count << endl;
222 }
223 tictoc_print_();
224}
225
226/* ************************************************************************* */
227// Sample from solution found above and evaluate cost function
228DiscreteBayesNet::shared_ptr createSampler(size_t i,
229 size_t slot, vector<Scheduler>& schedulers) {
230 Scheduler scheduler = largeExample(nrStudents: 1,addStudents: false);
231 addStudent(s&: scheduler, i);
232 cout << " creating sampler for " << scheduler.studentName(i: 0) << endl;
233 SETDEBUG("Scheduler::buildGraph", false);
234// scheduler.print();
235 scheduler.addStudentSpecificConstraints(i: 0, slot);
236 DiscreteBayesNet::shared_ptr chordal = scheduler.eliminate();
237 schedulers.push_back(x: scheduler);
238 return chordal;
239}
240
241void sampleSolutions() {
242
243 size_t nrFaculty = 17; // Change to correct number !
244
245 vector<Scheduler> schedulers;
246 vector<DiscreteBayesNet::shared_ptr> samplers(NRSTUDENTS);
247
248 // Given the time-slots, we can create NRSTUDENTS independent samplers
249 vector<size_t> slots{12,11,13, 21,16,1, 3,2,6, 7,22,4}; // given slots
250 for (size_t i = 0; i < NRSTUDENTS; i++)
251 samplers[i] = createSampler(i, slot: slots[i], schedulers);
252
253 // now, sample schedules
254 for (size_t n = 0; n < 10000; n++) {
255 vector<size_t> stats(nrFaculty, 0);
256 vector<DiscreteValues> samples;
257 for (size_t i = 0; i < NRSTUDENTS; i++) {
258 samples.push_back(x: samplers[i]->sample());
259 schedulers[i].accumulateStats(assignment: samples[i], stats);
260 }
261 size_t max = *max_element(first: stats.begin(), last: stats.end());
262 size_t min = *min_element(first: stats.begin(), last: stats.end());
263 size_t nz = count_if(first: stats.begin(), last: stats.end(), pred: NonZero);
264 if (nz >= 16 && max <= 3) {
265 cout << "Sampled schedule " << n + 1 << ", min = " << min << ", nz = " << nz << ", max = " << max << endl;
266 for (size_t i = 0; i < NRSTUDENTS; i++) {
267 cout << schedulers[i].studentName(i: 0) << " : " << schedulers[i].slotName(
268 s: slots[i]) << endl;
269 schedulers[i].printSpecial(assignment: samples[i]);
270 }
271 }
272 }
273}
274
275/* ************************************************************************* */
276int main() {
277// runLargeExample();
278// solveStaged(3);
279 sampleSolutions();
280 return 0;
281}
282/* ************************************************************************* */
283
284