HOG2
IBEX.h
Go to the documentation of this file.
1 //
2 // IBEX.h
3 // hog2
4 //
5 // This code contains an implementation of IBEX / BTS / BGS
6 // See also:
7 // https://webdocs.cs.ualberta.ca/~nathanst/papers/IBEX.pdf
8 // https://www.movingai.com/SAS/BTS/
9 //
10 
11 #ifndef IBEX_h
12 #define IBEX_h
13 
14 #include "vectorCache.h"
15 #include "AStarOpenClosed.h"
16 #ifndef DEBUG
17 #define DEBUG 0 // set debug mode
18 #endif
19 
20 #if DEBUG
21 #define debug_print(fmt, ...) printf(fmt,__VA_ARGS__)
22 #else
23 #define debug_print(fmt, ...) do {} while (0)
24 #endif
25 namespace IBEX {
26 
27  template <class state>
28  struct BFHSCompare {
29  bool operator()(const AStarOpenClosedData<state> &i1, const AStarOpenClosedData<state> &i2) const
30  {
31  return (fgreater(i1.g, i2.g));
32  }
33  };
34 
35  const int infiniteWorkBound = -1;
36 
37  template <class state, class action, class environment, bool DFS = true>
38  class IBEX {
39  public:
40  IBEX(uint64_t minGrow, uint64_t maxGrow, double growthRate, bool exponential)
41  :c1(minGrow), c2(maxGrow), gamma(growthRate), oracle(false), exponentialGrowth(exponential) {}
42  void GetPath(environment *env, state from, state to,
43  std::vector<action> &thePath);
44  void GetPath(environment *env, Heuristic<state> *heuristic, state from, state to,
45  std::vector<action> &thePath);
46  void Dovetail(environment *env, Heuristic<state> *heuristic, state from, state to,
47  std::vector<action> &thePath);
48  double RedoMinWork();
49 
50  uint64_t GetNodesExpanded() { return totalNodesExpanded; }
51  uint64_t GetNodesTouched() { return totalNodesTouched; }
52  void ResetNodeCount() { totalNodesExpanded = totalNodesTouched = 0; }
53  private:
54  struct searchBounds {
55  double f_below; // value below the actual limit
56  double f_above; // value above the actual limit
57  uint64_t nodes; // nodes used to search
58  };
59  struct costInterval {
60  double lowerBound;
61  double upperBound;
62  costInterval &operator&=(const costInterval &i)
63  {
64  lowerBound = std::max(lowerBound, i.lowerBound);
65  upperBound = std::min(upperBound, i.upperBound);
66  return *this;
67  }
68  };
69  IBEX<state, action, environment, DFS>::costInterval LowLevelSearch(double costLimit, uint64_t nodeLimit, uint64_t &nodesUsed);
70 
71  // Functions for DF Search
72  double GCost(const state &s1, const state &s2)
73  { return env->GCost(s1, s2); }
74  double GCost(const state &s, const action &a)
75  { return env->GCost(s, a); }
76  double HCost(const state &s)
77  { return h->HCost(s, goal); }
78  IBEX<state, action, environment, DFS>::costInterval DFBNB(double costLimit, uint64_t nodeLimit, uint64_t &nodesUsed);
79  IBEX<state, action, environment, DFS>::searchBounds DFBNBHelper(state &currState, double pathCost, double costLimit,
80  searchBounds &sd, uint64_t nodeLimit, action forbidden);
81 
82  // Functions for BFHS
83  IBEX<state, action, environment, DFS>::costInterval BFHS(double costLimit, uint64_t nodeLimit, uint64_t &nodesUsed);
84  void ExtractPathToStartFromID(uint64_t node, std::vector<state> &thePath);
85 
86 
87  uint64_t totalNodesExpanded, totalNodesTouched;
88  Heuristic<state> *h;
89  environment *env;
90  std::vector<action> solutionPath, currPath;
91  double solutionCost;
92  vectorCache<action> actCache;
93  state start, goal;
94  uint64_t c1, c2;
95  double gamma;
96  double dfsLowerBound;
97  bool oracle;
98  bool exponentialGrowth;
99 
100  // Data for BFHS
101  AStarOpenClosed<state, BFHSCompare<state>> q;
102  std::vector<state> neighbors;
103  std::vector<uint64_t> neighborID;
104  std::vector<double> edgeCosts;
105  std::vector<dataLocation> neighborLoc;
106  std::vector<state> solutionStates;
107  };
108 
109  template <class state, class action, class environment, bool DFS>
110  void IBEX<state, action, environment, DFS>::GetPath(environment *env, state from, state to,
111  std::vector<action> &thePath)
112  {
113  GetPath(env, env, from, to, thePath);
114  }
115 
116  template <class state, class action, class environment, bool DFS>
117  void IBEX<state, action, environment, DFS>::GetPath(environment *env, Heuristic<state> *heuristic, state from, state to,
118  std::vector<action> &thePath)
119  {
120  this->env = env;
121  h = heuristic;
122  start = from;
123  goal = to;
124  solutionPath.clear();
125  solutionCost = DBL_MAX;
126  ResetNodeCount();
127 
128  uint64_t nodeLB = 1;
129  costInterval solutionInterval;
130  uint64_t currentNodesUsed;
131  solutionInterval.lowerBound = HCost(from);
132  solutionInterval.upperBound = DBL_MAX;
133  while (fgreater(solutionCost, solutionInterval.lowerBound))
134  {
135  double delta = 1;
136  debug_print("IBEX: Base search: f: %1.5f, cost limit ∞, target [%" PRId64 ", %" PRId64 "]\n", solutionInterval.lowerBound, c1*nodeLB, c2*nodeLB);
137  dfsLowerBound = solutionInterval.lowerBound;
138  solutionInterval &= LowLevelSearch(solutionInterval.lowerBound, infiniteWorkBound, currentNodesUsed);
139 
140  // Move to next iteration
141  if (currentNodesUsed >= c1*nodeLB)
142  {
143  nodeLB = currentNodesUsed;
144  solutionInterval.upperBound = DBL_MAX;
145  continue;
146  }
147 
148  while (!(fequal(solutionInterval.upperBound, solutionInterval.lowerBound) ||
149  (currentNodesUsed >= c1*nodeLB && currentNodesUsed < c2*nodeLB)))
150  {
151  if (solutionInterval.upperBound == DBL_MAX)
152  {
153  debug_print(" ]--Critical f in [%1.5f, ∞]\n", solutionInterval.lowerBound);
154  }
155 
156  else
157  {
158  debug_print(" ]--Critical f in [%1.5f, %1.5f]\n", solutionInterval.lowerBound, solutionInterval.upperBound);
159  }
160 
161 
162  double nextCost;
163  delta *= gamma;
164  if (solutionInterval.upperBound == DBL_MAX)
165  {
166  if (exponentialGrowth)
167  nextCost = solutionInterval.lowerBound+delta;
168 // nextCost = baseHCost+(solutionInterval.lowerBound-baseHCost) * gamma;
169  else
170  nextCost = solutionInterval.lowerBound * gamma;
171  }
172  else
173  nextCost = (solutionInterval.lowerBound+solutionInterval.upperBound)/2.0;
174 
175  dfsLowerBound = solutionInterval.lowerBound;
176  solutionInterval &= LowLevelSearch(nextCost, c2*nodeLB, currentNodesUsed);
177  }
178 
179  nodeLB = std::max(currentNodesUsed, c1*nodeLB);
180  solutionInterval.upperBound = DBL_MAX;
181 
182  if (fequal(solutionInterval.lowerBound, solutionCost))
183  break;
184  }
185  thePath = solutionPath;
186  debug_print("Found solution cost %1.5f\n", solutionCost);
187  }
188 
189 
190  template <class state, class action, class environment, bool DFS>
191  typename IBEX<state, action, environment, DFS>::costInterval IBEX<state, action, environment, DFS>::DFBNB(double costLimit, uint64_t nodeLimit, uint64_t &nodesUsed)
192  {
193  state currState = start;
194  if (nodeLimit == infiniteWorkBound)
195  {
196  debug_print(" --+DFBnB f: %1.5f; nodes: ∞; ", costLimit);
197  }
198 
199  else
200  {
201  debug_print(" --+DFBnB f: %1.5f; nodes: %" PRId64 "; ", costLimit, nodeLimit);
202  }
203 
204  currPath.clear();
205  searchBounds sd;
206  sd.f_below = 0;
207  sd.f_above = DBL_MAX;
208  sd.nodes = 0;
209  action a;
210  sd = DFBNBHelper(currState, 0, costLimit, sd, nodeLimit, a);
211  totalNodesExpanded += sd.nodes;
212 
213  costInterval v;
214  if (sd.nodes >= nodeLimit)
215  {
216  v.lowerBound = 0;
217  v.upperBound = sd.f_below;
218  }
219  else if (solutionCost != DBL_MAX && fgreatereq(sd.f_below, solutionCost))
220  {
221  v.lowerBound = solutionCost;
222  v.upperBound = solutionCost;
223  }
224  else {
225  v.lowerBound = sd.f_above;
226  v.upperBound = DBL_MAX;
227  assert(fgreater(sd.f_above, costLimit));
228  }
229  nodesUsed = sd.nodes;
230  if (v.upperBound == DBL_MAX)
231  {
232  debug_print("%" PRId64 " (new) %" PRId64 " (total), solution range: [%1.5f, ∞] ", nodesUsed, totalNodesExpanded, v.lowerBound);
233  }
234  else
235  {
236  debug_print("%" PRId64 " (new) %" PRId64 " (total), solution range: [%1.5f, %1.5f] ", nodesUsed, totalNodesExpanded, v.lowerBound, v.upperBound);
237  }
238 
239  if (solutionCost != DBL_MAX)
240  {
241  debug_print("sol: %1.5f\n", solutionCost);
242  }
243  else
244  {
245  debug_print("\n",1);
246  }
247 
248  return v;
249  //return sd;
250  }
251 
252  template <class state, class action, class environment, bool DFS>
253  typename IBEX<state, action, environment, DFS>::searchBounds IBEX<state, action, environment, DFS>::DFBNBHelper(state &currState, double pathCost, double costLimit,
254  searchBounds &sd, uint64_t nodeLimit, action forbidden)
255  {
256  double currF = pathCost+HCost(currState);
257  // printf("-------->%f [%f]\n", currF, pathCost);
258  if (fequal(dfsLowerBound, solutionCost) && !oracle)
259  {
260  return sd;
261  }
262  if (fgreater(currF, costLimit))
263  {
264  sd.f_above = std::min(sd.f_above, currF);
265  return sd;
266  }
267  else if (fgreatereq(currF, solutionCost))
268  {
269  sd.f_below = solutionCost;
270  return sd;
271  }
272  else {
273  sd.f_below = std::max(currF, sd.f_below);
274  }
275 
276  if (sd.nodes >= nodeLimit)
277  return sd;
278  if (env->GoalTest(currState, goal))
279  {
280  if (fless(currF, solutionCost))
281  {
282  solutionPath = currPath;
283  solutionCost = currF;
284  }
285  return sd;
286  }
287 
288  std::vector<action> &acts = *actCache.getItem();
289  env->GetActions(currState, acts);
290  sd.nodes++;
291  totalNodesTouched+=acts.size();
292 
293  for (size_t x = 0; x < acts.size(); x++)
294  {
295  if (acts[x] == forbidden && currPath.size() > 0)
296  continue;
297  double edgeCost = GCost(currState, acts[x]);
298  env->ApplyAction(currState, acts[x]);
299  currPath.push_back(acts[x]);
300  action rev = acts[x];
301  env->InvertAction(rev);
302  sd = DFBNBHelper(currState, pathCost+edgeCost, costLimit, sd, nodeLimit, rev);
303  currPath.pop_back();
304  env->UndoAction(currState, acts[x]);
305  }
306  actCache.returnItem(&acts);
307  return sd;
308  }
309 
310  template <class state, class action, class environment, bool DFS>
311  double IBEX<state, action, environment, DFS>::RedoMinWork()
312  {
313  ResetNodeCount();
314  debug_print("IBEX Validation:\n",1);
315  oracle = true;
316  uint64_t nodesUsed;
317  LowLevelSearch(solutionCost, -1, nodesUsed);
318  oracle = false;
319  return solutionCost;
320  }
321 
322  template <class state, class action, class environment, bool DFS>
323  typename IBEX<state, action, environment, DFS>::costInterval IBEX<state, action, environment, DFS>::BFHS(double costLimit, uint64_t nodeLimit, uint64_t &nodesUsed)
324  {
325  if (nodeLimit == -1ull && costLimit == DBL_MAX)
326  {
327  debug_print(" --+BFHS f: ∞; nodes: ∞; ",1);
328  }
329  else if (nodeLimit == -1)
330  {
331  debug_print(" --+BFHS f: %1.5f; nodes: ∞; ", costLimit);
332  }
333  else
334  {
335  debug_print(" --+BFHS f: %1.5f; nodes: %" PRId64 "; ", costLimit, nodeLimit);
336  }
337 
338  searchBounds sd;
339  sd.f_below = 0;
340  sd.f_above = DBL_MAX;
341  sd.nodes = 0;
342 
343  q.Reset(env->GetMaxHash());
344 
345  // put start in open
346  q.AddOpenNode(start, env->GetStateHash(start), 0.0, 0.0, (uint64_t)0);
347 
348  while (sd.nodes < nodeLimit && q.OpenSize() > 0)
349  {
350  // expand by low g until
351  // (1) we find the goal
352  // (2) we hit the node limit
353  // (3) we exhaust all states
354  uint64_t nodeid = q.Close();
355  sd.nodes++;
356  totalNodesExpanded++;
357 
358  double nextf = q.Lookup(nodeid).g + HCost(q.Lookup(nodeid).data);
359  if (fgreater(nextf, costLimit))
360  {
361  // case shouldn't happen - pruned elsewhere
362  assert(false);
363  } else {
364  sd.f_below = std::max(sd.f_below, nextf);
365  }
366 
367 
368  if (env->GoalTest(q.Lookup(nodeid).data, goal))
369  {
370  solutionCost = q.Lookup(nodeid).g;
371  ExtractPathToStartFromID(nodeid, solutionStates);
372  // Path is backwards - reverse
373  reverse(solutionStates.begin(), solutionStates.end());
374  // f, nextF, failedF, nodes
375  for (int x = 0; x < solutionStates.size()-1; x++)
376  {
377  solutionPath.push_back(env->GetAction(solutionStates[x], solutionStates[x+1]));
378  }
379  // TODO: return range here
380  nodesUsed = sd.nodes;
381  return {q.Lookup(nodeid).g, q.Lookup(nodeid).g};
382  }
383 
384  neighbors.resize(0);
385  edgeCosts.resize(0);
386  neighborID.resize(0);
387  neighborLoc.resize(0);
388 
389 // std::cout << "Expanding: " << q.Lookup(nodeid).data << " with f:";
390 // std::cout << q.Lookup(nodeid).g << std::endl;
391 
392  env->GetSuccessors(q.Lookup(nodeid).data, neighbors);
393 
394  // 1. load all the children
395  for (size_t x = 0; x < neighbors.size(); x++)
396  {
397  uint64_t theID;
398  neighborLoc.push_back(q.Lookup(env->GetStateHash(neighbors[x]), theID));
399  neighborID.push_back(theID);
400  edgeCosts.push_back(GCost(q.Lookup(nodeid).data, neighbors[x]));
401  }
402 
403  // iterate again updating costs and writing out to memory
404  for (size_t x = 0; x < neighbors.size(); x++)
405  {
406  totalNodesTouched++;
407 
408  double childGCost = q.Lookup(nodeid).g+edgeCosts[x];
409  double childFCost = childGCost+HCost(neighbors[x]);
410  if (fgreater(childFCost, costLimit) || fgreatereq(childFCost, solutionCost))
411  {
412  sd.f_above = std::min(sd.f_above, childFCost);
413  continue;
414  }
415 
416  switch (neighborLoc[x])
417  {
418  case kClosedList:
419  break;
420  case kOpenList:
421  if (fless(childGCost, q.Lookup(neighborID[x]).g))
422  {
423  q.Lookup(neighborID[x]).parentID = nodeid;
424  q.Lookup(neighborID[x]).g = childGCost;
425  q.KeyChanged(neighborID[x]);
426  }
427  break;
428  case kNotFound:
429  {
430  q.AddOpenNode(neighbors[x],
431  env->GetStateHash(neighbors[x]),
432  childGCost,
433  0.0,
434  nodeid);
435  }
436  }
437  }
438  }
439  // f, nextF, failedF, nodes
440 
441  // TODO: return range here
442  costInterval v;
443  if (sd.nodes >= nodeLimit)
444  {
445  v.lowerBound = 0;
446  v.upperBound = sd.f_below;
447  }
448  else {
449  v.lowerBound = sd.f_above;
450  v.upperBound = DBL_MAX;
451  }
452  //v.nodes = sd.nodes;
453  nodesUsed = sd.nodes;
454 
455  if (v.upperBound == DBL_MAX)
456  {
457  debug_print("%" PRId64 " (new) %" PRId64 " (total), solution range: [%1.5f, ∞]\n", nodesUsed, totalNodesExpanded, v.lowerBound);
458  }
459 
460  else
461  {
462  debug_print("%" PRId64 " (new) %" PRId64 " (total), solution range: [%1.5f, %1.5f]\n", nodesUsed, totalNodesExpanded, v.lowerBound, v.upperBound);
463  }
464 
465 
466  return v;
467  }
468 
469  template <class state, class action,class environment,bool DFS>
470  void IBEX<state, action, environment, DFS>::ExtractPathToStartFromID(uint64_t node,
471  std::vector<state> &thePath)
472  {
473  thePath.clear();
474  do {
475  thePath.push_back(q.Lookup(node).data);
476  node = q.Lookup(node).parentID;
477  } while (q.Lookup(node).parentID != node);
478  thePath.push_back(q.Lookup(node).data);
479  }
480 
481 
482  template <class state, class action, class environment, bool DFS>
483  typename IBEX<state, action, environment, DFS>::costInterval IBEX<state, action, environment, DFS>::LowLevelSearch(double costLimit, uint64_t nodeLimit, uint64_t &nodesUsed)
484  {
485  if (DFS)
486  return DFBNB(costLimit, nodeLimit, nodesUsed);
487  else
488  return BFHS(costLimit, nodeLimit, nodesUsed);
489  }
490 
491  /* Node used by the UBS search */
492  class UBSNode {
493  public:
494  UBSNode(int k, int r) : r(r), k(k) {}
495  int r;
496  int k;
497  friend bool operator<(const UBSNode &n1, const UBSNode &n2) {return n1.T() > n2.T();}
498  int T() const {return r * pow(2, k);}
499  };
500 
501  template <class state, class action, class environment, bool DFS>
502  void IBEX<state, action, environment, DFS>::Dovetail(environment *env, Heuristic<state> *heuristic, state from, state to,
503  std::vector<action> &thePath)
504  {
505  this->env = env;
506  h = heuristic;
507  start = from;
508  goal = to;
509  solutionPath.clear();
510  solutionCost = DBL_MAX;
511  ResetNodeCount();
512 
513  //Graph &graph, int alpha, float gamma, Data &data)
514  int alpha=c2;
515 
516  /* lookup table maps programs k to uppder bounds.
517  Lower bound is tracked globally */
518  std::map<int,double> lookup;
519  /* priority queue for storing the UBS nodes */
520  std::priority_queue<UBSNode> q;
521  q.push(UBSNode(1,1));
522  /* b_low is a lower bound on the optimal budget */
523  uint64_t b_low = 0;
524  double low = HCost(from);
525  while (!q.empty()) {
526  /* get top element from queue */
527  auto n = q.top();
528  q.pop();
529  int k = n.k;
530  int r = n.r;
531  /* set budget */
532  int b = pow(alpha,k);
533 
534  /* update the UBS */
535  if (n.r == 1) {
536  q.push(UBSNode(n.k+1,1));
537  }
538 
539  /* skip the query if the budget is known to be insufficient
540  to find a solution */
541  if (b <= b_low) {
542  continue;
543  }
544 
545 
546  /* check to see if upper bound has been found yet for this program */
547  if (lookup.find(k) == lookup.end()) {
548  lookup[k] = DBL_MAX;//std::numeric_limits<float>::max();
549  }
550  double high = lookup[k];
551 
552  if (high != DBL_MAX)
553  {
554  debug_print("Running (k=%d, r=%d) with budget %d; [global] low = %f, [loca] high = %f\n", k, r, b, low, high);
555  }
556  else
557  {
558  debug_print("Running (k=%d, r=%d) with budget %d; [global] low = %f, [loca] high = ∞\n", k, r, b, low);
559  }
560 
561 
562 
563  /* compute the cost threshhold for the query */
564  float C;
565  if (exponentialGrowth)
566  C = low + (1<<(r-1));
567  else
568  C = gamma * low; /* by default, in the binary search mode */
569  if (r == 1)
570  { /* start with an infinite budget search */
571  C = low;
572  b = infiniteWorkBound;//std::numeric_limits<int>::max();
573  }
574  else if (high != DBL_MAX) { /* exponential search */
575  C = (low + high) / 2.0;
576  }
577  /* make the query */
578  uint64_t nodesUsed;
579  costInterval i = LowLevelSearch(C, b, nodesUsed);
580 
581  /* perform the intersection */
582  lookup[k] = std::min(i.upperBound, high);
583  low = std::max(low, i.lowerBound);
584 
585  /* the budget was sufficient and no solution found, so update the minimal budget */
586  if (i.upperBound == DBL_MAX) {
587  b_low = nodesUsed;
588  }
589 
590  /* update the UBS */
591  q.push(UBSNode(n.k, n.r+1));
592 
593  if (flesseq(solutionCost, low))
594  {
595  thePath = solutionPath;
596  debug_print("proven solution cost %f\n", solutionCost);
597  break;
598  }
599  }
600  }
601 
602 }
603 
604 #endif /* IBEX_h */
IBEX::UBSNode
Definition: IBEX.h:492
IBEX::IBEX::costInterval::operator&=
costInterval & operator&=(const costInterval &i)
Definition: IBEX.h:62
IBEX::IBEX::searchBounds::f_below
double f_below
Definition: IBEX.h:55
min
double min(double a, double b)
Definition: FPUtil.h:35
IBEX::IBEX::edgeCosts
std::vector< double > edgeCosts
Definition: IBEX.h:104
IBEX::IBEX::totalNodesTouched
uint64_t totalNodesTouched
Definition: IBEX.h:87
IBEX::UBSNode::k
int k
Definition: IBEX.h:496
IBEX::IBEX::costInterval::lowerBound
double lowerBound
Definition: IBEX.h:60
IBEX::IBEX::solutionCost
double solutionCost
Definition: IBEX.h:91
IBEX::IBEX::neighborID
std::vector< uint64_t > neighborID
Definition: IBEX.h:103
fgreatereq
bool fgreatereq(double a, double b)
Definition: FPUtil.h:31
IBEX::UBSNode::r
int r
Definition: IBEX.h:495
Heuristic
Definition: Heuristic.h:30
IBEX::IBEX::searchBounds::f_above
double f_above
Definition: IBEX.h:56
IBEX
Definition: IBEX.h:25
AStarOpenClosed.h
IBEX::IBEX::searchBounds::nodes
uint64_t nodes
Definition: IBEX.h:57
IBEX::infiniteWorkBound
const int infiniteWorkBound
Definition: IBEX.h:35
IBEX::IBEX::oracle
bool oracle
Definition: IBEX.h:97
IBEX::IBEX::solutionPath
std::vector< action > solutionPath
Definition: IBEX.h:90
IBEX::IBEX::neighborLoc
std::vector< dataLocation > neighborLoc
Definition: IBEX.h:105
vectorCache.h
IBEX::UBSNode::UBSNode
UBSNode(int k, int r)
Definition: IBEX.h:494
IBEX::IBEX::costInterval
Definition: IBEX.h:59
IBEX::IBEX::dfsLowerBound
double dfsLowerBound
Definition: IBEX.h:96
AStarOpenClosedData::g
double g
Definition: AStarOpenClosed.h:64
IBEX::UBSNode::T
int T() const
Definition: IBEX.h:498
IBEX::UBSNode::operator<
friend bool operator<(const UBSNode &n1, const UBSNode &n2)
Definition: IBEX.h:497
AStarOpenClosed
Definition: AStarOpenClosed.h:74
IBEX::IBEX::neighbors
std::vector< state > neighbors
Definition: IBEX.h:102
fless
bool fless(double a, double b)
Definition: FPUtil.h:28
AStarOpenClosedData
Definition: AStarOpenClosed.h:52
IBEX::IBEX::q
AStarOpenClosed< state, BFHSCompare< state > > q
Definition: IBEX.h:101
IBEX::IBEX::env
environment * env
Definition: IBEX.h:89
DFS
Definition: DFS.h:19
fgreater
bool fgreater(double a, double b)
Definition: FPUtil.h:29
max
#define max(a, b)
Definition: MinimalSectorAbstraction.cpp:40
vectorCache< action >
kOpenList
@ kOpenList
Definition: AStarOpenClosed.h:28
IBEX::IBEX::GetNodesExpanded
uint64_t GetNodesExpanded()
Definition: IBEX.h:50
debug_print
#define debug_print(fmt,...)
Definition: IBEX.h:23
IBEX::IBEX::searchBounds
Definition: IBEX.h:54
IBEX::IBEX::costInterval::upperBound
double upperBound
Definition: IBEX.h:61
IBEX::IBEX::GCost
double GCost(const state &s, const action &a)
Definition: IBEX.h:74
IBEX::IBEX::solutionStates
std::vector< state > solutionStates
Definition: IBEX.h:106
IBEX::IBEX::GCost
double GCost(const state &s1, const state &s2)
Definition: IBEX.h:72
IBEX::IBEX::start
state start
Definition: IBEX.h:93
IBEX::IBEX::IBEX
IBEX(uint64_t minGrow, uint64_t maxGrow, double growthRate, bool exponential)
Definition: IBEX.h:40
IBEX::BFHSCompare::operator()
bool operator()(const AStarOpenClosedData< state > &i1, const AStarOpenClosedData< state > &i2) const
Definition: IBEX.h:29
IBEX::IBEX::c2
uint64_t c2
Definition: IBEX.h:94
kNotFound
@ kNotFound
Definition: AStarOpenClosed.h:30
IBEX::IBEX
Definition: IBEX.h:38
IBEX::IBEX::gamma
double gamma
Definition: IBEX.h:95
fequal
bool fequal(double a, double b, double tolerance=TOLERANCE)
Definition: FPUtil.h:32
IBEX::IBEX::actCache
vectorCache< action > actCache
Definition: IBEX.h:92
IBEX::IBEX::HCost
double HCost(const state &s)
Definition: IBEX.h:76
IBEX::IBEX::GetNodesTouched
uint64_t GetNodesTouched()
Definition: IBEX.h:51
flesseq
bool flesseq(double a, double b)
Definition: FPUtil.h:30
IBEX::IBEX::h
Heuristic< state > * h
Definition: IBEX.h:88
kClosedList
@ kClosedList
Definition: AStarOpenClosed.h:29
node
Nodes to be stored within a Graph.
Definition: Graph.h:170
IBEX::IBEX::ResetNodeCount
void ResetNodeCount()
Definition: IBEX.h:52
IBEX::IBEX::exponentialGrowth
bool exponentialGrowth
Definition: IBEX.h:98
IBEX::BFHSCompare
Definition: IBEX.h:28
Generated by   doxygen 1.8.17