A* Search: The Engine of Intelligent Pathfinding

Welcome to our deep dive into the building blocks of AI agents. Today, we’re exploring a classic, yet perpetually relevant algorithm: A Search*. If you’ve ever wondered how an AI agent can formulate a plan to get from point A to point B—whether that’s a robot navigating a room, a game character finding its target, or a software agent figuring out the steps to complete a task—you’ve likely encountered the handiwork of A*.

This article will break down how A* works, where it comes from, and how you can use it to build smarter agents.

Imagine you’re in a city and need to get to a friend’s house. You could use Dijkstra’s algorithm, which would be like exploring every single street radiating outwards from your position until you stumble upon the destination—thorough, but incredibly inefficient. Or, you could use a Greedy Best-First Search, which would be like always walking in the straight-line direction of your friend’s house, even if it leads you into a dead-end alley or a river.

A (pronounced “A-star”)* offers a brilliant compromise. It’s a pathfinding algorithm that combines the best of both worlds.

2. Historical & Theoretical Context

A* isn’t a new kid on the block. It was developed in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael at the Stanford Research Institute (SRI). It was a significant improvement upon Dijkstra’s algorithm (1956), which could find the shortest path but did so “blindly,” without any sense of direction.

A* is a cornerstone of classical AI, also known as “Good Old-Fashioned AI” (GOFAI). It represents a paradigm where intelligence is achieved through symbolic manipulation and logical reasoning. For an agent to act, it must first plan, and A* provides a powerful and efficient engine for that planning process.

3. The Algorithm and its Math

The magic of A* is captured in a simple but powerful formula for evaluating nodes (potential steps) in the graph:

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

Where:

A* works by maintaining a priority queue of nodes to visit, called the “open set”. It always picks the node with the lowest f(n) score to explore next.

Here is the pseudocode:

function A_Star(start, goal)
    // The set of nodes already evaluated
    closedSet := {}

    // The set of currently discovered nodes that are not evaluated yet.
    // Initially, only the start node is known.
    openSet := {start}

    // For each node, which node it can most efficiently be reached from.
    cameFrom := an empty map

    // For each node, the cost of getting from the start node to that node.
    gScore := map with default value of Infinity
    gScore[start] := 0

    // For each node, the total cost of getting from the start node to the goal
    // by passing by that node. That value is partly known, partly heuristic.
    fScore := map with default value of Infinity
    fScore[start] := h(start) // h is the heuristic function

    while openSet is not empty
        current := the node in openSet with the lowest fScore[] value
        if current = goal
            return reconstruct_path(cameFrom, current)

        remove current from openSet
        add current to closedSet

        for each neighbor of current
            if neighbor in closedSet
                continue // Ignore the neighbor which is already evaluated.

            // The distance from start to a neighbor
            tentative_gScore := gScore[current] + d(current, neighbor)

            if neighbor not in openSet // Discover a new node
                add neighbor to openSet
            else if tentative_gScore >= gScore[neighbor]
                continue // This is not a better path.

            // This path is the best until now. Record it!
            cameFrom[neighbor] := current
            gScore[neighbor] := tentative_gScore
            fScore[neighbor] := gScore[neighbor] + h(neighbor)

    return failure // Open set is empty but goal was never reached

The key is the heuristic h(n). For pathfinding on a grid, a common heuristic is the Manhattan distance (sum of absolute differences of coordinates) or the Euclidean distance (straight-line distance).

4. Design Patterns & Architectures

A* is not just a standalone algorithm; it’s a component that fits neatly into larger agent architectures.

5. Practical Application: Python Example

Let’s see A* in action with a simple grid-based pathfinding problem. We’ll use Python’s heapq library to efficiently implement the priority queue (open set).

import heapq

def a_star_search(grid, start, goal):
    """
    Finds the shortest path from start to goal in a grid using A*.
    grid[row][col] = 0 for free, 1 for obstacle.
    """
    rows, cols = len(grid), len(grid[0])
    open_set = []
    heapq.heappush(open_set, (0, start)) # (f_score, node)
    
    came_from = {}
    g_score = { (r, c): float('inf') for r in range(rows) for c in range(cols) }
    g_score[start] = 0
    
    f_score = { (r, c): float('inf') for r in range(rows) for c in range(cols) }
    f_score[start] = heuristic(start, goal)

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

        if current == goal:
            return reconstruct_path(came_from, current)

        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]: # Neighbors
            neighbor = (current[0] + dr, current[1] + dc)

            if not (0 <= neighbor[0] < rows and 0 <= neighbor[1] < cols):
                continue
            if grid[neighbor[0]][neighbor[1]] == 1: # Obstacle
                continue

            tentative_g_score = g_score[current] + 1 # Cost is 1 for each step
            
            if tentative_g_score < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)
                if neighbor not in [i[1] for i in open_set]:
                    heapq.heappush(open_set, (f_score[neighbor], neighbor))
    
    return None # No path found

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

def reconstruct_path(came_from, current):
    path = [current]
    while current in came_from:
        current = came_from[current]
        path.append(current)
    return path[::-1]

# Example Usage:
# grid = [[0, 0, 0, 1], [1, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 0]]
# start = (0, 0)
# goal = (3, 3)
# path = a_star_search(grid, start, goal)
# print(path)

In a framework like LangGraph, you could wrap this logic in a planner node. This node would receive a complex goal, model it as a graph, and use A* to produce a step-by-step plan for other nodes to execute.

6. Comparisons & Tradeoffs

AlgorithmOptimalityCompletenessSpeed/ComplexityKey Feature
A Search*Yes (if h is admissible)YesFast (depends on h)Balances cost-so-far and estimated cost.
Dijkstra’sYesYesSlowerExplores blindly. A* with h=0.
Greedy BFSNoNoVery FastOnly uses heuristic h. Can be trapped.
Breadth-First (BFS)Yes (unweighted)YesSlowExplores level by level.

Limitations:

7. Latest Developments & Research

While A* is over 50 years old, it’s far from obsolete. Research continues to adapt it for modern challenges:

8. Cross-Disciplinary Insight

The core idea of A*—guided search—is universal.

9. Daily Challenge / Thought Exercise

Your task is to build an AI agent that can make a cup of tea.

Your 30-minute challenge:

  1. Model this as a search problem. What are the nodes and edges of your graph?
  2. Define an admissible heuristic h(n) for this problem. An admissible heuristic never overestimates the true cost. (Hint: Think about the minimum number of essential actions remaining to reach the goal from any given state).
  3. Sketch out the first 3-4 steps of the A* search starting from (False, False, False, False, False). Which node does A* expand first?

10. References & Further Reading

../