2 Problem Solving and Search

Representing a search problem

Search solves a problem by considering possible situations and actions, then finding a sequence of actions that reaches a goal. An AI system can use search to plan a route, solve a puzzle, or choose steps toward a desired outcome.

A search problem is defined by five parts:

• Initial state: where the problem starts.

• Actions: what the agent can do in each state.

• Transition model: which state results from taking an action.

• Goal test: how to determine whether a state meets the objective.

• Path cost: the total cost of the actions taken, such as distance, time, or energy.

A solution is a path from the initial state to any state that passes the goal test. What counts as the best solution depends on the objective: it may be the path with the fewest actions or the path with the lowest total cost.

For a robot moving through a grid, a state can be its current square. Actions move it to neighboring squares, the transition model specifies the resulting square, and the goal test checks whether it has reached the destination. The path cost might count moves or assign extra cost to difficult terrain.

Search spaces and trees

The State space is the set of states reachable by applying actions from the initial state. A search algorithm explores this space while maintaining a Frontier of discovered but unexplored states. In graph search, it also tracks explored states to avoid repeatedly visiting the same locations.

Tracking explored states matters because different action sequences can lead to the same state, and some problems contain cycles. The search tree represents the paths considered by the algorithm, so a state can appear more than once in the tree if different paths reach it.

The Branching factor is the typical number of successors per state, while depth is the number of actions from the start. When the branching factor is large, the number of possible paths can grow rapidly with depth, making the choice of search strategy important.

Uninformed search strategies

Uninformed search strategies use the problem definition but have no estimate of how close a state is to the goal. They differ mainly in which frontier state they explore next.

Breadth-first search (BFS) explores the shallowest paths first, typically using a queue. When every action has the same cost, it finds a solution with the fewest actions. It may use substantial memory because it keeps many states in the frontier.

Depth-first search (DFS) follows one path as far as it can before backtracking, typically using a stack. It can use less memory than BFS, but it may follow a long or looping path and does not generally find the shortest or least-cost solution. With graph search on a finite state space, checking for duplicates prevents infinite revisits; without duplicate checking, cycles can cause trouble.

Uniform-cost search (UCS) expands the frontier path with the lowest cost so far, typically using a priority queue. Unlike BFS, it accounts for different action costs. It finds a least-cost solution when step costs are positive and the search conditions permit a solution to be reached.

For example, on a map with roads of different lengths, BFS may find a route with the fewest road segments, whereas UCS seeks the route with the smallest total distance.

Informed search and heuristics

Informed search uses a Heuristic, written as $h(n)$, to estimate the remaining cost from state $n$ to a goal. A useful heuristic guides the search toward promising states, but its value depends on how accurately it estimates the remaining work.

Greedy best-first search expands the state with the smallest $h(n)$. A helpful estimate can let it reach a goal quickly, but the strategy ignores the cost already paid and is not generally guaranteed to find the least-cost path.

A* balances the cost so far with the estimated remaining cost. It selects the state with the smallest value of:

Here, $g(n)$ is the path cost from the start, and $h(n)$ estimates the remaining cost. If the heuristic is an Admissible heuristic—it never overestimates the true remaining cost—A* tree search finds an optimal solution. For graph search, **Consistency** is a common condition that supports optimality without reopening explored states.

On a grid with four-directional moves that each cost one, Manhattan distance is the sum of the horizontal and vertical differences from the goal. It is an admissible heuristic if each move changes position by just one square. This estimate is a lower bound on the number of moves still needed, even when obstacles make the actual route longer.

Choosing a search strategy

Choose a strategy according to the objective and the resources available:

• For the fewest actions when all actions cost the same, use BFS.

• For the lowest total cost when actions have different costs, use UCS.

• For lower memory use and a quick exploratory path without a shortest-path guarantee, use DFS.

• To use a useful distance estimate while seeking a low-cost solution, use A*.

• To quickly prioritize states that appear closest to the goal, use greedy best-first search.

No strategy removes the need for a good problem representation. If the state omits information needed to choose actions or test the goal, search may produce an invalid plan. Even well-designed search can require too much time or memory when the state space is very large.

In practice, search begins by specifying the states, actions, transitions, goal, and costs. The algorithms then explore the resulting state space by choosing which frontier path to consider next. Uninformed methods use different exploration orders, while informed methods use heuristic estimates; the choice depends on solution quality, action costs, available guidance, and computational limits.