Why ARA* is Hard to Beat for Pacman No Tunnel

To the right is a plot of all of the planners I have used in the pacman domain with the tunnels sealed such that they cannot be used to reach the other side of the graph. Most importantly in the plot are the curves corresponding to greedy, minallpaths and ARA*. Notice that "min all paths" performs best overall. This corresponds to being omniscient and selecting to compute only the arcs in the overlayed network that will allow pacman to reach the goal state with minimum cost. The next best performer is ARA*. It is only slightly worse than that of "min all paths", suggesting that there is not much possibility for improvement if we choose to move according to the arcs of the overlay graph.

Notice that greedy does much worst than either ARA* and "min all paths". So even if we include greedy actions in the metaplan, it may still not be able to achieve the performance of ARA* for tis particular setup, since even if you were omniscient you would do only slightly better.


This suggests that perhaps a larger maze is necessary, as Nick mentioned a while back. I had verified that "min all paths" was significantly better than ARA* in the case where the tunnels were allowed to be traversed. I think ARA* suffers a performance degradation in this case because it has to expand the breadth of its search, causing the search tree to be much larger resulting in longer planning times and a higher probability of being eaten while planning.