AI Notes
Master Uniform Cost Search for AI pathfinding. Learn UCS algorithm, weighted graph traversal, Dijkstra comparison, and implementation with priority queues. Complete BTech guide 2024.
Introduction
Uniform Cost Search (UCS) is a graph traversal algorithm that finds the shortest path in weighted graphs by always expanding the node with the lowest cumulative path cost. While BFS finds the shallowest goal (optimal only when all edges have equal weight), UCS handles arbitrary non-negative edge weights, guaranteeing the cheapest path to the goal.
UCS is essentially Dijkstra's algorithm applied to goal-directed search. The key difference from BFS: instead of a FIFO queue, UCS uses a priority queue ordered by the path cost g(n)—the total cost from the start to node n. This seemingly simple change transforms BFS from a depth-counting algorithm into a true cost-minimizing search.
In the context of AI search, UCS serves as the bridge between uninformed search (no heuristic) and informed search (A*). Understanding UCS deeply makes A* trivial: A* is just UCS with f(n) = g(n) + h(n) replacing plain g(n).
Algorithm
Evaluation Function
UCS uses: f(n) = g(n)
Where g(n) is the total cost of the path from the start state to node n. No heuristic is used—UCS is an uninformed strategy that happens to guarantee optimality.
Pseudocode
function Uniform_Cost_Search(problem):
node ← Node(state=problem.initial, path_cost=0)
frontier ← PriorityQueue ordered by path_cost
frontier.insert(node)
explored ← empty set
while frontier is not empty:
node ← frontier.extract_min() // cheapest path_cost
if problem.is_goal(node.state):
return node.solution() // GOAL TEST ON EXPANSION
explored.add(node.state)
for each action in problem.actions(node.state):
child ← child_node(problem, node, action)
if child.state not in explored and child not in frontier:
frontier.insert(child)
elif child in frontier with higher path_cost:
frontier.replace(child) // cheaper path found
return failureCritical detail: UCS applies the goal test when a node is *expanded* (popped from the queue), not when it's *generated* (added to the queue). This ensures optimality—a goal node might be generated via an expensive path before a cheaper path reaches it.
Complete Worked Example
Problem Setup
| S ------ | A ------→ G |
| B ------ | C ------→ D |
| Edges: S | A:2, S→B:1, A→G:3, B→C:3, C→A:1, C→D:1, D→G:1 |
Step-by-Step Trace
| STEP 1 | Initialize |
| Frontier | {S[g=0]} |
| Explored | {} |
| Child A | g = 0+2 = 2 |
| Child B | g = 0+1 = 1 |
| Frontier | {B[g=1], A[g=2]} |
| Explored | {S} |
| STEP 2 | Expand B (g=1) — cheapest |
| Child C | g = 1+3 = 4 |
| Frontier | {A[g=2], C[g=4]} |
| Explored | {S, B} |
| STEP 3 | Expand A (g=2) — cheapest |
| Child G | g = 2+3 = 5 |
| Frontier | {C[g=4], G[g=5]} |
| Explored | {S, B, A} |
| STEP 4 | Expand C (g=4) — cheapest (NOT G yet!) |
| Child A | already explored, skip |
| Child D | g = 4+1 = 5 |
| Frontier | {G[g=5], D[g=5]} |
| Explored | {S, B, A, C} |
| STEP 5 | Expand G (g=5) or D (g=5) — tie, say G first |
| G is GOAL | return path S→A→G, cost=5 |
| Wait — but D | G costs 1, so path S→B→C→D→G = 1+3+1+1 = 6 > 5 |
| So S | A→G (cost 5) IS optimal. ✓ |
Alternative Scenario (Showing Why Goal Test on Expansion Matters)
Suppose we change A→G to cost 10:
| STEP 3 | Expand A (g=2) |
| Child G | g = 2+10 = 12 |
| Frontier | {C[g=4], G[g=12]} |
| STEP 4 | Expand C (g=4) |
| Child D | g = 4+1 = 5 |
| Frontier | {D[g=5], G[g=12]} |
| STEP 5 | Expand D (g=5) |
| Child G: g = 5+1 = 6 < current 12 | UPDATE G to g=6 |
| Frontier | {G[g=6]} |
| STEP 6: Expand G (g=6) — GOAL! Path: S | B→C→D→G, cost=6 ✓ |
If we had tested for goal when G was *generated* (Step 3), we'd have returned the expensive path (cost 12). Testing on *expansion* ensures we always find the cheapest path.
Properties
| Property | Analysis |
|---|---|
| Complete | Yes, if all edge costs ≥ ε > 0 (prevents infinite zero-cost loops) |
| Optimal | Yes, always finds cheapest path |
| Time | O(b^(1 + ⌊C*/ε⌋)) where C* = optimal cost, ε = minimum edge cost |
| Space | O(b^(1 + ⌊C*/ε⌋)) — stores all nodes with g(n) ≤ C* |
The complexity depends on the ratio of optimal cost to minimum edge cost, not on the number of nodes or depth. This means UCS is efficient when edge costs are large relative to the optimal path, but expensive when there are many tiny-cost edges.
UCS vs. BFS vs. Dijkstra
BFS vs. UCS
| BFS: All edges cost 1? | BFS = UCS (and BFS is simpler) |
| Variable edge costs? | BFS may find suboptimal paths |
| Example: S | A (cost 1) → G (cost 10) = 11 |
| S | B (cost 5) → G (cost 2) = 7 |
| BFS finds S | A→G (cost 11) first (shallower) |
| UCS finds S | B→G (cost 7) first (cheaper) |
Dijkstra vs. UCS
Dijkstra's algorithm computes shortest paths to ALL nodes from the source. UCS stops as soon as the goal is expanded—it's goal-directed Dijkstra. For single-target pathfinding, UCS is more efficient because it can terminate early.
Implementation Considerations
Priority Queue with Decrease-Key
When a cheaper path to a frontier node is found, we need to update its priority:
The "lazy deletion" approach pushes duplicate entries and ignores stale ones when popped. This avoids the complexity of decrease-key operations.
Common Applications
- GPS navigation: Finding cheapest route considering distance, time, or fuel
- Network routing: Minimum-cost packet forwarding (OSPF protocol)
- Resource allocation: Minimizing total cost in planning problems
- Game AI: Finding cheapest movement path with terrain costs
Interview Questions
Q: Why can't UCS handle negative edge weights? A: UCS assumes that once a node is expanded, no cheaper path exists. Negative edges violate this—a longer path with negative edges could be cheaper. Use Bellman-Ford for negative weights.
**Q: What is UCS's relationship to A*?** A: UCS is A* with h(n) = 0 for all nodes. A* adds heuristic guidance to focus expansion toward the goal, potentially expanding far fewer nodes while maintaining optimality.
Q: When does UCS degenerate to BFS? A: When all edge costs are equal (say, all = 1). The priority queue then orders by depth, making UCS equivalent to BFS. In this case, BFS is preferred since FIFO queues are cheaper than priority queues.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Uniform Cost Search (UCS) - AI Weighted Graph Algorithm.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Artificial Intelligence topic.
Search Terms
artificial-intelligence, artificial intelligence, artificial, intelligence, search, algorithms, uniform, cost
Related Artificial Intelligence Topics