Sampling and Tree Generation

The amount of sampling used in generating the initial tree has a huge impact on the resulting tree an in turn on the resulting metaplanning policy. Here are 3 trees based on 250,1000,4000, and 16000 samples.




One thing to note which I discussed briefly in the previous post is that the decision tree predicts what the optimal solution will be given a set of arc outcomes. The key word being "optimal". That is if you knew the remaining arcs and were able to solve for the optimal path, on average it would take on the predicted cost. I believe that this is why the decision tree decides to generate leaf nodes, since all "optimal paths" have the same cost. It is still possible to find suboptimal paths, but the decision tree is not influence by this.

The story is differente when executing the metaplan, the optimal cost in not achievable because not all of the arc costs are known. The remaining arcs need to be selected carefully by the metaplanner, but as of yet there is no good way to do so.

The remainder of path was generated using a path completing algorithm that favored paths that had the most arcs computed. This would typically be that bad path because, the DTMP would follow queries deep in the tree, and discover a bad arc. Then the tree would run out of suggestions. So that the path closest to being completed would be the one with the bad arc.

Pacman Small Maze

These result are for the small maze pacman problem with 39 arcs. I found that for some ghost positions there was no way for the metaplanner to find a path though the ghosts because it cannot move backwards, whereas ARA* can. For these situations, DTMP always runs into ghosts. I was able to detect this for each run by solving for the optimal path to the goal. If this path exceeded 1000 in cost, then I flagged the data to indicate that no clear path exists. I did not include these cases in the comparision of ARA* and DTMP. In addition there were certain positions where no feasible solution (one where no ghosts were encountered) existed for ARA* nor DTMP. I also did not include these in the comparison. I generated random ghost positions and stored them. I used the same set of ghost positions to test ARA* and DTMP. Final note is that the tree is typically not deep enough to specify good behavior when the situation goes sour. In that case, the old procedure was try to complete the path to goal using our current knowledge of the world. This tended to perform badly since the path completing arcs would tend to correspond to the path with the most arcs already computed. This path was more than likely to be a "bad path". So by doing this the DTMP had no chance of finding a good path. After noticing this i changed the path completing procedure so that arcs that have been discovered to be occupied have a huge cost of 10000, all other known arcs have their known values, and the unknown arcs take on their max values. This discourages the path completing behavior to favor the paths that include occupied arcs, an tended to improve the quality of the plans.