HOG2
PDBHeuristic.h
Go to the documentation of this file.
1 //
2 // PDBHeuristic.h
3 // hog2 glut
4 //
5 // Created by Nathan Sturtevant on 8/19/15.
6 // Copyright (c) 2015 University of Denver. All rights reserved.
7 //
8 
9 #ifndef hog2_glut_PDBHeuristic_h
10 #define hog2_glut_PDBHeuristic_h
11 
12 #include <cassert>
13 #include <thread>
14 #include <string>
15 #include <cinttypes>
16 
17 #include "Heuristic.h"
18 #include "SharedQueue.h"
19 #include "NBitArray.h"
20 #include "Timer.h"
21 #include "RangeCompression.h"
22 
23 enum PDBLookupType {
24  kPlain,
25  kDivCompress,
26 // kFractionalCompress,
27 // kFractionalModCompress,
28  kModCompress,
29  kValueCompress,
30  kDivPlusValueCompress,
31  kDivPlusDeltaCompress, // two lookups with the same index, one is div, one is delta
32  kDefaultHeuristic
33 };
34 
35 const int coarseSize = 1024;
36 const int maxThreads = 32; // TODO: This isn't enforced in a static assert
37 
38 template <class abstractState, class abstractAction, class abstractEnvironment, class state = abstractState, uint64_t pdbBits = 8>
39 class PDBHeuristic : public Heuristic<state> {
40 public:
41  PDBHeuristic(abstractEnvironment *e) :type(kPlain), env(e)
42  { goalSet = false; }
43  virtual ~PDBHeuristic() {}
44 
45  void SetGoal(const state &goal)
46  {
47  goalState.resize(1);
48  GetStateFromPDBHash(this->GetAbstractHash(goal), goalState[0]);
49  goalSet = true;
50  }
51 
52  void SetGoal(const std::vector<state> &goals)
53  {
54  goalState.resize(0);
55  for (auto &i : goals)
56  {
57  goalState.resize(goalState.size()+1);
58  GetStateFromPDBHash(this->GetAbstractHash(i), goalState[goalState.size()-1]);
59  }
60  goalSet = true;
61  }
62 
63 
64  virtual double HCost(const state &a, const state &b) const;
65 
66  virtual uint64_t GetPDBSize() const = 0;
67 
68  virtual uint64_t GetPDBHash(const abstractState &s, int threadID = 0) const = 0;
69  virtual uint64_t GetAbstractHash(const state &s, int threadID = 0) const = 0;
70  virtual void GetStateFromPDBHash(uint64_t hash, abstractState &s, int threadID = 0) const = 0;
71  virtual state GetStateFromAbstractState(abstractState &s) const = 0;
72 
73  virtual bool Load(const char *prefix) = 0;
74  virtual void Save(const char *prefix) = 0;
75  virtual bool Load(FILE *f);
76  virtual void Save(FILE *f);
77  virtual std::string GetFileName(const char *prefix) = 0;
78 
80  void ShuffleValues();
81  void BuildPDB(const state &goal);
82  void BuildPDB(const state &goal, int numThreads)
83  { BuildPDBForwardBackward(goal, numThreads); }
84  void BuildPDBForward(const state &goal, int numThreads, bool useCoarseOpen = true, bool verbose = false);
85  void BuildPDBForward(const std::vector<state> &goal, int numThreads, bool useCoarseOpen = true, bool verbose = false);
86  void BuildPDBBackward(const state &goal, int numThreads);
87  void BuildPDBForwardBackward(const state &goal, int numThreads);
88 
89  void BuildAdditivePDB(const state &goal, int numThreads, bool useCourseOpen = true);
90 
91  void DivCompress(int factor, bool print_histogram);
92  void ModCompress(int factor, bool print_histogram);
93  void ModCompress(uint64_t newEntries, bool print_histogram);
94  void ZeroLowValues(int limit)
95  { for (uint64_t s = 0; s < PDB.Size(); s++)
96  if (PDB.Get(s) < limit) PDB.Set(s, 0); }
97 
98  void DeltaCompress(Heuristic<state> *h, state goal, bool print_histogram);
99 
100  void FractionalDivCompress(uint64_t count, bool print_histogram);
101  void FractionalModCompress(uint64_t factor, bool print_histogram);
102  void ValueCompress(int maxValue, bool print_histogram);
103  void ValueCompress(std::vector<int> cutoffs, bool print_histogram);
104  void ValueRangeCompress(int numBits, bool print_histogram);
105  void CustomValueRangeCompress(std::vector<uint64_t> dist, int numBits, bool print_histogram);
106 
107  void ValueRangeCompress(PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, 5> *, bool print_histogram);
108  void ValueRangeCompress(PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, 4> *, bool print_histogram);
109  void ValueRangeCompress(PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, 3> *, bool print_histogram);
110  void ValueRangeCompress(PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, 2> *, bool print_histogram);
111  void ValueRangeCompress(PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, 1> *, bool print_histogram);
112 
113  double PrintHistogram();
114  double GetAverageValue();
115  void GetHistogram(std::vector<uint64_t> &histogram);
116 //protected:
117 // friend class PDBHeuristic<abstractState, abstractAction, abstractEnvironment, abstractState, 4>;
118 // friend class PDBHeuristic<abstractState, abstractAction, abstractEnvironment, abstractState, 3>;
119 // friend class PDBHeuristic<abstractState, abstractAction, abstractEnvironment, abstractState, 2>;
120 // friend class PDBHeuristic<abstractState, abstractAction, abstractEnvironment, abstractState, 1>;
121 
122  // holds a Pattern Databases
123  NBitArray<pdbBits> PDB;
124  int vrcValues[1<<pdbBits];
125  PDBLookupType type;
126  uint64_t compressionValue;
127 
128  abstractEnvironment *env;
129  std::vector<abstractState> goalState;
130 private:
131  bool goalSet;
132  void AdditiveForwardThreadWorker(int threadNum, int depth,
133  NBitArray<pdbBits> &DB,
134  std::vector<bool> &coarse,
135  SharedQueue<std::pair<uint64_t, uint64_t> > *work,
136  SharedQueue<uint64_t> *results,
137  std::mutex *lock);
138  void GetAdditiveNeighbors(const abstractState &s,
139  std::vector<std::pair<abstractState, int>> &neighbors);
140 
141  void ForwardThreadWorker(int threadNum, int depth,
142  NBitArray<pdbBits> &DB,
143  std::vector<bool> &coarse,
144  SharedQueue<std::pair<uint64_t, uint64_t> > *work,
145  SharedQueue<uint64_t> *results,
146  std::mutex *lock);
147  void BackwardThreadWorker(int threadNum, int depth,
148  NBitArray<pdbBits> &DB,
149  std::vector<bool> &coarse,
150  SharedQueue<std::pair<uint64_t, uint64_t> > *work,
151  SharedQueue<uint64_t> *results,
152  std::mutex *lock);
153  void ForwardBackwardThreadWorker(int threadNum, int depth, bool forward,
154  NBitArray<pdbBits> &DB,
155  std::vector<bool> &coarseOpen,
156  std::vector<bool> &coarseClosed,
157  SharedQueue<std::pair<uint64_t, uint64_t> > *work,
158  SharedQueue<uint64_t> *results,
159  std::mutex *lock);
160 };
161 
162 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
163 double PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::HCost(const state &a, const state &b) const
164 {
165  switch (type)
166  {
167  case kPlain:
168  {
169  return PDB.Get(GetAbstractHash(a)); //PDB[GetPDBHash(a)];
170  }
171  case kDivCompress:
172  {
173  return PDB.Get(GetAbstractHash(a)/compressionValue);
174  }
175  case kModCompress:
176  {
177  return PDB.Get(GetAbstractHash(a)%compressionValue);
178  }
179  case kValueCompress:
180  {
181  return vrcValues[PDB.Get(GetAbstractHash(a))]; //PDB[GetPDBHash(a)];
182  }
183  case kDivPlusValueCompress:
184  {
185  return vrcValues[PDB.Get(GetAbstractHash(a)/compressionValue)];
186  }
187  default:
188  assert(!"Not implemented");
189  }
190 }
191 
192 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
193 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::BuildPDB(const state &goal)
194 {
195  assert(goalSet);
196 
197  uint64_t COUNT = GetPDBSize();
198  PDB.Resize(COUNT);
199  PDB.FillMax();
200 
201  uint64_t entries = goalState.size();
202  std::cout << "Num Entries: " << COUNT << std::endl;
203  std::cout << "Goal State: " << goalState[0] << std::endl;
204  //std::cout << "State Hash of Goal: " << GetStateHash(goal) << std::endl;
205  std::cout << "PDB Hash of Goal: " << GetPDBHash(goalState[0]) << std::endl;
206 
207  std::vector<abstractAction> acts;
208 
209  Timer t;
210  t.StartTimer();
211  for (auto &i : goalState)
212  PDB.Set(GetPDBHash(i), 0);
213 
214  int depth = 0;
215  uint64_t newEntries = 0;
216  abstractState s(goal), u(goal);
217  do {
218  Timer timer;
219  timer.StartTimer();
220  uint64_t total = 0;
221  for (uint64_t i = 0; i < COUNT; i++)
222  {
223  if (PDB.Get(i) == depth)
224  {
225  GetStateFromPDBHash(i, s);
226  env->GetActions(s, acts);
227  for (size_t y = 0; y < acts.size(); y++)
228  {
229  env->GetNextState(s, acts[y], u);
230  assert(env->InvertAction(acts[y]) == true);
231 
232  uint64_t nextRank = GetPDBHash(u);
233  int newCost = depth+(env->GCost(u, acts[y]));
234  if (PDB.Get(nextRank) > newCost)
235  {
236  PDB.Set(nextRank, newCost);
237  total++;
238  }
239  }
240  }
241  }
242 
243  entries += total;//newEntries;
244  printf("Depth %d complete; %1.2fs elapsed. %" PRId64 " new states written; %" PRId64 " of %" PRId64 " total\n",
245  depth, timer.EndTimer(), total, entries, COUNT);
246  depth++;
247  } while (entries != COUNT);
248 
249  printf("%1.2fs elapsed\n", t.EndTimer());
250  if (entries != COUNT)
251  {
252  printf("Entries: %" PRId64 "; count: %" PRId64 "\n", entries, COUNT);
253  assert(entries == COUNT);
254  }
255  PrintHistogram();
256 }
257 
258 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
259 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::BuildPDBForward(const state &goal, int numThreads, bool useCoarseOpen, bool verbose)
260 {
261  std::vector<state> tmp;
262  tmp.push_back(goal);
263  BuildPDBForward(tmp, numThreads, useCoarseOpen, verbose);
264 }
265 
266 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
267 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::BuildPDBForward(const std::vector<state> &goal, int numThreads, bool useCoarseOpen, bool verbose)
268 {
269  assert(goalSet);
270  SharedQueue<std::pair<uint64_t, uint64_t> > workQueue(numThreads*20);
271  SharedQueue<uint64_t> resultQueue;
272  std::mutex lock;
273 
274  uint64_t COUNT = GetPDBSize();
275  PDB.Resize(COUNT);
276  PDB.FillMax();
277 
278  // with weights we have to store the lowest weight stored to make sure
279  // we don't skip regions
280  std::vector<bool> coarseOpenCurr((COUNT+coarseSize-1)/coarseSize);
281  std::vector<bool> coarseOpenNext((COUNT+coarseSize-1)/coarseSize);
282 
283  uint64_t entries = goalState.size();
284  std::cout << "Num Entries: " << COUNT << std::endl;
285  std::cout << "Goal State: " << goalState[0] << std::endl;
286  //std::cout << "State Hash of Goal: " << GetStateHash(goal) << std::endl;
287  std::cout << "PDB Hash of Goal: " << GetPDBHash(goalState[0]) << std::endl;
288 
289  std::deque<state> q_curr, q_next;
290  std::vector<state> children;
291 
292  Timer t;
293  t.StartTimer();
294  for (auto &i : goalState)
295  {
296  PDB.Set(GetPDBHash(i), 0);
297  coarseOpenCurr[GetPDBHash(i)/coarseSize] = true;
298  }
299 
300  int depth = 0;
301  uint64_t newEntries;
302  std::vector<std::thread*> threads(numThreads);
303  printf("Creating %d threads\n", numThreads);
304  do {
305  newEntries = 0;
306  Timer s;
307  s.StartTimer();
308 
309  // TODO: clean up interface
310  if (!useCoarseOpen)
311  {
312  uint64_t smallestDepth = (1<<pdbBits)-1;
313  for (uint64_t x = 0; x < COUNT; x++)
314  {
315  uint64_t next = PDB.Get(x);
316  if (next >= depth && next < smallestDepth)
317  smallestDepth = next;
318  }
319  depth = smallestDepth;
320  }
321 
322  for (int x = 0; x < numThreads; x++)
323  {
324  threads[x] = new std::thread(&PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::ForwardThreadWorker,
325  this,
326  x, depth, std::ref(PDB), std::ref(coarseOpenNext),
327  &workQueue, &resultQueue, &lock);
328  }
329 
330  for (uint64_t x = 0; x < COUNT; x+=coarseSize)
331  {
332  if ((useCoarseOpen && coarseOpenCurr[x/coarseSize]) || !useCoarseOpen)
333  {
334  workQueue.WaitAdd({x, std::min(COUNT, x+coarseSize)});
335  }
336  coarseOpenCurr[x/coarseSize] = false;
337  }
338  for (int x = 0; x < numThreads; x++)
339  {
340  workQueue.WaitAdd({0,0});
341  }
342  for (int x = 0; x < numThreads; x++)
343  {
344  threads[x]->join();
345  delete threads[x];
346  threads[x] = 0;
347  }
348  // read out node counts
349  uint64_t total = 0;
350  {
351  uint64_t val;
352  while (resultQueue.Remove(val))
353  {
354  total+=val;
355  }
356  }
357 
358  entries += total;//newEntries;
359  if (verbose)
360  printf("Depth %d complete; %1.2fs elapsed. %" PRId64 " new states written; %" PRId64 " of %" PRId64 " total\n",
361  depth, s.EndTimer(), total, entries, COUNT);
362  depth++;
363  coarseOpenCurr.swap(coarseOpenNext);
364  } while (entries != COUNT);
365 
366  if (verbose)
367  printf("%1.2fs elapsed\n", t.EndTimer());
368  if (entries != COUNT)
369  {
370  if (verbose)
371  printf("Entries: %" PRId64 "; count: %" PRId64 "\n", entries, COUNT);
372  assert(entries == COUNT);
373  }
374  if (verbose)
375  PrintHistogram();
376 }
377 
378 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
379 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::BuildPDBBackward(const state &goal, int numThreads)
380 {
381  assert(goalSet);
382  SharedQueue<std::pair<uint64_t, uint64_t> > workQueue(numThreads*20);
383  SharedQueue<uint64_t> resultQueue;
384  std::mutex lock;
385 
386  uint64_t COUNT = GetPDBSize();
387  PDB.Resize(COUNT);
388  PDB.FillMax();
389 
390  // with weights we have to store the lowest weight stored to make sure
391  // we don't skip regions
392  std::vector<bool> coarseClosed((COUNT+coarseSize-1)/coarseSize);
393 
394  uint64_t entries = goalState.size();
395  std::cout << "Num Entries: " << COUNT << std::endl;
396  std::cout << "Goal State: " << goalState[0] << std::endl;
397  //std::cout << "State Hash of Goal: " << GetStateHash(goal) << std::endl;
398  std::cout << "PDB Hash of Goal: " << GetPDBHash(goalState[0]) << std::endl;
399 
400  std::deque<state> q_curr, q_next;
401  std::vector<state> children;
402 
403  Timer t;
404  t.StartTimer();
405  for (auto &i : goalState)
406  PDB.Set(GetPDBHash(i), 0);
407 
408  int depth = 0;
409  uint64_t newEntries;
410  std::vector<std::thread*> threads(numThreads);
411  printf("Creating %d threads\n", numThreads);
412  do {
413  newEntries = 0;
414  Timer s;
415  s.StartTimer();
416  for (int x = 0; x < numThreads; x++)
417  {
418  threads[x] = new std::thread(&PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::BackwardThreadWorker,
419  this,
420  x, depth, std::ref(PDB), std::ref(coarseClosed),
421  &workQueue, &resultQueue, &lock);
422  }
423  for (uint64_t x = 0; x < COUNT; x+=coarseSize)
424  {
425  if (coarseClosed[x/coarseSize] == false)
426  {
427  workQueue.WaitAdd({x, std::min(COUNT, x+coarseSize)});
428  }
429  }
430  for (int x = 0; x < numThreads; x++)
431  {
432  workQueue.WaitAdd({0,0});
433  }
434  for (int x = 0; x < numThreads; x++)
435  {
436  threads[x]->join();
437  delete threads[x];
438  threads[x] = 0;
439  }
440  // read out node counts
441  uint64_t total = 0;
442  {
443  uint64_t val;
444  while (resultQueue.Remove(val))
445  {
446  total+=val;
447  }
448  }
449 
450  entries += total;//newEntries;
451  printf("Depth %d complete; %1.2fs elapsed. %" PRId64 " new states written; %" PRId64 " of %" PRId64 " total\n",
452  depth, s.EndTimer(), total, entries, COUNT);
453  depth++;
454  } while (entries != COUNT);
455 
456  printf("%1.2fs elapsed\n", t.EndTimer());
457  if (entries != COUNT)
458  {
459  printf("Entries: %" PRId64 "; count: %" PRId64 "\n", entries, COUNT);
460  assert(entries == COUNT);
461  }
462  PrintHistogram();
463 }
464 
465 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
466 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::BuildPDBForwardBackward(const state &goal, int numThreads)
467 {
468  assert(goalSet);
469  SharedQueue<std::pair<uint64_t, uint64_t> > workQueue(numThreads*20);
470  SharedQueue<uint64_t> resultQueue;
471  std::mutex lock;
472 
473  uint64_t COUNT = GetPDBSize();
474  PDB.Resize(COUNT);
475  PDB.FillMax();
476 
477  // with weights we have to store the lowest weight stored to make sure
478  // we don't skip regions
479  std::vector<bool> coarseClosed((COUNT+coarseSize-1)/coarseSize);
480  std::vector<bool> coarseOpenCurr((COUNT+coarseSize-1)/coarseSize);
481  std::vector<bool> coarseOpenNext((COUNT+coarseSize-1)/coarseSize);
482 
483  uint64_t entries = goalState.size();
484  std::cout << "Num Entries: " << COUNT << std::endl;
485  std::cout << "Goal State: " << goalState[0] << std::endl;
486  //std::cout << "State Hash of Goal: " << GetStateHash(goal) << std::endl;
487  std::cout << "PDB Hash of Goal: " << GetPDBHash(goalState[0]) << std::endl;
488 
489  std::deque<state> q_curr, q_next;
490  std::vector<state> children;
491  std::vector<uint64_t> distribution;
492 
493  Timer t;
494  t.StartTimer();
495  int cnt = 0;
496  for (auto &i : goalState)
497  {
498  PDB.Set(GetPDBHash(i), 0);
499  coarseOpenCurr[GetPDBHash(i)/coarseSize] = true;
500  cnt++;
501  }
502  distribution.push_back(cnt);
503 
504  int depth = 0;
505  bool searchForward = true;
506  std::vector<std::thread*> threads(numThreads);
507  printf("Creating %d threads\n", numThreads);
508  do {
509  Timer s;
510  s.StartTimer();
511  for (int x = 0; x < numThreads; x++)
512  {
513  threads[x] = new std::thread(&PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::ForwardBackwardThreadWorker,
514  this,
515  x, depth, searchForward,
516  std::ref(PDB), std::ref(coarseOpenNext), std::ref(coarseClosed),
517  &workQueue, &resultQueue, &lock);
518  }
519  if (searchForward)
520  {
521  for (uint64_t x = 0; x < COUNT; x+=coarseSize)
522  {
523  if (coarseOpenCurr[x/coarseSize])
524  {
525  workQueue.WaitAdd({x, std::min(COUNT, x+coarseSize)});
526  }
527  coarseOpenCurr[x/coarseSize] = false;
528  }
529  }
530  else {
531  for (uint64_t x = 0; x < COUNT; x+=coarseSize)
532  {
533  if (coarseClosed[x/coarseSize] == false)
534  {
535  workQueue.WaitAdd({x, std::min(COUNT, x+coarseSize)});
536  }
537  }
538  }
539 
540  for (int x = 0; x < numThreads; x++)
541  {
542  workQueue.WaitAdd({0,0});
543  }
544  for (int x = 0; x < numThreads; x++)
545  {
546  threads[x]->join();
547  delete threads[x];
548  threads[x] = 0;
549  }
550  // read out node counts
551  uint64_t total = 0;
552  {
553  uint64_t val;
554  while (resultQueue.Remove(val))
555  {
556  total+=val;
557  }
558  }
559  entries += total;//newEntries;
560  distribution.push_back(total);
561  printf("Depth %d complete; %1.2fs elapsed. %" PRId64 " new states written; %" PRId64 " of %" PRId64 " total [%s]\n",
562  depth, s.EndTimer(), total, entries, COUNT, searchForward?"forward":"backward");
563  if (double(total)*double(total)*0.4 > double(COUNT-entries)*double(distribution[distribution.size()-2]))// || depth == 8)
564  searchForward = false;
565  if (COUNT-entries <= total) // If we wrote more entries than there are left, switch directions
566  searchForward = false;
567  depth++;
568  coarseOpenCurr.swap(coarseOpenNext);
569  } while (entries != COUNT);
570 
571  printf("%1.2fs elapsed\n", t.EndTimer());
572  if (entries != COUNT)
573  {
574  printf("Entries: %" PRId64 "; count: %" PRId64 "\n", entries, COUNT);
575  assert(entries == COUNT);
576  }
577  PrintHistogram();
578 }
579 
580 
581 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
582 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::ForwardThreadWorker(int threadNum, int depth,
583  NBitArray<pdbBits> &DB,
584  std::vector<bool> &coarse,
585  SharedQueue<std::pair<uint64_t, uint64_t> > *work,
586  SharedQueue<uint64_t> *results,
587  std::mutex *lock)
588 {
589 // lock->lock();
590 // printf("Thread %d online\n", threadNum);
591 // lock->unlock();
592 
593  std::pair<uint64_t, uint64_t> p;
594  uint64_t start, end;
595  std::vector<abstractAction> acts;
596  abstractState s(goalState[0]), t(goalState[0]);
597  uint64_t count = 0;
598 
599  struct writeInfo {
600  uint64_t rank;
601  int newGCost;
602  };
603  std::vector<writeInfo> cache;
604  while (true)
605  {
606  work->WaitRemove(p);
607  if (p.first == p.second)
608  {
609  break;
610  }
611  start = p.first;
612  end = p.second;
613  //int nextDepth = 255;
614  for (uint64_t x = start; x < end; x++)
615  {
616  int stateDepth = DB.Get(x);
617  if (stateDepth == depth)
618  {
619  GetStateFromPDBHash(x, s, threadNum);
620  //std::cout << "Expanding[r][" << stateDepth << "]: " << s << std::endl;
621  env->GetActions(s, acts);
622  for (int y = 0; y < acts.size(); y++)
623  {
624  env->GetNextState(s, acts[y], t);
625  assert(env->InvertAction(acts[y]) == true);
626  //virtual bool InvertAction(action &a) const = 0;
627 
628  uint64_t nextRank = GetPDBHash(t, threadNum);
629  int newCost = stateDepth+(env->GCost(t, acts[y]));
630  cache.push_back({nextRank, newCost});
631  }
632  }
633  }
634  // write out everything
635  lock->lock();
636  for (auto d : cache)
637  {
638  if (d.newGCost < DB.Get(d.rank)) // shorter path
639  {
640  if (DB.Get(d.rank) == (1<<pdbBits)-1)
641  count++;
642  coarse[d.rank/coarseSize] = true;
643  DB.Set(d.rank, d.newGCost);
644  }
645  }
646  lock->unlock();
647  cache.resize(0);
648  }
649  results->Add(count);
650 // lock->lock();
651 // printf("Thread %d offline\n", threadNum);
652 // lock->unlock();
653 }
654 
655 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
656 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::BackwardThreadWorker(int threadNum, int depth,
657  NBitArray<pdbBits> &DB,
658  std::vector<bool> &coarse,
659  SharedQueue<std::pair<uint64_t, uint64_t> > *work,
660  SharedQueue<uint64_t> *results,
661  std::mutex *lock)
662 {
663  std::pair<uint64_t, uint64_t> p;
664  uint64_t start, end;
665  std::vector<abstractAction> acts;
666  abstractState s(goalState[0]), t(goalState[0]);
667  uint64_t count = 0;
668  int blankEntries = 0;
669  struct writeInfo {
670  uint64_t rank;
671  int newGCost;
672  };
673  std::vector<writeInfo> cache;
674  while (true)
675  {
676  work->WaitRemove(p);
677  if (p.first == p.second)
678  {
679  break;
680  }
681  start = p.first;
682  end = p.second;
683  //int nextDepth = 255;
684  blankEntries = 0;
685  for (uint64_t x = start; x < end; x++)
686  {
687  int stateDepth = DB.Get(x);
688  if (stateDepth == ((1<<pdbBits)-1))//depth) // pdbBits
689  {
690  blankEntries++;
691  GetStateFromPDBHash(x, s, threadNum);
692  //std::cout << "Expanding[r][" << stateDepth << "]: " << s << std::endl;
693  env->GetActions(s, acts);
694  for (int y = 0; y < acts.size(); y++)
695  {
696  env->GetNextState(s, acts[y], t);
697  //assert(env->InvertAction(acts[y]) == true);
698  //virtual bool InvertAction(action &a) const = 0;
699 
700  uint64_t nextRank = GetPDBHash(t, threadNum);
701  if (DB.Get(nextRank) == depth)
702  {
703  int newCost = depth+(env->GCost(t, acts[y]));
704  cache.push_back({x, newCost});
705  blankEntries--;
706  break;
707  }
708  }
709  }
710  }
711  // write out everything
712  if (cache.size() > 0)
713  {
714  //printf("%d items to write\n", cache.size());
715  lock->lock();
716  if (blankEntries == 0)
717  coarse[start/coarseSize] = true; // closed
718  for (auto d : cache)
719  {
720  if (d.newGCost < DB.Get(d.rank)) // shorter path
721  {
722  count++;
723  DB.Set(d.rank, d.newGCost);
724  }
725  }
726  lock->unlock();
727  }
728  cache.resize(0);
729  }
730  results->Add(count);
731 }
732 
733 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
734 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::ForwardBackwardThreadWorker(int threadNum, int depth, bool forward,
735  NBitArray<pdbBits> &DB,
736  std::vector<bool> &coarseOpen,
737  std::vector<bool> &coarseClosed,
738  SharedQueue<std::pair<uint64_t, uint64_t> > *work,
739  SharedQueue<uint64_t> *results,
740  std::mutex *lock)
741 {
742  std::pair<uint64_t, uint64_t> p;
743  uint64_t start, end;
744  std::vector<abstractAction> acts;
745  abstractState s(goalState[0]), t(goalState[0]);
746  uint64_t count = 0;
747  int blankEntries = 0;
748  struct writeInfo {
749  uint64_t rank;
750  int newGCost;
751  };
752  std::vector<writeInfo> cache;
753  if (forward)
754  {
755  bool allEntriesWritten;
756  while (true)
757  {
758  work->WaitRemove(p);
759  if (p.first == p.second)
760  {
761  break;
762  }
763  start = p.first;
764  end = p.second;
765 
766  allEntriesWritten = true;
767  for (uint64_t x = start; x < end; x++)
768  {
769  int stateDepth = DB.Get(x);
770  if (stateDepth > depth)
771  allEntriesWritten = false;
772  if (stateDepth == depth)
773  {
774  GetStateFromPDBHash(x, s, threadNum);
775  //std::cout << "Expanding[r][" << stateDepth << "]: " << s << std::endl;
776  env->GetActions(s, acts);
777  for (size_t y = 0; y < acts.size(); y++)
778  {
779  env->GetNextState(s, acts[y], t);
780  assert(env->InvertAction(acts[y]) == true);
781  //virtual bool InvertAction(action &a) const = 0;
782 
783  uint64_t nextRank = GetPDBHash(t, threadNum);
784  int newCost = stateDepth+(env->GCost(t, acts[y]));
785  cache.push_back({nextRank, newCost});
786  }
787  }
788  }
789  // write out everything
790  lock->lock();
791  if (allEntriesWritten)
792  coarseClosed[start/coarseSize] = true;
793  for (auto d : cache)
794  {
795  if (d.newGCost < DB.Get(d.rank)) // shorter path
796  {
797  count++;
798  coarseOpen[d.rank/coarseSize] = true;
799  DB.Set(d.rank, d.newGCost);
800  }
801  }
802  lock->unlock();
803  cache.resize(0);
804  }
805  }
806  else {
807  while (true)
808  {
809  work->WaitRemove(p);
810  if (p.first == p.second)
811  {
812  break;
813  }
814  start = p.first;
815  end = p.second;
816  //int nextDepth = 255;
817  blankEntries = 0;
818  for (uint64_t x = start; x < end; x++)
819  {
820  int stateDepth = DB.Get(x);
821  if (stateDepth == ((1<<pdbBits)-1))//depth) // pdbBits
822  {
823  blankEntries++;
824  GetStateFromPDBHash(x, s, threadNum);
825  //std::cout << "Expanding[r][" << stateDepth << "]: " << s << std::endl;
826  env->GetActions(s, acts);
827  for (size_t y = 0; y < acts.size(); y++)
828  {
829  env->GetNextState(s, acts[y], t);
830  //assert(env->InvertAction(acts[y]) == true);
831  //virtual bool InvertAction(action &a) const = 0;
832 
833  uint64_t nextRank = GetPDBHash(t, threadNum);
834  if (DB.Get(nextRank) == depth)
835  {
836  int newCost = depth+(env->GCost(t, acts[y]));
837  cache.push_back({x, newCost});
838  blankEntries--;
839  break;
840  }
841  }
842  }
843  }
844  // write out everything
845  if (cache.size() > 0)
846  {
847  //printf("%d items to write\n", cache.size());
848  lock->lock();
849  if (blankEntries == 0)
850  coarseClosed[start/coarseSize] = true; // closed
851  for (auto d : cache)
852  {
853  if (d.newGCost < DB.Get(d.rank)) // shorter path
854  {
855  count++;
856  DB.Set(d.rank, d.newGCost);
857  }
858  }
859  lock->unlock();
860  }
861  cache.resize(0);
862  }
863  }
864  results->Add(count);
865 }
866 
867 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
868 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::BuildAdditivePDB(const state &goal, int numThreads, bool useCourseOpen)
869 {
870  assert(goalSet);
871  SharedQueue<std::pair<uint64_t, uint64_t> > workQueue(numThreads*20);
872  SharedQueue<uint64_t> resultQueue;
873  std::mutex lock;
874 
875  uint64_t COUNT = GetPDBSize();
876  PDB.Resize(COUNT);
877  PDB.FillMax();
878 
879  // with weights we have to store the lowest weight stored to make sure
880  // we don't skip regions
881  std::vector<bool> coarseOpenCurr((COUNT+coarseSize-1)/coarseSize);
882  std::vector<bool> coarseOpenNext((COUNT+coarseSize-1)/coarseSize);
883 
884  uint64_t entries = goalState.size();
885  std::cout << "Num Entries: " << COUNT << std::endl;
886  std::cout << "Goal State: " << goalState[0] << std::endl;
887  //std::cout << "State Hash of Goal: " << GetStateHash(goal) << std::endl;
888  std::cout << "PDB Hash of Goal: " << GetPDBHash(goalState[0]) << std::endl;
889 
890  std::deque<state> q_curr, q_next;
891  std::vector<state> children;
892 
893  Timer t;
894  t.StartTimer();
895  for (auto &i : goalState)
896  {
897  PDB.Set(GetPDBHash(i), 0);
898  coarseOpenCurr[GetPDBHash(i)/coarseSize] = true;
899  }
900  int depth = 0;
901  uint64_t newEntries;
902  std::vector<std::thread*> threads(numThreads);
903  printf("Creating %d threads\n", numThreads);
904  do {
905  newEntries = 0;
906  Timer s;
907  s.StartTimer();
908  for (int x = 0; x < numThreads; x++)
909  {
910  threads[x] = new std::thread(&PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::AdditiveForwardThreadWorker,
911  this,
912  x, depth, std::ref(PDB), std::ref(coarseOpenNext),
913  &workQueue, &resultQueue, &lock);
914  }
915 
916  for (uint64_t x = 0; x < COUNT; x+=coarseSize)
917  {
918  if (!useCourseOpen || coarseOpenCurr[x/coarseSize])
919  {
920  workQueue.WaitAdd({x, std::min(COUNT, x+coarseSize)});
921  }
922  coarseOpenCurr[x/coarseSize] = false;
923  }
924  for (int x = 0; x < numThreads; x++)
925  {
926  workQueue.WaitAdd({0,0});
927  }
928  for (int x = 0; x < numThreads; x++)
929  {
930  threads[x]->join();
931  delete threads[x];
932  threads[x] = 0;
933  }
934  // read out node counts
935  uint64_t total = 0;
936  {
937  uint64_t val;
938  while (resultQueue.Remove(val))
939  {
940  total+=val;
941  }
942  }
943 
944  entries += total;//newEntries;
945  printf("Depth %d complete; %1.2fs elapsed. %" PRId64 " new states written; %" PRId64 " of %" PRId64 " total\n",
946  depth, s.EndTimer(), total, entries, COUNT);
947  depth++;
948  coarseOpenCurr.swap(coarseOpenNext);
949 
950 // if (total == 0)
951 // {
952 // for (int x = 0; x < PDB.Size(); x++)
953 // {
954 // if (PDB.Get(x) == PDB.GetMaxValue())
955 // {
956 // abstractState s(goalState[0]);
957 // GetStateFromPDBHash(x, s, 0);
958 // std::cout << "Unassigned: [" << x << "]: " << s << "\n";
959 // }
960 // }
961 // break;
962 // }
963  } while (entries != COUNT);
964 
965  printf("%1.2fs elapsed\n", t.EndTimer());
966  if (entries != COUNT)
967  {
968  printf("Entries: %" PRId64 "; count: %" PRId64 "\n", entries, COUNT);
969  assert(entries == COUNT);
970  }
971  PrintHistogram();
972 }
973 
974 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
975 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::AdditiveForwardThreadWorker(int threadNum, int depth,
976  NBitArray<pdbBits> &DB,
977  std::vector<bool> &coarse,
978  SharedQueue<std::pair<uint64_t, uint64_t> > *work,
979  SharedQueue<uint64_t> *results,
980  std::mutex *lock)
981 {
982  std::pair<uint64_t, uint64_t> p;
983  uint64_t start, end;
984  std::vector<abstractAction> acts;
985  std::vector<std::pair<abstractState, int>> neighbors;
986  abstractState s(goalState[0]), t(goalState[0]);
987  uint64_t count = 0;
988 
989  struct writeInfo {
990  uint64_t rank;
991  int newGCost;
992  };
993  std::vector<writeInfo> cache;
994  std::vector<uint64_t> zeroCostNeighbors;
995  while (true)
996  {
997  work->WaitRemove(p);
998  if (p.first == p.second)
999  {
1000  break;
1001  }
1002  start = p.first;
1003  end = p.second;
1004  for (uint64_t x = start; x < end; x++)
1005  {
1006  int stateDepth = DB.Get(x);
1007  if (stateDepth == depth)
1008  {
1009  GetStateFromPDBHash(x, s, threadNum);
1010  //std::cout << "Expanding[r][" << stateDepth << "]: " << s << std::endl;
1011  env->GetActions(s, acts);
1012 
1013  for (size_t y = 0; y < acts.size(); y++)
1014  {
1015  env->GetNextState(s, acts[y], t);
1016  assert(env->InvertAction(acts[y]) == true);
1017  //virtual bool InvertAction(action &a) const = 0;
1018 
1019  uint64_t nextRank = GetPDBHash(t, threadNum);
1020  int newCost = stateDepth+(env->AdditiveGCost(t, acts[y]));
1021  cache.push_back({nextRank, newCost});
1022  }
1023  }
1024  }
1025  // write out everything
1026  do {
1027  lock->lock();
1028  for (auto d : cache)
1029  {
1030  auto val = DB.Get(d.rank);
1031  if (d.newGCost < val) // shorter path
1032  {
1033  if (val == DB.GetMaxValue()) // only update count if the value hasn't been set before
1034  count++;
1035  coarse[d.rank/coarseSize] = true;
1036  DB.Set(d.rank, d.newGCost);
1037  if (d.newGCost == depth) // zero-cost action
1038  zeroCostNeighbors.push_back(d.rank);
1039  }
1040  }
1041  lock->unlock();
1042  cache.resize(0);
1043 
1044  for (auto i : zeroCostNeighbors)
1045  {
1046  GetStateFromPDBHash(i, s, threadNum);
1047  env->GetActions(s, acts);
1048 
1049  for (size_t y = 0; y < acts.size(); y++)
1050  {
1051  env->GetNextState(s, acts[y], t);
1052  assert(env->InvertAction(acts[y]) == true);
1053  //virtual bool InvertAction(action &a) const = 0;
1054 
1055  uint64_t nextRank = GetPDBHash(t, threadNum);
1056  int newCost = depth+(env->AdditiveGCost(t, acts[y]));
1057  cache.push_back({nextRank, newCost});
1058  }
1059 
1060  }
1061  zeroCostNeighbors.clear();
1062  } while (cache.size() > 0);
1063  }
1064  results->Add(count);
1065 }
1066 
1067 //template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1068 //void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::DivCompressHelper(NBitArray<pdbBits> &original,
1069 // NBitArray<pdbBits> &copy)
1070 //{
1071 //
1072 //}
1073 
1074 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1075 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::DivCompress(int factor, bool print_histogram)
1076 {
1077  if (type != kPlain)
1078  return;
1079  type = kDivCompress;
1080  compressionValue = factor;
1081  NBitArray<pdbBits> copy(PDB);
1082  PDB.Resize((PDB.Size()+compressionValue-1)/compressionValue);
1083  PDB.FillMax();
1084  for (uint64_t x = 0; x < copy.Size(); x++)
1085  {
1086  uint64_t newIndex = x/compressionValue;
1087  PDB.Set(newIndex, std::min(copy.Get(x), PDB.Get(newIndex)));
1088  }
1089  if (print_histogram)
1090  PrintHistogram();
1091 }
1092 
1093 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1094 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::ModCompress(int factor, bool print_histogram)
1095 {
1096  ModCompress((PDB.Size()+factor-1)/factor, print_histogram);
1097 }
1098 
1099 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1100 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::ModCompress(uint64_t newEntries, bool print_histogram)
1101 {
1102  type = kModCompress;
1103  compressionValue = newEntries;
1104  NBitArray<pdbBits> copy(PDB);
1105  PDB.Resize(compressionValue);
1106  PDB.FillMax();
1107  for (uint64_t x = 0; x < copy.Size(); x++)
1108  {
1109  uint64_t newIndex = x%compressionValue;
1110  PDB.Set(newIndex, std::min(copy.Get(x), PDB.Get(newIndex)));
1111  }
1112  if (print_histogram)
1113  PrintHistogram();
1114 }
1115 
1116 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1117 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::DeltaCompress(Heuristic<state> *h, state goal, bool print_histogram)
1118 {
1119  abstractState s;
1120  state s1;
1121  for (size_t x = 0; x < PDB.Size(); x++)
1122  {
1123  GetStateFromPDBHash(x, s);
1124  s1 = GetStateFromAbstractState(s);
1125  PDB.Set(x, PDB.Get(x) - h->HCost(s1, goal));
1126  }
1127  if (print_histogram)
1128  PrintHistogram();
1129 }
1130 
1131 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1132 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::FractionalDivCompress(uint64_t count, bool print_histogram)
1133 {
1134  assert(!"Not currently implemented.");
1135 }
1136 
1137 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1138 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::FractionalModCompress(uint64_t factor, bool print_histogram)
1139 {
1140  assert(!"Not currently implemented.");
1141 }
1142 
1143 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1144 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::ValueCompress(int maxValue, bool print_histogram)
1145 {
1146  assert(!"Not currently implemented.");
1147 }
1148 
1149 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1150 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::ValueCompress(std::vector<int> cutoffs, bool print_histogram)
1151 {
1152  std::vector<uint64_t> dist;
1153  if (print_histogram)
1154  {
1155  printf("Setting boundaries [%d values]: ", cutoffs.size());
1156  for (int x = 0; x < cutoffs.size(); x++)
1157  printf("%d ", cutoffs[x]);
1158  printf("\n");
1159  }
1160  cutoffs.push_back(256);
1161 
1162  for (uint64_t x = 0; x < PDB.Size(); x++)
1163  {
1164  for (int y = 0; y < cutoffs.size(); y++)
1165  {
1166  if (PDB.Get(x) >= cutoffs[y] && PDB.Get(x) < cutoffs[y+1])
1167  {
1168  //printf("%d -> %d\n", PDB[whichPDB][x], cutoffs[y]);
1169  PDB.Set(x, cutoffs[y]);
1170  break;
1171  }
1172  }
1173  }
1174  if (print_histogram)
1175  PrintHistogram();
1176 }
1177 
1178 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1179 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::CustomValueRangeCompress(std::vector<uint64_t> dist, int numBits, bool print_histogram)
1180 {
1181  std::vector<int> cutoffs;
1182  GetOptimizedBoundaries(dist, 1<<numBits, cutoffs);
1183  if (print_histogram)
1184  {
1185  printf("Setting boundaries [%d values]: ", (1<<numBits));
1186  for (size_t x = 0; x < cutoffs.size(); x++)
1187  printf("%d ", cutoffs[x]);
1188  printf("\n");
1189  }
1190  cutoffs.push_back(256);
1191 
1192  for (uint64_t x = 0; x < PDB.Size(); x++)
1193  {
1194  for (size_t y = 0; y < cutoffs.size(); y++)
1195  {
1196  if (PDB.Get(x) >= cutoffs[y] && PDB.Get(x) < cutoffs[y+1])
1197  {
1198  //printf("%d -> %d\n", PDB[whichPDB][x], cutoffs[y]);
1199  PDB.Set(x, cutoffs[y]);
1200  break;
1201  }
1202  }
1203  }
1204  if (print_histogram)
1205  PrintHistogram();
1206 }
1207 
1208 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1209 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::ValueRangeCompress(int numBits, bool print_histogram)
1210 {
1211  std::vector<uint64_t> dist;
1212  std::vector<int> cutoffs;
1213  GetHistogram(dist);
1214  GetOptimizedBoundaries(dist, 1<<numBits, cutoffs);
1215  if (print_histogram)
1216  {
1217  printf("Setting boundaries [%d values]: ", (1<<numBits));
1218  for (int x = 0; x < cutoffs.size(); x++)
1219  printf("%d ", cutoffs[x]);
1220  printf("\n");
1221  }
1222  cutoffs.push_back(256);
1223 
1224  for (uint64_t x = 0; x < PDB.Size(); x++)
1225  {
1226  for (int y = 0; y < cutoffs.size(); y++)
1227  {
1228  if (PDB.Get(x) >= cutoffs[y] && PDB.Get(x) < cutoffs[y+1])
1229  {
1230  //printf("%d -> %d\n", PDB[whichPDB][x], cutoffs[y]);
1231  PDB.Set(x, cutoffs[y]);
1232  break;
1233  }
1234  }
1235  }
1236  if (print_histogram)
1237  PrintHistogram();
1238 }
1239 
1240 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1241 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::ValueRangeCompress(
1242  PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, 5> *newPDB,
1243  bool print_histogram)
1244 {
1245  std::vector<uint64_t> dist;
1246  std::vector<int> cutoffs;
1247  GetHistogram(dist);
1248  GetOptimizedBoundaries(dist, 1<<5, cutoffs);
1249  if (print_histogram)
1250  {
1251  printf("Setting boundaries [%d values]: ", (1<<4));
1252  for (int x = 0; x < cutoffs.size(); x++)
1253  printf("%d ", cutoffs[x]);
1254  printf("\n");
1255  }
1256  if (type == kPlain)
1257  newPDB->type = kValueCompress;
1258  else if (type == kDivCompress)
1259  {
1260  newPDB->type = kDivPlusValueCompress;
1261  newPDB->compressionValue = compressionValue;
1262  }
1263  else {
1264  printf("Unknown PDB type: %d\n", type);
1265  }
1266  for (int x = 0; x < cutoffs.size(); x++)
1267  newPDB->vrcValues[x] = cutoffs[x];
1268  newPDB->PDB.Resize(PDB.Size());
1269  cutoffs.push_back(256);
1270  for (uint64_t x = 0; x < PDB.Size(); x++)
1271  {
1272  for (int y = 0; y < cutoffs.size(); y++)
1273  {
1274  if (PDB.Get(x) >= cutoffs[y] && PDB.Get(x) < cutoffs[y+1])
1275  {
1276  //printf("%d -> %d\n", PDB[whichPDB][x], cutoffs[y]);
1277  newPDB->PDB.Set(x, y);
1278  break;
1279  }
1280  }
1281  }
1282  if (print_histogram)
1283  newPDB->PrintHistogram();
1284 }
1285 
1286 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1287 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::ValueRangeCompress(
1288  PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, 4> *newPDB,
1289  bool print_histogram)
1290 {
1291  std::vector<uint64_t> dist;
1292  std::vector<int> cutoffs;
1293  GetHistogram(dist);
1294  GetOptimizedBoundaries(dist, 1<<4, cutoffs);
1295  if (print_histogram)
1296  {
1297  printf("Setting boundaries [%d values]: ", (1<<4));
1298  for (int x = 0; x < cutoffs.size(); x++)
1299  printf("%d ", cutoffs[x]);
1300  printf("\n");
1301  }
1302  if (type == kPlain)
1303  newPDB->type = kValueCompress;
1304  else if (type == kDivCompress)
1305  {
1306  newPDB->type = kDivPlusValueCompress;
1307  newPDB->compressionValue = compressionValue;
1308  }
1309  else {
1310  printf("Unknown PDB type: %d\n", type);
1311  }
1312  for (int x = 0; x < cutoffs.size(); x++)
1313  newPDB->vrcValues[x] = cutoffs[x];
1314  newPDB->PDB.Resize(PDB.Size());
1315  cutoffs.push_back(256);
1316  for (uint64_t x = 0; x < PDB.Size(); x++)
1317  {
1318  for (int y = 0; y < cutoffs.size(); y++)
1319  {
1320  if (PDB.Get(x) >= cutoffs[y] && PDB.Get(x) < cutoffs[y+1])
1321  {
1322  //printf("%d -> %d\n", PDB[whichPDB][x], cutoffs[y]);
1323  newPDB->PDB.Set(x, y);
1324  break;
1325  }
1326  }
1327  }
1328  if (print_histogram)
1329  newPDB->PrintHistogram();
1330 }
1331 
1332 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1333 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::ValueRangeCompress(PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, 3> *newPDB, bool print_histogram)
1334 {
1335  std::vector<uint64_t> dist;
1336  std::vector<int> cutoffs;
1337  GetHistogram(dist);
1338  GetOptimizedBoundaries(dist, 1<<3, cutoffs);
1339  if (print_histogram)
1340  {
1341  printf("Setting boundaries [%d values]: ", (1<<4));
1342  for (int x = 0; x < cutoffs.size(); x++)
1343  printf("%d ", cutoffs[x]);
1344  printf("\n");
1345  }
1346  if (type == kPlain)
1347  newPDB->type = kValueCompress;
1348  else if (type == kDivCompress)
1349  {
1350  newPDB->type = kDivPlusValueCompress;
1351  newPDB->compressionValue = compressionValue;
1352  }
1353  else {
1354  printf("Unknown PDB type: %d\n", type);
1355  }
1356 
1357  for (int x = 0; x < cutoffs.size(); x++)
1358  newPDB->vrcValues[x] = cutoffs[x];
1359  newPDB->PDB.Resize(PDB.Size());
1360  cutoffs.push_back(256);
1361  for (uint64_t x = 0; x < PDB.Size(); x++)
1362  {
1363  for (int y = 0; y < cutoffs.size(); y++)
1364  {
1365  if (PDB.Get(x) >= cutoffs[y] && PDB.Get(x) < cutoffs[y+1])
1366  {
1367  //printf("%d -> %d\n", PDB[whichPDB][x], cutoffs[y]);
1368  newPDB->PDB.Set(x, y);
1369  break;
1370  }
1371  }
1372  }
1373  if (print_histogram)
1374  newPDB->PrintHistogram();
1375 
1376 }
1377 
1378 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1379 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::ValueRangeCompress(PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, 2> *newPDB, bool print_histogram)
1380 {
1381  std::vector<uint64_t> dist;
1382  std::vector<int> cutoffs;
1383  GetHistogram(dist);
1384  GetOptimizedBoundaries(dist, 1<<2, cutoffs);
1385  if (print_histogram)
1386  {
1387  printf("Setting boundaries [%d values]: ", (1<<4));
1388  for (size_t x = 0; x < cutoffs.size(); x++)
1389  printf("%d ", cutoffs[x]);
1390  printf("\n");
1391  }
1392  if (type == kPlain)
1393  newPDB->type = kValueCompress;
1394  else if (type == kDivCompress)
1395  {
1396  newPDB->type = kDivPlusValueCompress;
1397  newPDB->compressionValue = compressionValue;
1398  }
1399  else {
1400  printf("Unknown PDB type: %d\n", type);
1401  }
1402 
1403  for (size_t x = 0; x < cutoffs.size(); x++)
1404  newPDB->vrcValues[x] = cutoffs[x];
1405  newPDB->PDB.Resize(PDB.Size());
1406  cutoffs.push_back(256);
1407  for (uint64_t x = 0; x < PDB.Size(); x++)
1408  {
1409  for (size_t y = 0; y < cutoffs.size(); y++)
1410  {
1411  if (PDB.Get(x) >= cutoffs[y] && PDB.Get(x) < cutoffs[y+1])
1412  {
1413  //printf("%d -> %d\n", PDB[whichPDB][x], cutoffs[y]);
1414  newPDB->PDB.Set(x, y);
1415  break;
1416  }
1417  }
1418  }
1419  if (print_histogram)
1420  newPDB->PrintHistogram();
1421 
1422 }
1423 
1424 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1425 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::ValueRangeCompress(PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, 1> *newPDB, bool print_histogram)
1426 {
1427  std::vector<uint64_t> dist;
1428  std::vector<int> cutoffs;
1429  GetHistogram(dist);
1430  GetOptimizedBoundaries(dist, 1<<1, cutoffs);
1431  if (print_histogram)
1432  {
1433  printf("Setting boundaries [%d values]: ", (1<<4));
1434  for (size_t x = 0; x < cutoffs.size(); x++)
1435  printf("%d ", cutoffs[x]);
1436  printf("\n");
1437  }
1438  if (type == kPlain)
1439  newPDB->type = kValueCompress;
1440  else if (type == kDivCompress)
1441  {
1442  newPDB->type = kDivPlusValueCompress;
1443  newPDB->compressionValue = compressionValue;
1444  }
1445  else {
1446  printf("Unknown PDB type: %d\n", type);
1447  }
1448 
1449  for (int x = 0; x < cutoffs.size(); x++)
1450  newPDB->vrcValues[x] = cutoffs[x];
1451  newPDB->PDB.Resize(PDB.Size());
1452  cutoffs.push_back(256);
1453  for (uint64_t x = 0; x < PDB.Size(); x++)
1454  {
1455  for (size_t y = 0; y < cutoffs.size(); y++)
1456  {
1457  if (PDB.Get(x) >= cutoffs[y] && PDB.Get(x) < cutoffs[y+1])
1458  {
1459  //printf("%d -> %d\n", PDB[whichPDB][x], cutoffs[y]);
1460  newPDB->PDB.Set(x, y);
1461  break;
1462  }
1463  }
1464  }
1465  if (print_histogram)
1466  newPDB->PrintHistogram();
1467 
1468 }
1469 
1470 
1471 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1472 bool PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::Load(FILE *f)
1473 {
1474  if (fread(&type, sizeof(type), 1, f) != 1)
1475  return false;
1476  goalState.resize(0);
1477  if (fread(&goalState[0], sizeof(goalState[0]), 1, f) != 1)
1478  return false;
1479  return PDB.Read(f);
1480 }
1481 
1482 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1483 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::Save(FILE *f)
1484 {
1485  fwrite(&type, sizeof(type), 1, f);
1486  fwrite(&goalState[0], sizeof(goalState[0]), 1, f);
1487  PDB.Write(f);
1488 }
1489 
1490 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1491 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::GetHistogram(std::vector<uint64_t> &histogram)
1492 {
1493  histogram.resize(0);
1494  for (uint64_t x = 0; x < PDB.Size(); x++)
1495  {
1496  if (PDB.Get(x)+1 > histogram.size())
1497  {
1498  histogram.resize(PDB.Get(x)+1);
1499  }
1500  histogram[PDB.Get(x)]++;
1501  }
1502 }
1503 
1504 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1505 double PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::PrintHistogram()
1506 {
1507  int factor = 1;
1508  if (type == kDivCompress || type == kDivPlusValueCompress)
1509  factor = compressionValue;
1510  double average = 0;
1511  std::vector<uint64_t> histogram;
1512  if (type == kValueCompress || type == kDivPlusValueCompress)
1513  {
1514  for (uint64_t x = 0; x < PDB.Size(); x++)
1515  {
1516  if (vrcValues[PDB.Get(x)]+1 > histogram.size())
1517  {
1518  histogram.resize(vrcValues[PDB.Get(x)]+1);
1519  }
1520  histogram[vrcValues[PDB.Get(x)]]+=factor;
1521  average += vrcValues[PDB.Get(x)];
1522  }
1523  }
1524  else {
1525  for (uint64_t x = 0; x < PDB.Size(); x++)
1526  {
1527  if (PDB.Get(x)+1 > histogram.size())
1528  {
1529  histogram.resize(PDB.Get(x)+1);
1530  }
1531  histogram[PDB.Get(x)]+=factor;
1532  average += PDB.Get(x);
1533  }
1534  }
1535  for (size_t x = 0; x < histogram.size(); x++)
1536  {
1537  if (histogram[x] > 0)
1538  printf("%d: %" PRId64 "\n", (int)x, histogram[x]);
1539  }
1540  printf("Average: %f; count: %" PRId64 "\n", average/PDB.Size(), PDB.Size());
1541  return average/PDB.Size();
1542 }
1543 
1544 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1545 double PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::GetAverageValue()
1546 {
1547  double average = 0;
1548  for (uint64_t x = 0; x < PDB.Size(); x++)
1549  {
1550  average += PDB.Get(x);
1551  }
1552  return average/PDB.Size();
1553 }
1554 
1555 template <class abstractState, class abstractAction, class abstractEnvironment, class state, uint64_t pdbBits>
1556 void PDBHeuristic<abstractState, abstractAction, abstractEnvironment, state, pdbBits>::ShuffleValues()
1557 {
1558  for (uint64_t x = PDB.Size(); x > 0; x--)
1559  {
1560  uint64_t index = (((uint64_t)random()<<32)^(uint64_t)random())%(x);
1561  uint64_t tmp = PDB.Get(x-1);
1562  PDB.Set(x-1, PDB.Get(index));
1563  PDB.Set(index, tmp);
1564  }
1565 }
1566 
1567 #endif
PDBHeuristic::~PDBHeuristic
virtual ~PDBHeuristic()
Definition: PDBHeuristic.h:43
PDBHeuristic::goalSet
bool goalSet
Definition: PDBHeuristic.h:131
PDBHeuristic::AdditiveForwardThreadWorker
void AdditiveForwardThreadWorker(int threadNum, int depth, NBitArray< pdbBits > &DB, std::vector< bool > &coarse, SharedQueue< std::pair< uint64_t, uint64_t > > *work, SharedQueue< uint64_t > *results, std::mutex *lock)
Definition: PDBHeuristic.h:975
PDBHeuristic::PDB
NBitArray< pdbBits > PDB
Definition: PDBHeuristic.h:123
PDBHeuristic::SetGoal
void SetGoal(const std::vector< state > &goals)
Definition: PDBHeuristic.h:52
NBitArray< pdbBits >
PDBHeuristic::DivCompress
void DivCompress(int factor, bool print_histogram)
Definition: PDBHeuristic.h:1075
PDBHeuristic::DeltaCompress
void DeltaCompress(Heuristic< state > *h, state goal, bool print_histogram)
Definition: PDBHeuristic.h:1117
PDBHeuristic::BuildPDBForward
void BuildPDBForward(const state &goal, int numThreads, bool useCoarseOpen=true, bool verbose=false)
Definition: PDBHeuristic.h:259
min
double min(double a, double b)
Definition: FPUtil.h:35
kDivCompress
@ kDivCompress
Definition: PDBHeuristic.h:25
PDBHeuristic::type
PDBLookupType type
Definition: PDBHeuristic.h:125
PDBHeuristic::GetPDBHash
virtual uint64_t GetPDBHash(const abstractState &s, int threadID=0) const =0
PDBHeuristic::BuildPDBBackward
void BuildPDBBackward(const state &goal, int numThreads)
Definition: PDBHeuristic.h:379
Heuristic
Definition: Heuristic.h:30
RangeCompression.h
d
mcData d[]
Definition: MotionCaptureMovement.cpp:21
Timer::StartTimer
void StartTimer()
Definition: Timer.cpp:9
Heuristic.h
kValueCompress
@ kValueCompress
Definition: PDBHeuristic.h:29
PDBHeuristic::BuildAdditivePDB
void BuildAdditivePDB(const state &goal, int numThreads, bool useCourseOpen=true)
Definition: PDBHeuristic.h:868
SharedQueue::WaitAdd
void WaitAdd(const T &value)
Definition: SharedQueue.h:103
NBitArray::Set
void Set(uint64_t index, uint64_t val)
Definition: NBitArray.h:224
PDBHeuristic::ModCompress
void ModCompress(int factor, bool print_histogram)
Definition: PDBHeuristic.h:1094
PDBHeuristic::PDBHeuristic
PDBHeuristic(abstractEnvironment *e)
Definition: PDBHeuristic.h:41
maxThreads
const int maxThreads
Definition: PDBHeuristic.h:36
PDBHeuristic::PrintHistogram
double PrintHistogram()
Definition: PDBHeuristic.h:1505
PDBHeuristic::goalState
std::vector< abstractState > goalState
Definition: PDBHeuristic.h:129
coarseSize
const int coarseSize
Definition: PDBHeuristic.h:35
Timer.h
PDBHeuristic::BuildPDB
void BuildPDB(const state &goal)
Definition: PDBHeuristic.h:193
PDBHeuristic::CustomValueRangeCompress
void CustomValueRangeCompress(std::vector< uint64_t > dist, int numBits, bool print_histogram)
Definition: PDBHeuristic.h:1179
kPlain
@ kPlain
Definition: PDBHeuristic.h:24
PDBHeuristic::FractionalDivCompress
void FractionalDivCompress(uint64_t count, bool print_histogram)
Definition: PDBHeuristic.h:1132
NBitArray::Resize
void Resize(uint64_t newMaxEntries)
Definition: NBitArray.h:135
PDBHeuristic::compressionValue
uint64_t compressionValue
Definition: PDBHeuristic.h:126
NBitArray::Get
uint64_t Get(uint64_t index) const
Definition: NBitArray.h:209
PDBHeuristic
Definition: PDBHeuristic.h:39
verbose
const static int verbose
Definition: ClusterAbstraction.cpp:81
NBitArray.h
PDBHeuristic::GetAdditiveNeighbors
void GetAdditiveNeighbors(const abstractState &s, std::vector< std::pair< abstractState, int >> &neighbors)
Heuristic::HCost
virtual double HCost(const state &a, const state &b) const
Definition: Heuristic.h:73
PDBHeuristic::Save
virtual void Save(const char *prefix)=0
PDBHeuristic::GetStateFromPDBHash
virtual void GetStateFromPDBHash(uint64_t hash, abstractState &s, int threadID=0) const =0
PDBHeuristic::env
abstractEnvironment * env
Definition: PDBHeuristic.h:128
PDBHeuristic::ShuffleValues
void ShuffleValues()
This methods randomizes the entries in the PDB.
Definition: PDBHeuristic.h:1556
GetOptimizedBoundaries
void GetOptimizedBoundaries(const vector< uint64_t > &distribution, int numValues, vector< int > &result)
Definition: RangeCompression.cpp:214
kDivPlusDeltaCompress
@ kDivPlusDeltaCompress
Definition: PDBHeuristic.h:31
PDBHeuristic::BuildPDBForwardBackward
void BuildPDBForwardBackward(const state &goal, int numThreads)
Definition: PDBHeuristic.h:466
PDBHeuristic::SetGoal
void SetGoal(const state &goal)
Definition: PDBHeuristic.h:45
PDBHeuristic::Load
virtual bool Load(const char *prefix)=0
Heuristic< abstractState >::histogram
uint64_t histogram[256]
Definition: Heuristic.h:37
PDBHeuristic::ForwardBackwardThreadWorker
void ForwardBackwardThreadWorker(int threadNum, int depth, bool forward, NBitArray< pdbBits > &DB, std::vector< bool > &coarseOpen, std::vector< bool > &coarseClosed, SharedQueue< std::pair< uint64_t, uint64_t > > *work, SharedQueue< uint64_t > *results, std::mutex *lock)
Definition: PDBHeuristic.h:734
PDBHeuristic::HCost
virtual double HCost(const state &a, const state &b) const
Definition: PDBHeuristic.h:163
SharedQueue.h
kDivPlusValueCompress
@ kDivPlusValueCompress
Definition: PDBHeuristic.h:30
NBitArray::Size
uint64_t Size() const
Definition: NBitArray.h:144
PDBHeuristic::FractionalModCompress
void FractionalModCompress(uint64_t factor, bool print_histogram)
Definition: PDBHeuristic.h:1138
PDBLookupType
PDBLookupType
Definition: PDBHeuristic.h:23
PDBHeuristic::BackwardThreadWorker
void BackwardThreadWorker(int threadNum, int depth, NBitArray< pdbBits > &DB, std::vector< bool > &coarse, SharedQueue< std::pair< uint64_t, uint64_t > > *work, SharedQueue< uint64_t > *results, std::mutex *lock)
Definition: PDBHeuristic.h:656
kModCompress
@ kModCompress
Definition: PDBHeuristic.h:28
PDBHeuristic::GetAverageValue
double GetAverageValue()
Definition: PDBHeuristic.h:1545
PDBHeuristic::GetPDBSize
virtual uint64_t GetPDBSize() const =0
SharedQueue::Add
void Add(T value)
Definition: SharedQueue.h:75
Timer
Definition: Timer.h:19
PDBHeuristic::vrcValues
int vrcValues[1<< pdbBits]
Definition: PDBHeuristic.h:124
PDBHeuristic::GetStateFromAbstractState
virtual state GetStateFromAbstractState(abstractState &s) const =0
PDBHeuristic::GetAbstractHash
virtual uint64_t GetAbstractHash(const state &s, int threadID=0) const =0
PDBHeuristic::GetHistogram
void GetHistogram(std::vector< uint64_t > &histogram)
Definition: PDBHeuristic.h:1491
PDBHeuristic::BuildPDB
void BuildPDB(const state &goal, int numThreads)
Definition: PDBHeuristic.h:82
PDBHeuristic::ValueRangeCompress
void ValueRangeCompress(int numBits, bool print_histogram)
Definition: PDBHeuristic.h:1209
kDefaultHeuristic
@ kDefaultHeuristic
Definition: PDBHeuristic.h:32
NBitArray::GetMaxValue
uint64_t GetMaxValue() const
Definition: NBitArray.h:38
PDBHeuristic::ZeroLowValues
void ZeroLowValues(int limit)
Definition: PDBHeuristic.h:94
SharedQueue
Definition: SharedQueue.h:24
PDBHeuristic::ForwardThreadWorker
void ForwardThreadWorker(int threadNum, int depth, NBitArray< pdbBits > &DB, std::vector< bool > &coarse, SharedQueue< std::pair< uint64_t, uint64_t > > *work, SharedQueue< uint64_t > *results, std::mutex *lock)
Definition: PDBHeuristic.h:582
Timer::EndTimer
double EndTimer()
Definition: Timer.cpp:15
PDBHeuristic::ValueCompress
void ValueCompress(int maxValue, bool print_histogram)
Definition: PDBHeuristic.h:1144
SharedQueue::Remove
bool Remove(T &item)
Definition: SharedQueue.h:85
PDBHeuristic::GetFileName
virtual std::string GetFileName(const char *prefix)=0
Generated by   doxygen 1.8.17