A* search algorithm: Difference between revisions
No edit summary |
No edit summary |
||
Line 3: | Line 3: | ||
;Task |
;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 |
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 allow by one square in any direction including diagonals, similar to a king in chess. The standard movement cost is 1. To make things slightly harder, there is a barrier that occupy certain positions of the grid. Moving into any of the barrier positions has a cost of 100. The positions of the barrier is (2,4),(2,5),(2,6),(3,6),(4,6),(5,6),(5,5),(5,4),(5,3),(5,2),(4,2),(3,2). A route with the lowest cost should be found using the A* search algorithm (there are multiple optimal solutions with the same total cost). |
||
Print the optimal route in text format, as well as the total cost of the route. |
Print the optimal route in text format, as well as the total cost of the route. |
||
Line 15: | Line 15: | ||
<lang python>from __future__ import print_function |
<lang python>from __future__ import print_function |
||
import matplotlib.pyplot as plt |
import matplotlib.pyplot as plt |
||
class AStarGraph(object): |
class AStarGraph(object): |
||
#Define a class board like grid with two barriers |
#Define a class board like grid with two barriers |
||
def __init__(self): |
def __init__(self): |
||
self.barriers = [] |
self.barriers = [] |
||
self.barriers.append([(2, |
self.barriers.append([(2,4),(2,5),(2,6),(3,6),(4,6),(5,6),(5,5),(5,4),(5,3),(5,2),(4,2),(3,2)]) |
||
self.barriers.append([(5,7),(5,6),(5,5),(5,4),(5,3),(4,3)]) |
|||
def heuristic(self, start, goal): |
def heuristic(self, start, goal): |
||
#Use |
#Use Chebyshev distance heuristic if we can move one square either |
||
# |
#adjacent or diagonal |
||
D = 1 |
|||
return 1.5*(abs(start[0]-goal[0])+abs(start[1]-goal[1])) |
|||
D2 = 1 |
|||
dx = abs(start[0] - goal[0]) |
|||
dy = abs(start[1] - goal[1]) |
|||
return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy) |
|||
def get_vertex_neighbours(self, pos): |
def get_vertex_neighbours(self, pos): |
||
n = [] |
n = [] |
||
#Moves allow link a chess king |
|||
for dx, dy in [(1,0),(-1,0),(0,1),(0,-1)]: |
for dx, dy in [(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,1),(1,-1),(-1,-1)]: |
||
x2 = pos[0] + dx |
x2 = pos[0] + dx |
||
y2 = pos[1] + dy |
y2 = pos[1] + dy |
||
Line 38: | Line 42: | ||
n.append((x2, y2)) |
n.append((x2, y2)) |
||
return n |
return n |
||
def move_cost(self, a, b): |
def move_cost(self, a, b): |
||
for barrier in self.barriers: |
for barrier in self.barriers: |
||
Line 44: | Line 48: | ||
return 100 #Extremely high cost to enter barrier squares |
return 100 #Extremely high cost to enter barrier squares |
||
return 1 #Normal movement cost |
return 1 #Normal movement cost |
||
def AStarSearch(start, end, graph): |
def AStarSearch(start, end, graph): |
||
G = {} #Actual movement cost to each position from the start position |
G = {} #Actual movement cost to each position from the start position |
||
F = {} #Estimated movement cost of start to end going via this position |
F = {} #Estimated movement cost of start to end going via this position |
||
#Initialize starting values |
#Initialize starting values |
||
G[start] = 0 |
G[start] = 0 |
||
F[start] = graph.heuristic(start, end) |
F[start] = graph.heuristic(start, end) |
||
closedVertices = set() |
closedVertices = set() |
||
openVertices = set([start]) |
openVertices = set([start]) |
||
cameFrom = {} |
cameFrom = {} |
||
while len(openVertices) > 0: |
while len(openVertices) > 0: |
||
#Get the vertex in the open list with the lowest F score |
#Get the vertex in the open list with the lowest F score |
||
Line 76: | Line 80: | ||
path.reverse() |
path.reverse() |
||
return path, F[end] #Done! |
return path, F[end] #Done! |
||
#Mark the current vertex as closed |
#Mark the current vertex as closed |
||
openVertices.remove(current) |
openVertices.remove(current) |
||
closedVertices.add(current) |
closedVertices.add(current) |
||
#Update scores for vertices near the current position |
#Update scores for vertices near the current position |
||
for neighbour in graph.get_vertex_neighbours(current): |
for neighbour in graph.get_vertex_neighbours(current): |
||
Line 86: | Line 90: | ||
continue #We have already processed this node exhaustively |
continue #We have already processed this node exhaustively |
||
candidateG = G[current] + graph.move_cost(current, neighbour) |
candidateG = G[current] + graph.move_cost(current, neighbour) |
||
if neighbour not in openVertices: |
if neighbour not in openVertices: |
||
openVertices.add(neighbour) #Discovered a new vertex |
openVertices.add(neighbour) #Discovered a new vertex |
||
elif candidateG >= G[neighbour]: |
elif candidateG >= G[neighbour]: |
||
continue #This G score is worse than previously found |
continue #This G score is worse than previously found |
||
#Adopt this G score |
#Adopt this G score |
||
cameFrom[neighbour] = current |
cameFrom[neighbour] = current |
||
Line 97: | Line 101: | ||
H = graph.heuristic(neighbour, end) |
H = graph.heuristic(neighbour, end) |
||
F[neighbour] = G[neighbour] + H |
F[neighbour] = G[neighbour] + H |
||
raise RuntimeError("A* failed to find a solution") |
raise RuntimeError("A* failed to find a solution") |
||
if __name__=="__main__": |
if __name__=="__main__": |
||
graph = AStarGraph() |
graph = AStarGraph() |
Revision as of 22:45, 19 December 2016
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 allow by one square in any direction including diagonals, similar to a king in chess. The standard movement cost is 1. To make things slightly harder, there is a barrier that occupy certain positions of the grid. Moving into any of the barrier positions has a cost of 100. The positions of the barrier is (2,4),(2,5),(2,6),(3,6),(4,6),(5,6),(5,5),(5,4),(5,3),(5,2),(4,2),(3,2). A route with the lowest cost should be found using the A* search algorithm (there are multiple optimal solutions with the same total cost).
Print the optimal route in text format, as well as the total cost of the route.
Optimally, draw the optimal route and the barrier positions.
Note: using a heuristic score of zero is equivalent to Dijkstra's algorithm and that's kind of cheating/not really A*!
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,4),(2,5),(2,6),(3,6),(4,6),(5,6),(5,5),(5,4),(5,3),(5,2),(4,2),(3,2)])
def heuristic(self, start, goal): #Use Chebyshev distance heuristic if we can move one square either #adjacent or diagonal D = 1 D2 = 1 dx = abs(start[0] - goal[0]) dy = abs(start[1] - goal[1]) return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)
def get_vertex_neighbours(self, pos): n = [] #Moves allow link a chess king for dx, dy in [(1,0),(-1,0),(0,1),(0,-1),(1,1),(-1,1),(1,-1),(-1,-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, F[end] #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, cost = AStarSearch((0,0), (7,7), graph) print ("route", result) print ("cost", cost) 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)] cost 24.0