HOG2
IOS.h
Go to the documentation of this file.
1 //
2 // IOS.h
3 // hog2 mac native demos
4 //
5 // Improved Optimistic Search
6 // This is my re-implementation of the algorithm.
7 //
8 //
9 // Created by Nathan Sturtevant on 7/11/19.
10 // Copyright © 2019 NS Software. All rights reserved.
11 //
12 
13 #ifndef IOS_h
14 #define IOS_h
15 
16 template<typename state>
17 class IOSOpenClosedData {
18 public:
19  IOSOpenClosedData() { }
20  IOSOpenClosedData(const state &theData, double fCost, double gCost, double hCost, uint64_t parent, uint64_t openLoc, dataLocation location)
21  :data(theData), f(fCost), g(gCost), h(hCost), parentID(parent), openLocation(openLoc), where(location)
22  {
23  reopened = false; onOptimalPath = false;
24  }
25  state data;
26  double f;
27  double g;
28  double h;
29  bool onOptimalPath;
30  uint64_t parentID;
31  uint64_t openLocation;
32  bool reopened;
33  dataLocation where;
34 };
35 
36 template <class state>
37 struct IOSCompare {
38  // returns true if i2 is preferred over i1
39  bool operator()(const IOSOpenClosedData<state> &i1, const IOSOpenClosedData<state> &i2) const
40  {
41  if (fequal(i1.f, i2.f))
42  {
43  return (fless(i1.g, i2.g));
44  }
45  return fgreater(i1.f, i2.f);
46  }
47 };
48 
52 template <class state, class action, class environment>
53 class ImprovedOptimisticSearch : public GenericSearchAlgorithm<state,action,environment> {
54 public:
55  ImprovedOptimisticSearch()
56  {
57  ResetNodeCount(); env = 0; weight=3; bound = 1.5; theHeuristic = 0;
58  greedyPhi = phi = [](double x, double y){return x+y;};
59  }
60  virtual ~ImprovedOptimisticSearch() {}
61  void GetPath(environment *env, const state& from, const state& to, std::vector<state> &thePath);
62  void GetPath(environment *, const state& , const state& , std::vector<action> & );
63 
64  typedef AStarOpenClosed<state, IOSCompare<state>, IOSOpenClosedData<state>> openList;
65  // uses admissible heuristic (regular A* search)
66  AStarOpenClosed<state, IOSCompare<state>, IOSOpenClosedData<state>> openClosedList;
67 
68  state goal, start;
69 
70  bool InitializeSearch(environment *env, const state& from, const state& to, std::vector<state> &thePath);
71  bool DoSingleSearchStep(std::vector<state> &thePath);
72  void AddAdditionalStartState(state& newState);
73  void AddAdditionalStartState(state& newState, double cost);
74 
75  state CheckNextNode();
76  void ExtractPathToStart(state &node, std::vector<state> &thePath)
77  {
78  thePath.clear();
79  uint64_t theID;
80  if (openClosedList.Lookup(env->GetStateHash(node), theID) != kNotFound)
81  ExtractPathToStartFromID(theID, thePath);
82  }
83  void ExtractPathToStartFromID(uint64_t node, std::vector<state> &thePath);
84  const state &GetParent(const state &s);
85  virtual const char *GetName();
86 
87  void PrintStats();
88  uint64_t GetUniqueNodesExpanded() { return uniqueNodesExpanded; }
89  void ResetNodeCount() { nodesExpanded = nodesTouched = 0; uniqueNodesExpanded = 0; }
90  int GetMemoryUsage();
91 
92  bool GetClosedListGCost(const state &val, double &gCost) const;
93  bool GetOpenListGCost(const state &val, double &gCost) const;
94  bool GetFocalListGCost(const state &val, double &gCost) const;
95  bool GetClosedItem(const state &s, IOSOpenClosedData<state> &);
96  unsigned int GetNumOpenItems() { return openClosedList.OpenSize(); }
97  inline const IOSOpenClosedData<state> &GetOpenItem(unsigned int which)
98  { return openClosedList.Lookup(openClosedList.GetOpenItem(which)); }
99 
100  inline const int GetNumItems() { return openClosedList.size(); }
101  inline const IOSOpenClosedData<state> &GetItem(unsigned int which)
102  { return openClosedList.GetItem(which); }
103  bool HaveExpandedState(const state &val)
104  { uint64_t key; return openClosedList.Lookup(env->GetStateHash(val), key) != kNotFound; }
105  dataLocation GetStateLocation(const state &val)
106  { uint64_t key; return openClosedList.Lookup(env->GetStateHash(val), key); }
107 
108  void SetReopenNodes(bool re) { reopenNodes = re; }
109  bool GetReopenNodes() { return reopenNodes; }
110 
111  void SetHeuristic(Heuristic<state> *h) { theHeuristic = h; }
112 
113  uint64_t GetNodesExpanded() const { return nodesExpanded; }
114  uint64_t GetNodesTouched() const { return nodesTouched; }
115 
116  void LogFinalStats(StatCollection *) {}
117 
118  void OpenGLDraw() const;
119  void Draw(Graphics::Display &d) const;
120 
121  void SetWeight(double w) {weight = w;}
122  double GetWeight() { return weight; }
123  void SetOptimalityBound(double w) {bound = w;}
124  double GetOptimalityBound() {return bound;}
125  void SetPhi(std::function<double(double, double)> p)
126  {
127  greedyPhi = p;
128  }
129  double Phi(double h, double g)
130  {
131  return greedyPhi(h, g);
132  }
133 
134 private:
135  void DoGreedyStep(std::vector<state> &thePath);
136  void DoOptimalStep(std::vector<state> &thePath);
137 
138  uint64_t nodesTouched, nodesExpanded;
139 
140  std::vector<state> internalPath;
141  std::vector<state> neighbors;
142  std::vector<uint64_t> neighborID;
143  std::vector<double> edgeCosts;
144  std::vector<dataLocation> neighborLoc;
145 
146  environment *env;
147  std::function<double(double, double)> phi;
148  std::function<double(double, double)> greedyPhi;
149  double bestSolution, solutionReduction;
150  double weight;
151  double bound;
152  bool reopenNodes;
153  uint64_t uniqueNodesExpanded;
154  Heuristic<state> *theHeuristic;
155  bool doneGreedy;
156  double maxPriority;
157 };
158 
159 //static const bool verbose = false;
160 
169 template <class state, class action, class environment>
170 const char *ImprovedOptimisticSearch<state,action,environment>::GetName()
171 {
172  static char name[32];
173  sprintf(name, "IOS[%1.2f, %1.2f]", bound, weight);
174  return name;
175 }
176 
188 template <class state, class action, class environment>
189 void ImprovedOptimisticSearch<state,action,environment>::GetPath(environment *_env, const state& from, const state& to, std::vector<state> &thePath)
190 {
191  //discardcount=0;
192  if (!InitializeSearch(_env, from, to, thePath))
193  {
194  return;
195  }
196  while (!DoSingleSearchStep(thePath))
197  { }
198 }
199 
200 template <class state, class action, class environment>
201 void ImprovedOptimisticSearch<state,action,environment>::GetPath(environment *_env, const state& from, const state& to, std::vector<action> &path)
202 {
203  std::vector<state> thePath;
204  if (!InitializeSearch(_env, from, to, thePath))
205  {
206  return;
207  }
208  path.resize(0);
209  while (!DoSingleSearchStep(thePath))
210  {
211  }
212  for (int x = 0; x < thePath.size()-1; x++)
213  {
214  path.push_back(_env->GetAction(thePath[x], thePath[x+1]));
215  }
216 }
217 
218 
229 template <class state, class action, class environment>
230 bool ImprovedOptimisticSearch<state,action,environment>::InitializeSearch(environment *_env, const state& from, const state& to, std::vector<state> &thePath)
231 {
232  doneGreedy = false;
233  if (theHeuristic == 0)
234  theHeuristic = _env;
235  thePath.resize(0);
236  env = _env;
237  ResetNodeCount();
238  start = from;
239  goal = to;
240  bestSolution = DBL_MAX;
241  solutionReduction = 0;
242  maxPriority = 0;
243  internalPath.clear();
244  openClosedList.Reset();
245 
246  double w = GetWeight(); // could use 2w-1 on bound
247  phi = greedyPhi;
248 // phi = ([=](double x, double y){return y/(w)+x;});
249 
250  double h = theHeuristic->HCost(from, to);
251  openClosedList.AddOpenNode(from, env->GetStateHash(from), phi(h, 0), 0, h);
252  if (env->GoalTest(from, to)) //assumes that from and to are valid states
253  {
254  return true;
255  }
256  return false;
257 }
258 
264 template <class state, class action, class environment>
265 void ImprovedOptimisticSearch<state,action,environment>::AddAdditionalStartState(state& newState)
266 {
267  double h = theHeuristic->HCost(newState, goal);
268  openClosedList.AddOpenNode(newState, env->GetStateHash(newState), phi(h, 0), 0, h);
269 }
270 
276 template <class state, class action, class environment>
277 void ImprovedOptimisticSearch<state,action,environment>::AddAdditionalStartState(state& newState, double cost)
278 {
279  double h = theHeuristic->HCost(newState, goal);
280  openClosedList.AddOpenNode(newState, env->GetStateHash(newState), phi(h, cost), cost, h);
281 }
282 
293 template <class state, class action, class environment>
294 bool ImprovedOptimisticSearch<state,action,environment>::DoSingleSearchStep(std::vector<state> &thePath)
295 {
296  // Solution proven
297  if (flesseq(bestSolution-solutionReduction, GetOptimalityBound()*maxPriority))
298  {
299  ExtractPathToStart(goal, thePath);
300  return true;
301  }
302 
303  // TODO: Unclear if we could return no solution if the last node expanded was the goal
304  if (openClosedList.OpenSize() == 0)
305  {
306  thePath.resize(0); // no path found!
307  return true;
308  }
309 
310  // Do greedy search
311  if (bestSolution == DBL_MAX)
312  {
313  DoGreedyStep(internalPath);
314  return false;
315  }
316  else {
317  DoOptimalStep(internalPath);
318  return false;
319  }
320  return false;
321 }
322 
323 template <class state, class action, class environment>
324 void ImprovedOptimisticSearch<state,action,environment>::DoGreedyStep(std::vector<state> &thePath)
325 {
326  uint64_t nodeid = openClosedList.Close();
327  maxPriority = std::max(maxPriority, openClosedList.Lookup(nodeid).f);
328 
329  if (!openClosedList.Lookup(nodeid).reopened)
330  uniqueNodesExpanded++;
331  nodesExpanded++;
332 
333  if ((env->GoalTest(openClosedList.Lookup(nodeid).data, goal)))
334  {
335  // 1. Clear open list
336  openClosedList.CloseAllOnOpen();
337  // 2. Change search priority
338  phi = [](double x, double y){return x+y;};
339  // 3. put start back on open
340  uint64_t ID;
341  openClosedList.Lookup(env->GetStateHash(start), ID);
342  openClosedList.Lookup(ID).f = phi(openClosedList.Lookup(ID).h, openClosedList.Lookup(ID).g);
343  openClosedList.Reopen(ID);
344  // 4. extract path
345  ExtractPathToStartFromID(nodeid, thePath);
346  // 5. record path cost
347  bestSolution = env->GetPathLength(thePath);
348  // 6. record states on path
349  for (const auto &i : thePath)
350  {
351  uint64_t key;
352  openClosedList.Lookup(env->GetStateHash(i), key);
353  openClosedList.Lookup(key).onOptimalPath = true;
354  }
355  printf("IOS: Found initial solution cost %f -- C* >= %f [%f]\n", bestSolution, maxPriority, bestSolution/maxPriority);
356  return;
357  }
358 
359  neighbors.resize(0);
360  edgeCosts.resize(0);
361  neighborID.resize(0);
362  neighborLoc.resize(0);
363 
364  // std::cout << "Expanding: " << openClosedList.Lookup(nodeid).data << " with f:";
365  // std::cout << openClosedList.Lookup(nodeid).g+openClosedList.Lookup(nodeid).h << std::endl;
366 
367  env->GetSuccessors(openClosedList.Lookup(nodeid).data, neighbors);
368  // 1. load all the children
369  for (unsigned int x = 0; x < neighbors.size(); x++)
370  {
371  uint64_t theID;
372  neighborLoc.push_back(openClosedList.Lookup(env->GetStateHash(neighbors[x]), theID));
373  neighborID.push_back(theID);
374  edgeCosts.push_back(env->GCost(openClosedList.Lookup(nodeid).data, neighbors[x]));
375  }
376 
377  // iterate again updating costs and writing out to memory
378  for (int x = 0; x < neighbors.size(); x++)
379  {
380  nodesTouched++;
381 
382  switch (neighborLoc[x])
383  {
384  case kClosedList:
385  // No re-openings in greedy search
386  break;
387  case kOpenList:
388  if (fless(openClosedList.Lookup(nodeid).g+edgeCosts[x], openClosedList.Lookup(neighborID[x]).g))
389  {
390  auto &i = openClosedList.Lookup(neighborID[x]);
391  i.parentID = nodeid;
392  i.g = openClosedList.Lookup(nodeid).g+edgeCosts[x];
393  i.f = phi(i.h, i.g);
394  // This line isn't normally needed, but in some state spaces we might have
395  // equality but different meta information, so we need to make sure that the
396  // meta information is also copied, since this is the most generic A* implementation
397  i.data = neighbors[x];
398  openClosedList.KeyChanged(neighborID[x]);
399  }
400  break;
401  case kNotFound:
402  {
403  double h = theHeuristic->HCost(neighbors[x], goal);
404  openClosedList.AddOpenNode(neighbors[x],
405  env->GetStateHash(neighbors[x]),
406  phi(h, openClosedList.Lookup(nodeid).g+edgeCosts[x]),
407  openClosedList.Lookup(nodeid).g+edgeCosts[x],
408  h,
409  nodeid);
410  }
411  }
412  }
413 }
414 
415 template <class state, class action, class environment>
416 void ImprovedOptimisticSearch<state,action,environment>::DoOptimalStep(std::vector<state> &thePath)
417 {
418  uint64_t nodeid = openClosedList.Close();
419  maxPriority = std::max(maxPriority, openClosedList.Lookup(nodeid).f);
420 
421  if (!openClosedList.Lookup(nodeid).reopened)
422  uniqueNodesExpanded++;
423  nodesExpanded++;
424 
425  if ((env->GoalTest(openClosedList.Lookup(nodeid).data, goal)))
426  {
427  // Solution is optimal. Return.
428  // 1. extract path
429  ExtractPathToStartFromID(nodeid, thePath);
430  reverse(thePath.begin(), thePath.end());
431  bestSolution = env->GetPathLength(thePath);
432  return;
433  }
434 
435  neighbors.resize(0);
436  edgeCosts.resize(0);
437  neighborID.resize(0);
438  neighborLoc.resize(0);
439 
440  // std::cout << "Expanding: " << openClosedList.Lookup(nodeid).data << " with f:";
441  // std::cout << openClosedList.Lookup(nodeid).g+openClosedList.Lookup(nodeid).h << std::endl;
442 
443  env->GetSuccessors(openClosedList.Lookup(nodeid).data, neighbors);
444  // 1. load all the children
445  for (unsigned int x = 0; x < neighbors.size(); x++)
446  {
447  uint64_t theID;
448  neighborLoc.push_back(openClosedList.Lookup(env->GetStateHash(neighbors[x]), theID));
449  neighborID.push_back(theID);
450  edgeCosts.push_back(env->GCost(openClosedList.Lookup(nodeid).data, neighbors[x]));
451  }
452 
453  // iterate again updating costs and writing out to memory
454  for (int x = 0; x < neighbors.size(); x++)
455  {
456  nodesTouched++;
457 
458  switch (neighborLoc[x])
459  {
460  case kClosedList:
461  {
462  auto &i = openClosedList.Lookup(neighborID[x]);
463  if (i.onOptimalPath) // must be closed
464  {
465  if ((i.g)>(openClosedList.Lookup(nodeid).g+edgeCosts[x]))
466  {
467  printf("IOS: Reduced solution cost by %f\n", (i.g)-(openClosedList.Lookup(nodeid).g+edgeCosts[x]));
468  solutionReduction = std::max(solutionReduction,
469  (i.g)-(openClosedList.Lookup(nodeid).g+edgeCosts[x])
470  );
471  printf("IOS: Current solution cost %f -- C* >= %f [%f]\n", bestSolution-solutionReduction,
472  maxPriority, (bestSolution-solutionReduction)/maxPriority);
473  }
474  }
475  if (i.reopened == false) // Re-open at most once (from suboptimal to optimal search)
476  {
477  i.reopened = true;
478  i.parentID = nodeid;
479  i.g = openClosedList.Lookup(nodeid).g+edgeCosts[x];
480  i.f = phi(i.h, i.g);
481  openClosedList.Reopen(neighborID[x]);
482  // This line isn't normally needed, but in some state spaces we might have
483  // equality but different meta information, so we need to make sure that the
484  // meta information is also copied, since this is the most generic A* implementation
485  i.data = neighbors[x];
486  }
487  }
488  break;
489  case kOpenList:
490  if (fless(openClosedList.Lookup(nodeid).g+edgeCosts[x], openClosedList.Lookup(neighborID[x]).g))
491  {
492  auto &i = openClosedList.Lookup(neighborID[x]);
493  i.parentID = nodeid;
494  i.g = openClosedList.Lookup(nodeid).g+edgeCosts[x];
495  i.f = phi(i.h, i.g);
496  // This line isn't normally needed, but in some state spaces we might have
497  // equality but different meta information, so we need to make sure that the
498  // meta information is also copied, since this is the most generic A* implementation
499  i.data = neighbors[x];
500  openClosedList.KeyChanged(neighborID[x]);
501  }
502  break;
503  case kNotFound:
504  {
505  double h = theHeuristic->HCost(neighbors[x], goal);
506  openClosedList.AddOpenNode(neighbors[x],
507  env->GetStateHash(neighbors[x]),
508  phi(h, openClosedList.Lookup(nodeid).g+edgeCosts[x]),
509  openClosedList.Lookup(nodeid).g+edgeCosts[x],
510  h,
511  nodeid);
512  }
513  }
514  }
515 }
516 
517 
525 template <class state, class action, class environment>
526 state ImprovedOptimisticSearch<state, action,environment>::CheckNextNode()
527 {
528  uint64_t key = openClosedList.Peek();
529  return openClosedList.Lookup(key).data;
530 }
531 
540 template <class state, class action,class environment>
541 void ImprovedOptimisticSearch<state, action,environment>::ExtractPathToStartFromID(uint64_t node,
542  std::vector<state> &thePath)
543 {
544  do {
545  thePath.push_back(openClosedList.Lookup(node).data);
546  node = openClosedList.Lookup(node).parentID;
547  } while (openClosedList.Lookup(node).parentID != node);
548  thePath.push_back(openClosedList.Lookup(node).data);
549 }
550 
551 template <class state, class action,class environment>
552 const state &ImprovedOptimisticSearch<state, action,environment>::GetParent(const state &s)
553 {
554  uint64_t theID;
555  openClosedList.Lookup(env->GetStateHash(s), theID);
556  theID = openClosedList.Lookup(theID).parentID;
557  return openClosedList.Lookup(theID).data;
558 }
559 
566 template <class state, class action, class environment>
567 void ImprovedOptimisticSearch<state, action,environment>::PrintStats()
568 {
569  printf("%u items in closed list\n", (unsigned int)openClosedList.ClosedSize());
570  printf("%u items in open queue\n", (unsigned int)openClosedList.OpenSize());
571 }
572 
580 template <class state, class action, class environment>
581 int ImprovedOptimisticSearch<state, action,environment>::GetMemoryUsage()
582 {
583  return openClosedList.size();
584 }
585 
596 template <class state, class action, class environment>
597 bool ImprovedOptimisticSearch<state, action,environment>::GetClosedListGCost(const state &val, double &gCost) const
598 {
599  uint64_t theID;
600  dataLocation loc = openClosedList.Lookup(env->GetStateHash(val), theID);
601  if (loc == kClosedList)
602  {
603  gCost = openClosedList.Lookat(theID).g;
604  return true;
605  }
606  return false;
607 }
608 
609 template <class state, class action, class environment>
610 bool ImprovedOptimisticSearch<state, action,environment>::GetOpenListGCost(const state &val, double &gCost) const
611 {
612  uint64_t theID;
613  dataLocation loc = openClosedList.Lookup(env->GetStateHash(val), theID);
614  if (loc == kOpenList)
615  {
616  gCost = openClosedList.Lookat(theID).g;
617  return true;
618  }
619  return false;
620 }
621 
628 template <class state, class action, class environment>
629 void ImprovedOptimisticSearch<state, action,environment>::OpenGLDraw() const
630 {
631 }
632 
633 template <class state, class action, class environment>
634 void ImprovedOptimisticSearch<state, action,environment>::Draw(Graphics::Display &disp) const
635 {
636  double transparency = 1.0;
637  if (openClosedList.size() == 0)
638  return;
639  uint64_t top = -1;
640  // double minf = 1e9, maxf = 0;
641  if (openClosedList.OpenSize() > 0)
642  {
643  top = openClosedList.Peek();
644  }
645  for (unsigned int x = 0; x < openClosedList.size(); x++)
646  {
647  const auto &data = openClosedList.Lookat(x);
648  if (x == top)
649  {
650  env->SetColor(1.0, 1.0, 0.0, transparency);
651  env->Draw(disp, data.data);
652  }
653  else if ((data.where == kOpenList) && (data.reopened))
654  {
655  env->SetColor(0.0, 0.5, 0.5, transparency);
656  env->Draw(disp, data.data);
657  }
658  else if (data.where == kOpenList)
659  {
660  env->SetColor(0.0, 1.0, 0.0, transparency);
661  env->Draw(disp, data.data);
662  }
663  else if ((data.where == kClosedList) && (data.onOptimalPath))
664  {
665  env->SetColor(0.5, 0.5, 0.5, transparency);
666  env->Draw(disp, data.data);
667  }
668  else if ((data.where == kClosedList) && (data.reopened))
669  {
670  env->SetColor(0.5, 0.0, 0.5, transparency);
671  env->Draw(disp, data.data);
672  }
673  else if (data.where == kClosedList)
674  {
675  // if (top != -1)
676  // {
677  // env->SetColor((data.g+data.h-minf)/(maxf-minf), 0.0, 0.0, transparency);
678  // }
679  // else {
680  if (data.parentID == x)
681  env->SetColor(1.0, 0.5, 0.5, transparency);
682  else
683  env->SetColor(1.0, 0.0, 0.0, transparency);
684  // }
685  env->Draw(disp, data.data);
686  }
687  }
688  env->SetColor(1.0, 0.5, 1.0, 0.5);
689  env->Draw(disp, goal);
690 }
691 
692 
693 #endif /* IOS_h */
ImprovedOptimisticSearch::GetItem
const IOSOpenClosedData< state > & GetItem(unsigned int which)
Definition: IOS.h:101
ImprovedOptimisticSearch::DoOptimalStep
void DoOptimalStep(std::vector< state > &thePath)
Definition: IOS.h:416
AStarOpenClosed::Close
uint64_t Close(uint64_t objKey)
Move the given item to the closed list and return key.
Definition: AStarOpenClosed.h:291
ImprovedOptimisticSearch::InitializeSearch
bool InitializeSearch(environment *env, const state &from, const state &to, std::vector< state > &thePath)
Initialize the A* search.
Definition: IOS.h:230
AStarOpenClosed::KeyChanged
void KeyChanged(uint64_t objKey)
Indicate that the key for a particular object has changed.
Definition: AStarOpenClosed.h:253
ImprovedOptimisticSearch::GetOpenItem
const IOSOpenClosedData< state > & GetOpenItem(unsigned int which)
Definition: IOS.h:97
ImprovedOptimisticSearch::greedyPhi
std::function< double(double, double)> greedyPhi
Definition: IOS.h:148
ImprovedOptimisticSearch::~ImprovedOptimisticSearch
virtual ~ImprovedOptimisticSearch()
Definition: IOS.h:60
ImprovedOptimisticSearch::internalPath
std::vector< state > internalPath
Definition: IOS.h:140
IOSOpenClosedData::where
dataLocation where
Definition: IOS.h:33
ImprovedOptimisticSearch::GetClosedListGCost
bool GetClosedListGCost(const state &val, double &gCost) const
Get state from the closed list.
Definition: IOS.h:597
ImprovedOptimisticSearch::GetFocalListGCost
bool GetFocalListGCost(const state &val, double &gCost) const
ImprovedOptimisticSearch::SetWeight
void SetWeight(double w)
Definition: IOS.h:121
IOSOpenClosedData::data
state data
Definition: IOS.h:25
ImprovedOptimisticSearch::ResetNodeCount
void ResetNodeCount()
Definition: IOS.h:89
Heuristic
Definition: Heuristic.h:30
ImprovedOptimisticSearch::DoSingleSearchStep
bool DoSingleSearchStep(std::vector< state > &thePath)
Expand a single node.
Definition: IOS.h:294
ImprovedOptimisticSearch::GetName
virtual const char * GetName()
Return the name of the algorithm.
Definition: IOS.h:170
ImprovedOptimisticSearch::bestSolution
double bestSolution
Definition: IOS.h:149
ImprovedOptimisticSearch::GetMemoryUsage
int GetMemoryUsage()
Return the amount of memory used by ImprovedOptimisticSearch.
Definition: IOS.h:581
ImprovedOptimisticSearch
A templated version of A*, based on HOG genericAStar.
Definition: IOS.h:53
d
mcData d[]
Definition: MotionCaptureMovement.cpp:21
AStarOpenClosed::Lookat
const dataStructure & Lookat(uint64_t objKey) const
Definition: AStarOpenClosed.h:87
ImprovedOptimisticSearch::openList
AStarOpenClosed< state, IOSCompare< state >, IOSOpenClosedData< state > > openList
Definition: IOS.h:64
ImprovedOptimisticSearch::GetOptimalityBound
double GetOptimalityBound()
Definition: IOS.h:124
ImprovedOptimisticSearch::maxPriority
double maxPriority
Definition: IOS.h:156
IOSOpenClosedData::parentID
uint64_t parentID
Definition: IOS.h:30
IOSOpenClosedData::g
double g
Definition: IOS.h:27
ImprovedOptimisticSearch::GetWeight
double GetWeight()
Definition: IOS.h:122
ImprovedOptimisticSearch::neighborLoc
std::vector< dataLocation > neighborLoc
Definition: IOS.h:144
ImprovedOptimisticSearch::SetHeuristic
void SetHeuristic(Heuristic< state > *h)
Definition: IOS.h:111
ImprovedOptimisticSearch::ImprovedOptimisticSearch
ImprovedOptimisticSearch()
Definition: IOS.h:55
ImprovedOptimisticSearch::uniqueNodesExpanded
uint64_t uniqueNodesExpanded
Definition: IOS.h:153
IOSOpenClosedData::IOSOpenClosedData
IOSOpenClosedData(const state &theData, double fCost, double gCost, double hCost, uint64_t parent, uint64_t openLoc, dataLocation location)
Definition: IOS.h:20
ImprovedOptimisticSearch::GetNumItems
const int GetNumItems()
Definition: IOS.h:100
AStarOpenClosed::size
size_t size() const
Definition: AStarOpenClosed.h:103
AStarOpenClosed::CloseAllOnOpen
void CloseAllOnOpen()
Definition: AStarOpenClosed.h:94
IOSOpenClosedData::reopened
bool reopened
Definition: IOS.h:32
ImprovedOptimisticSearch::goal
state goal
Definition: IOS.h:68
IOSOpenClosedData
Definition: IOS.h:17
GenericSearchAlgorithm
Definition: GenericSearchAlgorithm.h:35
ImprovedOptimisticSearch::start
state start
Definition: IOS.h:68
ImprovedOptimisticSearch::bound
double bound
Definition: IOS.h:151
ImprovedOptimisticSearch::neighbors
std::vector< state > neighbors
Definition: IOS.h:141
AStarOpenClosed::Reopen
void Reopen(uint64_t objKey)
Move item off the closed list and back onto the open list.
Definition: AStarOpenClosed.h:329
AStarOpenClosed::ClosedSize
size_t ClosedSize() const
Definition: AStarOpenClosed.h:102
loc
Definition: MapGenerators.cpp:296
ImprovedOptimisticSearch::theHeuristic
Heuristic< state > * theHeuristic
Definition: IOS.h:154
ImprovedOptimisticSearch::OpenGLDraw
void OpenGLDraw() const
Draw the open/closed list.
Definition: IOS.h:629
ImprovedOptimisticSearch::GetUniqueNodesExpanded
uint64_t GetUniqueNodesExpanded()
Definition: IOS.h:88
AStarOpenClosed
Definition: AStarOpenClosed.h:74
ImprovedOptimisticSearch::GetOpenListGCost
bool GetOpenListGCost(const state &val, double &gCost) const
Definition: IOS.h:610
ImprovedOptimisticSearch::CheckNextNode
state CheckNextNode()
Returns the next state on the open list (but doesn't pop it off the queue).
Definition: IOS.h:526
Graphics::Display
Definition: Graphics.h:146
IOSOpenClosedData::openLocation
uint64_t openLocation
Definition: IOS.h:31
fless
bool fless(double a, double b)
Definition: FPUtil.h:28
AStarOpenClosed::AddOpenNode
uint64_t AddOpenNode(const state &val, uint64_t hash, double f, double g, double h, uint64_t parent=kTAStarNoNode)
Add object into open list.
Definition: AStarOpenClosed.h:146
ImprovedOptimisticSearch::HaveExpandedState
bool HaveExpandedState(const state &val)
Definition: IOS.h:103
dataLocation
dataLocation
Definition: AStarOpenClosed.h:27
ImprovedOptimisticSearch::GetStateLocation
dataLocation GetStateLocation(const state &val)
Definition: IOS.h:105
IOSOpenClosedData::IOSOpenClosedData
IOSOpenClosedData()
Definition: IOS.h:19
IOSOpenClosedData::f
double f
Definition: IOS.h:26
IOSCompare::operator()
bool operator()(const IOSOpenClosedData< state > &i1, const IOSOpenClosedData< state > &i2) const
Definition: IOS.h:39
ImprovedOptimisticSearch::DoGreedyStep
void DoGreedyStep(std::vector< state > &thePath)
Definition: IOS.h:324
fgreater
bool fgreater(double a, double b)
Definition: FPUtil.h:29
max
#define max(a, b)
Definition: MinimalSectorAbstraction.cpp:40
AStarOpenClosed::Peek
uint64_t Peek() const
Peek at the next item to be expanded.
Definition: AStarOpenClosed.h:280
ImprovedOptimisticSearch::AddAdditionalStartState
void AddAdditionalStartState(state &newState)
Add additional start state to the search.
Definition: IOS.h:265
AStarOpenClosed::OpenSize
size_t OpenSize() const
Definition: AStarOpenClosed.h:101
ImprovedOptimisticSearch::GetParent
const state & GetParent(const state &s)
Definition: IOS.h:552
ImprovedOptimisticSearch::SetReopenNodes
void SetReopenNodes(bool re)
Definition: IOS.h:108
kOpenList
@ kOpenList
Definition: AStarOpenClosed.h:28
ImprovedOptimisticSearch::env
environment * env
Definition: IOS.h:146
ImprovedOptimisticSearch::edgeCosts
std::vector< double > edgeCosts
Definition: IOS.h:143
StatCollection
The StatCollection class is for collecting stats across different parts of the simulation.
Definition: StatCollection.h:34
AStarOpenClosed::GetOpenItem
uint64_t GetOpenItem(unsigned int which)
Definition: AStarOpenClosed.h:100
ImprovedOptimisticSearch::doneGreedy
bool doneGreedy
Definition: IOS.h:155
IOSOpenClosedData::onOptimalPath
bool onOptimalPath
Definition: IOS.h:29
ImprovedOptimisticSearch::phi
std::function< double(double, double)> phi
Definition: IOS.h:147
ImprovedOptimisticSearch::GetNodesTouched
uint64_t GetNodesTouched() const
Definition: IOS.h:114
ImprovedOptimisticSearch::nodesExpanded
uint64_t nodesExpanded
Definition: IOS.h:138
AStarOpenClosed::Lookup
dataLocation Lookup(uint64_t hashKey, uint64_t &objKey) const
Returns location of object as well as object key.
Definition: AStarOpenClosed.h:263
ImprovedOptimisticSearch::ExtractPathToStart
void ExtractPathToStart(state &node, std::vector< state > &thePath)
Definition: IOS.h:76
ImprovedOptimisticSearch::Draw
void Draw(Graphics::Display &d) const
Definition: IOS.h:634
ImprovedOptimisticSearch::ExtractPathToStartFromID
void ExtractPathToStartFromID(uint64_t node, std::vector< state > &thePath)
Get the path from a goal state to the start state.
Definition: IOS.h:541
ImprovedOptimisticSearch::GetPath
void GetPath(environment *env, const state &from, const state &to, std::vector< state > &thePath)
Perform an A* search between two states.
Definition: IOS.h:189
ImprovedOptimisticSearch::GetNodesExpanded
uint64_t GetNodesExpanded() const
Definition: IOS.h:113
ImprovedOptimisticSearch::solutionReduction
double solutionReduction
Definition: IOS.h:149
ImprovedOptimisticSearch::PrintStats
void PrintStats()
A function that prints the number of states in the closed list and open queue.
Definition: IOS.h:567
ImprovedOptimisticSearch::GetReopenNodes
bool GetReopenNodes()
Definition: IOS.h:109
ImprovedOptimisticSearch::nodesTouched
uint64_t nodesTouched
Definition: IOS.h:138
ImprovedOptimisticSearch::GetNumOpenItems
unsigned int GetNumOpenItems()
Definition: IOS.h:96
AStarOpenClosed::Reset
void Reset(int val=0)
Remove all objects from queue.
Definition: AStarOpenClosed.h:135
kNotFound
@ kNotFound
Definition: AStarOpenClosed.h:30
path
A linked list of nodes which form a continuous path.
Definition: Path.h:20
ImprovedOptimisticSearch::Phi
double Phi(double h, double g)
Definition: IOS.h:129
IOSCompare
Definition: IOS.h:37
ImprovedOptimisticSearch::SetPhi
void SetPhi(std::function< double(double, double)> p)
Definition: IOS.h:125
fequal
bool fequal(double a, double b, double tolerance=TOLERANCE)
Definition: FPUtil.h:32
ImprovedOptimisticSearch::neighborID
std::vector< uint64_t > neighborID
Definition: IOS.h:142
ImprovedOptimisticSearch::reopenNodes
bool reopenNodes
Definition: IOS.h:152
ImprovedOptimisticSearch::SetOptimalityBound
void SetOptimalityBound(double w)
Definition: IOS.h:123
ImprovedOptimisticSearch::LogFinalStats
void LogFinalStats(StatCollection *)
Definition: IOS.h:116
IOSOpenClosedData::h
double h
Definition: IOS.h:28
flesseq
bool flesseq(double a, double b)
Definition: FPUtil.h:30
kClosedList
@ kClosedList
Definition: AStarOpenClosed.h:29
node
Nodes to be stored within a Graph.
Definition: Graph.h:170
ImprovedOptimisticSearch::openClosedList
AStarOpenClosed< state, IOSCompare< state >, IOSOpenClosedData< state > > openClosedList
Definition: IOS.h:66
ImprovedOptimisticSearch::weight
double weight
Definition: IOS.h:150
Graphics::Display::data
Definition: Graphics.h:226
ImprovedOptimisticSearch::GetClosedItem
bool GetClosedItem(const state &s, IOSOpenClosedData< state > &)
Generated by   doxygen 1.8.17