Section 3.3 The A* Algorithm: Balancing Past Cost and Future Estimation

The A* (A-Star) algorithm is one of the most popular pathfinding algorithms in mobile robotics. It balances how far you’ve already traveled with an estimate of how far is left to go.

For any candidate cell \(n\text{,}\) A* combines two numbers into a single total score \(f(n) = g(n) + h(n)\text{:}\) \(g(n)\text{,}\) the distance already traveled from the start to \(n\text{,}\) and \(h(n)\text{,}\) the estimated distance remaining from \(n\) to the goal.

Subsection 3.3.1 The A* Cost Formula

For every candidate cell \(n\) on the map, A* calculates a total cost score \(f(n)\text{:}\)

\begin{equation*} f(n) = g(n) + h(n) \end{equation*}

\(g(n)\) (Exact Path Cost): The actual cost (distance or steps) taken to move from the start position to current cell \(n\text{.}\)
\(h(n)\) (Heuristic Cost): The estimated cost to travel from cell \(n\) to the goal position.
\(f(n)\) (Total Priority Cost): A* always expands the cell with the lowest \(f(n)\) score next!

Figure 3.3.1. A* pathfinding balances the known cost from the start with the estimated cost to the goal as it searches for an efficient route.

Subsection 3.3.2 Intuition: Why A* Beats Breadth-First or Greedy Search

If we only used \(g(n)\text{,}\) the search would expand in all directions equally like ripples in water (Dijkstra’s Algorithm), wasting time searching away from the goal.
If we only used \(h(n)\text{,}\) the search would head blindly toward the goal (Greedy Best-First), often getting trapped in dead-end obstacles.
Combining \(g(n) + h(n)\) ensures A* finds the shortest overall path efficiently!

Subsection 3.3.3 Section 3.3 Interactive Exercises

Subsubsection 3.3.3.1 Exercise 3.3.2: Parsons Problem — A* Main Loop Steps

Reorder the core steps of the main A* search loop in logical sequence.

Checkpoint 3.3.2.

Arrange the blocks to form the main A* search loop, which repeatedly pops the lowest-\(f\)-score cell from the open list, checks whether it is the goal, and otherwise expands its unvisited neighbors.

while open_list is not empty:
---
    # Step 1: Select cell with lowest f-score
    current = pop_lowest_f_score(open_list)
---
    # Step 2: Check if target reached
    if current == goal:
        return reconstruct_path(current)
---
    # Step 3: Move current cell to processed list
    closed_list.add(current)
---
    # Step 4: Explore adjacent unvisited neighbors
    for neighbor in get_valid_neighbors(grid, current):
        if neighbor in closed_list:
            continue
---
        # Step 5: Update costs and add neighbor to open list
        tentative_g = g_score[current] + 1
        if tentative_g < g_score[neighbor]:
            g_score[neighbor] = tentative_g
            f_score[neighbor] = tentative_g + h(neighbor, goal)
            open_list.add(neighbor)

Reading Questions 3.3.4 Reading Questions

Check your understanding

1. Exercise 3.3.1: A* Cost Score Calculation.

An A* search algorithm is deciding which of two frontier cells to expand next:

Cell A: \(g(\text{Cell A}) = 3\text{,}\) \(h(\text{Cell A}) = 2\)
Cell B: \(g(\text{Cell B}) = 5\text{,}\) \(h(\text{Cell B}) = 1\)

Which cell will A* explore first, and why?

Cell A will be evaluated first because its \(g(n)\) is lower.
Incorrect. A* does not look at \(g(n)\) in isolation.
Cell B will be evaluated first because its \(h(n)\) is lower.
Incorrect. A* does not look at \(h(n)\) in isolation.
Cell A will be evaluated first because its total \(f(n)\) cost is lower (5 vs 6).
Correct! \(f(\text{Cell A}) = 3 + 2 = 5\text{,}\) while \(f(\text{Cell B}) = 5 + 1 = 6\text{.}\) A* always picks the cell with the lowest total \(f(n)\) score.
Both cells have equal priority.
Incorrect. Their total \(f(n)\) scores are 5 and 6, which are not equal.

You have attempted of activities on this page.

Prev Top Next