A* Search Algorithm

Introduction

A* combines benefits of Dijkstra's algorithm (optimal pathfinding) and greedy best-first search (efficiency via heuristics). Uses estimated cost to goal h(n) to guide search toward target. If h(n) admissible (never overestimates), A* guarantees optimal path.

Ubiquitous in pathfinding: video game AI (NPCs navigating maps), GPS navigation, robotics (motion planning), network routing. Gold standard for single-source shortest path with heuristic guidance.

Key insight: Dijkstra expands nodes by actual cost, greedy expands by estimated cost to goal. A* balance: expand by f(n) = g(n) + h(n) (actual cost so far + estimated remaining cost). Prioritizes promising paths without sacrificing optimality.

"A* is the best algorithm for finding optimal paths when heuristics available. Combines optimality guarantee with efficient pruning via heuristic estimates." -- Artificial Intelligence textbooks

Informed Search and Heuristics

Uninformed vs. Informed

Uninformed (blind): BFS, DFS, Dijkstra explore based on graph structure only. No knowledge of goal location. Inefficient for large graphs.

Informed: use heuristic (estimated cost to goal) h(n) to guide search. Prioritize nodes appearing closer to goal. Much more efficient when good heuristic available.

Heuristic Function h(n)

Estimate of cost from node n to goal. Must be non-negative: h(n) >= 0. Goal state: h(goal) = 0.

Examples:
- Straight-line distance (A to B) for path planning
- Manhattan distance |x1-x2| + |y1-y2| for grid navigation
- Number of misplaced tiles in 8-puzzle
- Remaining fuel for vehicle routing

Greedy Best-First

Expand node with lowest h(n) (greedy toward goal). Fast but not optimal. May choose suboptimal paths if heuristic misleading.

Cost Function: g(n) + h(n)

Components

g(n) = actual cost from start to node n. h(n) = estimated cost from n to goal.

f(n) = g(n) + h(n) = estimated total cost of path through n.

Example (path planning):
Start A, Goal G. Consider node B.
g(B) = distance from A to B (actual: 5)
h(B) = estimated distance from B to G (15)
f(B) = 5 + 15 = 20

A* expands node with lowest f value next.

Why This Works

g(n) ensures considering cost actually incurred. h(n) biases toward goal. Together: expand most promising paths (low g: inexpensive so far, low h: close to goal).

Comparison with Dijkstra

Dijkstra: expand by g(n) only (no heuristic). A*: expand by g(n) + h(n) (with heuristic). For equal h(n), A* reduces to Dijkstra.

A* Algorithm Details

Pseudocode

def a_star(start, goal, heuristic, graph):
 open_set = PriorityQueue() # Nodes to expand
 open_set.add(start, f=heuristic(start))

 came_from = {} # For path reconstruction
 g_score = {start: 0} # Cost from start

 closed_set = set() # Expanded nodes

 while not open_set.empty():
 current = open_set.pop() # Lowest f value

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

 closed_set.add(current)

 for neighbor in graph[current]:
 if neighbor in closed_set:
 continue

 tentative_g = g_score[current] + cost(current, neighbor)

 if neighbor not in g_score or tentative_g < g_score[neighbor]:
 came_from[neighbor] = current
 g_score[neighbor] = tentative_g
 f_score = tentative_g + heuristic(neighbor)
 open_set.add(neighbor, f=f_score)

 return None # No path found

Data Structures

• open_set: priority queue (min-heap on f value)
• closed_set: visited nodes (prevent re-expansion)
• g_score: actual cost from start to each node
• came_from: parent pointers for path reconstruction

Admissible Heuristics

Definition

Heuristic h(n) admissible if never overestimates: h(n) <= actual_cost(n, goal) for all n.

Example: straight-line distance in map
- Straight line shortest distance between two points
- Actual path (roads) always >= straight line
- Therefore: h(n) <= actual_cost(n, goal)
- Admissible!

Optimality Guarantee

If h(n) admissible, A* guarantees finding optimal path. Proof: when goal expanded, must be via optimal path (any suboptimal path has f >= optimal, so would be expanded first).

Examples

Consistency and Monotonicity

Consistency Definition

Heuristic h(n) consistent if h(n) <= cost(n, successor) + h(successor) for all successors. Ensures triangle inequality.

Intuition: estimated cost to goal from n should not exceed one step cost plus estimated cost from successor.

Consistency implies Admissibility

Consistent heuristics admissible (but not vice versa). Consistency stronger condition.

Advantage of Consistency

Consistent heuristics: each node expanded once (g_score never decreases for same node). Allows removing closed_set, saving memory. Non-consistent may re-expand nodes.

Example

Euclidean distance in grid:
h(A) = distance(A, goal)
h(successor) = distance(successor, goal)

Triangle inequality: distance(A, successor) + distance(successor, goal) >= distance(A, goal)
Therefore: cost(A, successor) + h(successor) >= h(A)
Consistent!

Optimality Proof

Theorem

If h(n) admissible, A* finds optimal path.

Proof Sketch

Suppose A* returns path of cost C, but optimal path cost C* < C. Let n be any node on optimal path not yet expanded. Then:

