CODEWITHSUNDEEP
pythonalgorithma-star
Timothy Cottrell
Timothy Cottrell

Reputation: 11

Need help cracking the A* (A star) algorithm in python

import math
import heapq

class Node:
    def __init__(self, location, parent, pathCost, goalLocation):
        self.location = location
        self.parent = parent
        self.g = pathCost
        if not isinstance(parent, Node):
            self.pathValue = pathCost
        else:
            self.pathValue = parent.g + pathCost
        self.h = math.sqrt((location[0] - goalLocation[0]) ** 2 + (location[1] - goalLocation[1]) ** 2)
        self.f = self.g + self.h

    def __eq__(self, other):
        if self.f == other.f:
            return True
        else:
            return False

    def __lt__(self, other):
        if self.f <= other.f:
            return True
        else:
            return False

    def __str__(self):
        return "Location: [" + str(self.location[0]) + "," + str(self.location[1]) + "] | MoveValue:" + str(self.g)

    def __repr__(self):
        return "Location: [" + str(self.location[0]) + "," + str(self.location[1]) + "] | MoveValue:" + str(self.g)

def getNeighbors(location, grid):
    neighbors = []
    if location[1] != 0 and grid[location[1] - 1][location[0]] != 0:
        neighbors.append([location[0], location[1] - 1])
    if location[0] != 0 and grid[location[1]][location[0] - 1] != 0:
        neighbors.append([location[0] - 1, location[1]])
    if location[1] != len(grid[0]) - 1 and grid[location[1] + 1][location[0]] != 0:
        neighbors.append([location[0], location[1] + 1])
    if location[0] != len(grid[0]) - 1 and grid[location[1]][location[0] + 1] != 0:
        neighbors.append([location[0] + 1, location[1]])
    return neighbors

def expandNode(node, grid, clist, olist, goalLocation):
    neighbors = getNeighbors(node.location, grid)
    #print(neighbors)
    for n in neighbors:
        child = Node(n, node, grid[n[1]][n[0]], goalLocation)
        if child in olist:
            if child.g < node.g:
                heapq.heappush(olist, child)
            if child in clist:
                clist.remove(child)
        elif not child in clist:
            heapq.heappush(olist, child)

grid = [[0, 2, 1, 3], #the top right is [3,0] the starting location
        [1, 1, 1, 0],
        [0, 4, 1, 3],
        [1, 1, 1, 1]] #the bottom left is [0,3] the goal location

goalLocation = [0, 3]
startLocation = [3, 0]

firstNode = Node(startLocation, 0, grid[startLocation[1]][startLocation[0]], goalLocation)
olist, clist = [], []
heapq.heappush(olist, firstNode)

for i in range(6):
    node = heapq.heappop(olist)
    print(node)
    print(str(i) + "| Open list: " + str(olist))
    print(str(i) + "| Closed list: " + str(clist))
    if node.location == goalLocation:
        print("Found Goal")
        break
    clist.append(node)
    expandNode(node, grid, clist, olist, goalLocation)

I have been trying to create a simple version of the A* algorithm in python that can traverse a 2-dimensional list. I believe that the algorithm itself is working but for some reason, it won't create a Node object for the position [2, 2] in my grid. Because of this, it is possible to not find the optimal solution. If anyone can see the logical error that I am missing or can point out how if the algorithm isn't correct.

Currently, it prints out:

Location: [3,0] | MoveValue:3
0| Open list: []
0| Closed list: []
Location: [2,0] | MoveValue:1
1| Open list: []
1| Closed list: [Location: [3,0] | MoveValue:3]
Location: [2,1] | MoveValue:1
2| Open list: [Location: [1,0] | MoveValue:2]
2| Closed list: [Location: [3,0] | MoveValue:3, Location: [2,0] | MoveValue:1]
Location: [1,1] | MoveValue:1
3| Open list: [Location: [1,0] | MoveValue:2]
3| Closed list: [Location: [3,0] | MoveValue:3, Location: [2,0] | MoveValue:1, Location: [2,1] | MoveValue:1]s
Location: [0,1] | MoveValue:1
4| Open list: [Location: [1,0] | MoveValue:2, Location: [1,2] | MoveValue:4]
4| Closed list: [Location: [3,0] | MoveValue:3, Location: [2,0] | MoveValue:1, Location: [2,1] | MoveValue:1, Location: [1,1] | MoveValue:1]
Location: [1,0] | MoveValue:2
5| Open list: [Location: [1,2] | MoveValue:4]
5| Closed list: [Location: [3,0] | MoveValue:3, Location: [2,0] | MoveValue:1, Location: [2,1] | MoveValue:1, Location: [1,1] | MoveValue:1, Location: [0,1] | MoveValue:1]

Upvotes: 1

Views: 411

Answers (1)

kcsquared
kcsquared

Reputation: 5409

There are several issues with the code and the algorithm, I'll try to list them from most to least serious:

  1. self.h = math.sqrt((location[0] - goalLocation[0]) ** 2 + (location[1] - goalLocation[1]) ** 2) -- this is the cause of most of the problems. For A* search to produce correct output, your heuristic h needs to be admissible, which means it never overestimates the cost to reach the goal. Your cost function is a sum of vertex weights, so a Euclidean distance on list indices is not an admissible heuristic. You can set h to 0 (which will cause A* to become Dijkstra's algorithm) or find special properties of the graph to get a consistent heuristic too.

child = Node(n, node, grid[n[1]][n[0]], goalLocation)
if child in olist:

The main issue here is the equality tests and the in statement. First, equality of nodes (for membership testing) should be done based on graph coordinates, not by distance, as it currently is. You probably need to pass in tuples of (f_value, node) into the min-heap, rather than defining __eq__ in a way that messes up distinctness testing. Also, use a set instead of a list, or the runtime of A* becomes much worse.

  1. for i in range(6): should probably be while olist; it's not clear why the maximum number of nodes explored is hardcoded at 6.
  2. The fourth if statement in getNeighbors should start with if location[0] != len(grid) - 1, although you'll notice a problem as soon as your matrix isn't square and you get an IndexError. I'll also recommend again to find a way to avoid having the index order reversed everywhere from Python's default, as these kinds of subtle bugs become more common and harder to catch.
  3. I'm not familiar with the version of A* you're trying to implement or the reference you're using, but I'd double check that the loop in expandNode matches that reference. I'm not sure what the purpose of a closed list is, or the logic behind those conditionals, so I can't comment on their correctness.

Upvotes: 1

Related Questions