A* Search for Optimal Pathfinding

Hello! Welcome to your second lesson in the "Artificial Intelligence: Search and Reasoning" module.

In our previous lesson, we established the crucial first step in AI problem-solving: formulation. You learned how to take a real-world goal and translate it into a formal state-space search problem with an initial state, actions, a transition model, a goal test, and path costs.

Now that we can define a problem, how do we find the best solution? Today, we will explore one of the most celebrated and effective algorithms for this task. Our learning outcome is to implement the A search algorithm to find the optimal path in a weighted graph*. A* is the secret sauce behind many applications, from GPS navigation in Google Maps to character pathfinding in video games.

1. The Best of Both Worlds: Why A* is Special

Imagine you're trying to find the shortest route from one city to another. You could use a few different strategies:

Greedy Approach: At every intersection, you choose the road that seems to point most directly toward your final destination, ignoring the actual distance you've traveled. This is fast but might lead you down a long, winding path that looked promising at first.
Conservative Approach (Uniform Cost Search): You meticulously explore all paths, expanding outwards from your starting point, always extending the shortest path found so far. This guarantees you'll find the best route, but it's very slow because you waste a lot of time exploring in the wrong direction.

Neither of these is ideal. We want an algorithm that is both smart (like the greedy approach) and optimal (like the conservative one). This is exactly what A* provides.

To build an intuition for this, let's watch a video that introduces these concepts and shows how A* emerges as the perfect middle ground.

A* Search: How Your Map Applications Find Shortest Routes

This video from the Reducible channel provides an excellent visual and conceptual build-up to A* search. It explains the limitations of simpler algorithms and introduces A* as an intelligent combination of their strengths.

Watch the video from the beginning until 08:42. Pay close attention to: How a map routing problem is modeled as a graph. The limitation of the 'greedy' approach. The limitation of 'uniform cost search'. How A* is introduced as a combination of the two.

2. The A* Evaluation Function: $f (n) = g (n) + h (n)$

As the video explained, A* achieves its balance by combining two key pieces of information into a single evaluation function, $f (n)$ . For any given node (or state) $n$ in our graph, this function estimates the total cost of a path from the start to the goal that goes through n.

The formula is elegantly simple:
$f (n) = g (n) + h (n)$

Let's break this down:

$g (n)$ : The actual cost of the path from the starting node to node $n$ . This is the "uniform cost search" part—it's what we know for sure based on the path we've already taken.
$h (n)$ : The estimated cost (or heuristic) from node $n$ to the goal node. This is the "greedy" part—it's our intelligent guess about the remaining distance.

A* Search Algorithm Cost Function Explained — This diagram illustrates the core idea of A*. The total estimated cost of a path through node 'n', denoted by f(n), is the sum of the actual cost to get to 'n' (g(n)) and the estimated cost from 'n' to the goal (h(n)).

The A* algorithm works by always choosing to explore the node with the lowest $f (n)$ value. This means it prioritizes paths that are not only cheap so far ( $g (n)$ is low) but also seem promising for the future ( $h (n)$ is low).

To manage this process, A* uses two main data structures:

Open List: A list of nodes that have been discovered but not yet evaluated. This is typically implemented as a priority queue, which is crucial for efficiently getting the node with the lowest $f (n)$ value.
Closed List: A list of nodes that have already been evaluated. This prevents the algorithm from re-visiting nodes and getting stuck in cycles.

You can read a concise summary of these key concepts in the following article.

The A* Algorithm: A Complete Guide

This article, 'The A* Algorithm: A Complete Guide' from DataCamp, provides clear definitions for the cost functions and the open/closed lists.

Read the section 'Key Concepts in A* Search' to solidify your understanding of g(n), h(n), f(n), and the open and closed lists.

3. A* in Action: A Step-by-Step Example

Let's trace the algorithm on a concrete example to see how it works. We will use the graph below. The number on each edge is the actual cost ( $g$ ), and the table provides the heuristic values ( $h$ ) for each node. Our goal is to find the optimal path from S to G.

A* Search Algorithm Problem on a Weighted Graph — A weighted graph with nodes S, A, B, C, D, and G. Edge weights are given on the connections, and a table of heuristic values h(n) is provided for each node.

We'll maintain our Open List (a priority queue ordered by f-cost) and a Closed List.

Step 1:

Start at S. Calculate $f (S) = g (S) + h (S) = 0 + 5 = 5$ .
Add S to the Open List: Open = [(S, f=5)]
Closed = []

Step 2:

Pop the node with the lowest f-cost from Open: S. Move it to Closed.
Open = [], Closed = [S]
Explore neighbors of S: A and D.
For A: $g (A) = g (S) + cos t (S, A) = 0 + 1 = 1$ . $h (A) = 7$ . So, $f (A) = 1 + 7 = 8$ .
For D: $g (D) = g (S) + cos t (S, D) = 0 + 4 = 4$ . $h (D) = 1$ . So, $f (D) = 4 + 1 = 5$ .
Add A and D to the Open List: Open = [(D, f=5), (A, f=8)]. (D is first because it has a lower f-cost).

Step 3:

Pop D from Open. Move it to Closed.
Open = [(A, f=8)], Closed = [S, D]
Explore neighbors of D: B and G.
For B: $g (B) = g (D) + cos t (D, B) = 4 + 3 = 7$ . $h (B) = 2$ . So, $f (B) = 7 + 2 = 9$ .
For G: $g (G) = g (D) + cos t (D, G) = 4 + 5 = 9$ . $h (G) = 0$ . So, $f (G) = 9 + 0 = 9$ .
Add B and G to the Open List: Open = [(A, f=8), (B, f=9), (G, f=9)]. (A is now first).