f(n) = g(n) + h(n)
 <= C* + 0 (g(n) <= C*, h(n) <= 0 at goal)
 < C (by assumption C* < C)

Since A* always expands lowest f value, would expand n before returning C.
Contradiction! Therefore C* must be optimal.

Implications

A* optimality depends on h(n) being admissible. Non-admissible heuristics may find suboptimal paths. Trade-off: inadmissible heuristics faster but lose optimality.

Common Heuristics

Manhattan Distance

h(n) = |x_n - x_goal| + |y_n - y_goal|

Grid-based movement (4 directions). Admissible when each step costs 1.
Used in puzzle solving, grid navigation.

Euclidean Distance

h(n) = sqrt((x_n - x_goal)^2 + (y_n - y_goal)^2)

Geometric distance. Admissible for any movement (diagonal costs sqrt(2) in grid).
Used in continuous spaces, route planning.

Chebyshev Distance

h(n) = max(|x_n - x_goal|, |y_n - y_goal|)

Allows 8-direction movement (diagonals). Admissible for 8-connected grids.

Pattern Databases

Precompute optimal costs for subproblems (patterns). h(n) = max cost over all patterns. Admissible, often tighter than simple distances.

Relaxed Problems

Remove constraints from problem (relaxation). Optimal cost of relaxed problem >= actual cost. Use as heuristic. Example: ignoring obstacles in pathfinding gives straight-line distance.

Implementation with Priority Queues

Priority Queue Requirements

A* efficiency depends on priority queue. Need: extract min O(log n), insert O(log n), decrease key O(log n).

Binary Heap

Most common. All operations O(log n). Sufficient for most applications.

Fibonacci Heap

Theoretical improvement: decrease key O(1) amortized. But constants larger, rarely faster in practice.

Implementation Notes

class AStarSearcher:
 def __init__(self, heuristic):
 self.heuristic = heuristic

 def search(self, graph, start, goal):
 # Uses binary heap priority queue
 open_set = MinHeap()
 open_set.insert(start, self.heuristic(start, goal))

 g_score = {start: 0}
 came_from = {}

 while open_set:
 current, _ = open_set.extract_min()
 if current == goal:
 return self._reconstruct_path(came_from, current)

 for neighbor, cost in graph[current]:
 new_g = g_score[current] + cost
 if neighbor not in g_score or new_g < g_score[neighbor]:
 g_score[neighbor] = new_g
 f_score = new_g + self.heuristic(neighbor, goal)
 open_set.insert(neighbor, f_score)

 return None

Time and Space Complexity

Time Complexity

Worst case O(b^d) where b = branching factor, d = depth. Same as uninformed search. Good heuristic reduces nodes explored (practical improvement).

Space Complexity

O(b^d) for open and closed sets. Storing all nodes in memory. Large graphs may exceed memory.

Effective Branching Factor

Metric: effective branching factor b* where b*^d = N (nodes expanded). Good heuristics reduce b*. Examples:

• No heuristic (Dijkstra): b* = actual branching factor
• Good heuristic: b* = 1-2 (nearly optimal path)
• Bad heuristic: b* = original branching factor (no benefit)

Practical Performance

Depends on heuristic quality. With good heuristic, A* dramatically faster than uninformed search (often 100-1000x improvement).

Applications: Game AI, Robotics, GPS

Video Game AI

NPC pathfinding: units navigate maps avoiding obstacles. Heuristic: Euclidean or Manhattan distance to goal. A* finds near-optimal paths efficiently.

GPS Navigation

Route planning: find fastest route between locations. Graph: road network. Edge weights: travel time. Heuristic: straight-line distance to destination. A* much faster than Dijkstra for long routes.

Robotics Motion Planning

Robot navigating obstacle-filled environment. State space: (x, y, orientation). Graph: valid movements. Heuristic: distance to goal ignoring obstacles. A* computes collision-free paths.

Puzzle Solving

8-puzzle, 15-puzzle: find goal state from initial configuration. Heuristic: number of misplaced tiles or Manhattan distance of tiles. A* finds solution efficiently.

Network Routing

Routers find paths for data packets. Edge weights: latency. Heuristic: geographic distance or hop count estimate. A* optimizes routing decisions.

Game Theory

Minimax with alpha-beta pruning uses heuristic evaluation. A* variant explores game tree, prioritizing promising branches.

References

• Hart, P. E., Nilsson, N. J., and Raphael, B. "A Formal Basis for the Heuristic Determination of Minimum Cost Paths." IEEE Transactions on Systems Science and Cybernetics, vol. 4, no. 2, 1968.
• Russell, S. J., and Norvig, P. "Artificial Intelligence: A Modern Approach." Prentice Hall, 4th edition, 2020.
• Korf, R. E. "Depth-First Iterative Deepening: An Optimal Admissible Tree Search." Artificial Intelligence, vol. 27, 1985.
• Nilsson, N. J. "Principles of Artificial Intelligence." Tioga Publishing, 1980.
• Pohl, I. "Heuristic Search Viewed as Path Finding in Graphs." Artificial Intelligence, vol. 1, 1970.