Astar with New Heuristic

I noticed when coding up the ARA* path planner that the heuristic function I used was not correctly implemented. I used the Manhattan distance between pacman and the goal location divide by two. Since pacman is able to use the side tunnels to move from the left to the right this heuristic was not always a lower bound. Now I use the new heuristic function where the Manhattan distance is calculated in the following way:


H = min[abs(pacManX-goalX),...
abs(pacManX-rightSide)+abs(goalX-leftSide),...
abs(pacManX-leftSide)+abs(goalX-rightSide)]+...
abs(pacManY-goalY)

where the first term is the x straight-line distance; the second term is the x-distance if it is shorter for pacman to move through the right tunnel to get to the goal; and the third term is the x distance if pacman must move through the left tunnel to reach the goal. The last term is the y distance.

I have rerun the results for the Astar algorithms, leading to improvement from the old heuristic.

Corrected Results

The results at the bottom right are the corrected results for the Pacman problem. The x-axis numbers are mislabeled, but correspond to the number of nodes expanded per unit ghost move. 1= 250 expansions/move; 2=100; 3=50;4=10 expansion/move.


The old results are shown at the upper left.

Mistake in pacman implemetation (follow up)

I corrected the mistake of counting the number of collisions from the wrong starting location during planning for the metaplanner. The results are slightly worse as expected.

I found another error in planning location for the corrected random planner (i.e. the random planner cannot execute until a feasible plan to the goal has been found). Rather than setting the start location to be the head of the arc being planned, the start location was always the pacman origin. This would cause pacman to have to plan much more than was necessary resulting in more planning collisions. I expect the results of the random algorithm to improve.


I found an even more egregious error: I never ran the corrected version of the random planner which was in a script file named testRand2. Instead the results generated was from the original testRand. I will be fixing this too.

Mistake in pacman implementation

I found a mistake today in the way I was counting the collisions when pacman is stationary and planning in the metaplanner code. I set the pacman location to the head of the arc being computed rather than the origin position.

The result of this could be why the pacman data does not indicate that it is being eaten as much during planning when compared to A* and Random. I will generate new results with the correction.

I have also implemented anytime repairing A* (ARA*) for a map navigation problem and am in the process of integrating it with the pacman problem as the anytime algorithm to compare against.

Preliminary Data Plus Random Strategy Data

Preliminary Plots

Stationary Pacman Plots

What happens when pacman is sitting still and thinking.

Pacman Arc Cost Plots

Plots expected arc costs as a function of initial ghost distance

PathCost = move cost+collisionCost*(#times collided when executing the path)
move cost = 1,collision cost = 10.

E[PathCost/dist] =
E[Path Cost/collision]*(P_collison/dist)+E[Path Cost/no collision]*(P_no_collision/dist)

Pacman Probability of Collision Plots

Plots probability of at least 1 collision as a funciton of initial ghost distance
seems like some arcs are insensitive to initial distance.

Average Minimum Ghost Distance

Plots of the distributions of the minimum ghost distances for each arc
x-axis is the initial minimum manhattan distance and y-axis is the percentage of time that occurred over 500 samples for each arc.

Pacman Graph

9 nodes 11 arc, where P is initial pacman location G is goal and X are intermediate nodes