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 = 9;
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: "Pan, Yunpeng", area1: "Controls", area2: "Perception", area3: "Mechanics", advisor: "Eric Johnson");
31 break;
32 case 1:
33 s.addStudent(studentName: "Sawhney, Rahul", area1: "Controls", area2: "AI", area3: "Perception", advisor: "Henrik Christensen");
34 break;
35 case 2:
36 s.addStudent(studentName: "Akgun, Baris", area1: "Controls", area2: "AI", area3: "HRI", advisor: "Andrea Thomaz");
37 break;
38 case 3:
39 s.addStudent(studentName: "Jiang, Shu", area1: "Controls", area2: "AI", area3: "Perception", advisor: "Ron Arkin");
40 break;
41 case 4:
42 s.addStudent(studentName: "Grice, Phillip", area1: "Controls", area2: "Perception", area3: "HRI", advisor: "Charlie Kemp");
43 break;
44 case 5:
45 s.addStudent(studentName: "Huaman, Ana", area1: "Controls", area2: "AI", area3: "Perception", advisor: "Mike Stilman");
46 break;
47 case 6:
48 s.addStudent(studentName: "Levihn, Martin", area1: "AI", area2: "Autonomy", area3: "Perception", advisor: "Mike Stilman");
49 break;
50 case 7:
51 s.addStudent(studentName: "Nieto, Carlos", area1: "AI", area2: "Autonomy", area3: "Perception", advisor: "Henrik Christensen");
52 break;
53 case 8:
54 s.addStudent(studentName: "Robinette, Paul", area1: "Controls", area2: "AI", area3: "HRI", advisor: "Ayanna Howard");
55 break;
56 }
57}
58
59/* ************************************************************************* */
60Scheduler largeExample(size_t nrStudents = NRSTUDENTS) {
61 string path("../../../gtsam_unstable/discrete/examples/");
62 Scheduler s(nrStudents, path + "Doodle2012.csv");
63
64 s.addArea(facultyName: "Harvey Lipkin", areaName: "Mechanics");
65 s.addArea(facultyName: "Jun Ueda", areaName: "Mechanics");
66
67 s.addArea(facultyName: "Patricio Vela", areaName: "Controls");
68 s.addArea(facultyName: "Magnus Egerstedt", areaName: "Controls");
69 s.addArea(facultyName: "Jun Ueda", areaName: "Controls");
70 s.addArea(facultyName: "Panos Tsiotras", areaName: "Controls");
71 s.addArea(facultyName: "Fumin Zhang", areaName: "Controls");
72
73 s.addArea(facultyName: "Henrik Christensen", areaName: "Perception");
74 s.addArea(facultyName: "Aaron Bobick", areaName: "Perception");
75
76 s.addArea(facultyName: "Mike Stilman", areaName: "AI");
77// s.addArea("Henrik Christensen", "AI");
78 s.addArea(facultyName: "Ayanna Howard", areaName: "AI");
79 s.addArea(facultyName: "Charles Isbell", areaName: "AI");
80 s.addArea(facultyName: "Tucker Balch", areaName: "AI");
81
82 s.addArea(facultyName: "Ayanna Howard", areaName: "Autonomy");
83 s.addArea(facultyName: "Charlie Kemp", areaName: "Autonomy");
84 s.addArea(facultyName: "Tucker Balch", areaName: "Autonomy");
85 s.addArea(facultyName: "Ron Arkin", areaName: "Autonomy");
86
87 s.addArea(facultyName: "Andrea Thomaz", areaName: "HRI");
88 s.addArea(facultyName: "Karen Feigh", areaName: "HRI");
89 s.addArea(facultyName: "Charlie Kemp", areaName: "HRI");
90
91 // add students
92 for (size_t i = 0; i < nrStudents; i++)
93 addStudent(s, i);
94
95 return s;
96}
97
98/* ************************************************************************* */
99void runLargeExample() {
100
101 Scheduler scheduler = largeExample();
102 scheduler.print();
103
104 // BUILD THE GRAPH !
105 size_t addMutex = 3;
106 // SETDEBUG("Scheduler::buildGraph", true);
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#define SAMPLE
120#ifdef SAMPLE
121 gttic(large);
122 DiscreteBayesNet::shared_ptr chordal = scheduler.eliminate();
123 gttoc(large);
124 tictoc_finishedIteration();
125 tictoc_print();
126 for (size_t i=0;i<100;i++) {
127 auto assignment = chordal->sample();
128 vector<size_t> stats(scheduler.nrFaculty());
129 scheduler.accumulateStats(assignment, stats);
130 size_t max = *max_element(first: stats.begin(), last: stats.end());
131 size_t min = *min_element(first: stats.begin(), last: stats.end());
132 size_t nz = count_if(first: stats.begin(), last: stats.end(), pred: NonZero);
133// cout << min << ", " << max << ", " << nz << endl;
134 if (nz >= 13 && min >=1 && max <= 4) {
135 cout << "======================================================\n";
136 scheduler.printAssignment(assignment);
137 }
138 }
139#else
140 gttic(large);
141 auto MPE = scheduler.optimize();
142 gttoc(large);
143 tictoc_finishedIteration();
144 tictoc_print();
145 scheduler.printAssignment(MPE);
146#endif
147}
148
149/* ************************************************************************* */
150// Solve a series of relaxed problems for maximum flexibility solution
151void solveStaged(size_t addMutex = 2) {
152
153 // super-hack! just count...
154 bool debug = false;
155 SETDEBUG("DiscreteConditional::COUNT", true);
156 SETDEBUG("DiscreteConditional::DiscreteConditional", debug); // progress
157
158 // make a vector with slot availability, initially all 1
159 // Reads file to get count :-)
160 vector<double> slotsAvailable(largeExample(nrStudents: 0).nrTimeSlots(), 1.0);
161
162 // now, find optimal value for each student, using relaxed mutex constraints
163 for (size_t s = 0; s < NRSTUDENTS; s++) {
164 // add all students first time, then drop last one second time, etc...
165 Scheduler scheduler = largeExample(nrStudents: NRSTUDENTS - s);
166 //scheduler.print(str(boost::format("Scheduler %d") % (NRSTUDENTS-s)));
167
168 // only allow slots not yet taken
169 scheduler.setSlotsAvailable(slotsAvailable);
170
171 // BUILD THE GRAPH !
172 scheduler.buildGraph(mutexBound: addMutex);
173
174 // Do EXACT INFERENCE
175 gttic_(eliminate);
176 DiscreteBayesNet::shared_ptr chordal = scheduler.eliminate();
177 gttoc_(eliminate);
178
179 // find root node
180 DiscreteConditional::shared_ptr root = chordal->back();
181 if (debug)
182 root->print(s: ""/*scheduler.studentName(s)*/);
183
184 // solve root node only
185 size_t bestSlot = root->argmax();
186
187 // get corresponding count
188 DiscreteKey dkey = scheduler.studentKey(i: NRSTUDENTS - 1 - s);
189 DiscreteValues values;
190 values[dkey.first] = bestSlot;
191 size_t count = (*root)(values);
192
193 // remove this slot from consideration
194 slotsAvailable[bestSlot] = 0.0;
195 cout << scheduler.studentName(i: NRSTUDENTS - 1 - s) << " = " <<
196 scheduler.slotName(s: bestSlot) << " (" << bestSlot
197 << "), count = " << count << endl;
198 }
199 tictoc_print_();
200}
201
202/* ************************************************************************* */
203// Sample from solution found above and evaluate cost function
204DiscreteBayesNet::shared_ptr createSampler(size_t i,
205 size_t slot, vector<Scheduler>& schedulers) {
206 Scheduler scheduler = largeExample(nrStudents: 0); // todo: wrong nr students
207 addStudent(s&: scheduler, i);
208 SETDEBUG("Scheduler::buildGraph", false);
209 scheduler.addStudentSpecificConstraints(i: 0, slot);
210 DiscreteBayesNet::shared_ptr chordal = scheduler.eliminate();
211 schedulers.push_back(x: scheduler);
212 return chordal;
213}
214
215void sampleSolutions() {
216
217 vector<Scheduler> schedulers;
218 vector<DiscreteBayesNet::shared_ptr> samplers(NRSTUDENTS);
219
220 // Given the time-slots, we can create NRSTUDENTS independent samplers
221 vector<size_t> slots{3, 20, 2, 6, 5, 11, 1, 4}; // given slots
222 for (size_t i = 0; i < NRSTUDENTS; i++)
223 samplers[i] = createSampler(i, slot: slots[i], schedulers);
224
225 // now, sample schedules
226 for (size_t n = 0; n < 500; n++) {
227 vector<size_t> stats(19, 0);
228 vector<DiscreteValues> samples;
229 for (size_t i = 0; i < NRSTUDENTS; i++) {
230 samples.push_back(x: samplers[i]->sample());
231 schedulers[i].accumulateStats(assignment: samples[i], stats);
232 }
233 size_t max = *max_element(first: stats.begin(), last: stats.end());
234 size_t min = *min_element(first: stats.begin(), last: stats.end());
235 size_t nz = count_if(first: stats.begin(), last: stats.end(), pred: NonZero);
236 if (nz >= 15 && max <= 2) {
237 cout << "Sampled schedule " << (n + 1) << ", min = " << min
238 << ", nz = " << nz << ", max = " << max << endl;
239 for (size_t i = 0; i < NRSTUDENTS; i++) {
240 cout << schedulers[i].studentName(i: 0) << " : " << schedulers[i].slotName(
241 s: slots[i]) << endl;
242 schedulers[i].printSpecial(assignment: samples[i]);
243 }
244 }
245 }
246}
247
248/* ************************************************************************* */
249int main() {
250// runLargeExample();
251 solveStaged(addMutex: 3);
252// sampleSolutions();
253 return 0;
254}
255/* ************************************************************************* */
256
257