Is problem formulation the same as prompting?

No. A prompt may describe a problem, but formulation specifies its decision structure, constraints, and success conditions.

Must every problem use a state graph?

No. Other formulations include constraint satisfaction, optimization, and probabilistic decision models. State-space search is the focus here.

Can the formulation change after testing?

Yes. Discovering an omitted resource or an incorrect action effect is a reason to revise the model and re-evaluate solutions.

AI Glossary / Graphs and symbolic AI / Intermediate

Problem formulation

Definition

Problem formulation is the process of turning a goal into a precise problem that an AI method can solve. For state-space search, it specifies the initial state, possible actions and their effects, a goal test, and a way to measure solution cost. The formulation determines what the solver considers possible, successful, and preferable.

What it means

A request such as “deliver the parcel efficiently” leaves many choices unstated. Does delivery require a signature? Can the vehicle use every road? Does efficiency mean time, distance, or money? Which facts must be represented to predict the consequences of each action?
Problem formulation answers those questions at an appropriate level of abstraction. It leaves out irrelevant detail while retaining information needed for valid decisions. Goal formulation chooses the desired outcome; problem formulation specifies the modeled route toward it. Search then operates within that model. A perfectly executed search can still solve the wrong problem if the formulation misses an essential constraint.

How it works

Describe the starting situation and identify state variables. Specify which actions are available in each state and the successor state or outcome model for each action. Define a test for whether a state meets the goal and a cost for comparing solutions.
Then check the abstraction using concrete cases. Two real situations should not be merged into one modeled state if their available actions or relevant consequences differ. Classical deterministic search can return an action sequence; uncertainty or incomplete observations may require a richer formulation and a conditional plan or policy. The representation should match the problem's assumptions rather than merely fit a favorite algorithm.

Three practical examples

A route-planning exercise can define locations as states, permitted road segments as actions, and travel distance as cost.
A puzzle solver can represent tile arrangements and legal moves, with a test for the target arrangement.
A document workflow planner can include whether review and approval have occurred, ensuring that publication is unavailable before its prerequisites hold.

Think of it this way

Think of writing the rules and scoring system for a board game before asking someone to find the best play. If the rules omit a locked gate, the proposed winning move may be impossible in the actual game. The analogy is limited because real-world abstraction is itself a judgment task: the designer must decide which details affect valid outcomes.

Worked example

Consider an invented courier problem with depot D, collection point A, and destination G. The courier starts at D without the parcel. Travel D - G costs 2, D - A costs 2, and A - G costs 3. All routes are bidirectional. Collecting at A costs 1 and changes parcel possession from false to true. Delivering at G costs 1 and requires possession.
If the state contains only location and the goal is “at G,” the direct journey costs 2 and appears to solve the problem. It does not deliver anything. A better state records location, parcel possession, and whether delivery is complete. The goal test checks delivery completion.
The sequence D to A, collect, A to G, deliver costs 2 + 1 + 3 + 1 = 7. Traveling through D after collection costs 2 + 1 + 2 + 2 + 1 = 8. With these stated actions and costs, 7 is optimal: collection and delivery are mandatory, and A to G directly is cheaper than returning via D. The improvement comes from formulating the right task before searching.

Illustrative case study

Fictional case: Larch Studio prototypes a planner for preparing product pages. Its first model marks a page ready when the text and image exist. Editors point out that images also need an approved usage record.
The team adds a permission-status variable and makes approval a prerequisite for publication. It then checks examples where a page is complete in appearance but still awaiting review. The fictional project illustrates how a missing state variable creates an invalid solution even when the search algorithm behaves correctly. No deployment outcome or productivity claim is intended.

Common misconceptions and mistakes

Do not confuse the goal test with the cost function. Reaching an acceptable state and choosing the best route to it are different questions. Do not omit history-dependent information when it changes future choices; often the relevant part of that history must become part of the state.
Avoid adding every available detail, which may make search unnecessarily large. Conversely, a simpler model is not useful if its actions cannot be carried out. A heuristic helps guide search after formulation; it does not repair a false transition model. If the world changes during execution, a once-valid formulation or plan may need updating.

Business use

For a business workflow, formulation is where objectives become testable. A useful review asks the process owner to inspect representative states, action prerequisites, and examples of both success and failure. This can reveal a disagreement about what completion means before a solver is built.
Document the units of cost and how competing goals are handled. A weighted score should reflect an agreed trade-off rather than conceal it. Keep model assumptions visible when presenting a recommended plan. The resulting solution is justified by that representation; operational acceptance still depends on whether the representation captures the actual task.

Check your understanding

Why is the direct D - G journey not a solution to the corrected courier formulation, even though it reaches the destination?

Answer: The goal is completed delivery, and delivery requires possessing the parcel. The direct journey neither collects the parcel nor performs the delivery action. Location alone is insufficient to determine success.

Related terms

Learn next

Learn state-space search and abstraction next. Add a carrying-capacity limit to the courier example, then explain which state variables and action prerequisites must change. Check a proposed plan by simulating every transition rather than judging it only by its final location.

Sources

Stuart Russell and Peter Norvig, AIMA Chapter 3 teaching slides, problem formulation and state-space abstraction: https://aima.cs.berkeley.edu/slides-pdf/chapter03.pdf

Previous: Probit model Next: Problem generator