COMP 3200 - Intro to Artificial Intelligence - Lecture 05 - Heuristic Search + A* Algorithm

Overview

Dave Churchill introduces informed heuristic search and develops A* as a pathfinding algorithm that selects the open-list node minimizing f(n) = g(n) + h(n). He explains when A* is complete and optimal, distinguishes admissible heuristics from the stricter consistency requirement for graph search, and demonstrates how heuristic weighting trades search effort for solution quality.

Key takeaways

A* ranks nodes using f(n) = g(n) + h(n), balancing the path cost already paid against an estimate of the remaining cost.
A* tree search is optimal with an admissible heuristic, but A* graph search with a closed list needs a consistent heuristic to guarantee an optimal route.
Heuristic admissibility depends on the legal actions: Manhattan distance is admissible for four-direction movement, while diagonal movement calls for an estimate such as octile distance.
Weighted A* uses f(n) = g(n) + W·h(n); increasing W usually cuts node expansions while sacrificing the guarantee of an optimal solution.
In the demonstrated cave map, standard A* and uniform-cost search both found a path costing 16,298, while greedy best-first search returned a costlier path of 18,836.

Chapters

0:00 Informed Search Uses Problem Knowledge to Guide Exploration

Unlike uninformed breadth-first search, informed search uses problem-specific knowledge to prioritize promising states.
A heuristic is a function that estimates which direction leads toward a goal and can reduce the number of expanded nodes.
The extra computation for a heuristic is worthwhile only when it saves more search effort than it costs.

3:30 Best-First Search Selects Nodes by an Evaluation Function

Best-first search keeps the general tree-search framework but removes the open-list node with the smallest evaluation value f(n).
A priority queue can retrieve a minimum-f node efficiently, though an array or other structure can implement the same selection rule.
“Best-first” means best according to the chosen estimate, not guaranteed to be the globally best path.

6:30 Heuristic Functions Estimate Remaining Cost to the Goal

The heuristic h(n) estimates the cost of an optimal path from node n to a goal; by definition, h(goal) = 0.
Euclidean distance estimates straight-line distance, while Manhattan distance estimates travel along a four-direction grid.
Obstacles can make either estimate inaccurate; closer estimates can guide search better, but no simple distance measure works perfectly in every map.

12:55 Greedy Best-First Search Follows the Heuristic Alone

Greedy best-first search sets f(n) = h(n), choosing the open-list node that appears closest to the goal.
On an uncomplicated grid, this can find a route while expanding far fewer states than breadth-first search.
Obstacles can mislead the heuristic, forcing detours; without safeguards such as a closed list, tree search can loop or fail to find a goal.
Greedy best-first search is generally neither complete nor optimal, and its worst-case time complexity is comparable to depth-first search.

19:20 Admissible Heuristics Never Overestimate the True Cost

A heuristic is admissible when h(n) ≤ h*(n), where h*(n) is the true optimal remaining cost; it is an optimistic estimate.
Euclidean distance is admissible because a straight line cannot exceed the length of a valid route, and an always-zero heuristic is also admissible.
Manhattan distance is admissible for four-direction movement, but can overestimate when diagonal moves are allowed.
Octile (diagonal Manhattan) distance is appropriate for eight-direction movement and remains admissible when movement is restricted to four directions.

28:00 A* Combines Cost So Far with Estimated Remaining Cost

A* sets f(n) = g(n) + h(n), combining the cost already incurred, g(n), with the estimated cost to the goal, h(n).
The algorithm repeatedly removes the open-list node with minimum f; the main change from greedy best-first search is adding g(n).
With tree search, A* is complete and is optimal when h is admissible.

32:10 Consistency Makes A* Graph Search Optimal

An admissible heuristic alone does not guarantee optimality for A* graph search with a closed list, because an early, worse route to a repeated state may cause the better route to be discarded.
Consistency requires h(a) ≤ cost(a,b) + h(b), so the heuristic difference between neighboring states cannot exceed the transition cost.
Consistent heuristics are also admissible; consistency makes f-values nondecreasing along paths and ensures the first goal removed from the open list is optimal.
Manhattan distance for four-direction grids and octile distance for eight-direction grids satisfy consistency under their matching movement costs.

40:18 A* Graph Search, Algorithm Comparisons, and Open-List Pruning

A* graph search adds a closed list of states to the tree-search algorithm and expands each closed state at most once.
The same search framework yields A* with f = g + h, greedy best-first with f = h, uniform-cost search with f = g, breadth-first search with a queue, and depth-first search with a stack.
Checking whether a generated child is already closed can avoid unnecessary open-list entries and save memory.
A further optional optimization skips a new route to a state when the open list already contains a cheaper route, but checking the entire open list can be costly.

49:03 A*’s Optimal Efficiency and Remaining Memory Costs

With a consistent heuristic, A* graph search expands all nodes with f-values below the optimal solution cost, then can stop when it removes the first goal.
For a given heuristic, A* is optimally efficient in the sense that no other algorithm is guaranteed to expand fewer nodes while preserving the optimal solution.
A* can still require exponential time or memory as solution depth grows, making vanilla A* impractical for some large problems.

53:12 Grid-World A* Example: States, Costs, and Heuristic Values

Churchill’s hand-worked map uses light-gray traversable tiles, dark-gray obstacles, and eight-direction movement.
Cardinal moves cost 100 and diagonal moves cost 141; each open-list node records its state, g, h, f, action, and parent.
The start state begins with g = 0, and its heuristic uses diagonal Manhattan distance to estimate the remaining route.

58:55 Tracing A* Through the Open and Closed Lists

After expanding the start, A* adds legal neighboring states to the open list and places the start state on the closed list.
At each iteration, it selects the smallest-f node, closes its state, and generates legal children while ignoring closed states.
Different paths can reach the same state with different g-costs; keeping the cheaper open-list route avoids wasting space on a dominated route.
A node enters the closed list only after its cheapest route is established under the consistent-heuristic condition.

1:04:13 A* Confirms the Best Route Only When the Goal Is Removed

Generating a goal child does not prove that its route is optimal; A* must first place it on the open list and later remove it as the minimum-f node.
With a consistent heuristic, the goal’s removal confirms that no cheaper unresolved path remains.
Parent pointers let the algorithm reconstruct the final path from the goal back to the start.

1:06:53 Weighted A* Tunes Trust in the Heuristic

Weighted A* uses f(n) = g(n) + W·h(n), with W controlling how strongly the heuristic influences node selection.
W = 1 gives standard A*, W = 0 gives uniform-cost search, and very large W approaches greedy best-first behavior.
Increasing W generally reduces the number of expanded nodes but can produce a suboptimal path.

1:10:00 Search-Demo Results Show the Speed–Optimality Tradeoff

In Churchill’s search demo, breadth-first search expands outward by depth, while uniform-cost search forms a cost-based wavefront from the start.
On the cave map, greedy best-first search found a route costing 18,836, while A* found the optimal cost of 16,298; uniform-cost search matched A* but expanded more nodes.
A heuristic weight of 1.5 reduced expansions from about 4,200 to 1,300 in the example, but the resulting route was no longer guaranteed optimal.
As the weight rises toward infinity, search approaches greedy best-first: fewer nodes are explored, while suboptimality becomes more likely.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, Dave Churchill.