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