HOG2
FLRTAStar.h
Go to the documentation of this file.
1 /*
2  * FLRTAStar.h
3  * hog2
4  *
5  * Created by Nathan Sturtevant on 9/15/10.
6  * Copyright 2010 University of Denver. All rights reserved.
7  *
8  */
9 
10 #ifndef FLRTASTAR_H
11 #define FLRTASTAR_H
12 
13 #include "LearningAlgorithm.h"
14 #include "SearchEnvironment.h"
15 #include "FPUtil.h"
16 #include <deque>
17 #include <vector>
18 #include <unordered_map>
19 #include "TemplateAStar.h"
20 #include "Timer.h"
21 #include "vectorCache.h"
22 #include <queue>
23 #include <iostream>
24 
25 namespace FLRTA {
26  static bool verbose = false;
27  static double theWeight = 1.0;
28 
29  template <class state>
30  class borderData {
31  public:
32  borderData(const state &s, const double val) :theState(s), value(val) {}
33  state theState;
34  double value;
35  };
36 
37  template <class state>
38  class compareBorderData
39  {
40  public:
41  bool operator() (const borderData<state> &lhs, const borderData<state> &rhs) const
42  {
43  return (lhs.value > rhs.value);
44  }
45  };
46 
47  template <class state>
48  class learnedStateData {
49  public:
50  learnedStateData() :theState(), gCost(DBL_MAX), hCost(0), dead(false), redundant(false), parents(0), children(0) {}
51  ~learnedStateData() { delete parents; delete children; }
52  state theState;
53  double gCost;
54  double hCost;
55  bool dead;
56  bool redundant;
57  std::vector<state> *parents;
58  std::vector<state> *children;
59  };
60 
61  template <class state>
62  struct dblCmp {
63  bool operator()(const AStarOpenClosedData<state> &i1, const AStarOpenClosedData<state> &i2) const
64  {
65  //return (fgreater(i1.g, i2.g));
66  return (fgreater(i1.g+theWeight*i1.h, i2.g+theWeight*i2.h));
67  }
68  };
69 
70  template <class state, class action, class environment>
71  class FLRTAStar : public LearningAlgorithm<state,action,environment>, public Heuristic<state> {
72  public:
73  FLRTAStar(int nodeLimit = 8, double weight = 1.5)
74  { fAmountLearned = 0.0f; nodeExpansionLimit = nodeLimit; /*pe = 0;*/ nodeLearningLimit = 1;
75  fWeight = weight; orderRedundant = false; lastTrial = false;
76  followLocalGCost = false;
77  }
78  virtual ~FLRTAStar(void) { /*delete pe;*/ }
79 
80  bool GetLastTrial() { return lastTrial; }
81  void SetLastTrial() { lastTrial = true; }
82  double GetWeight() { return fWeight; }
83  void SetWeight(double w) { fWeight = w; }
84  void GetPath(environment *env, const state& from, const state& to, std::vector<state> &thePath);
85  void GetPath(environment *, const state& , const state& , std::vector<action> & ) { assert(false); };
86  virtual const char *GetName()
87  { static char name[255]; sprintf(name, "FLRTAStar(%d,%1.1f,%c,%c)", nodeExpansionLimit, fWeight, orderRedundant?'o':'u', followLocalGCost?'l':'g'); return name; }
88  void SetOrderRedundant(bool val) { orderRedundant = val; }
89  void SetUseLocalGCost(bool val) { followLocalGCost = val; }
90 
91  void VerifyParentChildren()
92  {
93  for (typename LearnedStateData::const_iterator it = stateData.begin(); it != stateData.end(); it++)
94  {
95  const learnedStateData<state> *s = &((*it).second);
96  if ((s->dead) && ((s->children->size() > 0) || s->children->size() > 0))
97  {
98  std::cout << s->theState << " is dead but has parents and/or children " << std::endl;
99  }
100  for (unsigned int x = 0; x < s->children->size(); x++)
101  {
102  bool found = false;
103  for (int y = 0; y < stateData[m_pEnv->GetStateHash(s->children->at(x))].parents->size(); y++)
104  {
105  if (stateData[m_pEnv->GetStateHash(s->children->at(x))].parents->at(y) == s->theState)
106  {
107  found = true;
108  break;
109  }
110  }
111  if (!found)
112  {
113  std::cout << s->theState << " lists " << s->children->at(x) << " as child, but the child doesn't list the parent" << std::endl;
114  }
115  }
116 
117  }
118 
119  }
120 
121 // void LivenState(const state &where)
122 // {
123 // stateData[m_pEnv->GetStateHash(where)].dead = true;
124 // }
125 
126  void KillState(const state &where)
127  {
128  uint64_t hash = m_pEnv->GetStateHash(where);
129  learnedStateData<state> &theState = stateData[hash];
130 
131  if (verbose) std::cout << "Killing " << where << std::endl;
132  for (unsigned int x = 0; x < theState.parents->size(); x++)
133  {
134  RemoveChild(theState.parents->at(x), where);
135  }
136  theState.parents->resize(0);
137  for (unsigned int x = 0; x < theState.children->size(); x++)
138  {
139  RemoveParent(where, theState.children->at(x));
140  }
141  theState.children->resize(0);
142  // if (stateData.find(m_pEnv->GetStateHash(where)) != stateData.end())
143 // theState.dead = true;
144 // else {
145  //std::cout << "Hashing state:1 " << std::endl << where << std::endl;
146  theState.theState = where;
147  theState.dead = true;
148 // }
149 // VerifyParentChildren();
150  }
151 
152  bool IsDead(const state &where)
153  {
154  // the default constructor makes dead == false, so we only have to initalize the state
155  uint64_t hash = m_pEnv->GetStateHash(where);
156  typename LearnedStateData::iterator it = stateData.find(hash);
157  if (it == stateData.end())
158  {
159  return false;
160  }
161  (*it).second.theState = where;
162  return (*it).second.dead;
163 
164 // stateData[m_pEnv->GetStateHash(where)].theState = where;
165 // return stateData[m_pEnv->GetStateHash(where)].dead;
166  }
167 
168  void AddParent(const state &parent, const state &child)
169  {
170  if (verbose)
171  {
172  if (IsDead(child) || IsDead(parent))
173  std::cout << "ABORT! trying to add dead child " << child << " to parent " << parent << std::endl;
174  }
175 
176  uint64_t hash = m_pEnv->GetStateHash(child);
177  learnedStateData<state> &theState = stateData[hash];
178 
179  for (unsigned int x = 0; x < theState.parents->size(); x++)
180  {
181  if (theState.parents->at(x) == parent)
182  return;
183  }
184  theState.parents->push_back(parent);
185  }
186 
187  void RemoveParent(const state &parent, const state &child)
188  {
189  uint64_t hash = m_pEnv->GetStateHash(child);
190  learnedStateData<state> &theState = stateData[hash];
191 
192  for (unsigned int x = 0; x < theState.parents->size(); x++)
193  {
194  if (theState.parents->at(x) == parent)
195  {
196  if (verbose)
197  std::cout << parent << " was parent of " << child << std::endl;
198  theState.parents->at(x) = theState.parents->back();
199  theState.parents->resize(theState.parents->size()-1);
200  return;
201  }
202  }
203  }
204 
205  void ClearParents(const state &which)
206  {
207  stateData[m_pEnv->GetStateHash(which)].parents->resize(0);
208  }
209 
210  void AddChild(const state &parent, const state &child)
211  {
212  uint64_t hash = m_pEnv->GetStateHash(parent);
213  learnedStateData<state> &theState = stateData[hash];
214 
215  for (unsigned int x = 0; x < theState.children->size(); x++)
216  {
217  if (theState.children->at(x) == child)
218  return;
219  }
220  theState.children->push_back(child);
221  }
222 
223  void RemoveChild(const state &parent, const state &child)
224  {
225  uint64_t hash = m_pEnv->GetStateHash(parent);
226  learnedStateData<state> &theState = stateData[hash];
227 
228  for (unsigned int x = 0; x < theState.children->size(); x++)
229  {
230  if (theState.children->at(x) == child)
231  {
232  if (verbose) std::cout << child << " was child of " << parent << std::endl;
233  theState.children->at(x) = theState.children->back();
234  theState.children->resize(theState.children->size()-1);
235  return;
236  }
237  }
238  }
239 
240  void ClearChildren(const state &which)
241  {
242  stateData[m_pEnv->GetStateHash(which)].children->resize(0);
243  }
244 
245  bool IsOnlyParent(const state &parent, const state &child)
246  {
247  if ((stateData[m_pEnv->GetStateHash(child)].parents->size() == 1) &&
248  (stateData[m_pEnv->GetStateHash(child)].parents->at(0) == parent))
249  return true;
250  return false;
251  }
252 
253  void SetGCost(environment *env, const state &where, double val)
254  {
255  uint64_t hash = env->GetStateHash(where);
256  learnedStateData<state> &theState = stateData[hash];
257  //TODO: reset parent/children
258  if (theState.parents == 0)
259  theState.parents = new std::vector<state>();
260  if (theState.children == 0)
261  theState.children = new std::vector<state>();
262 
263  for (unsigned int x = 0; x < theState.parents->size(); x++)
264  {
265  RemoveChild(theState.parents->at(x), where);
266  }
267  theState.parents->resize(0);
268  for (unsigned int x = 0; x < theState.children->size(); x++)
269  {
270  RemoveParent(where, theState.children->at(x));
271  }
272  theState.children->resize(0);
273 
274  if (verbose) std::cout << "-->GCost of " << where << " setting to " << val << std::endl;
275  //std::cout << "Hashing state:3 " << std::endl << where << std::endl;
276  fAmountLearned -= theState.hCost;
277  theState.hCost = 0;
278  theState.gCost = val;
279  theState.theState = where;
280  theState.dead = false; // updated g-cost, make it alive again
281  }
282 
283  double FCost(const state &where, const state &goal)
284  {
285  // could be more efficient
286  return GCost(where)+HCost(where, goal);
287  }
288 
289  double GCost(environment *env, const state &where)
290  {
291  uint64_t hash = env->GetStateHash(where);
292  //std::cout << "Hashing state:4 " << std::endl << where << std::endl;
293  typename LearnedStateData::iterator it = stateData.find(hash);
294  if (it != stateData.end())
295  {
296  //(*it).second.theState = where;
297  return (*it).second.gCost;
298  }
299  return DBL_MAX; // g-costs can only be lowered, hence the high start
300  }
301  double GCost(const state &where)
302  { return GCost(m_pEnv, where); }
303 
304 
305  void SetHCost(environment *env, const state &where, const state &to, double val)
306  {
307  double tmp = val-env->HCost(where, to);
308  if (tmp < 0) tmp = 0;
309  //std::cout << "Hashing state:5 " << std::endl << where << std::endl;
310  stateData[env->GetStateHash(where)].hCost = tmp;
311  stateData[env->GetStateHash(where)].theState = where;
312  }
313  double HCost(environment *env, const state &from, const state &to) const
314  {
315  auto val = stateData.find(env->GetStateHash(from));
316  if (val != stateData.end())
317  {
318  return val->second.hCost+env->HCost(from, to);
319  }
320  return env->HCost(from, to);
321 
322 
323 // //std::cout << "Hashing state:6 " << std::endl << from << std::endl;
324 // if (stateData.find(env->GetStateHash(from)) != stateData.end())
325 // {
326 // return stateData[env->GetStateHash(from)].hCost+env->HCost(from, to);
327 // }
328 // return env->HCost(from, to);
329  }
330  double HCost(const state &from, const state &to) const
331  { return HCost(m_pEnv, from, to); }
332 
333  void TryToKill(const state &where, const state &goal)
334  {
335  uint64_t hash = m_pEnv->GetStateHash(where);
336  learnedStateData<state> &theState = stateData[hash];
337  //VerifyParentChildren();
338  if (where == goal) return;
339  //if (IsDead(where)) return;
340  if (theState.dead) return;
341  if (verbose) std::cout << "Trying to kill: " << where << std::endl;
342  for (unsigned int x = 0; x < theState.children->size(); x++)
343  {
344  if (IsOnlyParent(where, theState.children->at(x)))
345  {
346  if (verbose)
347  {
348  if (IsDead(theState.children->at(x)))
349  printf("---But the state below is dead!\n");
350  std::cout << " Thwarted by " << theState.children->at(x) << std::endl;
351  }
352  return;
353  }
354  }
355 // nextToKill = *theState.parents;
356  KillState(where);
357 // for (unsigned int x = 0; x < theState.children->size(); x++)
358 // {
359 // RemoveParent(where, theState.children->at(x));
360 // //x--;
361 // }
362 // ClearChildren(where);
363 // for (unsigned int x = 0; x < theState.parents->size(); x++)
364 // {
365 // RemoveChild(theState.parents->at(x), where);
366 // //x--;
367 // }
368 // ClearParents(where);
369 
370  //VerifyParentChildren();
371  // this isn't agent centric
372 // for (unsigned int x = 0; x < parents.size(); x++)
373 // TryToKill(parents[x], goal);
374 // for (int x = 0; x < theState.parents->size(); x++)
375 // TryToKill(theState.parents->at(x), goal);
376  }
377 
378  bool IsRedundant(const state &where)
379  {
380  if (stateData[m_pEnv->GetStateHash(where)].children->size() == 0)
381  return true;
382  for (int x = 0; x < stateData[m_pEnv->GetStateHash(where)].children->size(); x++)
383  {
384  if (IsOnlyParent(where, stateData[m_pEnv->GetStateHash(where)].children->at(x)))
385  return false;
386  }
387  return true;
388 // std::vector<state> succ;
389 // m_pEnv->GetSuccessors(where, succ);
390 // for (unsigned int x = 0; x < succ.size(); x++)
391 // {
392 // if (IsDead(succ[x]))
393 // {
394 // if (verbose) std::cout << succ[x] << " is dead" << std::endl;
395 // continue;
396 // }
397 // if (fequal(GCost(succ[x]), DBL_MAX))
398 // {
399 // if (verbose) std::cout << where << " has child " << succ[x] << " with infinite g-cost. Not redundant!" << std::endl;
400 // return false;
401 // }
402 // //std::cout << "GCost state:1 " << std::endl << succ[x] << where << std::endl;
403 // if (fequal(GCost(succ[x]),
404 // GCost(where)+m_pEnv->GCost(where, succ[x])) &&
405 // (NumParents(succ[x]) <= 1))
406 // {
407 // if (verbose)
408 // std::cout << succ[x] << " relies on " << where << " as its only parent, not redundant" << std::endl;
409 // return false;
410 // }
411 // if (verbose) std::cout << DBL_MAX << succ[x] << " has no status -- gcost: " << GCost(succ[x]) << std::endl;
412 // if (orderRedundant && IsBestParent(succ[x], where))
413 // return false;
414 // }
415 // return true;
416  }
417 
418  int NumParents(const state &where)
419  {
420  int count = 0;
421  std::vector<state> succ;
422  m_pEnv->GetSuccessors(where, succ);
423  for (unsigned int x = 0; x < succ.size(); x++)
424  {
425 // // unexplored parent/child, counts as a parent for now
426 // if (fequal(GCost(succ[x]), DBL_MAX))
427 // count++;
428  // parent has less or equal path cost
429  //std::cout << "GCost state:2 " << std::endl << succ[x] << where << std::endl;
430  if (fequal(GCost(succ[x])+m_pEnv->GCost(succ[x], where),
431  GCost(where)) &&
432  !IsDead(succ[x]))
433  count++;
434  }
435  if (verbose) std::cout << where << " has " << count << " successors" << std::endl;
436  return count;
437  }
438 
439  bool IsBestParent(const state &child, const state &parent)
440  {
441  std::vector<state> succ;
442  m_pEnv->GetSuccessors(child, succ);
443  for (unsigned int x = 0; x < succ.size(); x++)
444  {
445  if (succ[x] == parent) continue;
446 
447  //std::cout << "GCost state:3 " << std::endl << succ[x] << parent << child << std::endl;
448  if (fequal(GCost(succ[x])+m_pEnv->GCost(succ[x], child),
449  GCost(child)) &&
450  !IsDead(succ[x]) &&
451  GCost(succ[x]) >= GCost(parent))
452  return true;
453  }
454  return false;
455  }
456 
457  virtual uint64_t GetNodesExpanded() const { return nodesExpanded; }
458  virtual uint64_t GetNodesTouched() const { return nodesTouched; }
459  virtual void LogFinalStats(StatCollection *s) { s->AddStat("TotalLearning", GetName(),fAmountLearned); }
460 
461  double GetAmountLearned() { return fAmountLearned; }
462  void OpenGLDraw() const {}
463  void OpenGLDraw(const environment *env) const;
464  private:
465  typedef std::unordered_map<uint64_t, learnedStateData<state>, Hash64 > LearnedStateData;
466  typedef std::unordered_map<uint64_t, bool, Hash64 > ClosedList;
467  void ExtractBestPath(environment *env, const state &from, const state &to, std::vector<state> &thePath);
468  void MakeTrappedMove(environment *env, const state &from, std::vector<state> &thePath);
469 
470  void ExpandLSS(const state &from, const state &to, std::vector<state> &thePath);
471  void MarkDeadRedundant(environment *env, const state &goal);
472  void DoHCostLearning(environment *env, const state &from, const state &to);
473  void PropagateGCosts(const state &next, const state &to, bool alsoExpand);
474 
475  environment *m_pEnv;
476  LearnedStateData stateData;
477  double fAmountLearned, fWeight;
478  uint64_t nodesExpanded, nodesTouched;
479  int nodeExpansionLimit, nodeLearningLimit;
480  state theEnd;
481  bool orderRedundant, lastTrial, followLocalGCost;
482 
483  typedef std::priority_queue<borderData<state>,std::vector<borderData<state> >,compareBorderData<state> > pQueue;
484  pQueue gCostQueue;
485 
486  AStarOpenClosed<state, dblCmp<state> > aoc;
487  };
488 
490  template <class state, class action, class environment>
491  void FLRTAStar<state, action, environment>::GetPath(environment *env, const state& from, const state& to, std::vector<state> &thePath)
492  {
493 // Timer t;
494 // t.StartTimer();
495 // VerifyParentChildren();
496  //theWeight = fWeight;
497  nodesExpanded = nodesTouched = 0;
498  m_pEnv = env;
499  thePath.resize(0);
500  theEnd = to;
501  aoc.Reset();
502  assert(gCostQueue.empty());
503  if (from==to)
504  return;
505 
506  if (GCost(from) == DBL_MAX)
507  SetGCost(env, from, 0);
508 
509  if (IsDead(from))
510  {
511  MakeTrappedMove(env, from, thePath);
512  return;
513  }
514 
515  ExpandLSS(from, to, thePath);
516 // if (nodesExpanded >= nodeExpansionLimit)
517 // std::cout << GetName() << " Lookahead " << nodeExpansionLimit << ", " << nodesExpanded-nodeExpansionLimit << " expanded during g-cost propagation" << std::endl;
518 // else
519 // std::cout << GetName() << " Lookahead " << nodeExpansionLimit << ", " << 0 << " expanded during g-cost propagation" << std::endl;
520  // in case goal was found in LSS
521  if (thePath.size() != 0)
522  return;
523 // uint64_t old = nodesExpanded;
524  DoHCostLearning(env, from, to);
525 // std::cout << GetName() << " " << nodesExpanded-old << " learning expansions before dead/redundant " << std::endl;
526 
527  // folded into HCost learning
528  MarkDeadRedundant(env, to);
529 // std::cout << GetName() << nodesExpanded << " total nodes this step" << std::endl;
530  ExtractBestPath(env, from, to, thePath);
531 
532 
533  if (verbose) std::cout << "FLRTA* heading towards " << thePath[0] << " with h-value " << HCost(env, thePath[0], to) << std::endl;
534  //t.EndTimer();
535  //std::cout << GetName() << "\t" << nodesExpanded << "\t" << t.GetElapsedTime() << "\t" << nodesExpanded/t.GetElapsedTime() << std::endl;
536  }
537 
538  template <class state, class action, class environment>
539  void FLRTAStar<state, action, environment>::ExtractBestPath(environment *env, const state &from, const state &to, std::vector<state> &thePath)
540  {
541  state best;
542  unsigned int cnt = 0;
543  for (; cnt < aoc.OpenSize(); cnt++)
544  {
545  if (!IsDead(aoc.Lookat(aoc.GetOpenItem(cnt)).data) &&
546  !(aoc.Lookat(aoc.GetOpenItem(cnt)).data == from))
547  {
548  best = aoc.Lookat(aoc.GetOpenItem(cnt)).data;
549  break;
550  }
551  }
552  // no path found, go backwards in g-cost
553  if (cnt == aoc.OpenSize())
554  {
555  MakeTrappedMove(env, from, thePath);
556  return;
557  }
558  // 3. Find node with highest f-cost / g-cost
559  double bestG = 0;
560  for (; cnt < aoc.OpenSize(); cnt++)
561  {
562  const AStarOpenClosedData<state> data = aoc.Lookat(aoc.GetOpenItem(cnt));
563  if (IsDead(data.data))
564  continue;
565  double tmp = fWeight;
566  if (lastTrial)
567  fWeight = 1;
568  if (followLocalGCost)
569  {
570  if (fgreater(bestG+fWeight*HCost(best, to),
571  data.g+fWeight*HCost(data.data, to)) &&
572  !(data.data == from))
573  {
574  best = data.data;
575  bestG = data.g;
576  }
577  else if (fequal(bestG+fWeight*HCost(best, to), data.g+fWeight*HCost(data.data, to)) &&
578  fgreater(data.g, bestG) &&
579  !(data.data == from))
580  {
581  best = data.data;
582  bestG = data.g;
583  }
584  }
585  else {
586  if (fgreater(GCost(best)+fWeight*HCost(best, to),
587  GCost(data.data)+fWeight*HCost(data.data, to)) &&
588  !(data.data == from))
589  {
590  best = data.data;
591  }
592  else if (fequal(GCost(best)+fWeight*HCost(best, to), GCost(data.data)+fWeight*HCost(data.data, to)) &&
593  fgreater(GCost(data.data), GCost(best)) &&
594  !(data.data == from))
595  {
596  best = data.data;
597  }
598  }
599  fWeight = tmp;
600  }
601  // 4. construct best path
602  if (verbose) std::cout << "Moving towards " << best << " cost " << GCost(best) << std::endl;
603  uint64_t node;
604  aoc.Lookup(env->GetStateHash(best), node);
605  do {
606  thePath.push_back(aoc.Lookup(node).data);
607  node = aoc.Lookup(node).parentID;
608  } while (aoc.Lookup(node).parentID != node);
609  thePath.push_back(aoc.Lookup(node).data);
610  }
611 
612  template <class state, class action, class environment>
613  void FLRTAStar<state, action, environment>::MakeTrappedMove(environment *env, const state &from, std::vector<state> &thePath)
614  {
615  std::vector<state> succ;
616  env->GetSuccessors(from, succ);
617  nodesExpanded++;
618  int back = -1;
619  bool found = false;
620  for (unsigned int x = 0; x < succ.size(); x++)
621  {
622  if ((back == -1) && (GCost(succ[x]) < GCost(from)))
623  {
624  back = x;
625  found = true;
626  }
627  else if ((back != -1) && (GCost(succ[x]) < GCost(succ[back])))
628  {
629  back = x;
630  found = true;
631  }
632  }
633  if (!found)
634  {
635  std::cout << "No successors of " << from << " with smaller g-cost than " << GCost(from) << std::endl;
636  for (unsigned int x = 0; x < succ.size(); x++)
637  std::cout << succ[x] << " has cost " << GCost(succ[x]) << std::endl;
638  assert(!"Invalid environment; apparently cannot reach all predecessors of a state");
639  exit(0);
640  }
641  thePath.push_back(succ[back]);
642  thePath.push_back(from);
643  //if (verbose) std::cout << "FLRTA* heading towards " << thePath[0] << " with h-value " << HCost(env, thePath[0], to) << std::endl;
644  return;
645  }
646 
647  template <class state, class action, class environment>
648  void FLRTAStar<state, action, environment>::ExpandLSS(const state &from, const state &to, std::vector<state> &thePath)
649  {
650  if (verbose) std::cout << "Expanding LSS" << std::endl;
651  // 0. put from on OPEN
652  //std::cout << "Hashing state:8 " << std::endl << from << std::endl;
653  aoc.AddOpenNode(from, m_pEnv->GetStateHash(from), 0.0, 0.0);
654  std::vector<state> tempDead;
655 
656  for (int x = 0; x < nodeExpansionLimit; x++)//nodeLearningLimit
657  {
658  if (aoc.OpenSize() == 0)
659  break;
660  // 1. choose next node to expand
661  uint64_t next = aoc.Close();
662  if (verbose) std::cout << "Next in LSS: " << aoc.Lookat(next).data << std::endl;
663 
664  // 2. propagate g-costs to neighbors and beyond if this node isn't dead
665  if (IsDead(aoc.Lookat(next).data))// && x != 0)
666  {
667  // dead; ignore(?)
668  //x--;
669  //tempDead.push_back(aoc.Lookat(next).data)
670  if (verbose) std::cout << aoc.Lookat(next).data << " is dead; left on closed (LSS)" << std::endl;
671  continue;
672  }
673  else {
674  // cannot pass data from AOC by reference, because when data structures are
675  // resized it can become invalidated
676  state val = aoc.Lookat(next).data;
677  PropagateGCosts(val, to, true);
678  }
679 
680  // 3. reached goal, stop
681  if (aoc.Lookat(next).data == to)
682  {
683  uint64_t node = next;
684  do {
685 // std::cout << aoc.Lookup(node).data << " ";
686  thePath.push_back(aoc.Lookup(node).data);
687  node = aoc.Lookup(node).parentID;
688  } while (aoc.Lookup(node).parentID != node);
689  thePath.push_back(aoc.Lookup(node).data);
690  return;
691  }
692  }
693 
694 // // 4. finish propagation from edge of open list
695  for (unsigned int x = 0; x < aoc.OpenSize(); x++)
696  {
697  state s = aoc.Lookat(aoc.GetOpenItem(x)).data;
698  if (!IsDead(s))
699  PropagateGCosts(s, to, false);
700  //gCostQueue.push(borderData<state>(s, GCost(s)));
701  }
702  }
703 
704 
705  template <class state, class action, class environment>
706  void FLRTAStar<state, action, environment>::PropagateGCosts(const state &next, const state &to, bool alsoExpand)
707  {
708  if (verbose) std::cout << "=Propagating from: " << next << (alsoExpand?" and expanding":" not expanding") << std::endl;
709  // decrease g-cost as long as somewhere on aoc / expand if requested
710  static vectorCache<state> vc;
711 
712  std::vector<state> *neighbors = vc.getItem();;
713  m_pEnv->GetSuccessors(next, *neighbors);
714  nodesExpanded++;
715  uint64_t parentKey;
716  //std::cout << "Hashing state:9 " << std::endl << next << std::endl;
717  dataLocation pLoc = aoc.Lookup(m_pEnv->GetStateHash(next), parentKey);
718 
719  if (verbose) std::cout << GCost(next) << " gcost in " <<
720  ((pLoc==kOpenList)?("open"):((pLoc==kClosedList)?"closed":"none")) << std::endl;
721  for (unsigned int x = 0; x < neighbors->size(); x++)
722  {
723  nodesTouched++;
724  double edgeCost = m_pEnv->GCost(next, neighbors->at(x));
725  uint64_t childKey;
726  //std::cout << "Hashing state:10 " << std::endl << neighbors->at(x) << std::endl;
727  dataLocation cLoc = aoc.Lookup(m_pEnv->GetStateHash(neighbors->at(x)), childKey);
728 
729  if (alsoExpand && pLoc != kNotFound)
730  {
731  if (cLoc == kNotFound) // add node even if it is dead!
732  {
733 // double cost = min(GCost(next)+edgeCost, GCost(neighbors->at(x)));
734 
735  if (verbose) std::cout << "Adding " << neighbors->at(x) << " to open with f:" <<
736  aoc.Lookat(parentKey).g+edgeCost + HCost(neighbors->at(x), to) << std::endl;
737  aoc.AddOpenNode(neighbors->at(x), m_pEnv->GetStateHash(neighbors->at(x)),
738  aoc.Lookat(parentKey).g+edgeCost,
739  //cost,
740  HCost(neighbors->at(x), to), parentKey);
741  cLoc = kOpenList;
742  }
743  else if (cLoc == kOpenList)
744  { // these are local g costs
745  if (fless(aoc.Lookup(parentKey).g+edgeCost, aoc.Lookup(childKey).g))
746  {
747  if (verbose) std::cout << "Updating " << neighbors->at(x) << " on open" << std::endl;
748  aoc.Lookup(childKey).parentID = parentKey;
749  aoc.Lookup(childKey).g = aoc.Lookup(parentKey).g+edgeCost;
750  aoc.KeyChanged(childKey);
751  }
752  }
753  else if (cLoc == kClosedList)
754  {
755  if (fless(aoc.Lookup(parentKey).g+edgeCost, aoc.Lookup(childKey).g))
756  {
757  if (verbose) std::cout << "Reopening " << neighbors->at(x) << std::endl;
758  aoc.Lookup(childKey).parentID = parentKey;
759  aoc.Lookup(childKey).g = aoc.Lookup(parentKey).g+edgeCost;
760  aoc.Reopen(childKey);
761  cLoc = kOpenList; // since we moved it, and this is re-used below
762  }
763  }
764  }
765 
766  // shorter g-cost to neighbors->at(x) from global search perspective
767  assert(GCost(next) != DBL_MAX);
768  // TODO: handle equal case:
769  if (!IsDead(neighbors->at(x)) && fequal(GCost(next)+edgeCost, GCost(neighbors->at(x))))
770  {
771  AddParent(next, neighbors->at(x));
772  AddChild(next, neighbors->at(x));
773  }
774  if (fless(GCost(next)+edgeCost, GCost(neighbors->at(x))))
775  {
776  if (verbose) std::cout << "Updating " << neighbors->at(x) << " from " << GCost(neighbors->at(x)) <<
777  " to " << GCost(next) << "(" << next << ") + " << edgeCost << " = " << GCost(next)+edgeCost << std::endl;
778  if (IsDead(neighbors->at(x)) && (cLoc == kClosedList)) // important step in proof!
779  {
780  // node was dead. If this is on the optimal path, it needs to be opened
781  cLoc = kOpenList;
782  //aoc.Reopen(childKey);
783  SetGCost(m_pEnv, neighbors->at(x), GCost(next)+edgeCost);
784  //TODO:
785  AddParent(next, neighbors->at(x));
786  AddChild(next, neighbors->at(x));
787  PropagateGCosts(neighbors->at(x), to, true);
788  }
789  else {
790  SetGCost(m_pEnv, neighbors->at(x), GCost(next)+edgeCost);
791  //TODO:
792  AddParent(next, neighbors->at(x));
793  AddChild(next, neighbors->at(x));
794  //if (cLoc == kClosedList)
795  if (alsoExpand || (cLoc == kOpenList || cLoc == kClosedList))
796  PropagateGCosts(neighbors->at(x), to, false);
797  }
798  }
799 // // shorter g-cost from neighbor to here, reverse search
800 // //std::cout << "GCost state:9 " << std::endl << next << neighbors[x] << std::endl;
801 
802  if (fless(edgeCost+GCost(neighbors->at(x)), GCost(next)) && !IsDead(neighbors->at(x)))
803  {
804  //assert(!IsDead(neighbors->at(x)));
805  //LivenState(neighbors->at(x)); // would need to put back on open, but happens elsewhere. [simplify later?]
806  if (verbose) std::cout << "[Recursing to] Update " << next << " from " << GCost(next) <<
807  " to " << GCost(neighbors->at(x)) << "(" << neighbors->at(x) << ") + " << edgeCost << " = " << GCost(neighbors->at(x))+edgeCost << std::endl;
808  SetGCost(m_pEnv, next, GCost(neighbors->at(x))+edgeCost);
809  //TODO:
810  if (!IsDead(neighbors->at(x)))
811  {
812  AddParent(neighbors->at(x), next);
813  AddChild(neighbors->at(x), next);
814 // if (cLoc == kOpenList || cLoc == kClosedList)
815 // PropagateGCosts(neighbors->at(x), to, false);
816  }
817  if (x != 0) x = -1;
818  }
819  }
820  vc.returnItem(neighbors);
821  if (verbose) std::cout << "=Done Propagating from: " << next << std::endl;
822  }
823 
824  template <class state, class action, class environment>
825  void FLRTAStar<state, action, environment>::MarkDeadRedundant(environment *env, const state &goal)
826  {
827 // VerifyParentChildren();
828 // // 1. put all open nodes in pqueue
829  pQueue q;
830 //
831  unsigned int openSize = aoc.size();
832  for (unsigned int x = 0; x < openSize; x++)
833  {
834  const AStarOpenClosedData<state> data = aoc.Lookat(x);//astar.GetItem(x);
835  //if ((data.where == kClosedList) || (nodeExpansionLimit == 1))
836  {
837  q.push(borderData<state>(data.data, -GCost(data.data)));
838  if (verbose) std::cout <<std::endl<< ">>>Preparing state: " << data.data << " g: " << GCost(data.data) << std::endl;
839  }
840  }
841 
842 // std::vector<state> succ;
843  state first = q.top().theState;
844  while (q.size() > 0)
845  {
846 // //nodesExpanded++;
847 // //nodesTouched++;
848  state s = q.top().theState;
849  TryToKill(s, goal);
850 // if (verbose) std::cout << "Doing update from " << s << " g: " << q.top().value << "/" << GCost(s) << std::endl;
851  q.pop();
852  if (fgreater(GCost(s)+HCost(s, goal), GCost(goal)))
853  {
854  if (verbose) std::cout<<"Marking " << GCost(s) << ":" << HCost(s, goal) << " " << s << " as dead -- too far from goal: " << GCost(goal) << goal << std::endl;
855  KillState(s);
856  }
857  }
858  }
859 
860 
861  template <class state, class action, class environment>
862  void FLRTAStar<state, action, environment>::DoHCostLearning(environment *env, const state &from, const state &to)
863  {
864  // 1. put all open nodes in pqueue
865  pQueue q;
866 
867  // dead guys
868  std::vector<state> toKill;
869  // for successors
870  std::vector<state> succ;
871 
872  unsigned int openSize = aoc.OpenSize();
873  for (unsigned int x = 0; x < openSize; x++)
874  {
875  const AStarOpenClosedData<state> data = aoc.Lookat(aoc.GetOpenItem(x));
876  if (!IsDead(data.data))
877  {
878  q.push(borderData<state>(data.data, HCost(data.data, to)));
879  if (verbose) std::cout << "Preparing border state: " << data.data << " h: " << data.h << std::endl;
880  }
881  }
882  if (q.size() == 0)
883  {
884  return;
885  }
886 
887  state first = q.top().theState;
888  ClosedList c;
889  while (q.size() > 0)
890  {
891  state s = q.top().theState;
892  if (verbose) std::cout << "Propagating from " << s << " h: " << q.top().value << "/" << HCost(s, to) << std::endl;
893  q.pop();
894  // std::cout << s << " " << learnData[env->GetStateHash(s)].learnedHeuristic << std::endl;
895  env->GetSuccessors(s, succ);
896  nodesExpanded++;
897  nodesTouched++;
898  double hCost = HCost(s, to);
899 // bool shouldKill = true;
900  for (unsigned int x = 0; x < succ.size(); x++)
901  {
902 // if (IsOnlyParent(s, succ[x]))
903 // shouldKill = false;
904  nodesTouched++;
905  double succHCost;
906 
907  uint64_t succKey;
908  //std::cout << "Hashing state:15 " << std::endl << succ[x] << std::endl;
909  dataLocation pLoc = aoc.Lookup(env->GetStateHash(succ[x]), succKey);
910  if (pLoc != kClosedList)
911  {
912  //if (verbose) std::cout << succ[x] << " not in closed\n";
913  continue;
914  }
915  double edgeCost = env->GCost(s, succ[x]);
916  succHCost = HCost(env, succ[x], to);
917  if (c[env->GetStateHash(succ[x])]) // in closed list, but seen before, update if smaller
918  {
919  if (verbose) std::cout << succ[x] << " updated before " << std::endl;
920  if (fless(hCost + edgeCost, succHCost))
921  {
922  fAmountLearned -= succHCost-hCost-edgeCost;
923  if (verbose) std::cout << "lowering cost to " << hCost + edgeCost;
924  //if (verbose) std::cout << " learning now " << fAmountLearned;
925  SetHCost(env, succ[x], to, hCost + edgeCost);
926  q.push(borderData<state>(succ[x], hCost + edgeCost));
927  }
928  //if (verbose) std::cout << std::endl;
929  }
930  else { // not expanded before and in closed list, always update
931  // 2. expand successors, checking if they are in closed list and adding to queue
932  // if (fless(succHCost, hCost - edgeCost))
933  if (verbose) std::cout << succ[x] << " NOT updated before ";
934  //if (fgreater(hCost + edgeCost, succHCost))
935  {
936  if (verbose) std::cout << "setting cost to " << hCost + edgeCost << " over " << succHCost << std::endl;
937  fAmountLearned += (edgeCost + hCost) - succHCost;
938  //if (verbose) std::cout << " learning now " << fAmountLearned;
939  SetHCost(env, succ[x], to, hCost + edgeCost);
940  q.push(borderData<state>(succ[x], hCost + edgeCost));
941  c[env->GetStateHash(succ[x])] = true;
942  }
943  //if (verbose) std::cout << std::endl;
944  }
945  }
946  }
947  }
948 
949  template <class state, class action, class environment>
950  void FLRTAStar<state, action, environment>::OpenGLDraw(const environment *e) const
951  {
952 // if (astar.GetNodesExpanded() > 0)
953 // astar.OpenGLDraw();
954  char str[32];
955 
956  double learned = 0;
957  for (typename LearnedStateData::const_iterator it = stateData.begin(); it != stateData.end(); it++)
958  {
959  double thisState = (*it).second.hCost;
960  if (learned < thisState)
961  learned = thisState;
962  }
963  for (typename LearnedStateData::const_iterator it = stateData.begin(); it != stateData.end(); it++)
964  {
965  uint64_t node;
966  dataLocation loc = (aoc.Lookup(m_pEnv->GetStateHash((*it).second.theState), node));
967  //if (loc != kOpenList) continue;
968 
969  for (size_t x = 0; x < (*it).second.children->size(); x++)
970  {
971  m_pEnv->GLDrawLine((*it).second.theState, (*it).second.children->at(x));
972  }
973  for (size_t x = 0; x < (*it).second.parents->size(); x++)
974  {
975  m_pEnv->GLDrawLine((*it).second.theState, (*it).second.parents->at(x));
976  }
977 
978  if (loc == kOpenList)
979  {
980  if ((*it).second.dead)
981  sprintf(str, " %1.1f", (*it).second.gCost);
982  else
983  sprintf(str, "%1.1f %1.1f", (*it).second.gCost, (*it).second.hCost+m_pEnv->HCost((*it).second.theState, theEnd));
984  e->SetColor(0.9, 0.9, 0.9, 1);
985  e->GLLabelState((*it).second.theState, str);
986  }
987 
988  if ((*it).second.dead)
989  {
990  e->SetColor(0.0, 0.0+((loc==kOpenList)?0.5:0.0), 0.0, 1);
991  e->OpenGLDraw((*it).second.theState);
992  }
993  else
994  {
995  double r = (*it).second.hCost;
996  if (r > 0)
997  {
998  e->SetColor(0.5+0.5*r/learned, ((loc==kOpenList)?0.5:0.0), 0, 0.1+0.8*r/learned);
999  e->OpenGLDraw((*it).second.theState);
1000  }
1001  else if (loc == kOpenList)
1002  {
1003  e->SetColor(0.0, 0.5, 0.0, 1);
1004  e->OpenGLDraw((*it).second.theState);
1005  }
1006  }
1007  }
1008  }
1009 
1010 }
1011 
1012 #endif
FLRTA::FLRTAStar::IsOnlyParent
bool IsOnlyParent(const state &parent, const state &child)
Definition: FLRTAStar.h:245
FLRTA::FLRTAStar::ClearChildren
void ClearChildren(const state &which)
Definition: FLRTAStar.h:240
FLRTA::FLRTAStar::FLRTAStar
FLRTAStar(int nodeLimit=8, double weight=1.5)
Definition: FLRTAStar.h:73
FLRTA::FLRTAStar::nodeExpansionLimit
int nodeExpansionLimit
Definition: FLRTAStar.h:479
FLRTA::FLRTAStar::KillState
void KillState(const state &where)
Definition: FLRTAStar.h:126
FLRTA::FLRTAStar::OpenGLDraw
void OpenGLDraw() const
Definition: FLRTAStar.h:462
FLRTA::learnedStateData::gCost
double gCost
Definition: FLRTAStar.h:53
stateData::theState
state theState
Definition: HeuristicLearningMeasure.h:23
FLRTA::FLRTAStar::GetNodesTouched
virtual uint64_t GetNodesTouched() const
Definition: FLRTAStar.h:458
FLRTA::theWeight
static double theWeight
Definition: FLRTAStar.h:27
AStarOpenClosedData::data
state data
Definition: AStarOpenClosed.h:57
FLRTA::FLRTAStar::SetHCost
void SetHCost(environment *env, const state &where, const state &to, double val)
Definition: FLRTAStar.h:305
FLRTA::FLRTAStar::ClosedList
std::unordered_map< uint64_t, bool, Hash64 > ClosedList
Definition: FLRTAStar.h:466
FLRTA::FLRTAStar::GetName
virtual const char * GetName()
Definition: FLRTAStar.h:86
FLRTA::FLRTAStar::TryToKill
void TryToKill(const state &where, const state &goal)
Definition: FLRTAStar.h:333
Heuristic
Definition: Heuristic.h:30
FLRTA::FLRTAStar::LogFinalStats
virtual void LogFinalStats(StatCollection *s)
Definition: FLRTAStar.h:459
FLRTA::FLRTAStar::orderRedundant
bool orderRedundant
Definition: FLRTAStar.h:481
FLRTA::FLRTAStar::aoc
AStarOpenClosed< state, dblCmp< state > > aoc
Definition: FLRTAStar.h:486
FLRTA::FLRTAStar::IsRedundant
bool IsRedundant(const state &where)
Definition: FLRTAStar.h:378
LearningAlgorithm
Definition: LearningAlgorithm.h:15
FLRTA::FLRTAStar::AddParent
void AddParent(const state &parent, const state &child)
Definition: FLRTAStar.h:168
FLRTA::FLRTAStar::GetPath
void GetPath(environment *, const state &, const state &, std::vector< action > &)
Definition: FLRTAStar.h:85
FLRTA::FLRTAStar::RemoveChild
void RemoveChild(const state &parent, const state &child)
Definition: FLRTAStar.h:223
FLRTA::learnedStateData::theState
state theState
Definition: FLRTAStar.h:52
FPUtil.h
FLRTA::learnedStateData::dead
bool dead
Definition: FLRTAStar.h:55
FLRTA::FLRTAStar::MakeTrappedMove
void MakeTrappedMove(environment *env, const state &from, std::vector< state > &thePath)
Definition: FLRTAStar.h:613
FLRTA::FLRTAStar::nodesTouched
uint64_t nodesTouched
Definition: FLRTAStar.h:478
vectorCache.h
FLRTA::FLRTAStar::fAmountLearned
double fAmountLearned
Definition: FLRTAStar.h:477
FLRTA::learnedStateData::parents
std::vector< state > * parents
Definition: FLRTAStar.h:57
FLRTA::FLRTAStar::MarkDeadRedundant
void MarkDeadRedundant(environment *env, const state &goal)
Definition: FLRTAStar.h:825
FLRTA::dblCmp
Definition: FLRTAStar.h:62
FLRTA::FLRTAStar::lastTrial
bool lastTrial
Definition: FLRTAStar.h:481
FLRTA
Definition: FLRTAStar.h:25
FLRTA::FLRTAStar::AddChild
void AddChild(const state &parent, const state &child)
Definition: FLRTAStar.h:210
FLRTA::FLRTAStar::SetGCost
void SetGCost(environment *env, const state &where, double val)
Definition: FLRTAStar.h:253
AStarOpenClosedData::g
double g
Definition: AStarOpenClosed.h:64
Timer.h
FLRTA::FLRTAStar::gCostQueue
pQueue gCostQueue
Definition: FLRTAStar.h:484
FLRTA::FLRTAStar::PropagateGCosts
void PropagateGCosts(const state &next, const state &to, bool alsoExpand)
Definition: FLRTAStar.h:706
FLRTA::FLRTAStar::HCost
double HCost(const state &from, const state &to) const
Definition: FLRTAStar.h:330
loc
Definition: MapGenerators.cpp:296
FLRTA::FLRTAStar::HCost
double HCost(environment *env, const state &from, const state &to) const
Definition: FLRTAStar.h:313
FLRTA::dblCmp::operator()
bool operator()(const AStarOpenClosedData< state > &i1, const AStarOpenClosedData< state > &i2) const
Definition: FLRTAStar.h:63
FLRTA::learnedStateData::redundant
bool redundant
Definition: FLRTAStar.h:56
FLRTA::FLRTAStar::GetAmountLearned
double GetAmountLearned()
Definition: FLRTAStar.h:461
AStarOpenClosed
Definition: AStarOpenClosed.h:74
Hash64
Definition: SearchEnvironment.h:23
fless
bool fless(double a, double b)
Definition: FPUtil.h:28
openSize
const int openSize
Definition: EnvUtil.h:19
vectorCache::getItem
std::vector< storage > * getItem()
Definition: vectorCache.h:39
FLRTA::borderData::theState
state theState
Definition: FLRTAStar.h:33
AStarOpenClosedData
Definition: AStarOpenClosed.h:52
dataLocation
dataLocation
Definition: AStarOpenClosed.h:27
FLRTA::compareBorderData
Definition: FLRTAStar.h:38
FLRTA::FLRTAStar::ExtractBestPath
void ExtractBestPath(environment *env, const state &from, const state &to, std::vector< state > &thePath)
Definition: FLRTAStar.h:539
FLRTA::FLRTAStar::DoHCostLearning
void DoHCostLearning(environment *env, const state &from, const state &to)
Definition: FLRTAStar.h:862
FLRTA::verbose
static bool verbose
Definition: FLRTAStar.h:26
FLRTA::borderData::borderData
borderData(const state &s, const double val)
Definition: FLRTAStar.h:32
FLRTA::FLRTAStar::IsBestParent
bool IsBestParent(const state &child, const state &parent)
Definition: FLRTAStar.h:439
TemplateAStar.h
FLRTA::learnedStateData::learnedStateData
learnedStateData()
Definition: FLRTAStar.h:50
FLRTA::FLRTAStar::SetUseLocalGCost
void SetUseLocalGCost(bool val)
Definition: FLRTAStar.h:89
fgreater
bool fgreater(double a, double b)
Definition: FPUtil.h:29
FLRTA::learnedStateData::hCost
double hCost
Definition: FLRTAStar.h:54
FLRTA::FLRTAStar::NumParents
int NumParents(const state &where)
Definition: FLRTAStar.h:418
FLRTA::FLRTAStar::nodesExpanded
uint64_t nodesExpanded
Definition: FLRTAStar.h:478
FLRTA::borderData::value
double value
Definition: FLRTAStar.h:34
FLRTA::learnedStateData::~learnedStateData
~learnedStateData()
Definition: FLRTAStar.h:51
vectorCache
Definition: vectorCache.h:14
FLRTA::FLRTAStar::GCost
double GCost(environment *env, const state &where)
Definition: FLRTAStar.h:289
kOpenList
@ kOpenList
Definition: AStarOpenClosed.h:28
StatCollection
The StatCollection class is for collecting stats across different parts of the simulation.
Definition: StatCollection.h:34
FLRTA::FLRTAStar::GetNodesExpanded
virtual uint64_t GetNodesExpanded() const
Definition: FLRTAStar.h:457
FLRTA::FLRTAStar::pQueue
std::priority_queue< borderData< state >, std::vector< borderData< state > >, compareBorderData< state > > pQueue
Definition: FLRTAStar.h:483
FLRTA::FLRTAStar::SetOrderRedundant
void SetOrderRedundant(bool val)
Definition: FLRTAStar.h:88
FLRTA::FLRTAStar::LearnedStateData
std::unordered_map< uint64_t, learnedStateData< state >, Hash64 > LearnedStateData
Definition: FLRTAStar.h:465
FLRTA::FLRTAStar
Definition: FLRTAStar.h:71
FLRTA::FLRTAStar::GetLastTrial
bool GetLastTrial()
Definition: FLRTAStar.h:80
FLRTA::FLRTAStar::m_pEnv
environment * m_pEnv
Definition: FLRTAStar.h:475
LearningAlgorithm.h
FLRTA::FLRTAStar::VerifyParentChildren
void VerifyParentChildren()
Definition: FLRTAStar.h:91
FLRTA::FLRTAStar::IsDead
bool IsDead(const state &where)
Definition: FLRTAStar.h:152
AStarOpenClosedData::h
double h
Definition: AStarOpenClosed.h:65
StatCollection::AddStat
void AddStat(const char *category, const char *owner, double value)
Add a new stat entry for the given category, owner and value.
Definition: StatCollection.cpp:67
FLRTA::borderData
Definition: FLRTAStar.h:30
FLRTA::FLRTAStar::fWeight
double fWeight
Definition: FLRTAStar.h:477
FLRTA::FLRTAStar::nodeLearningLimit
int nodeLearningLimit
Definition: FLRTAStar.h:479
FLRTA::FLRTAStar::SetWeight
void SetWeight(double w)
Definition: FLRTAStar.h:83
FLRTA::FLRTAStar::stateData
LearnedStateData stateData
Definition: FLRTAStar.h:476
FLRTA::FLRTAStar::SetLastTrial
void SetLastTrial()
Definition: FLRTAStar.h:81
FLRTA::FLRTAStar::GetWeight
double GetWeight()
Definition: FLRTAStar.h:82
FLRTA::FLRTAStar::ExpandLSS
void ExpandLSS(const state &from, const state &to, std::vector< state > &thePath)
Definition: FLRTAStar.h:648
kNotFound
@ kNotFound
Definition: AStarOpenClosed.h:30
FLRTA::FLRTAStar::theEnd
state theEnd
Definition: FLRTAStar.h:480
FLRTA::FLRTAStar::GetPath
void GetPath(environment *env, const state &from, const state &to, std::vector< state > &thePath)
The core routine of FLRTAStar – computes at most one-move path.
Definition: FLRTAStar.h:491
FLRTA::FLRTAStar::followLocalGCost
bool followLocalGCost
Definition: FLRTAStar.h:481
FLRTA::FLRTAStar::FCost
double FCost(const state &where, const state &goal)
Definition: FLRTAStar.h:283
fequal
bool fequal(double a, double b, double tolerance=TOLERANCE)
Definition: FPUtil.h:32
FLRTA::learnedStateData
Definition: FLRTAStar.h:48
FLRTA::FLRTAStar::GCost
double GCost(const state &where)
Definition: FLRTAStar.h:301
FLRTA::compareBorderData::operator()
bool operator()(const borderData< state > &lhs, const borderData< state > &rhs) const
Definition: FLRTAStar.h:41
FLRTA::FLRTAStar::~FLRTAStar
virtual ~FLRTAStar(void)
Definition: FLRTAStar.h:78
stateData
Definition: HeuristicLearningMeasure.h:20
kClosedList
@ kClosedList
Definition: AStarOpenClosed.h:29
node
Nodes to be stored within a Graph.
Definition: Graph.h:170
SearchEnvironment.h
FLRTA::FLRTAStar::RemoveParent
void RemoveParent(const state &parent, const state &child)
Definition: FLRTAStar.h:187
FLRTA::FLRTAStar::ClearParents
void ClearParents(const state &which)
Definition: FLRTAStar.h:205
FLRTA::learnedStateData::children
std::vector< state > * children
Definition: FLRTAStar.h:58
Generated by   doxygen 1.8.17