Formulating a Search Problem

Five ingredients

A search problem needs: an initial state, the actions available in each state, a transition model (what state an action leads to), a goal test, and a path cost. Route finding, puzzle solving, scheduling and robot motion all fit this pattern. The set of reachable states is the state space; it is usually far too large to list, so algorithms explore it incrementally, keeping a frontier of states to visit next. How the frontier is ordered defines the algorithm.

States, actions, goals

Many AI problems become finding a path through a space of states.

Route finding as a search problem

The same template fits many problems.

initial state   at Pune
actions         drive along a road to a neighbouring city
transition      drive(Pune -> Lonavala) => at Lonavala
goal test       at Mumbai?
path cost       total kilometres (or minutes)
frontier        cities discovered but not yet expanded

Keep states small

Include only what affects future actions in a state; extra details multiply the state space for no benefit.

Quick check: What is the frontier in search?

• The goal state
• The set of discovered states waiting to be expanded
• The cheapest path found
• The list of all possible states