2 Search and Problem Solving

Formulate the problem

A search problem describes how an agent can move from its current situation to a desired one. A solution, often called a plan, is a sequence of actions from the start state to a goal state. Rather than trying every possible sequence, a search algorithm represents the problem and explores possible states in a chosen order.

A complete formulation identifies:

• State space: the possible situations relevant to the task.

• Actions: the choices available in each state.

• Transition model: the state produced by taking an action.

• Action cost: the cost of a transition, such as distance, time, or energy.

• Start state: the initial situation.

• Goal test: the rule for deciding whether a state satisfies the objective.

The state representation must preserve enough information to determine what actions are possible and whether the goal has been reached, while excluding irrelevant details. For example, finding a route through a maze may require only the agent’s location. If the task also requires collecting every object, the state must record which objects have already been collected.

Represent states and paths

A State-space graph represents states as nodes and actions as edges. A Search tree represents candidate paths through that graph; a state may appear multiple times in the tree if different paths reach it.

Algorithms typically maintain a Frontier of discovered but not yet expanded paths. Graph search also tracks visited or reached states to avoid repeatedly exploring cycles. This distinction matters because the paths considered in a search tree are not necessarily unique states in the underlying graph.

Choose an uninformed search strategy

Uninformed search uses the problem definition but has no estimate of how close a state is to a goal. Its strategies mainly differ in the order in which they choose paths from the frontier.

Breadth-first search (BFS) expands the shallowest path first, using a first-in, first-out queue. It is useful when each action has the same cost and a solution with the fewest actions is wanted. BFS is complete when the shallowest goal is at finite depth, and it is optimal when all actions have equal cost. It can use substantial memory, and with unequal action costs the shallowest solution need not be the cheapest.

Depth-first search (DFS) expands the deepest path first, using a last-in, first-out stack. It can be useful when memory is limited and exploring a deep solution is acceptable. In spaces with cycles or unbounded depth, it is not generally complete: it can follow a cycle or unbounded path indefinitely. It does not guarantee a least-cost solution.

Uniform-cost search (UCS) expands the path with the smallest accumulated cost so far. It is useful when action costs vary and a least-cost solution is required. UCS is complete and finds a least-cost solution when step costs are nonnegative and bounded away from zero, but it may explore many low-cost paths before reaching a goal.

Guide search with heuristics

Informed search uses additional guidance about the likely distance to a goal. A Heuristic, written $h(n)$, estimates the remaining cost from state $n$ to a goal. The estimate helps prioritize paths, but it is not necessarily the actual remaining cost.

Greedy best-first search expands the state with the smallest $h(n)$. It may head quickly toward a goal that appears close, but it can overlook a cheaper route and is not generally optimal.

A* search combines the cost already paid with an estimate of the cost remaining. It expands the state with the smallest estimated total solution cost:

Here, $g(n)$ is the cost already paid from the start, and $h(n)$ estimates the cost remaining. A* is optimal under appropriate conditions. An Admissible heuristic never overestimates the true remaining cost; for graph search, consistency or suitable handling of improved paths is also needed for the usual optimality guarantee.

Design and assess a heuristic

A heuristic can often be designed by solving a simplified version of the task. For a grid where movement is allowed in four directions, Manhattan distance—the sum of the horizontal and vertical differences—estimates how many moves remain when obstacles are ignored. In that setting, walls can only add detours, so the estimate does not overstate the shortest distance.

A heuristic that is too optimistic may still be correct, but it provides less guidance. Setting $h(n) = 0$ makes A* equivalent to uniform-cost search.

Apply search to route planning

For a delivery robot traveling from a depot to an address through a road network, the state can be the robot’s current intersection. The available actions are roads to neighboring intersections, and the transition model says which intersection follows from taking a chosen road. The action cost can be road distance or estimated travel time; the depot is the start, and the goal test checks whether the robot is at the address.

If all roads are treated as equal-cost steps, BFS finds a route with the fewest roads. If roads have different lengths or travel times, UCS finds the least-cost route. A* can often search more efficiently by adding straight-line distance to the destination as a heuristic, provided that this distance does not exceed the true remaining travel cost.

In real systems, costs and routes may change, so the problem representation and estimates may need updating as new information arrives. The same approach applies to puzzles and robot motion planning: define the state, legal actions and their costs, and the goal test, then choose a suitable search strategy. A poor formulation can make the state space unnecessarily large or omit information needed for correct decisions.