Keeping track of tiles in a* search

Question

I am having a hard time keeping track of the tiles generated by getAdjacentTiles(..). I have identified the performance issue of my A* implementation below is that I do not keep track of the tiles that have seen before, every call to getAdjacentTiles returns new tiles (Node's) and not any of the tiles in openSet or closedSet. I decided to use a list of Node objects as all of the tiles created so far, and pass that to getAdjacentTiles to determine if a tile it produces has already been visited.

My problem is, that I cannot seem to keep track of these tiles properly. Whenever my A* needs to take more than about 4 movements to get to the end location it craps out. Which I am sure has to do with how I am trying to keep track of the tiles (again Node's that have been visited) I would have to suspect the issue is with my knowledge of python, am I allowed to do .apped(tile) like I do in getAdjacentTiles(...) when looping through the allTiles set?

Here's a link to the question that led me to this one

The error generated (sometimes, only when the A* path is longer than about 3 steps..)

File "P3.py", line 67, in aStar
 openSet.remove(curNode) 
KeyError: <__main__.Node instance at 0xa39edcc>

Source

  #Perform an A* search to find the best path to the dirt
  def aStar(self, current, end):
    openSet = set()
    openHeap = []
    closedSet = set()
    allTiles = set()
    curNode = Node(0, current, self.manHatDist(current, end))
    openSet.add(curNode)
    allTiles.add(curNode)
    openHeap.append((curNode.cost,curNode))
    while openSet:
      curNode = heapq.heappop(openHeap)[1]
      if curNode.pos == end:
          return self.getDirections(curNode)
      openSet.remove(curNode)
      closedSet.add(curNode)
      adjNodes = self.getAdjacentNodes(curNode.pos, allTiles)
      for tile in adjNodes:
        t = tile
        if t not in closedSet:
          cost = (curNode.cost - self.manHatDist(curNode.pos, end) 
                  + self.euclidDist(curNode.pos, current)
                  + self.manHatDist(t.pos, end))
          if t not in openSet or cost < t.cost:
            t.parent = curNode
            t.cost = cost
            openSet.add(t)
            heapq.heappush(openHeap, (cost,t))
        allTiles.add(t)
    return []

  #Get the moves made to get to this endNode
  def getDirections(self, endNode):
    moves = []
    tmpNode = endNode
    while tmpNode.parent is not None:
      moves.append(tmpNode.value)
      tmpNode = tmpNode.parent
    moves.reverse()
    return moves

  #Return all possible moves from given tile as Node objects
  def getAdjacentNodes(self, curPos, allTiles):
    allMoves = ['North','South','East','West']
    posMoves = []
    for direction in allMoves:
      if(self.canMove(direction, curPos)):
        posMoves.append(Node(direction, self.getLocIfMove(curPos, direction)))
    retNodes = []
    for posLocNode in posMoves:
      set = False
      for tile in allTiles:
        if(posLocNode.pos == tile.pos):
          set = True
          retNodes.append(tile)
      if(not set):
        retNodes.append(posLocNode)
    return retNodes

Answer 1

Let's fire up the interactive interpreter and see what we can find. (You didn't give the name of your class in the question, so I've called it Search.)

>>> Search().aStar((0,0), (2,2))
Traceback (most recent call last):
  ...
  File "q19128695.py", line 25, in aStar
    openSet.remove(curNode)
KeyError: <__main__.Node instance at 0x104895518>

OK, the first problem is that these Node instances are not self-explanatory. We can't do anything with "Node instance at 0x104895518", so let's add a __repr__ method to the Node class:

def __repr__(self):
    return 'Node({0.value}, {0.pos}, {0.cost})'.format(self)

and try again:

>>> Search().aStar((0,0), (2,2))
Traceback (most recent call last):
  ...
  File "q19128695.py", line 25, in aStar
    openSet.remove(curNode)
KeyError: Node(East, (1, 2), 3.41421356237)

OK, that's more informative. Let's fire up the Python debugger and do a postmortem:

>>> import pdb
>>> pdb.pm()
> q19128695.py(25)aStar()
-> openSet.remove(curNode)
(Pdb) openSet
set([Node(North, (2, -1), 6.0), Node(East, (2, 2), 4.65028153987), 
     Node(West, (-1, 1), 5.0), Node(North, (0, -1), 5.0),
     Node(South, (1, 3), 6.65028153987), Node(South, (0, 3), 6.0), 
     Node(East, (3, 0), 6.0), Node(West, (-1, 0), 5.0),
     Node(North, (1, -1), 5.0), Node(East, (3, 1), 6.65028153987),
     Node(West, (-1, 2), 6.0)])
(Pdb) closedSet
set([Node(0, (0, 0), 4), Node(South, (2, 1), 3.41421356237),
     Node(East, (1, 1), 3.0), Node(South, (0, 1), 3.0),
     Node(East, (2, 0), 3.0), Node(East, (1, 0), 3.0),
     Node(East, (1, 2), 3.41421356237), Node(South, (0, 2), 3.0)])
(Pdb) curNode
Node(East, (1, 2), 3.41421356237)
(Pdb) curNode in closedSet
True

So the node has already been closed. How could this have happened? Well, it could happen if the node had been added to openSet and openHeap twice. It would then be popped from openHeap twice (because heaps can have multiple identical items), but it can only be removed from openSet once. The code in question looks like this:

if t not in openSet or cost < t.cost:
    t.parent = curNode
    t.cost = cost
    openSet.add(t)
    heapq.heappush(openHeap, (cost,t))

The first problem with this, is that you push the pair (cost, t) even though you've gone to the trouble to give your Node objects __lt__ and __gt__ methods. Instead, just push t onto the heap:

heapq.heappush(openHeap, t)

This requires a couple of changes elsewhere: instead of

openHeap.append((curNode.cost,curNode))
while openSet:
    curNode = heapq.heappop(openHeap)[1]

you'll have to write

openHeap = [curNode]
while openSet:
    curNode = heapq.heappop(openHeap)

Now, the second problem (which is my fault—sorry), is that if t is already in openSet then we shouldn't add it to the heap again. Instead, we should re-heapify:

t_open = t in openSet
if not t_open or cost < t.cost:
    t.parent = curNode
    t.cost = cost
    if t_open:
        heapq.heapify(openHeap)
    else:
        openSet.add(t)
        heapq.heappush(openHeap, t)

Going back to the debugger output, recall this:

(Pdb) curNode
Node(East, (1, 2), 3.41421356237)

That 3.41421356237 should be worrying you: shouldn't the cost always be an integer? It looks as though the cost calculation is still wrong. It says:

    cost = (curNode.cost
            - self.manHatDist(curNode.pos, end) 
            + self.euclidDist(curNode.pos, current)
            + self.manHatDist(t.pos, end))

but that third line should say:

            + self.euclidDist(curNode.pos, t.pos)

So, with all those fixes in place, let's try again:

>>> Search().aStar((0,0), (2,2))
['North', 'North', 'East', 'East']

Replies to comments

1. "How did you call Search().aStar(...) from the interpreter?" I ran the interpreter and then typed in that line of code at the interpreter prompt. See the tutorial.

2. "So the Euclidean distance will always be one." Yes, if you're searching for paths in a uniform-cost grid, then the Euclidean distance between neighbours will always be the same.

3. "Now that I think about it, curNode.cost - self.manHatDist(curNode.pos, end) is always equal to zero." That's not right. In your implementation, the cost of a search node is (i) the cost of reaching that node from the start, plus (ii) an admissible estimate of the cost of reaching the end from that node. So if you subtract the admissible estimate then you should get back to (i) again.