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
20/* ************************************************************************* */
21void addStudent(Scheduler& s, size_t i) {
22 switch (i) {
23 case 0:
24 s.addStudent(studentName: "Michael N", area1: "AI", area2: "Autonomy", area3: "Perception", advisor: "Tucker Balch");
25 break;
26 case 1:
27 s.addStudent(studentName: "Tucker H", area1: "Controls", area2: "AI", area3: "Perception", advisor: "Jim Rehg");
28 break;
29 case 2:
30 s.addStudent(studentName: "Jake H", area1: "Controls", area2: "AI", area3: "Perception", advisor: "Henrik Christensen");
31 break;
32 case 3:
33 s.addStudent(studentName: "Tobias K", area1: "Controls", area2: "AI", area3: "Autonomy", advisor: "Mike Stilman");
34 break;
35 case 4:
36 s.addStudent(studentName: "Shu J", area1: "Controls", area2: "AI", area3: "HRI", advisor: "N/A 1");
37 break;
38 case 5:
39 s.addStudent(studentName: "Akansel C", area1: "AI", area2: "Autonomy", area3: "Mechanics",
40 advisor: "Henrik Christensen");
41 break;
42 case 6:
43 s.addStudent(studentName: "Tiffany C", area1: "Controls", area2: "N/A 1", area3: "N/A 2", advisor: "Charlie Kemp");
44 break;
45 }
46}
47/* ************************************************************************* */
48Scheduler largeExample(size_t nrStudents = 7) {
49// char cCurrentPath[FILENAME_MAX];
50// if (!getcwd(cCurrentPath, sizeof(cCurrentPath))) return errno;
51// cCurrentPath[sizeof(cCurrentPath) - 1] = '\0'; /* not really required */
52// printf ("The current working directory is %s", cCurrentPath);
53
54 string path("../../../gtsam_unstable/discrete/examples/");
55 Scheduler s(nrStudents, path + "Doodle.csv");
56
57 s.addArea(facultyName: "Harvey Lipkin", areaName: "Mechanics");
58 s.addArea(facultyName: "Wayne Book", areaName: "Mechanics");
59 s.addArea(facultyName: "Jun Ueda", areaName: "Mechanics");
60
61 // s.addArea("Wayne Book", "Controls");
62 s.addArea(facultyName: "Patricio Vela", areaName: "Controls");
63 s.addArea(facultyName: "Magnus Egerstedt", areaName: "Controls");
64 s.addArea(facultyName: "Jun Ueda", areaName: "Controls");
65
66 // s.addArea("Frank Dellaert", "Perception");
67 s.addArea(facultyName: "Jim Rehg", areaName: "Perception");
68 s.addArea(facultyName: "Irfan Essa", areaName: "Perception");
69 s.addArea(facultyName: "Aaron Bobick", areaName: "Perception");
70 s.addArea(facultyName: "Henrik Christensen", areaName: "Perception");
71
72 s.addArea(facultyName: "Mike Stilman", areaName: "AI");
73 s.addArea(facultyName: "Henrik Christensen", areaName: "AI");
74 s.addArea(facultyName: "Frank Dellaert", areaName: "AI");
75 s.addArea(facultyName: "Ayanna Howard", areaName: "AI");
76 // s.addArea("Tucker Balch", "AI");
77
78 s.addArea(facultyName: "Ayanna Howard", areaName: "Autonomy");
79 // s.addArea("Andrea Thomaz", "Autonomy");
80 s.addArea(facultyName: "Charlie Kemp", areaName: "Autonomy");
81 s.addArea(facultyName: "Tucker Balch", areaName: "Autonomy");
82 s.addArea(facultyName: "Ron Arkin", areaName: "Autonomy");
83
84 s.addArea(facultyName: "Andrea Thomaz", areaName: "HRI");
85 s.addArea(facultyName: "Karen Feigh", areaName: "HRI");
86 s.addArea(facultyName: "Charlie Kemp", areaName: "HRI");
87
88 // Allow students not to take three areas
89 s.addArea(facultyName: "N/A 1", areaName: "N/A 1");
90 s.addArea(facultyName: "N/A 2", areaName: "N/A 2");
91
92 // add students
93 for (size_t i = 0; i < nrStudents; i++)
94 addStudent(s, i);
95
96 return s;
97}
98
99/* ************************************************************************* */
100void runLargeExample() {
101
102 Scheduler scheduler = largeExample();
103 scheduler.print();
104
105 // BUILD THE GRAPH !
106 size_t addMutex = 2;
107 scheduler.buildGraph(mutexBound: addMutex);
108
109 // Do brute force product and output that to file
110 if (scheduler.nrStudents() == 1) { // otherwise too slow
111 DecisionTreeFactor product =
112 *std::dynamic_pointer_cast<DecisionTreeFactor>(r: scheduler.product());
113 product.dot(name: "scheduling-large", keyFormatter: DefaultKeyFormatter, showZero: false);
114 }
115
116 // Do exact inference
117 // SETDEBUG("timing-verbose", true);
118 SETDEBUG("DiscreteConditional::DiscreteConditional", true);
119 gttic(large);
120 auto MPE = scheduler.optimize();
121 gttoc(large);
122 tictoc_finishedIteration();
123 tictoc_print();
124 scheduler.printAssignment(assignment: MPE);
125}
126
127/* ************************************************************************* */
128// Solve a series of relaxed problems for maximum flexibility solution
129void solveStaged(size_t addMutex = 2) {
130
131 // super-hack! just count...
132 bool debug = false;
133 SETDEBUG("DiscreteConditional::COUNT", true);
134 SETDEBUG("DiscreteConditional::DiscreteConditional", debug); // progress
135
136 // make a vector with slot availability, initially all 1
137 // Reads file to get count :-)
138 vector<double> slotsAvailable(largeExample(nrStudents: 0).nrTimeSlots(), 1.0);
139
140 // now, find optimal value for each student, using relaxed mutex constraints
141 for (size_t s = 0; s < 7; s++) {
142 // add all students first time, then drop last one second time, etc...
143 Scheduler scheduler = largeExample(nrStudents: 7 - s);
144 //scheduler.print(str(boost::format("Scheduler %d") % (7-s)));
145
146 // only allow slots not yet taken
147 scheduler.setSlotsAvailable(slotsAvailable);
148
149 // BUILD THE GRAPH !
150 scheduler.buildGraph(mutexBound: addMutex);
151
152 // Do EXACT INFERENCE
153 gttic_(eliminate);
154 DiscreteBayesNet::shared_ptr chordal = scheduler.eliminate();
155 gttoc_(eliminate);
156
157 // find root node
158 DiscreteConditional::shared_ptr root = chordal->back();
159 if (debug)
160 root->print(s: ""/*scheduler.studentName(s)*/);
161
162 // solve root node only
163 size_t bestSlot = root->argmax();
164
165 // get corresponding count
166 DiscreteKey dkey = scheduler.studentKey(i: 6 - s);
167 DiscreteValues values;
168 values[dkey.first] = bestSlot;
169 size_t count = (*root)(values);
170
171 // remove this slot from consideration
172 slotsAvailable[bestSlot] = 0.0;
173 cout << scheduler.studentName(i: 6 - s) << " = " << scheduler.slotName(s: bestSlot) << " (" << bestSlot
174 << "), count = " << count << endl;
175 }
176 tictoc_print_();
177
178 // Solution with addMutex = 2: (20 secs)
179 // TC = Wed 2 (9), count = 96375041778
180 // AC = Tue 2 (5), count = 4076088090
181 // SJ = Mon 1 (0), count = 29596704
182 // TK = Mon 3 (2), count = 755370
183 // JH = Wed 4 (11), count = 12000
184 // TH = Fri 2 (17), count = 220
185 // MN = Fri 1 (16), count = 5
186 //
187 // Mutex does make a difference !!
188
189}
190
191/* ************************************************************************* */
192// Sample from solution found above and evaluate cost function
193bool NonZero(size_t i) {
194 return i > 0;
195}
196
197DiscreteBayesNet::shared_ptr createSampler(size_t i,
198 size_t slot, vector<Scheduler>& schedulers) {
199 Scheduler scheduler = largeExample(nrStudents: 0); // todo: wrong nr students
200 addStudent(s&: scheduler, i);
201 SETDEBUG("Scheduler::buildGraph", false);
202 scheduler.addStudentSpecificConstraints(i: 0, slot);
203 DiscreteBayesNet::shared_ptr chordal = scheduler.eliminate();
204 // chordal->print(scheduler[i].studentKey(0).name()); // large !
205 schedulers.push_back(x: scheduler);
206 return chordal;
207}
208
209void sampleSolutions() {
210
211 vector<Scheduler> schedulers;
212 vector<DiscreteBayesNet::shared_ptr> samplers(7);
213
214 // Given the time-slots, we can create 7 independent samplers
215 vector<size_t> slots{16, 17, 11, 2, 0, 5, 9}; // given slots
216 for (size_t i = 0; i < 7; i++)
217 samplers[i] = createSampler(i, slot: slots[i], schedulers);
218
219 // now, sample schedules
220 for (size_t n = 0; n < 500; n++) {
221 vector<size_t> stats(19, 0);
222 vector<DiscreteValues> samples;
223 for (size_t i = 0; i < 7; i++) {
224 samples.push_back(x: samplers[i]->sample());
225 schedulers[i].accumulateStats(assignment: samples[i], stats);
226 }
227 size_t max = *max_element(first: stats.begin(), last: stats.end());
228 size_t min = *min_element(first: stats.begin(), last: stats.end());
229 size_t nz = count_if(first: stats.begin(), last: stats.end(), pred: NonZero);
230 if (nz >= 15 && max <= 2) {
231 cout << "Sampled schedule " << (n + 1) << ", min = " << min << ", nz = " << nz
232 << ", max = " << max << endl;
233 for (size_t i = 0; i < 7; i++) {
234 cout << schedulers[i].studentName(i: 0) << " : " << schedulers[i].slotName(
235 s: slots[i]) << endl;
236 schedulers[i].printSpecial(assignment: samples[i]);
237 }
238 }
239 }
240 // Output was
241 // Sampled schedule 359, min = 0, nz = 15, max = 2
242 // Michael N : Fri 9:00-10.30
243 // Michael N AI: Frank Dellaert
244 // Michael N Autonomy: Charlie Kemp
245 // Michael N Perception: Henrik Christensen
246 //
247 // Tucker H : Fri 10:30-12:00
248 // Tucker H AI: Ayanna Howard
249 // Tucker H Controls: Patricio Vela
250 // Tucker H Perception: Irfan Essa
251 //
252 // Jake H : Wed 3:00-4:30
253 // Jake H AI: Mike Stilman
254 // Jake H Controls: Magnus Egerstedt
255 // Jake H Perception: Jim Rehg
256 //
257 // Tobias K : Mon 1:30-3:00
258 // Tobias K AI: Ayanna Howard
259 // Tobias K Autonomy: Charlie Kemp
260 // Tobias K Controls: Magnus Egerstedt
261 //
262 // Shu J : Mon 9:00-10.30
263 // Shu J AI: Mike Stilman
264 // Shu J Controls: Jun Ueda
265 // Shu J HRI: Andrea Thomaz
266 //
267 // Akansel C : Tue 10:30-12:00
268 // Akansel C AI: Frank Dellaert
269 // Akansel C Autonomy: Tucker Balch
270 // Akansel C Mechanics: Harvey Lipkin
271 //
272 // Tiffany C : Wed 10:30-12:00
273 // Tiffany C Controls: Patricio Vela
274 // Tiffany C N/A 1: N/A 1
275 // Tiffany C N/A 2: N/A 2
276
277}
278
279/* ************************************************************************* */
280void accomodateStudent() {
281
282 // super-hack! just count...
283 bool debug = false;
284 // SETDEBUG("DiscreteConditional::COUNT",true);
285 SETDEBUG("DiscreteConditional::DiscreteConditional", debug); // progress
286
287 Scheduler scheduler = largeExample(nrStudents: 0);
288 // scheduler.addStudent("Victor E", "Autonomy", "HRI", "AI",
289 // "Henrik Christensen");
290 scheduler.addStudent(studentName: "Carlos N", area1: "Perception", area2: "AI", area3: "Autonomy",
291 advisor: "Henrik Christensen");
292 scheduler.print(s: "scheduler");
293
294 // rule out all occupied slots
295 vector<size_t> slots{16, 17, 11, 2, 0, 5, 9, 14};
296 vector<double> slotsAvailable(scheduler.nrTimeSlots(), 1.0);
297 for(size_t s: slots)
298 slotsAvailable[s] = 0;
299 scheduler.setSlotsAvailable(slotsAvailable);
300
301 // BUILD THE GRAPH !
302 scheduler.buildGraph(mutexBound: 1);
303
304 // Do EXACT INFERENCE
305 DiscreteBayesNet::shared_ptr chordal = scheduler.eliminate();
306
307 // find root node
308 DiscreteConditional::shared_ptr root = chordal->back();
309 if (debug)
310 root->print(s: ""/*scheduler.studentName(s)*/);
311 // GTSAM_PRINT(*chordal);
312
313 // solve root node only
314 size_t bestSlot = root->argmax();
315
316 // get corresponding count
317 DiscreteKey dkey = scheduler.studentKey(i: 0);
318 DiscreteValues values;
319 values[dkey.first] = bestSlot;
320 size_t count = (*root)(values);
321 cout << scheduler.studentName(i: 0) << " = " << scheduler.slotName(s: bestSlot) << " (" << bestSlot
322 << "), count = " << count << endl;
323 // sample schedules
324 for (size_t n = 0; n < 10; n++) {
325 auto sample0 = chordal->sample();
326 scheduler.printAssignment(assignment: sample0);
327 }
328}
329
330/* ************************************************************************* */
331int main() {
332 runLargeExample();
333 solveStaged(addMutex: 3);
334// sampleSolutions();
335 // accomodateStudent();
336 return 0;
337}
338/* ************************************************************************* */
339
340