A* Algorithm in AI

A* Algorithm

Understanding A* Algorithm

A* is widely used in AI for pathfinding in games, robotics, and navigation systems due to its efficiency and optimality when paired with an admissible heuristic.

Real-World Example: In video games, A* finds the shortest path for characters avoiding obstacles.

Comparing A* Algorithm

The textual diagram below compares A* with other search algorithms.

Exploring A* Algorithm

Below, we explore A* and related algorithms with vibrant cards.

A* Algorithm: Python Code

Below is a Python implementation of A* for the grid example.

from heapq import heappush, heappop

def a_star(grid, start, goal):
    rows, cols = len(grid), len(grid[0])
    open_list = [(0, start, [])]  # (f, node, path)
    closed = set()
    
    def h(node):
        return abs(goal[0] - node[0]) + abs(goal[1] - node[1])  # Manhattan distance
    
    while open_list:
        f, current, path = heappop(open_list)
        if current in closed:
            continue
        closed.add(current)
        
        if current == goal:
            return path + [current]
        
        x, y = current
        for dx, dy in [(0,1), (1,0), (0,-1), (-1,0)]:  # Right, down, left, up
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 0:  # Valid move
                successor = (nx, ny)
                if successor not in closed:
                    g = len(path) + 1
                    f_new = g + h(successor)
                    heappush(open_list, (f_new, successor, path + [current]))
    
    return None

grid = [
    [0, 0, 0, 0],
    [0, 1, 0, 0],
    [0, 1, 0, 0],
    [0, 0, 0, 0]
]
start, goal = (0,0), (3,3)
path = a_star(grid, start, goal)
print("Path:", path if path else "No path")
                    

This code finds the shortest path from (0,0) to (3,3), avoiding obstacles.

Technical Insights for Students

Mastering A* enhances your AI programming skills:

• Heuristic Design: Ensure h(n) is admissible for optimality.
• Loop Prevention: Use closed list to avoid redundant exploration.
• Implementation: Use priority queues for efficient node selection.
• Practical Tip: Implement A* in a maze game using Colab.

Key Takeaways

• A* is optimal for pathfinding with admissible heuristics.
• Balances g(n) and h(n) for efficiency.
• Closed list prevents loops.
• Key for games, robotics, and navigation.