schedulingQuals13.cpp
Go to the documentation of this file.
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
12 #include <gtsam/base/debug.h>
13 #include <gtsam/base/timing.h>
14 
15 #include <algorithm>
16 
17 using namespace std;
18 using namespace gtsam;
19 
20 size_t NRSTUDENTS = 12;
21 
22 bool NonZero(size_t i) {
23  return i > 0;
24 }
25 
26 /* ************************************************************************* */
27 void addStudent(Scheduler& s, size_t i) {
28  switch (i) {
29  case 0:
30  s.addStudent("Young, Carol", "Controls", "Autonomy", "Mechanics", "Fumin Zhang");
31  break;
32  case 1:
33  s.addStudent("Erdogan, Can", "Controls", "AI", "Perception", "Mike Stilman");
34  break;
35  case 2:
36  s.addStudent("Arslan, Oktay", "Controls", "AI", "Mechanics", "Panos Tsiotras");
37  break;
38  case 3:
39  s.addStudent("Bhattacharjee, Tapomayukh", "Controls", "AI", "Mechanics", "Charlie Kemp");
40  break;
41  case 4:
42  s.addStudent("Grey, Michael", "Controls", "AI", "Mechanics", "Wayne Book");
43  break;
44  case 5:
45  s.addStudent("O'Flaherty, Rowland", "Controls", "AI", "Mechanics", "Magnus Egerstedt");
46  break;
47  case 6:
48  s.addStudent("Pickem, Daniel", "Controls", "AI", "Mechanics", "Jeff Shamma");
49  break;
50  case 7:
51  s.addStudent("Lee, Kimoon", "Controls", "Autonomy", "Mechanics", "Henrik Christensen");
52  break;
53  case 8:
54  s.addStudent("Melim, Andrew Lyon", "Controls", "AI", "Perception", "Frank Dellaert");
55  break;
56  case 9:
57  s.addStudent("Jensen, David", "Controls", "Autonomy", "HRI", "Andrea Thomaz");
58  break;
59  case 10:
60  s.addStudent("Nisbett, Jared", "Controls", "Perception", "Mechanics", "Magnus Egerstedt");
61  break;
62  case 11:
63  s.addStudent("Pan, Yunpeng", "Controls", "Perception", "Mechanics", "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 /* ************************************************************************* */
78 Scheduler 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("Harvey Lipkin", "Mechanics");
83  s.addArea("Jun Ueda", "Mechanics");
84  s.addArea("Mike Stilman", "Mechanics");
85 // s.addArea("Frank Dellaert", "Mechanics");
86  s.addArea("Wayne Book", "Mechanics");
87 // s.addArea("Charlie Kemp", "Mechanics");
88 
89  s.addArea("Patricio Vela", "Controls");
90  s.addArea("Magnus Egerstedt", "Controls");
91  s.addArea("Jun Ueda", "Controls");
92  s.addArea("Panos Tsiotras", "Controls");
93  s.addArea("Fumin Zhang", "Controls");
94  s.addArea("Ayanna Howard", "Controls");
95  s.addArea("Jeff Shamma", "Controls");
96 
97  s.addArea("Frank Dellaert", "Perception");
98  s.addArea("Henrik Christensen", "Perception");
99 
100  s.addArea("Mike Stilman", "AI");
101 // s.addArea("Henrik Christensen", "AI");
102 // s.addArea("Ayanna Howard", "AI");
103  s.addArea("Charles Isbell", "AI");
104 // s.addArea("Tucker Balch", "AI");
105  s.addArea("Andrea Thomaz", "AI");
106 
107  s.addArea("Ayanna Howard", "Autonomy");
108  s.addArea("Charlie Kemp", "Autonomy");
109 
110 // s.addArea("Andrea Thomaz", "HRI");
111  s.addArea("Karen Feigh", "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 /* ************************************************************************* */
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(addMutex);
132 
133  // Do brute force product and output that to file
134  if (scheduler.nrStudents() == 1) { // otherwise too slow
135  DecisionTreeFactor product = scheduler.product();
136  product.dot("scheduling-large", DefaultKeyFormatter, false);
137  }
138 
139  // Do exact inference
140  // SETDEBUG("timing-verbose", true);
141  SETDEBUG("DiscreteConditional::DiscreteConditional", true);
142 //#define SAMPLE
143 #ifdef SAMPLE
144  gttic(large);
145  DiscreteBayesNet::shared_ptr chordal = scheduler.eliminate();
146  gttoc(large);
148  tictoc_print();
149  for (size_t i=0;i<100;i++) {
150  auto assignment = sample(*chordal);
151  vector<size_t> stats(scheduler.nrFaculty());
152  scheduler.accumulateStats(assignment, stats);
153  size_t max = *max_element(stats.begin(), stats.end());
154  size_t min = *min_element(stats.begin(), stats.end());
155  size_t nz = count_if(stats.begin(), stats.end(), NonZero);
156 // cout << min << ", " << max << ", " << nz << endl;
157  if (nz >= 13 && min >=1 && max <= 4) {
158  cout << "======================================================\n";
159  scheduler.printAssignment(assignment);
160  }
161  }
162 #else
163  gttic(large);
164  auto MPE = scheduler.optimize();
165  gttoc(large);
167  tictoc_print();
168  scheduler.printAssignment(MPE);
169 #endif
170 }
171 
172 /* ************************************************************************* */
173 // Solve a series of relaxed problems for maximum flexibility solution
174 void solveStaged(size_t addMutex = 2) {
175 
176  bool debug = false;
177 
178  // super-hack! just count...
179  SETDEBUG("DiscreteConditional::COUNT", true);
180  SETDEBUG("DiscreteConditional::DiscreteConditional", debug); // progress
181 
182  // make a vector with slot availability, initially all 1
183  // Reads file to get count :-)
184  vector<double> slotsAvailable(largeExample(0).nrTimeSlots(), 1.0);
185 
186  // now, find optimal value for each student, using relaxed mutex constraints
187  for (size_t s = 0; s < NRSTUDENTS; s++) {
188  // add all students first time, then drop last one second time, etc...
189  Scheduler scheduler = largeExample(NRSTUDENTS - s);
190 // scheduler.print(str(boost::format("Scheduler %d") % (NRSTUDENTS-s)));
191 
192  // only allow slots not yet taken
193  scheduler.setSlotsAvailable(slotsAvailable);
194 
195  // BUILD THE GRAPH !
196  scheduler.buildGraph(addMutex);
197 
198  // Do EXACT INFERENCE
199  gttic_(eliminate);
200  DiscreteBayesNet::shared_ptr chordal = scheduler.eliminate();
201  gttoc_(eliminate);
202 
203  // find root node
204  DiscreteConditional::shared_ptr root = chordal->back();
205  if (debug)
206  root->print(""/*scheduler.studentName(s)*/);
207 
208  // solve root node only
209  size_t bestSlot = root->argmax();
210 
211  // get corresponding count
212  DiscreteKey dkey = scheduler.studentKey(NRSTUDENTS - 1 - s);
214  values[dkey.first] = bestSlot;
215  double count = (*root)(values);
216 
217  // remove this slot from consideration
218  slotsAvailable[bestSlot] = 0.0;
219  cout << scheduler.studentName(NRSTUDENTS - 1 - s) << " = " << scheduler.slotName(bestSlot) << " (" << bestSlot
220  << "), count = " << count << endl;
221  }
222  tictoc_print_();
223 }
224 
225 /* ************************************************************************* */
226 // Sample from solution found above and evaluate cost function
228  size_t slot, vector<Scheduler>& schedulers) {
229  Scheduler scheduler = largeExample(1,false);
230  addStudent(scheduler, i);
231  cout << " creating sampler for " << scheduler.studentName(0) << endl;
232  SETDEBUG("Scheduler::buildGraph", false);
233 // scheduler.print();
234  scheduler.addStudentSpecificConstraints(0, slot);
235  DiscreteBayesNet::shared_ptr chordal = scheduler.eliminate();
236  schedulers.push_back(scheduler);
237  return chordal;
238 }
239 
241 
242  size_t nrFaculty = 17; // Change to correct number !
243 
244  vector<Scheduler> schedulers;
245  vector<DiscreteBayesNet::shared_ptr> samplers(NRSTUDENTS);
246 
247  // Given the time-slots, we can create NRSTUDENTS independent samplers
248  vector<size_t> slots{12,11,13, 21,16,1, 3,2,6, 7,22,4}; // given slots
249  for (size_t i = 0; i < NRSTUDENTS; i++)
250  samplers[i] = createSampler(i, slots[i], schedulers);
251 
252  // now, sample schedules
253  for (size_t n = 0; n < 10000; n++) {
254  vector<size_t> stats(nrFaculty, 0);
255  vector<DiscreteValues> samples;
256  for (size_t i = 0; i < NRSTUDENTS; i++) {
257  samples.push_back(samplers[i]->sample());
258  schedulers[i].accumulateStats(samples[i], stats);
259  }
260  size_t max = *max_element(stats.begin(), stats.end());
261  size_t min = *min_element(stats.begin(), stats.end());
262  size_t nz = count_if(stats.begin(), stats.end(), NonZero);
263  if (nz >= 16 && max <= 3) {
264  cout << "Sampled schedule " << n + 1 << ", min = " << min << ", nz = " << nz << ", max = " << max << endl;
265  for (size_t i = 0; i < NRSTUDENTS; i++) {
266  cout << schedulers[i].studentName(0) << " : " << schedulers[i].slotName(
267  slots[i]) << endl;
268  schedulers[i].printSpecial(samples[i]);
269  }
270  }
271  }
272 }
273 
274 /* ************************************************************************* */
275 int main() {
276 // runLargeExample();
277 // solveStaged(3);
278  sampleSolutions();
279  return 0;
280 }
281 /* ************************************************************************* */
282 
gttoc
#define gttoc(label)
Definition: timing.h:296
timing.h
Timing utilities.
NRSTUDENTS
size_t NRSTUDENTS
Definition: schedulingQuals13.cpp:20
gtsam::DecisionTreeFactor
Definition: DecisionTreeFactor.h:44
SETDEBUG
#define SETDEBUG(S, V)
Definition: debug.h:61
s
RealScalar s
Definition: level1_cplx_impl.h:126
gtsam::Scheduler::slotName
const std::string & slotName(size_t s) const
Definition: Scheduler.h:88
tictoc_finishedIteration
#define tictoc_finishedIteration()
Definition: timing.h:299
createSampler
DiscreteBayesNet::shared_ptr createSampler(size_t i, size_t slot, vector< Scheduler > &schedulers)
Definition: schedulingQuals13.cpp:227
main
int main()
Definition: schedulingQuals13.cpp:275
gtsam::Scheduler::accumulateStats
void accumulateStats(const DiscreteValues &assignment, std::vector< size_t > &stats) const
Definition: Scheduler.cpp:233
NonZero
bool NonZero(size_t i)
Definition: schedulingQuals13.cpp:22
largeExample
Scheduler largeExample(size_t nrStudents=NRSTUDENTS, bool addStudents=true)
Definition: schedulingQuals13.cpp:78
different_sigmas::values
HybridValues values
Definition: testHybridBayesNet.cpp:245
gtsam::DefaultKeyFormatter
KeyFormatter DefaultKeyFormatter
Assign default key formatter.
Definition: Key.cpp:30
n
int n
Definition: BiCGSTAB_simple.cpp:1
samples
set noclip points set clip one set noclip two set bar set border lt lw set xdata set ydata set zdata set x2data set y2data set boxwidth set dummy y set format x g set format y g set format x2 g set format y2 g set format z g set angles radians set nogrid set key title set key left top Right noreverse box linetype linewidth samplen spacing width set nolabel set noarrow set nologscale set logscale x set set pointsize set encoding default set nopolar set noparametric set set samples
Definition: gnuplot_common_settings.hh:32
gttoc_
#define gttoc_(label)
Definition: timing.h:250
gtsam::Scheduler::addStudentSpecificConstraints
void addStudentSpecificConstraints(size_t i, std::optional< size_t > slot={})
Definition: Scheduler.cpp:102
stats
bool stats
Definition: SolverComparer.cpp:100
gttic_
#define gttic_(label)
Definition: timing.h:245
tictoc_print
#define tictoc_print()
Definition: timing.h:300
debug
static constexpr bool debug
Definition: testDiscreteBayesTree.cpp:31
gtsam::tictoc_print_
void tictoc_print_()
Definition: timing.h:268
gtsam::Scheduler::eliminate
DiscreteBayesNet::shared_ptr eliminate() const
Definition: Scheduler.cpp:246
sampleSolutions
void sampleSolutions()
Definition: schedulingQuals13.cpp:240
Scheduler.h
matlab_wrap.path
path
Definition: matlab_wrap.py:66
gtsam::Scheduler::printAssignment
void printAssignment(const DiscreteValues &assignment) const
Definition: Scheduler.cpp:205
gtsam::DiscreteFactorGraph::product
DecisionTreeFactor product() const
Definition: DiscreteFactorGraph.cpp:67
gtsam::DiscreteConditional::shared_ptr
std::shared_ptr< This > shared_ptr
shared_ptr to this class
Definition: DiscreteConditional.h:43
gtsam::Scheduler
Definition: Scheduler.h:22
addStudent
void addStudent(Scheduler &s, size_t i)
Definition: schedulingQuals13.cpp:27
runLargeExample
void runLargeExample()
Definition: schedulingQuals13.cpp:123
gtsam
traits
Definition: SFMdata.h:40
gtsam::DiscreteValues
Definition: DiscreteValues.h:34
gtsam::DiscreteKey
std::pair< Key, size_t > DiscreteKey
Definition: DiscreteKey.h:38
std
Definition: BFloat16.h:88
gtsam::Scheduler::nrStudents
size_t nrStudents() const
current number of students
Definition: Scheduler.h:119
gtsam::Scheduler::setSlotsAvailable
void setSlotsAvailable(const std::vector< double > &slotsAvailable)
Definition: Scheduler.h:91
gtsam::DiscreteBayesNet::shared_ptr
std::shared_ptr< This > shared_ptr
Definition: DiscreteBayesNet.h:43
solveStaged
void solveStaged(size_t addMutex=2)
Definition: schedulingQuals13.cpp:174
product
void product(const MatrixType &m)
Definition: product.h:20
min
#define min(a, b)
Definition: datatypes.h:19
gtsam::Scheduler::print
void print(const std::string &s="Scheduler", const KeyFormatter &formatter=DefaultKeyFormatter) const override
Definition: Scheduler.cpp:176
gtsam::Scheduler::studentName
const std::string & studentName(size_t i) const
Definition: Scheduler.cpp:86
gtsam::DiscreteFactorGraph::optimize
DiscreteValues optimize(OptionalOrderingType orderingType={}) const
Find the maximum probable explanation (MPE) by doing max-product.
Definition: DiscreteFactorGraph.cpp:189
gtsam::Scheduler::buildGraph
void buildGraph(size_t mutexBound=7)
Definition: Scheduler.cpp:149
gtsam::Scheduler::nrFaculty
size_t nrFaculty() const
Definition: Scheduler.h:79
max
#define max(a, b)
Definition: datatypes.h:20
i
int i
Definition: BiCGSTAB_step_by_step.cpp:9
gtsam::Scheduler::studentKey
const DiscreteKey & studentKey(size_t i) const
Definition: Scheduler.cpp:91
gttic
#define gttic(label)
Definition: timing.h:295
debug.h
Global debugging flags.


gtsam
Author(s):
autogenerated on Sat Nov 16 2024 04:04:02