A* Search: A Comprehensive Guide

The A* (A-star) search algorithm is a powerful tool for finding the shortest path from a starting node to a target node in a graph. It is widely used in pathfinding for games, robotics, and various optimization problems.

Key Concepts

A* search uses the evaluation function:

f(n)=g(n)+h(n)

• f(n): Total cost from start to goal through node n.
• g(n): Cost from the start node to node n.
• h(n): Heuristic estimate of the cost from node n to the goal.

How A* Search Works

1. Initialization: Start with the initial node in the priority queue with f(n)=g(n)+h(n).
2. Node Expansion: Extract the node with the lowest f(n) value. If it’s the goal node, the search ends.
3. Neighbor Evaluation: For each neighbor of the current node, compute the tentative g(n). If it offers a better path, update g(n) and f(n), then add it to the queue.
4. Repeat: Continue expanding nodes until the goal is reached or the queue is empty.

Example Code

Here’s a simple Python example demonstrating the A* algorithm on a grid:

import heapq

def heuristic(a, b):
    # Manhattan distance heuristic
    return abs(b[0] - a[0]) + abs(b[1] - a[1])

def astar(grid, start, goal):
    # Priority queue: stores tuples of (f, current_node)
    open_list = []
    heapq.heappush(open_list, (0 + heuristic(start, goal), start))

    came_from = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, goal)}

    while open_list:
        _, current = heapq.heappop(open_list)

        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            path.reverse()
            return path

        x, y = current
        neighbors = [(x + dx, y + dy) for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]]

        for neighbor in neighbors:
            if 0 <= neighbor[0] < len(grid) and 0 <= neighbor[1] < len(grid[0]) and grid[neighbor[0]][neighbor[1]] == 0:
                tentative_g_score = g_score[current] + 1
                if neighbor not in g_score or tentative_g_score < g_score[neighbor]:
                    came_from[neighbor] = current
                    g_score[neighbor] = tentative_g_score
                    f_score[neighbor] = tentative_g_score + heuristic(neighbor, goal)
                    heapq.heappush(open_list, (f_score[neighbor], neighbor))

    return None  # Path not found

# Example usage
grid = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 0, 0],
    [0, 0, 0, 0, 0]
]

start = (0, 0)
goal = (4, 4)
path = astar(grid, start, goal)
print("Path:", path)

Output: Path: [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (1, 4), (2, 4), (3, 4), (4, 4)]

Summary

• A Search*: An efficient algorithm for finding the shortest path using a heuristic.
• f(n) = g(n) + h(n): Balances the cost to reach the node and the estimated cost to the goal.
• Priority Queue: Ensures nodes are expanded in the order of their total cost.

A* search is optimal and complete, making it an invaluable tool in solving complex pathfinding problems. Whether in games, robotics, or optimization, A* helps in navigating the most efficient routes to success.

A* Search

Artificial Intelligence — Tutorial #6 “A* Search”

For previous subject go here -> https://medium.com/p/4672bbc5e48c

For next subject go here -> https://medium.com/p/46e33f1ecc02

Let me know if you’d like any further refinements or additions to this post! tahsinsoyakk@gmail.com