HOG2
MM.h
Go to the documentation of this file.
1 //
2 // MM.h
3 // hog2 glut
4 //
5 // Created by Nathan Sturtevant on 10/27/15.
6 // Copyright © 2015 University of Denver. All rights reserved.
7 //
8 
9 #ifndef MM_h
10 #define MM_h
11 
12 #include "AStarOpenClosed.h"
13 #include "FPUtil.h"
14 #include "Timer.h"
15 #include <unordered_map>
16 #include <cinttypes>
17 
18 template <class state, int epsilon = 1>
19 struct MMCompare {
20  bool operator()(const AStarOpenClosedData<state> &i1, const AStarOpenClosedData<state> &i2) const
21  {
22  double p1 = std::max(i1.g+i1.h, i1.g*2+epsilon);
23  double p2 = std::max(i2.g+i2.h, i2.g*2+epsilon);
24  if (fequal(p1, p2))
25  {
26  //return (fgreater(i1.g, i2.g)); // low g-cost over high
27  return (fless(i1.g, i2.g)); // high g-cost over low
28  }
29  return (fgreater(p1, p2)); // low priority over high
30  }
31 };
32 
33 namespace std {
34  template <> struct hash<std::pair<double, double>>
35  {
36  size_t operator()(const std::pair<double, double> & x) const
37  {
38  return std::hash<double>()(x.first)^(std::hash<double>()(x.second)<<16);
39  }
40  };
41 }
42 
43 
44 template <class state, class action, class environment, class priorityQueue = AStarOpenClosed<state, MMCompare<state>> >
45 class MM {
46 public:
47  MM(double epsilon = 1.0):epsilon(epsilon) { forwardHeuristic = 0; backwardHeuristic = 0; env = 0; ResetNodeCount(); }
48  virtual ~MM() {}
49  void GetPath(environment *env, const state& from, const state& to,
50  Heuristic<state> *forward, Heuristic<state> *backward, std::vector<state> &thePath);
51  bool InitializeSearch(environment *env, const state& from, const state& to,
52  Heuristic<state> *forward, Heuristic<state> *backward, std::vector<state> &thePath);
53  bool DoSingleSearchStep(std::vector<state> &thePath);
54 
55  virtual const char *GetName() { return "MM"; }
56 
57  void ResetNodeCount() { nodesExpanded = nodesTouched = uniqueNodesExpanded = 0; }
58 
59  inline const int GetNumForwardItems() { return forwardQueue.size(); }
60  inline const AStarOpenClosedData<state> &GetForwardItem(unsigned int which) { return forwardQueue.Lookat(which); }
61  inline const int GetNumBackwardItems() { return backwardQueue.size(); }
62  inline const AStarOpenClosedData<state> &GetBackwardItem(unsigned int which) { return backwardQueue.Lookat(which); }
63 
64  uint64_t GetUniqueNodesExpanded() const { return uniqueNodesExpanded; }
65  uint64_t GetNodesExpanded() const { return nodesExpanded; }
66  uint64_t GetNodesTouched() const { return nodesTouched; }
67  uint64_t GetNecessaryExpansions() const;
68  //void FullBPMX(uint64_t nodeID, int distance);
69 
70  std::string SVGDraw() const;
71  void OpenGLDraw() const;
72  void PrintHDist()
73  {
74  std::vector<uint64_t> d;
75  for (auto i = dist.begin(); i != dist.end(); i++)
76  {
77  if (i->first.first < i->first.second)
78  {
79  int h = (int)i->first.second;
80  if (h >= d.size())
81  d.resize(h+1);
82  d[h] += i->second;
83  }
84  }
85  printf("MM Dynamic Distribution\n");
86  for (int x = 0; x < d.size(); x++)
87  {
88  if (d[x] != 0)
89  printf("%d\t%" PRId64 "\n", x, d[x]);
90  }
91  }
92  void PrintOpenStats(std::unordered_map<std::pair<double, double>, int> &s)
93  {
94  printf("Search distributions: (%s)\n", ((&s)==(&f))?"forward":"backward");
95  for (auto i = s.begin(); i != s.end(); i++)
96  {
97  if (i->second > 0)
98  {
99  bool ignore = false;
100  ignore = (i->first.first+i->first.second >= currentCost);
101  printf("%c g: %1.1f h: %1.1f count: %d\n", ignore?'*':' ',
102  i->first.first, i->first.second, i->second);
103  }
104  }
105  }
106 
107 // void SetWeight(double w) {weight = w;}
108 private:
109 
110  void ExtractPathToGoal(state &node, std::vector<state> &thePath)
111  { uint64_t theID; backwardQueue.Lookup(env->GetStateHash(node), theID); ExtractPathToGoalFromID(theID, thePath); }
112  void ExtractPathToGoalFromID(uint64_t node, std::vector<state> &thePath)
113  {
114  do {
115  thePath.push_back(backwardQueue.Lookup(node).data);
116  node = backwardQueue.Lookup(node).parentID;
117  } while (backwardQueue.Lookup(node).parentID != node);
118  thePath.push_back(backwardQueue.Lookup(node).data);
119  }
120 
121  void ExtractPathToStart(state &node, std::vector<state> &thePath)
122  { uint64_t theID; forwardQueue.Lookup(env->GetStateHash(node), theID); ExtractPathToStartFromID(theID, thePath); }
123  void ExtractPathToStartFromID(uint64_t node, std::vector<state> &thePath)
124  {
125  do {
126  thePath.push_back(forwardQueue.Lookup(node).data);
127  node = forwardQueue.Lookup(node).parentID;
128  } while (forwardQueue.Lookup(node).parentID != node);
129  thePath.push_back(forwardQueue.Lookup(node).data);
130  }
131 
132  void OpenGLDraw(const priorityQueue &queue) const;
133  std::string SVGDraw(const priorityQueue &queue) const;
134 
135  void Expand(priorityQueue &current,
136  priorityQueue &opposite,
137  Heuristic<state> *heuristic,
138  const state &target,
139  std::unordered_map<std::pair<double, double>, int> &count);
140 // std::unordered_map<double, int> &ming,
141 // std::unordered_map<double, int> &minf);
142  priorityQueue forwardQueue, backwardQueue;
143  state goal, start;
144  std::unordered_map<std::pair<double, double>, int> dist;
145  std::unordered_map<std::pair<double, double>, int> f, b;
146  uint64_t nodesTouched, nodesExpanded, uniqueNodesExpanded;
147  state middleNode;
148  double currentCost;
149  double lastMinForwardG;
150  double lastMinBackwardG;
151  double epsilon;
152 
153  std::vector<state> neighbors;
154  environment *env;
155  Timer t;
156  Heuristic<state> *forwardHeuristic;
157  Heuristic<state> *backwardHeuristic;
158 
159  double oldp1;
160  double oldp2;
161  bool recheckPath;
162 };
163 
164 template <class state, class action, class environment, class priorityQueue>
165 void MM<state, action, environment, priorityQueue>::GetPath(environment *env, const state& from, const state& to,
166  Heuristic<state> *forward, Heuristic<state> *backward, std::vector<state> &thePath)
167 {
168  if (InitializeSearch(env, from, to, forward, backward, thePath) == false)
169  return;
170  t.StartTimer();
171  while (!DoSingleSearchStep(thePath))
172  { }
173 }
174 
175 template <class state, class action, class environment, class priorityQueue>
176 bool MM<state, action, environment, priorityQueue>::InitializeSearch(environment *env, const state& from, const state& to,
177  Heuristic<state> *forward, Heuristic<state> *backward,
178  std::vector<state> &thePath)
179 {
180  this->env = env;
181  forwardHeuristic = forward;
182  backwardHeuristic = backward;
183  currentCost = DBL_MAX;
184  forwardQueue.Reset();
185  backwardQueue.Reset();
186  ResetNodeCount();
187  thePath.resize(0);
188  start = from;
189  goal = to;
190  if (start == goal)
191  return false;
192  oldp1 = oldp2 = 0;
193  lastMinForwardG = 0;
194  lastMinBackwardG = 0;
195  forwardQueue.AddOpenNode(start, env->GetStateHash(start), 0, forwardHeuristic->HCost(start, goal));
196  backwardQueue.AddOpenNode(goal, env->GetStateHash(goal), 0, backwardHeuristic->HCost(goal, start));
197  f.clear();
198  b.clear();
199  recheckPath = false;
200  return true;
201 }
202 
203 template <class state, class action, class environment, class priorityQueue>
204 bool MM<state, action, environment, priorityQueue>::DoSingleSearchStep(std::vector<state> &thePath)
205 {
206  if (forwardQueue.OpenSize() == 0 || backwardQueue.OpenSize() == 0)
207  {
208  return true;
209  }
210 
211 // if (forwardQueue.OpenSize() == 0)
212 // //Expand(backwardQueue, forwardQueue, backwardHeuristic, start, g_b, f_b);
213 // Expand(backwardQueue, forwardQueue, backwardHeuristic, start, b);
214 //
215 // if (backwardQueue.OpenSize() == 0)
216 // //Expand(forwardQueue, backwardQueue, forwardHeuristic, goal, g_f, f_f);
217 // Expand(forwardQueue, backwardQueue, forwardHeuristic, goal, f);
218 
219  uint64_t forward = forwardQueue.Peek();
220  uint64_t backward = backwardQueue.Peek();
221 
222  const AStarOpenClosedData<state> &nextForward = forwardQueue.Lookat(forward);
223  const AStarOpenClosedData<state> &nextBackward = backwardQueue.Lookat(backward);
224 
225  double p1 = std::max(nextForward.g+nextForward.h, nextForward.g*2);
226  double p2 = std::max(nextBackward.g+nextBackward.h, nextBackward.g*2);
227  if (p1 > oldp1)
228  {
229 // printf("Forward priority to %1.2f [%" PRId64 " expanded - %1.2fs]\n", p1, GetNodesExpanded(), t.EndTimer());
230  oldp1 = p1;
231  //PrintOpenStats(f);
232  }
233  if (p2 > oldp2)
234  {
235 // printf("Backward priority to %1.2f [%" PRId64 " expanded - %1.2fs]\n", p2, GetNodesExpanded(), t.EndTimer());
236  oldp2 = p2;
237  //PrintOpenStats(b);
238  }
239 
240  if (fless(p1, p2))
241  {
242  //Expand(forwardQueue, backwardQueue, forwardHeuristic, goal, g_f, f_f);
243  Expand(forwardQueue, backwardQueue, forwardHeuristic, goal, f);
244  }
245  else if (fless(p2, p1))
246  {
247  //Expand(backwardQueue, forwardQueue, backwardHeuristic, start, g_b, f_b);
248  Expand(backwardQueue, forwardQueue, backwardHeuristic, start, b);
249  }
250  else { // equal priority
251  if (fless(nextForward.g, nextBackward.g))
252  {
253  //Expand(forwardQueue, backwardQueue, forwardHeuristic, goal, g_f, f_f);
254  Expand(forwardQueue, backwardQueue, forwardHeuristic, goal, f);
255  }
256  else if (fless(nextBackward.g, nextForward.g))
257  {
258  //Expand(backwardQueue, forwardQueue, backwardHeuristic, start, g_b, f_b);
259  Expand(backwardQueue, forwardQueue, backwardHeuristic, start, b);
260  }
261  else {
262  Expand(forwardQueue, backwardQueue, forwardHeuristic, goal, f);
263  //Expand(forwardQueue, backwardQueue, forwardHeuristic, goal, g_f, f_f);
264  }
265  }
266  // check if we can terminate
267  if (recheckPath)
268  {
269  recheckPath = false;
270  // TODO: make this more efficient
271  double minForwardG = DBL_MAX;
272  double minBackwardG = DBL_MAX;
273  double minForwardF = DBL_MAX;
274  double minBackwardF = DBL_MAX;
275  double forwardP;
276  double backwardP;
277 
278  for (auto i = f.begin(); i != f.end(); i++)
279  {
280  if (i->second > 0) // some elements
281  {
282  if ((i->first.first + i->first.second < currentCost) && // termination only stopped by lower f-cost
283  (i->first.first + lastMinBackwardG + 1.0 < currentCost))
284  {
285  minForwardG = std::min(minForwardG, i->first.first);
286  minForwardF = std::min(minForwardF, i->first.first+i->first.second);
287  }
288  }
289  }
290  for (auto i = b.begin(); i != b.end(); i++)
291  {
292  if (i->second > 0) // some elements
293  {
294  if ((i->first.first + i->first.second < currentCost) && // termination only stopped by lower f-cost
295  (i->first.first + lastMinForwardG + 1.0 < currentCost))
296  {
297  minBackwardG = std::min(minBackwardG, i->first.first);
298  minBackwardF = std::min(minBackwardF, i->first.first+i->first.second);
299  }
300  }
301  }
302 
303  {
304  auto iB = backwardQueue.Lookat(backwardQueue.Peek());
305  backwardP = std::max(iB.g+iB.h, iB.g*2);
306  auto iF = forwardQueue.Lookat(forwardQueue.Peek());
307  forwardP = std::max(iF.g+iF.h, iF.g*2);
308  }
309  bool done = false;
310  if (minForwardF == DBL_MAX)
311  {
312  minForwardF = minForwardG = currentCost+1;
313  }
314  if (minBackwardF == DBL_MAX)
315  {
316  minBackwardF = minBackwardG = currentCost+1;
317  }
318  if (!fgreater(currentCost, minForwardF))
319  {
320 // printf("Terminated on forwardf (%f >= %f)\n", minForwardF, currentCost);
321  done = true;
322  }
323  if (!fgreater(currentCost, minBackwardF))
324  {
325 // printf("Terminated on backwardf (%f >= %f)\n", minBackwardF, currentCost);
326  done = true;
327  }
328  if (!fgreater(currentCost, minForwardG+minBackwardG+epsilon)) // TODO: epsilon
329  {
330 // printf("Terminated on g+g+epsilon (%f+%f+%f >= %f)\n", minForwardG, minBackwardG, epsilon, currentCost);
331  done = true;
332  }
333  if (!fgreater(currentCost, std::min(forwardP, backwardP)))
334  {
335 // printf("Terminated on forwardP/backwardP (min(%f, %f) >= %f)\n", forwardP, backwardP, currentCost);
336  done = true;
337  }
338 // if (!fgreater(currentCost, backwardP))
339 // {
340 // printf("Terminated on backwardP\n");
341 // done = true;
342 // }
343  // for now, always terminate
344  lastMinBackwardG = minBackwardG;
345  lastMinForwardG = minForwardG;
346  if (done)
347  {
348 // PrintOpenStats(f);
349 // PrintOpenStats(b);
350 
351  std::vector<state> pFor, pBack;
352  ExtractPathToGoal(middleNode, pBack);
353  ExtractPathToStart(middleNode, pFor);
354  reverse(pFor.begin(), pFor.end());
355  thePath = pFor;
356  thePath.insert( thePath.end(), pBack.begin()+1, pBack.end() );
357 
358  return true;
359  }
360  }
361  return false;
362 }
363 
364 template <class state, class action, class environment, class priorityQueue>
365 void MM<state, action, environment, priorityQueue>::Expand(priorityQueue &current,
366  priorityQueue &opposite,
367  Heuristic<state> *heuristic, const state &target,
368  std::unordered_map<std::pair<double, double>, int> &count)
369 // std::unordered_map<double, int> &ming,
370 // std::unordered_map<double, int> &minf)
371 {
372  uint64_t nextID = current.Close();
373  nodesExpanded++;
374  if (current.Lookup(nextID).reopened == false)
375  uniqueNodesExpanded++;
376 
377  // decrease count from parent
378  {
379  auto &parentData = current.Lookup(nextID);
380  count[{parentData.g,parentData.h}]--;
381  if (count[{parentData.g,parentData.h}] == 0 && currentCost < DBL_MAX)
382  {
383  recheckPath = true;
384  }
385  }
386 // std::cout << "Expanding " << current.Lookup(nextID).data << "\n";
387  env->GetSuccessors(current.Lookup(nextID).data, neighbors);
388  for (auto &succ : neighbors)
389  {
390  nodesTouched++;
391  uint64_t childID;
392  uint64_t hash = env->GetStateHash(succ);
393  auto loc = current.Lookup(hash, childID);
394  auto &childData = current.Lookup(childID);
395  auto &parentData = current.Lookup(nextID);
396 
397  double edgeCost = env->GCost(parentData.data, succ);
398  switch (loc)
399  {
400  case kClosedList: // ignore
401  if (fless(parentData.g+edgeCost, childData.g))
402  {
403  childData.h = std::max(childData.h, parentData.h-edgeCost);
404  childData.parentID = nextID;
405  childData.g = parentData.g+edgeCost;
406  count[{childData.g,childData.h}]++;
407  dist[{childData.g,childData.h}]++;
408  current.Reopen(childID);
409  }
410  break;
411  case kOpenList: // update cost if needed
412  {
413  // 1-step BPMX
414  parentData.h = std::max(childData.h-edgeCost, parentData.h);
415 
416  if (fgreater(parentData.h-edgeCost, childData.h))
417  {
418  count[{childData.g,childData.h}]--;
419  dist[{childData.g,childData.h}]--;
420  //minf[childData.g+childData.h]--;
421  childData.h = parentData.h-edgeCost;
422  //minf[childData.g+childData.h]++;
423  count[{childData.g,childData.h}]++;
424  dist[{childData.g,childData.h}]++;
425  }
426  if (fless(parentData.g+edgeCost, childData.g))
427  {
428  count[{childData.g,childData.h}]--;
429  dist[{childData.g,childData.h}]--;
430  childData.parentID = nextID;
431  childData.g = parentData.g+edgeCost;
432  current.KeyChanged(childID);
433  count[{childData.g,childData.h}]++;
434  dist[{childData.g,childData.h}]++;
435 
436 
437  // TODO: check if we improved the current solution?
438  uint64_t reverseLoc;
439  auto loc = opposite.Lookup(hash, reverseLoc);
440  if (loc == kOpenList)
441  {
442  if (fless(parentData.g+edgeCost + opposite.Lookup(reverseLoc).g, currentCost))
443  {
444  recheckPath = true;
445  // TODO: store current solution
446 // printf("Potential updated solution found, cost: %1.2f + %1.2f = %1.2f\n",
447 // parentData.g+edgeCost,
448 // opposite.Lookup(reverseLoc).g,
449 // parentData.g+edgeCost+opposite.Lookup(reverseLoc).g);
450  currentCost = parentData.g+edgeCost + opposite.Lookup(reverseLoc).g;
451  middleNode = succ;
452 // PrintOpenStats(f);
453 // PrintOpenStats(b);
454  }
455  }
456  }
457  }
458  break;
459  case kNotFound:
460  {
461  double g = parentData.g+edgeCost;
462  double h = std::max(heuristic->HCost(succ, target), parentData.h-edgeCost);
463 
464  // Ignore nodes that don't have lower f-cost than the incumbant solution
465  if (!fless(g+h, currentCost))
466  break;
467 // ming[g]++;
468 // minf[g+h]++;
469  count[{g,h}]++;
470  dist[{g,h}]++;
471  // 1-step BPMX
472  parentData.h = std::max(h-edgeCost, parentData.h);
473 
474  current.AddOpenNode(succ, // This may invalidate our references
475  hash,
476  g,
477  h,
478  nextID);
479 
480  // check for solution
481  uint64_t reverseLoc;
482  auto loc = opposite.Lookup(hash, reverseLoc);
483  if (loc == kOpenList)
484  {
485  if (fless(current.Lookup(nextID).g+edgeCost + opposite.Lookup(reverseLoc).g, currentCost))
486  {
487  recheckPath = true;
488  // TODO: store current solution
489 // printf("Potential solution found, cost: %1.2f + %1.2f = %1.2f\n",
490 // current.Lookup(nextID).g+edgeCost,
491 // opposite.Lookup(reverseLoc).g,
492 // current.Lookup(nextID).g+edgeCost+opposite.Lookup(reverseLoc).g);
493  currentCost = current.Lookup(nextID).g+edgeCost + opposite.Lookup(reverseLoc).g;
494  middleNode = succ;
495 // PrintOpenStats(f);
496 // PrintOpenStats(b);
497  }
498  }
499  }
500  }
501  }
502 }
503 
504 template <class state, class action, class environment, class priorityQueue>
505 uint64_t MM<state, action, environment, priorityQueue>::GetNecessaryExpansions() const
506 {
507  uint64_t count = 0;
508  for (unsigned int x = 0; x < forwardQueue.size(); x++)
509  {
510  const AStarOpenClosedData<state> &data = forwardQueue.Lookat(x);
511  if ((data.where == kClosedList) && (fless(data.g+data.h, currentCost)) && fless(data.g*2, currentCost))
512  count++;
513  }
514  for (unsigned int x = 0; x < backwardQueue.size(); x++)
515  {
516  const AStarOpenClosedData<state> &data = backwardQueue.Lookat(x);
517  if ((data.where == kClosedList) && (fless(data.g+data.h, currentCost)) && (fless(data.g*2, currentCost)))
518  count++;
519  }
520  return count;
521 }
522 
523 template <class state, class action, class environment, class priorityQueue>
524 void MM<state, action, environment, priorityQueue>::OpenGLDraw() const
525 {
526  OpenGLDraw(forwardQueue);
527  OpenGLDraw(backwardQueue);
528 }
529 
530 template <class state, class action, class environment, class priorityQueue>
531 void MM<state, action, environment, priorityQueue>::OpenGLDraw(const priorityQueue &queue) const
532 {
533  double transparency = 0.9;
534  if (queue.size() == 0)
535  return;
536  uint64_t top = -1;
537  // double minf = 1e9, maxf = 0;
538  if (queue.OpenSize() > 0)
539  {
540  top = queue.Peek();
541  }
542  for (unsigned int x = 0; x < queue.size(); x++)
543  {
544  const AStarOpenClosedData<state> &data = queue.Lookat(x);
545  if (x == top)
546  {
547  env->SetColor(1.0, 1.0, 0.0, transparency);
548  env->OpenGLDraw(data.data);
549  }
550  if ((data.where == kOpenList) && (data.reopened))
551  {
552  env->SetColor(0.0, 0.5, 0.5, transparency);
553  env->OpenGLDraw(data.data);
554  }
555  else if (data.where == kOpenList)
556  {
557  env->SetColor(0.0, 1.0, 0.0, transparency);
558  env->OpenGLDraw(data.data);
559  }
560  else if ((data.where == kClosedList) && (data.reopened))
561  {
562  env->SetColor(0.5, 0.0, 0.5, transparency);
563  env->OpenGLDraw(data.data);
564  }
565  else if (data.where == kClosedList)
566  {
567  env->SetColor(1.0, 0.0, 0.0, transparency);
568  env->OpenGLDraw(data.data);
569  }
570  }
571 }
572 
573 template <class state, class action, class environment, class priorityQueue>
574 std::string MM<state, action, environment, priorityQueue>::SVGDraw() const
575 {
576  std::string s;
577  s += SVGDraw(forwardQueue);
578  s += SVGDraw(backwardQueue);
579  return s;
580 }
581 
582 template <class state, class action, class environment, class priorityQueue>
583 std::string MM<state, action, environment, priorityQueue>::SVGDraw(const priorityQueue &queue) const
584 {
585  std::string s;
586  double transparency = 1.0;
587  if (queue.size() == 0)
588  return s;
589  uint64_t top = -1;
590 
591  if (queue.OpenSize() > 0)
592  {
593  top = queue.Peek();
594  }
595  for (unsigned int x = 0; x < queue.size(); x++)
596  {
597  const auto &data = queue.Lookat(x);
598 
599  if (x == top)
600  {
601  env->SetColor(1.0, 1.0, 0.0, transparency);
602  s+=env->SVGDraw(data.data);
603  }
604  else if ((data.where == kOpenList) && (data.reopened))
605  {
606  env->SetColor(0.0, 0.5, 0.5, transparency);
607  s+=env->SVGDraw(data.data);
608  }
609  else if (data.where == kOpenList)
610  {
611  env->SetColor(0.0, 1.0, 0.0, transparency);
612  s+=env->SVGDraw(data.data);
613  }
614  else if ((data.where == kClosedList) && (data.reopened))
615  {
616  env->SetColor(0.5, 0.0, 0.5, transparency);
617  s+=env->SVGDraw(data.data);
618  }
619  else if (data.where == kClosedList)
620  {
621  env->SetColor(1.0, 0.0, 0.0, transparency);
622  s+=env->SVGDraw(data.data);
623  }
624  }
625  return s;
626 }
627 
628 #endif /* MM_h */
MM::b
std::unordered_map< std::pair< double, double >, int > b
Definition: MM.h:145
MM::OpenGLDraw
void OpenGLDraw() const
Definition: MM.h:524
MM::f
std::unordered_map< std::pair< double, double >, int > f
Definition: MM.h:145
std::hash< std::pair< double, double > >::operator()
size_t operator()(const std::pair< double, double > &x) const
Definition: MM.h:36
MM::ExtractPathToGoal
void ExtractPathToGoal(state &node, std::vector< state > &thePath)
Definition: MM.h:110
MM::ExtractPathToStart
void ExtractPathToStart(state &node, std::vector< state > &thePath)
Definition: MM.h:121
MM::backwardQueue
priorityQueue backwardQueue
Definition: MM.h:142
AStarOpenClosedData::reopened
bool reopened
Definition: AStarOpenClosed.h:68
MM::PrintOpenStats
void PrintOpenStats(std::unordered_map< std::pair< double, double >, int > &s)
Definition: MM.h:92
min
double min(double a, double b)
Definition: FPUtil.h:35
AStarOpenClosedData::data
state data
Definition: AStarOpenClosed.h:57
MM::goal
state goal
Definition: MM.h:143
Heuristic
Definition: Heuristic.h:30
if
if(state==GLUT_DOWN)
Definition: GLUThog.cpp:244
AStarOpenClosed.h
d
mcData d[]
Definition: MotionCaptureMovement.cpp:21
MM::InitializeSearch
bool InitializeSearch(environment *env, const state &from, const state &to, Heuristic< state > *forward, Heuristic< state > *backward, std::vector< state > &thePath)
Definition: MM.h:176
MM::nodesTouched
uint64_t nodesTouched
Definition: MM.h:146
MM::nodesExpanded
uint64_t nodesExpanded
Definition: MM.h:146
MMCompare
Definition: MM.h:19
MM::GetForwardItem
const AStarOpenClosedData< state > & GetForwardItem(unsigned int which)
Definition: MM.h:60
MM::env
environment * env
Definition: MM.h:154
FPUtil.h
MM::ExtractPathToStartFromID
void ExtractPathToStartFromID(uint64_t node, std::vector< state > &thePath)
Definition: MM.h:123
MM::GetNumForwardItems
const int GetNumForwardItems()
Definition: MM.h:59
AStarOpenClosedData::where
dataLocation where
Definition: AStarOpenClosed.h:69
MM::forwardQueue
priorityQueue forwardQueue
Definition: MM.h:142
MM::recheckPath
bool recheckPath
Definition: MM.h:161
MMCompare::operator()
bool operator()(const AStarOpenClosedData< state > &i1, const AStarOpenClosedData< state > &i2) const
Definition: MM.h:20
MM::currentCost
double currentCost
Definition: MM.h:148
MM::start
state start
Definition: MM.h:143
AStarOpenClosedData::g
double g
Definition: AStarOpenClosed.h:64
Timer.h
MM::GetBackwardItem
const AStarOpenClosedData< state > & GetBackwardItem(unsigned int which)
Definition: MM.h:62
MM::GetUniqueNodesExpanded
uint64_t GetUniqueNodesExpanded() const
Definition: MM.h:64
MM::lastMinBackwardG
double lastMinBackwardG
Definition: MM.h:150
MM::GetNodesTouched
uint64_t GetNodesTouched() const
Definition: MM.h:66
loc
Definition: MapGenerators.cpp:296
MM::forwardHeuristic
Heuristic< state > * forwardHeuristic
Definition: MM.h:156
MM::GetPath
void GetPath(environment *env, const state &from, const state &to, Heuristic< state > *forward, Heuristic< state > *backward, std::vector< state > &thePath)
Definition: MM.h:165
MM::Expand
void Expand(priorityQueue &current, priorityQueue &opposite, Heuristic< state > *heuristic, const state &target, std::unordered_map< std::pair< double, double >, int > &count)
Definition: MM.h:365
MM::DoSingleSearchStep
bool DoSingleSearchStep(std::vector< state > &thePath)
Definition: MM.h:204
fless
bool fless(double a, double b)
Definition: FPUtil.h:28
MM::uniqueNodesExpanded
uint64_t uniqueNodesExpanded
Definition: MM.h:146
MM
Definition: MM.h:45
MM::ExtractPathToGoalFromID
void ExtractPathToGoalFromID(uint64_t node, std::vector< state > &thePath)
Definition: MM.h:112
AStarOpenClosedData
Definition: AStarOpenClosed.h:52
MM::neighbors
std::vector< state > neighbors
Definition: MM.h:153
Heuristic::HCost
virtual double HCost(const state &a, const state &b) const
Definition: Heuristic.h:73
MM::epsilon
double epsilon
Definition: MM.h:151
MM::ResetNodeCount
void ResetNodeCount()
Definition: MM.h:57
MM::PrintHDist
void PrintHDist()
Definition: MM.h:72
fgreater
bool fgreater(double a, double b)
Definition: FPUtil.h:29
max
#define max(a, b)
Definition: MinimalSectorAbstraction.cpp:40
MM::t
Timer t
Definition: MM.h:155
kOpenList
@ kOpenList
Definition: AStarOpenClosed.h:28
MM::oldp1
double oldp1
Definition: MM.h:159
MM::SVGDraw
std::string SVGDraw() const
Definition: MM.h:574
MM::GetNecessaryExpansions
uint64_t GetNecessaryExpansions() const
Definition: MM.h:505
std
Definition: CanonicalGraphEnvironment.h:26
AStarOpenClosedData::h
double h
Definition: AStarOpenClosed.h:65
MM::MM
MM(double epsilon=1.0)
Definition: MM.h:47
Timer
Definition: Timer.h:19
MM::GetName
virtual const char * GetName()
Definition: MM.h:55
MM::GetNumBackwardItems
const int GetNumBackwardItems()
Definition: MM.h:61
kNotFound
@ kNotFound
Definition: AStarOpenClosed.h:30
MM::dist
std::unordered_map< std::pair< double, double >, int > dist
Definition: MM.h:144
MM::middleNode
state middleNode
Definition: MM.h:147
MM::GetNodesExpanded
uint64_t GetNodesExpanded() const
Definition: MM.h:65
fequal
bool fequal(double a, double b, double tolerance=TOLERANCE)
Definition: FPUtil.h:32
MM::~MM
virtual ~MM()
Definition: MM.h:48
MM::lastMinForwardG
double lastMinForwardG
Definition: MM.h:149
kClosedList
@ kClosedList
Definition: AStarOpenClosed.h:29
MM::oldp2
double oldp2
Definition: MM.h:160
node
Nodes to be stored within a Graph.
Definition: Graph.h:170
MM::backwardHeuristic
Heuristic< state > * backwardHeuristic
Definition: MM.h:157
Generated by   doxygen 1.8.17