Step 4:

Pop A from Open. Move it to Closed.
Open = [(B, f=9), (G, f=9)], Closed = [S, D, A]
Explore neighbors of A: B and C.
For B: We have a new path to B through A. Let's check its cost. $g (B)_{n e w} = g (A) + cos t (A, B) = 1 + 2 = 3$ .
- This new g-cost (3) is better than the old g-cost we found for B (7). So we update B!
- New $f (B) = g (B)_{n e w} + h (B) = 3 + 2 = 5$ .
For C: $g (C) = g (A) + cos t (A, C) = 1 + 4 = 5$ . $h (C) = 3$ . So, $f (C) = 5 + 3 = 8$ .
Update B and add C to the Open List. The Open List is re-sorted: Open = [(B, f=5), (C, f=8), (G, f=9)].

Step 5:

Pop B (with its new low f-cost of 5). Move it to Closed.
Open = [(C, f=8), (G, f=9)], Closed = [S, D, A, B]
The only neighbor of B is G.
For G: New path through B. $g (G)_{n e w} = g (B) + cos t (B, G) = 3 + 4 = 7$ .
- This new g-cost (7) is better than the old one (9).
- New $f (G) = 7 + 0 = 7$ .
Update G in the Open list: Open = [(G, f=7), (C, f=8)].

Step 6:

Pop G. We have reached the goal!
The path can be reconstructed by backtracking from G using the parent pointers that we would have stored at each update: G came from B, B came from A, A came from S.
Optimal Path: S -> A -> B -> G
Total Cost: 7

Test your understanding!

In Step 4, we found a new, better path to node B via node A. Why didn't we just stop exploring from D and immediately switch to A in Step 3, since A's edge cost from S (1) was less than D's (4)?

Show answer

Because A* doesn't just look at the cost-so-far ( $g (n)$ ), it looks at the total estimated cost ( $f (n)$ ). In Step 2, even though the path to A was cheaper ( $g (A) = 1$ ), its high heuristic value made it seem like a less promising overall path ( $f (A) = 8$ ). The path to D, while more expensive initially ( $g (D) = 4$ ), seemed much more promising because it was estimated to be very close to the goal ( $f (D) = 5$ ). A* correctly chose to explore the more promising path via D first. It was only later, after exploring from A, that it discovered a "shortcut" to B. This demonstrates the power of the $f (n)$ function in guiding the search.

4. The Importance of an Admissible Heuristic

A* is guaranteed to find the shortest path, but only if the heuristic function, $h (n)$ , has a special property: it must be admissible.

An admissible heuristic is one that never overestimates the actual cost to reach the goal. It's an "optimistic" estimate.

In our route-finding example, the straight-line distance (Euclidean distance) between a city and the destination is an admissible heuristic, because the shortest possible road path can never be shorter than a straight line.
A heuristic of $h (n) = 0$ for all nodes is also admissible (but useless!). If we use it, A* becomes identical to the slow but optimal Uniform Cost Search.

If you use a non-admissible heuristic that overestimates the cost, you lose the guarantee of finding the optimal path. A* might be faster, but it could return a suboptimal solution.

5. Implementing A* in Python

Now it's time to translate this logic into code. Your learning outcome is to implement the algorithm, and we'll do this for a common scenario: finding a path on a 2D grid with obstacles.

The following resource provides a complete, step-by-step Python implementation. Since you are building foundational coding skills, I encourage you to read through it carefully and even type it out yourself to get a feel for how the pieces connect.

The A* Algorithm: A Complete Guide

We will now use the DataCamp article again, this time focusing on its excellent Python implementation. It breaks the code down into logical steps, making it easy to follow.

Read the sections 'A* Search Algorithm Pseudocode' and 'Python Implementation of A* Algorithm'. Focus on understanding: The Pseudocode: This is the blueprint for our code. find_path function: This is the main A* logic. Notice the while open_list: loop. heapq library: This is Python's implementation of a priority queue, used for our open_list. Data Structures: See how open_list (a list of tuples), open_dict (a dictionary for quick lookups), and closed_set (a set) are used together. Path Updates: Look for the elif tentative_g < open_dict[neighbor_pos]['g']: block. This is where the algorithm finds a better path to an existing node, just like we did for node B in our manual trace.

This implementation uses numpy for the grid and matplotlib for visualization, both of which are standard tools in data science and AI. The use of Python's heapq module is a practical and efficient way to manage the priority queue, a core component of many important algorithms.

Conclusion

Congratulations! You have delved into one of the most fundamental algorithms in AI. By understanding and implementing A*, you've gained a powerful tool for solving a wide class of optimization and pathfinding problems.

Key Takeaways:

A* search intelligently finds the shortest path by balancing the actual cost-so-far ( $g (n)$ ) and an estimated cost-to-go ( $h (n)$ ).
The core of the algorithm is the evaluation function: $f (n) = g (n) + h (n)$ .
It uses a priority queue (the open list) to always explore the most promising node next.
For A* to be optimal (guarantee the shortest path), its heuristic function $h (n)$ must be admissible (never overestimate the true cost).
The implementation involves managing open and closed lists, updating node costs when better paths are found, and reconstructing the path at the end.

Preview of the Next Lesson:

We've now seen how to solve pathfinding problems. However, not all AI problems are about finding a path. What about problems like solving a Sudoku puzzle, scheduling exams without conflicts, or designing a floor plan? These problems are less about a sequence of moves and more about assigning values to variables under a set of rules.

In the next lesson, we will explore a different but equally powerful way of thinking about problems by learning to formulate them as Constraint Satisfaction Problems (CSPs).

Recommended resources