A* search algorithm

A* search algorithm is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

The A* search algorithm is an extension of Dijkstra's algorithm for route finding that uses heuristics to quickly find an approximate solution.

Task

Consider the problem of finding a route across the diagonal of a chess board-like 8x8 grid. The rows are numbered from 0 to 7. The columns are also numbered 0 to 7. The start position is (0, 0) and the end position is (7, 7). Movement is only possible to directly adjacent squares; diagonal moves are not allowed. The standard movement cost is 1. To make things slightly harder, there are two barriers that occupy certain positions of the grid. Moving into any of the barrier positions has a cost of 100. The positions of the first barrier are (2,0),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(1,6). The positions of the second barrier are (5,7),(5,6),(5,5),(5,4),(5,3),(4,3). A route with the lowest cost should be found using the A* search algorithm (there are multiple optimal solutions).

Optimally, draw the optimal route and the barrier positions.

Python

<lang python>from __future__ import print_function import matplotlib.pyplot as plt

class AStarGraph(object): #Define a class board like grid with two barriers

def __init__(self): self.barriers = [] self.barriers.append([(2,0),(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(1,6)]) self.barriers.append([(5,7),(5,6),(5,5),(5,4),(5,3),(4,3)])

def heuristic(self, start, goal): #Use Manhattan distance heuristic if we can only move in 4 directions #on the grid return 1.5*(abs(start[0]-goal[0])+abs(start[1]-goal[1]))

def get_vertex_neighbours(self, pos): n = [] for dx, dy in [(1,0),(-1,0),(0,1),(0,-1)]: x2 = pos[0] + dx y2 = pos[1] + dy if x2 < 0 or x2 > 7 or y2 < 0 or y2 > 7: continue n.append((x2, y2)) return n

def move_cost(self, a, b): for barrier in self.barriers: if b in barrier: return 100 #Extremely high cost to enter barrier squares return 1 #Normal movement cost

def AStarSearch(start, end, graph):

G = {} #Actual movement cost to each position from the start position F = {} #Estimated movement cost of start to end going via this position

#Initialize starting values G[start] = 0 F[start] = graph.heuristic(start, end)

closedVertices = set() openVertices = set([start]) cameFrom = {}

while len(openVertices) > 0: #Get the vertex in the open list with the lowest F score current = None currentFscore = None for pos in openVertices: if current is None or F[pos] < currentFscore: currentFscore = F[pos] current = pos

#Check if we have reached the goal if current == end: #Retrace our route backward path = [current] while current in cameFrom: current = cameFrom[current] path.append(current) path.reverse() return path #Done!

#Mark the current vertex as closed openVertices.remove(current) closedVertices.add(current)

#Update scores for vertices near the current position for neighbour in graph.get_vertex_neighbours(current): if neighbour in closedVertices: continue #We have already processed this node exhaustively candidateG = G[current] + graph.move_cost(current, neighbour)

if neighbour not in openVertices: openVertices.add(neighbour) #Discovered a new vertex elif candidateG >= G[neighbour]: continue #This G score is worse than previously found

#Adopt this G score cameFrom[neighbour] = current G[neighbour] = candidateG H = graph.heuristic(neighbour, end) F[neighbour] = G[neighbour] + H

raise RuntimeError("A* failed to find a solution")

if __name__=="__main__": graph = AStarGraph() result = AStarSearch((0,0), (7,7), graph) print ("route", result) plt.plot([v[0] for v in result], [v[1] for v in result]) for barrier in graph.barriers: plt.plot([v[0] for v in barrier], [v[1] for v in barrier]) plt.xlim(-1,8) plt.ylim(-1,8) plt.show()</lang>

Output:

route [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (1, 7), (2, 7), (3, 7), (3, 6), (3, 5), (3, 4), (3, 3), (3, 2), (4, 2), (5, 2), (6, 2), (7, 2), (7, 3), (7, 4), (7, 5), (7, 6), (7, 7)]