4.5 Problem-solving agents and problem formulation

What this is and why it exists

Search algorithms are the straightforward half of this unit. Formulating the problem is where the work is, and where projects go wrong before any algorithm runs. This topic is the four components every search problem must have, the order in which to decide them, and the one skill that separates a workable formulation from an intractable one: deciding what detail you are allowed to throw away, and being able to justify each thing you threw.

The vocabulary

• Goal formulation — deciding what counts as done.
• Problem formulation — deciding how the situation is described and what actions exist.
• State — one situation the world can be in, as the agent represents it.
• State space — every state reachable from the initial one.
• Successor function — what each action does to a state.
• Goal test — how you recognise that a state is a solution.
• Path cost — the total cost of a sequence of actions.
• Abstraction — a description that leaves detail out.

The mental model

Goal formulation comes first, and the order is not a formality. Until you have said what counts as done, you cannot know which distinctions between situations matter — and it is the distinctions that matter which decide how a state is represented. Choose a representation first and you will have chosen it for reasons you did not examine, and you will discover halfway through that it cannot express the goal, or that it carries detail the goal never needed.

The practical form of this is a sentence: "the problem is solved when ...". Write it before anything else. If the sentence is hard to write, that is not a delay, it is the discovery that the problem was not yet defined — and it takes a moment to get right and a long time to recover from getting wrong.

Then the four components, which fully specify any search problem.

The initial state, where the agent starts.

The successor function, giving for each state the actions available and the state each one leads to. Together with the initial state this implicitly defines the entire state space, which is worth saying because the state space is almost never written out — it is generated as needed, and its size is what decides whether search is feasible.

The goal test, which decides whether a state is a solution. Sometimes it is a comparison against one named state; sometimes it is a property, such as "no queen attacks another", where many states pass and none was named in advance.

The path cost, assigning a number to a sequence of actions, usually as a sum of step costs. It exists so that "best" has a meaning, and its units should be whatever you actually care about — time, distance, money, risk. A path cost of one per step means you care about the number of actions and nothing else, which is a modelling choice worth making deliberately rather than by default.

Four more words used constantly, pinned down. The state space is the set of all states reachable from the initial state. A path is a sequence of actions and the states they pass through. A solution is a path from the initial state to a state passing the goal test. An optimal solution is a solution with the lowest path cost. The distinction between the last two is the whole subject of the next several topics — most algorithms find a solution and only some find an optimal one.

Now abstraction, which is the real skill here. A state description leaves things out. Formulating a journey between cities as a graph of cities and roads leaves out the weather, the radio, the passengers, the colour of the car, the exact position on the carriageway, and effectively everything about the world except where you are and which roads exist. That is not a simplification for convenience — without it the state space is unbounded and the problem cannot be posed at all.

So which omissions are legitimate? The criterion is that any solution in the abstract problem can be turned back into a solution in the real one. If the abstract answer is "take this road, then that one", and a real driver can carry out that plan, the abstraction is valid. If the abstract plan cannot be executed — because it ignored something that actually prevents it, such as the road being one-way, or the vehicle not fitting — the abstraction is broken, and no amount of good searching will save it.

Two related tests are worth applying alongside. Every abstract action should correspond to something the agent can actually do, possibly as a sequence of finer actions. And the detail you removed must not be able to change which abstract solution is best — remove the traffic from a journey problem and the shortest route may no longer be the fastest, so if you care about time you have removed something that decides the answer.

The practical habit is to state your abstractions explicitly as a list, alongside the four components, with one line each on why the omission cannot change the answer. It takes a few minutes. It converts an unexamined assumption into a written statement somebody can challenge, and when the resulting agent behaves oddly, that list is the first place to look — because the usual cause is not the algorithm but a piece of the world that was left out and turned out to matter.

Two failure modes to recognise. Too little abstraction gives a state space so large that no algorithm finishes, and the symptom is a search that runs forever on a problem a person solves easily. Too much gives plans that cannot be executed, and the symptom is an elegant solution that fails on contact with reality. The formulation is the design work; the algorithm is the implementation — and reaching for a better algorithm when the formulation is wrong is the most common wasted week in this material.

What you should now be able to explain or do

Do goal formulation before problem formulation and say what goes wrong in the other order. Specify the four components for a described task. Explain why the state space is implicit rather than written out. Choose path-cost units deliberately. Define state space, path, solution and optimal solution precisely. State the criterion for a valid abstraction and apply it to a proposed omission. List your abstractions with a justification each. Recognise the two failure modes of too little and too much abstraction.

Check yourself