# Formulating a Search Problem — Artificial Intelligence

Source: https://www.skillbyai.com/en/artificial-intelligence/s-form

> Turn a task into states and actions.

## 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.

![Four ideas: formulation, uninformed search, A*, local search.](assets/figures/artificial-intelligence/section-2-map.svg) — Figure 2.1 — Formulation, uninformed search, A* and local search.

## Route finding as a search problem

The same template fits many problems.

```text
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.

**Quiz:** What is the frontier in search?

- [ ] The goal state
- [x] The set of discovered states waiting to be expanded
- [ ] The cheapest path found
- [ ] The list of all possible states

*Answer:* The set of discovered states waiting to be expanded. Algorithms differ in how they order the frontier.