Intelligent Agents and Problem Formulation

An intelligent system can be judged by what it does or by how it thinks. It can also be judged against human performance or against a standard of rationality. These two choices give four views of AI.

Choose the standard

Cognitive modeling belongs to thinking humanly. A puzzle solver with the right final answer may still be a poor model of human thought if people use different steps. Psychological experiments, introspection and brain imaging help test the model. Newell and Simon used human reasoning traces when developing the General Problem Solver.

The laws-of-thought approach uses logic. From “All people are mortal” and “Socrates is a person,” it derives “Socrates is mortal.” Real decisions also involve uncertain premises and a choice of action. Probability handles uncertainty; an action policy connects conclusions to behavior.

What the Turing test tests

Turing's 1950 imitation game uses typed exchanges with a hidden human and machine. The machine succeeds when the interrogator cannot reliably tell them apart. Language processing, knowledge representation, reasoning and learning support this task. The total Turing test adds physical interaction: vision for seeing objects, robotics for handling them, and speech recognition for spoken interaction.

A convincing conversation establishes humanlike conversational behavior. Whether it establishes understanding is a different question. ELIZA, released in 1966, could turn a user's statement into a question: “I feel lonely” might prompt “Why do you feel lonely?” Such responses can suggest understanding without a model of the speaker's situation. Imitation can also reward human errors or evasive replies.

Searle's 1980 Chinese Room makes the distinction sharper. A person follows a rule book to return Chinese answers while understanding no Chinese. Searle argues that executing rules alone is insufficient for understanding. The systems reply locates any understanding in the complete system, including the rules and room. The philosophical dispute remains open. Weak AI concerns acting intelligently; strong AI claims actual thought and understanding.

Acting well with limited resources

The rational-agent view, AI's standard model, judges actions by their expected consequences. A fast reflex can be rational; lengthy logical reasoning is unnecessary when immediate withdrawal avoids a burn. Practical agents face limits on time and computation, so limited rationality means doing as well as those resources permit.

Choosing the objective matters too. A machine rewarded only for closing support requests may close them without solving problems. This is a value alignment failure: the optimized measure misses what people value. One proposed design keeps the machine uncertain about the true objective and responsive to human guidance.

Narrow AI handles particular tasks. AGI would flexibly learn and perform across a broad range of tasks at human level. Broad conversational fluency and excellence at one game answer different questions from whether a system has that general ability; there is no agreed AGI test.

AI combines ideas from fields that asked different parts of the same question: how can a system represent the world, learn about it and choose useful actions?

Ideas before the field

Philosophy supplied logic and theories of mind. Mathematics supplied probability, formal reasoning and limits on computation. Economics contributed utility and decision theory. Psychology and neuroscience offered accounts of information processing and neurons. Computer engineering supplied hardware; linguistics supplied language structure. Control theory and cybernetics studied feedback, as when a thermostat corrects a temperature error. The agent view brings these contributions together.

From early models to early limits

McCulloch and Pitts described artificial neurons computing logical functions in 1943. Turing proposed the imitation game in 1950. McCarthy, Minsky, Rochester and Shannon submitted the Dartmouth proposal in 1955; the workshop held in 1956 established AI as a field. Its ambition was to describe learning and intelligence precisely enough for machines to simulate them.

Early successes included Newell and Simon's Logic Theorist and General Problem Solver, Samuel's learning checkers program, McCarthy's Lisp language in 1958 and Rosenblatt's perceptron in 1958. These programs demonstrated reasoning or learning in restricted settings. Optimistic predictions outran progress: the forecast of a world chess champion within ten years took about forty years to fulfill.

Three obstacles became clear. Programs lacked domain knowledge, search spaces grew too quickly, and some representations were too limited. Combinatorial explosion means that adding a few choices can multiply the possibilities enormously. Minsky and Papert's 1969 analysis showed limits of single-layer perceptrons, including failure to represent XOR. It did not establish that multilayer networks were impossible. The 1966 ALPAC report reduced US machine-translation support; the 1973 Lighthill report contributed to UK funding cuts. The mid-1970s funding decline became the first AI winter.

Knowledge, uncertainty and learning

Expert systems encoded specialist knowledge as if–then rules. DENDRAL investigated molecular structure, MYCIN advised on blood infections, and R1/XCON configured computer orders, saving millions of dollars annually. Commercial growth in the early 1980s exposed the cost of acquiring and maintaining rules. Systems were brittle beyond their domains; the Lisp-machine market collapsed in 1987 and a second winter followed. Research continued during both winters.

From the mid-1980s, several lines advanced together. Rumelhart, Hinton and Williams popularized backpropagation in 1986. Pearl's 1988 book helped establish Bayesian networks for uncertainty. Hidden Markov models became central to speech recognition. Shared data sets and benchmarks made comparisons more systematic.

Large data sets and faster hardware supported the next wave. AlexNet's GPU-trained deep network won ImageNet in 2012. AlphaGo defeated Lee Sedol 4–1 in 2016. Transformers appeared in 2017; ChatGPT's November 2022 release brought conversational AI to a broad public.

Compare two game-playing milestones

Go typically offers roughly 250 legal moves against roughly 35 in chess. Learned guidance helped select promising continuations without searching everything. Both systems used search: learning expanded AI's methods without replacing the rest of the field. The AI effect describes the tendency to stop calling a solved capability AI once it becomes familiar.

AI is a collection of methods for perception, reasoning, learning and action. A useful comparison asks how a system represents knowledge, where that knowledge comes from and what happens when its assumptions fail.

Compare the main approaches

A symbolic route planner can establish the cheapest route on its map. Its guarantee concerns that map and cost model. Knowledge is often written by experts, creating a knowledge acquisition bottleneck, but symbolic rules can also be learned. A learned decision tree, for example, can yield readable rules.

Probabilistic methods represent uncertainty explicitly. A robot with noisy distance readings can combine evidence about several possible locations. Bayesian networks and Markov models organize such reasoning; decision models connect probabilities to choices. Uncertainty is represented and managed, not removed by naming a probability.

Learning-based methods use examples or experience to improve performance. Neural networks are connectionist models; deep learning uses multiple layers. Large deep networks can require substantial data and computation and can be difficult to interpret. Smaller learned models can be readable. Across learned systems, training bias and unfamiliar inputs can undermine performance.

Combine methods when the task needs them

Rodney Brooks's behavior-based robotics in the 1980s emphasized simple reactive behaviors. Evolutionary computation searches by varying candidates and selecting better ones. Hybrid systems combine methods: AlphaGo joins learned evaluation to search; an automated vehicle can combine learned vision, probabilistic tracking, route planning and explicit safety rules. Neurosymbolic research combines neural learning with symbolic reasoning.

Imagine a warehouse robot that reads package labels, estimates its position and selects a route. Label recognition benefits from learning, uncertain location estimates call for probability, and routing calls for search. The physical task links these methods without turning them into a single interchangeable technique.

Judge what a capability establishes

AI systems plan routes, translate text, recognize speech, assist medical-image analysis and operate warehouse robots. Driverless taxi services carry passengers in several cities. AlphaFold 2 demonstrated strong protein-structure prediction; Hassabis and Jumper shared half of the 2024 Nobel Prize in Chemistry for protein structure prediction.

These are substantial task achievements. To evaluate a broader claim, identify the objective, percepts, available actions and environment. A chess champion program aims to win, perceives the board and chooses legal moves in a discrete, deterministic game. Driving demands perception of hidden hazards and timely physical control. Winning chess gives evidence about chess performance, not about driving skill.

Current systems can fail outside familiar conditions, generate confident errors or reproduce biased patterns. Physical systems can create safety failures; other risks include surveillance, disinformation and job disruption. Benefits include scientific discovery, support for diagnosis and automation of dangerous work. Neural networks are mathematical models inspired by neurons; that inspiration alone says little about how closely their reasoning resembles a brain's.

A robot and a spam filter both receive information and change something outside themselves. The agent model describes this loop without requiring a body or a claim of humanlike intelligence.

Separate the parts of the loop

Sensors obtain information; a percept is the information reported at one moment. Actuators provide ways to act on the environment. A camera is a sensor, its current image is a percept, a wheel motor is an actuator, and moving forward is an action.

For a software agent, incoming messages, file contents or keystrokes supply percepts. Writing a file, moving a message or displaying a response changes its digital environment. An embodied agent also faces physical dynamics: mass, speed, friction, battery limits and wear matter to its behavior.

The percept sequence is the complete history of percepts. Two agents receiving the same current reading may act differently because their earlier readings differ. A warehouse robot that saw an aisle blocked a moment ago has information that a newly started robot lacks.

Behavior and its implementation

The function describes what the agent would do for every input history, including histories never actually encountered. The program receives the current percept at each call. Any needed history must be retained in memory. Agent = architecture + program: the same code on a platform with different sensors or actions may behave very differently.

Work through a two-square vacuum

Squares A and B may each be clean or dirty. The vacuum senses its own location and the dirt status of its current square. It can perform Left, Right, Suck or NoOp. A current percept such as “[A, Dirty]” contains no report about B.

A simple program can use these rules:

if current_square_is_dirty:
    return "Suck"
if location == "A":
    return "Right"
return "Left"

Starting at dirty A, it sucks. Its next percept is “[A, Clean],” so it moves right. On dirty B, it sucks again. Once both squares are clean, these rules keep moving, because they store no fact saying that both have been cleaned. Whether that movement harms performance depends on the scoring rule.

Why not list every input history?

There are four current percepts: A or B crossed with clean or dirty. A table indexed by histories of lengths 1 through 3 needs:

For lengths 1 through 10, it needs 1,398,100 entries. A longer history is a different table key even when its final percept repeats an earlier one. Cameras make the number of possible inputs much larger still. A compact program exploits regularities, such as cleaning whenever dirt is sensed, instead of storing every case.

Calling a thermostat an agent describes its sensor–action relationship. It does not imply sophisticated reasoning. The agent view becomes especially useful when choosing actions involves perception, inference, learning or planning, and when the information available to the program must be made explicit.

Good behavior needs an explicit standard. A performance measure evaluates the sequence of environment states produced by the agent, so two programs can be compared by their consequences.

Reward the outcome people want

A vacuum rewarded for dirt collected could dump dirt and collect it again. Rewarding a clean floor better captures the desired outcome. The designer or user sets the measure; letting an agent freely redefine success would let it award itself a perfect score.

A measure may combine cleanliness, energy and noise. These choices matter: a clean floor maintained quietly is different from the same average cleanliness achieved with disruptive bursts. The definition of success comes before choosing an algorithm.

Compute a score over time

Both squares start dirty, with the vacuum in A. After each of 10 actions, award one point per clean square. Clean squares stay clean.

1. Agent 1 performs Suck, Right, Suck, then NoOp seven times. The clean-square counts after the first three actions are 1, 1 and 2. Its total is $1+1+2+7\times 2=18$.
2. Agent 2 performs Right, Suck, Left, Suck, then NoOp six times. Its total is $0+1+1+2+6\times 2=16$.
3. Agent 3 begins like Agent 1 but keeps moving for its last seven actions. Its cleanliness score is also 18.

Now subtract one point per move. Agent 1 moves once and scores 17. Agent 3 moves eight times and scores 10. The new measure makes stopping valuable once the agent knows both squares are clean.

Judge a decision before seeing its outcome

A rational agent selects the action expected to maximize its performance measure, given its percept sequence and built-in knowledge. Four ingredients determine the judgment: the measure, prior knowledge, available actions and percept history.

Rationality differs from omniscience, which would mean knowing the actual outcome in advance. A cyclist sees a 5% rain forecast. Carrying a bulky jacket is a certain burden that, for this cyclist, outweighs that chance of getting wet. Leaving it behind can be rational even if rain later arrives. A bad outcome does not change the evidence available when the decision was made.

Information gathering can itself be a rational action. Looking before crossing a road costs little and improves the next decision. In an unfamiliar setting, exploration can reveal what actions do, trading some immediate reward for better later choices.

Let experience improve behavior

Autonomy grows as an agent relies on its own experience instead of only its designer's assumptions. A vacuum with a fixed map may repeatedly hit a moved sofa. Updating the map from new readings lets it adapt. Useful prior knowledge helps it start; learning keeps that knowledge responsive to the environment.

A high score is meaningful only if the measure captures the intended outcome. Closing support tickets quickly while leaving problems unsolved is a measurement failure, even if the system optimizes that score effectively.

Before designing an agent, specify what success means and what the agent can sense and change. PEAS organizes the task environment into Performance measure, Environment, Actuators and Sensors.

Start with success

P describes outcomes that can be evaluated. E describes the setting and the entities affecting those outcomes. A lists the means of acting; S lists the means of obtaining information. The task environment is the problem the agent is meant to solve, not the algorithm used to solve it.

For an automated taxi, “drive well” is too vague. A useful P includes safe, legal, comfortable and timely trips, earnings and effects on other road users. These can conflict. Safety constraints can be fixed requirements, with speed optimized only among safe choices.

Fill in the taxi's description

A passenger display is an actuator because it changes what the passenger sees. A touchscreen can also provide sensor input when the passenger chooses a destination. Classify each role by the direction of information or action, not by the device's everyday name.

Apply PEAS beyond driving

A medical diagnosis assistant aims at patient health, accurate diagnoses, useful tests and few unnecessary procedures. Its environment includes patients, clinicians, laboratories and the hospital. Its outputs include questions, test requests, suggested diagnoses and referrals. Its inputs include reported symptoms, findings, records and test results.

A warehouse picking robot aims for correct picks per hour without damage or injury. Shelves, bins, conveyors and people form its environment. Wheels, an arm and a gripper are actuators. Cameras, barcode readers, joint-angle sensors and force sensors supply information. The robot needs force sensing if its measure penalizes crushed goods: seeing the correct item alone cannot reveal excessive gripping force.

For a spam filter, P balances blocked spam against legitimate email wrongly blocked. E includes the mailbox and senders. A allows delivery or movement to spam. S provides message text, headers and user reports. Increasing blocked spam by blocking every message would sacrifice legitimate delivery.

Check that the parts fit

Write P first, then E, A and S. For each desired outcome, identify how the actuators influence it. For each fact needed to choose an action, identify a sensor or prior knowledge that supplies it. A comfort objective needs evidence such as acceleration readings or passenger feedback. If neither exists, the design cannot reliably judge that aspect of the ride.

Keep instruments, observations and choices separate. A camera is a sensor; an image is a percept. A gripper is an actuator; “pick item 37” is an action. The routing algorithm belongs inside the agent, while the road network belongs in E. The chosen sensors also determine how much relevant information is visible to the agent.

Environment labels describe separate demands on an agent. A task can be fully observable yet uncertain, or have known rules yet hidden information. Classify each dimension independently.

Information, other agents and outcomes

An environment is fully observable when sensors reveal every fact relevant to action choice. It is partially observable when relevant facts are hidden or readings are noisy. An agent with no sensors faces an unobservable environment. A chess board is visible; poker hides opponents' cards.

A multiagent task includes other entities whose goal-directed choices affect the result and depend on our behavior. Chess is competitive; robots carrying a table cooperate. Drivers cooperate to avoid collisions and may compete for parking. A fallen tree is an obstacle, not another agent. Randomizing can help in competition by making choices harder to predict.

In a deterministic environment, the state and action fix the next state. A nondeterministic model lists possible outcomes; a stochastic model assigns probabilities to them. Chess is conventionally deterministic because the uncertainty about the opponent's choice belongs to the multiagent dimension. Hidden information can make deterministic dynamics appear uncertain to an agent.

Dependence and the passage of time

A static task can be sequential. Filling one crossword answer constrains later answers even though the grid does not change while the solver thinks. Episodic means decisions concern independent episodes, not merely that actions occur at separate times.

Values and knowledge

Discrete states or actions have distinct alternatives. Continuous quantities vary through a range, such as a car's speed or steering angle. Classify state, time, percepts and actions separately: digital images contain discrete values but often represent continuously varying brightness and position. Clocked chess combines discrete moves with continuously passing time.

A known environment has specified action effects or outcome probabilities. In an unknown environment, the agent must learn them. These labels concern the model, not what the sensors currently show. Solitaire has known rules and hidden cards. A new game can show its complete state while leaving the effects of its buttons unknown.

Apply each test to the task

Ask, in order: What relevant facts are hidden? Who else chooses actions? Is the next state fixed? Do decisions affect later ones? What changes while the agent thinks? Which quantities are discrete or continuous? Are action effects known?

Taxi driving combines partial observability, multiple agents, stochastic outcomes, sequential decisions, a dynamic world and continuous quantities. Much of the vehicle's dynamics is known, but an unfamiliar vehicle may require learning. The hardest combination includes unknown dynamics too. Do not infer all seven labels from one difficult feature: fully observable Go still has an enormous state space.

A classification becomes useful when it changes how the agent is built. Hidden state can require estimation; uncertain outcomes call for several possible futures; a changing world sets a limit on deliberation time.

Compare familiar tasks

These game descriptions assume their usual rules are known. A clock changes the timing classification without hiding pieces or changing the move rules. Dice change transition uncertainty without hiding the visible board.

Classify physical and diagnostic tasks

A taxi has blind spots and cannot directly observe other drivers' intentions. Other road users pursue goals, and traffic changes while the agent thinks. A missed exit affects later choices. Positions, speeds and steering angles vary continuously; unexpected events make outcomes stochastic. This combination requires perception, prediction, timely control and planning.

A medical diagnosis assistant has incomplete evidence about internal conditions. Test results are imperfect, treatments have uncertain outcomes, and one test shapes the next decision. The patient's condition may change during deliberation; many measurements are continuous. A common model treats the patient as part of a single-agent environment, with the assistant making decisions to improve health. That choice differs from modeling several clinicians as interacting decision makers.

An inspection camera judges finished parts independently. A hidden internal defect makes the task partially observable, but previous parts need not help judge the current one. If a moving conveyor changes the part's position while the camera deliberates, the task is dynamic. If a frozen image remains unchanged and only delay reduces the score, it is semidynamic. A deadline alone does not specify which situation applies.

Translate properties into design choices

When earlier readings reveal something about hidden current state, use memory and a world model. A taxi can remember a car that entered its blind spot. In independent image classification, memory of previous items may add nothing useful; partial observability by itself does not establish a need for history.

Stochastic tasks require comparing uncertain outcomes. Competitive tasks require anticipating opponents, sometimes with randomization. Sequential tasks require considering consequences. Dynamic tasks require decisions soon enough to remain useful. Unknown effects require learning and exploration. Continuous quantities require representations and methods that handle ranges.

Classical search fits known, deterministic, fully observable, discrete single-agent models. Adversarial search handles competitive games. Probabilistic inference estimates hidden state; decision processes support uncertain sequential choices; reinforcement learning addresses learning through interaction. Supervised learning fits many independent classification tasks. A real system may combine several of these methods because its environment combines several demands.

Agent programs differ in what information they use to select an action. A table can describe behavior directly; practical designs exploit rules and models to avoid enumerating every history.

Compare three designs

A table-driven program can implement an agent function in principle. With four possible percepts, histories up to length 10 already require 1,398,100 entries. A rule such as “if dirty, suck” covers many histories with one piece of code.

See why a reflex can loop

A simple reflex agent matches the current situation to a condition–action rule, then acts. A brake-light detector can trigger braking quickly. For a task whose correct response is available from the current reading, this is efficient. Full observability supplies the relevant state information, but the rules must still choose suitable actions.

Remove the vacuum's location sensor. It now sees only “Clean” or “Dirty.” Starting in clean A, a rule “if clean, move Left” hits the wall. The next reading is still “Clean,” so it repeats forever. The same reading occurs at clean B, where moving Left would make sense. Missing information makes the two situations indistinguishable.

Randomizing Left and Right can escape: from A, each attempt reaches B with probability one half. The mean number of attempts is 2. This removes the deterministic loop but does not tell the agent where it is or which square remains dirty.

Update an internal estimate

A model-based reflex agent keeps internal state derived from earlier percepts. It updates this state using the last action and the new percept, then applies rules to the updated estimate.

Two models serve different roles:

• A transition model describes how the world changes, including action effects.
• A sensor model describes how world states produce observations.

For a taxi, seeing a car in a mirror establishes a recent observation. Predicting where the car moves belongs to the transition model. Relating a camera image to the car's position belongs to the sensor model. The taxi may retain the car in its internal estimate after it enters a blind spot.

A vacuum can remember that A was cleaned. After it cleans B, its state says both squares are clean and its rule can select NoOp. Under the ten-action cleanliness score with a one-point move penalty, stopping scores 17; continued wandering scores 10.

Reactive and deliberative control

Reflex designs are reactive: rules select actions without simulating future sequences. Goal-based and utility-based designs are deliberative: they predict consequences. Systems can layer fast emergency braking with slower route planning. “Model-based” does not itself mean “goal-based”: remembering unseen facts and asking which future achieves a destination are different operations. In partial observability, internal state is an estimate that new evidence may revise.

Remembering the world supports better decisions, but it does not say which future is desirable. Goal-based and utility-based agents make that preference explicit.

From a destination to a plan

A goal-based agent predicts action results and asks whether they lead to a desired situation. A taxi at a junction may turn left, right or go straight safely. The passenger's destination determines which continuation helps. Changing the destination changes the goal, allowing the same map and reasoning machinery to find a new route.

A goal is a yes/no test: reached or not reached. Search and planning find action sequences that pass it. Explicit knowledge makes the agent flexible: a new destination changes the goal, while reduced braking ability in rain changes the model used to predict outcomes.

A utility-based agent assigns numbers to how desirable outcomes are. Several routes may reach the same destination but differ in time, safety or comfort. Utility expresses these preferences and trade-offs. Its internal utility function must agree with the external performance measure for utility maximization to serve the intended objective.

A binary utility of 1 for success and 0 for failure can represent a goal under uncertainty. More detailed utility can distinguish among successful outcomes or attach different values to different failures.

Calculate expected utility

For each possible outcome, multiply its probability by its utility, then add the products:

Here the probability model describes the outcome states for an action, and the utility function evaluates those outcomes. The rational utility-based choice has the largest expected utility.

Work through a train decision

A train leaves in 40 minutes. Route A takes 30 minutes for certain. Route B takes 20 minutes with probability 0.8 or 50 minutes with probability 0.2.

If the objective is to minimize expected travel time:

Route B has the smaller expected time. But the commuter values catching the train. Set utility to 1 for arrival before departure and 0 for missing it. A always catches it; B catches it only on its 20-minute outcome:

A is now preferred. The probability model did not change. The evaluation of the outcomes did. An average arrival time of 26 minutes does not mean each trip lasts 26 minutes.

Account for computation

Utility can represent time, health, comfort or other valued outcomes; it need not represent money. Exact prediction over every possible future is generally too expensive, so practical agents approximate. Looking ahead also consumes time. A reflex response is useful when immediate action is sufficient, while deliberation earns its cost when future consequences distinguish the choices.

Learning can improve a reflex, goal-based or utility-based program. It is a way of building and adapting an agent, not a competing action-selection category.

Follow the learning loop

The critic needs an external standard because a percept alone does not say whether an outcome is good. Seeing a checkmate position is not the same as knowing that winning is rewarded. The agent must not be able to redefine its standard to make poor behavior count as success.

Consider a delivery drone. The performance element flies a route. A headwind leaves only 8% battery at landing, below a fixed 15% safety standard. The critic reports the shortfall. The learning element revises the energy model so that similar headwinds predict greater consumption. Future flights may carry smaller loads or take shorter routes. The problem generator suggests a slower test flight to learn whether lower cruising speed saves energy.

Exploration may reduce immediate reward while improving later choices. Learning can change rules, transition models, sensor models or an internal utility estimate. An updated utility estimate must still serve the external performance standard; changing what the agent has learned about preferences differs from granting it permission to redefine success.

Choose how states are represented

An atomic representation treats a state as an indivisible item, such as a town name. The algorithm can compare states without examining attributes inside them. This is a common view in basic search and game models.

A factored representation describes a state through variables with values. A vehicle might have position, fuel and an oil-warning flag. Two states can share a fuel value while differing in position, letting rules refer to shared properties. Planning, constraint models, Bayesian networks and much machine learning use this kind of structure.

A structured representation describes objects and their relationships. “The truck is behind the gate” distinguishes a truck, a gate and the relation between them. First-order logic and language understanding use such representations to express who did what to whom.

Count combinations without listing them

Suppose a factored state has three yes/no variables and another variable with 10 values. The number of possible assignments is:

One compact variable description stands for 80 atomic alternatives. Constraints may reduce which assignments are possible or reachable. More expressive representations can describe regularities concisely, but they require more involved reasoning. Atomic does not mean unintelligent: treating towns as names is effective when only the road links matter. Objects and relationships earn their complexity when the task needs to reuse knowledge about their roles.

A problem-solving agent separates deciding what to achieve from deciding how to achieve it. It formulates a goal, formulates a problem, searches its model for a solution and executes the chosen actions.

Specify the model precisely

Some courses combine actions, results and costs in a successor function returning action–state–cost triples. The same information is present. These components describe the problem; the search algorithm decides which possibilities to examine.

A path is a sequence of actions. Its cost is the sum of the action costs. A solution leads from the initial state to a goal state; an optimal solution has the lowest cost among solutions. With positive unequal costs, fewer actions can still cost more.

Compare routes by their costs

Road lengths in kilometers are Alden–Brook 40, Alden–Cove 25, Brook–Cove 10, Brook–Elm 30, Cove–Dale 35 and Dale–Elm 20. Roads can be used in both directions. The state is the current town; start at Alden and test for Elm. Applicable actions follow roads from the current town, and each action costs the road's length.

The simple solution paths are:

• Alden → Brook → Elm: 70 km.
• Alden → Cove → Brook → Elm: 65 km.
• Alden → Cove → Dale → Elm: 80 km.
• Alden → Brook → Cove → Dale → Elm: 105 km.

The three-road route through Cove and Brook beats the two-road route through Brook. Positive road lengths mean adding a cycle cannot improve the distance.

Formulate the vacuum world

A state records the vacuum's location and each square's dirt status: two positions crossed with two independent dirt flags gives 8 states. Actions are Left, Right and Suck. Suck cleans the current square. Left in A and Right in B leave the location unchanged. The goal test asks whether both squares are clean; every action costs 1.

Starting in A with both dirty, Suck, Right, Suck reaches the goal at cost 3. Two cleaning actions and at least one move are necessary, so this plan is optimal. A model may omit boundary moves from ACTIONS or include them as no-ops; ACTIONS and RESULT must implement the same convention.

Separate states from paths

The state-space graph has one vertex per state and directed edges for actions. A two-way road contributes two directed edges. A search tree represents paths from the start: two different paths can end at the same state, creating different tree nodes. A graph can be generated as needed using ACTIONS and RESULT without storing every state in advance.

In a fully observable, deterministic, known model, a fixed plan can run open-loop without further sensing. When execution can diverge from prediction, closed-loop control monitors percepts and replans or follows branches for different outcomes. The goal state alone specifies a destination; the action sequence explains how to get there.

A world state contains all details of the environment. A search state keeps what planning needs.

Test what must be remembered

Include enough information to determine applicable actions, transition results, goal status and action costs from the current state. If two situations need different answers to any of those questions, keep them distinct.

For reaching an exit on a fixed grid, location may be enough. For collecting packages, location alone loses which items remain. For limited-battery movement, location alone loses whether the next action is possible. Wall color can be omitted when it changes none of these decisions.

An abstraction is valid when every abstract solution can be expanded into a real solution. It is useful when its actions are simpler to carry out than solving the original problem. Replacing detailed steering with “drive from Cove to Brook” helps only if that abstract drive can actually be performed.

Build the count one variable at a time

A robot moves on a 5 × 6 grid containing 8 fixed packages.

1. To reach the exit, store the cell: $5\times 6=30$ possibilities.
2. To collect all packages, add eight collected/not-collected flags: $30\times 2^8=\mathrm{7,680}$ assignments.
3. If battery charge matters, add 11 levels, from 0 through 10: $\mathrm{7,680}\times 11=\mathrm{84,480}$ assignments.

Multiply domain sizes when all combinations are allowed. This counts represented configurations; the number reachable from the initial state may be smaller. The 8-puzzle has $9!=\mathrm{362,880}$ arrangements, but only 181,440 are reachable from any one arrangement. For the 15-puzzle, the corresponding reachable count is 10,461,394,944,000, about 1.05 × 10¹³.

A vacuum with n squares has a location and n dirt flags, giving $n{2}^n$ states. Two squares give 8 states; ten give 10,240. Adding a binary variable multiplies the count by two, which explains exponential growth.

Change the formulation, not the task

The eight-queens task asks for eight nonattacking queens. A complete-state formulation starts with eight queens and moves them. An incremental formulation starts empty and adds queens.

Allowing each new queen on any empty square produces about 1.8 × 10¹⁴ ordered sequences of eight placements. Many orders create the same board. Counting distinct boards with zero through eight queens gives 5,130,659,561 states. These are different quantities: sequences record how a board was built; states record the board.

Instead, add a queen only in the leftmost empty column and only on an unattacked square. This formulation has 2,057 states, including 92 solutions, about 2.5 million times fewer distinct states than the unrestricted incremental version. It prevents many doomed choices before search explores them.

Keep necessary history in compact form

A tour that must visit every town needs the set of visited towns as well as the current town. It usually does not need the exact order of all earlier moves unless order affects legality or cost. Storing unnecessary history makes equivalent situations look different and prevents reuse of work. State count is one clue to difficulty; the structure of the graph and the method used to explore it matter too.

A good formulation makes the objective, legal moves and cost precise enough that a search method can use them. Small puzzles make these choices visible; practical tasks add timing, uncertainty or constraints that the state must preserve.

Follow a formulation sequence

1. State a measurable goal tied to the performance measure.
2. Choose the minimum sufficient state variables and the initial state.
3. Define applicable actions and their results.
4. Write the goal test.
5. Assign action costs with units.
6. Check the abstraction and estimate the state count.

For the 8-puzzle, store the positions of eight tiles and the blank. Move the blank into an adjacent cell and swap it with that tile. A corner allows 2 moves, an edge 3 and the center 4. The goal test compares the arrangement with a specified target. Unit action costs make path cost equal to the number of moves.

Model a pair of water jugs

Use unmarked 4-liter and 3-liter jugs, a tap and a drain. Start empty. Store the amounts as an ordered pair: first the 4-liter jug, then the 3-liter jug. The allowed operations are filling, emptying and pouring until the source is empty or the destination is full. Every operation costs 1.

From (3, 3), pour the smaller jug into the larger. The source has 3 liters, but the destination has room for only 1 liter. Transfer the smaller amount:

The result is (4, 2). Pouring does not split water arbitrarily; the stopping rule determines the amount transferred. Starting empty, whole-liter amounts remain whole liters. There are 20 integer combinations in the representation and 14 reachable from (0, 0).

Let the goal test determine success

For “either jug contains 2 liters,” a shortest plan takes four actions:

(0, 0) → fill smaller → (0, 3) → pour into larger → (3, 0) → fill smaller → (3, 3) → pour into larger → (4, 2).

For “the 4-liter jug contains 2 liters,” (4, 2) fails the test. A shortest plan takes six actions:

(0, 0) → fill larger → (4, 0) → pour into smaller → (1, 3) → empty smaller → (1, 0) → pour into smaller → (0, 1) → fill larger → (4, 1) → pour into smaller → (2, 3).

Changing a few words in the goal changes which endpoint counts as success. Keeping the state order fixed prevents confusing the amount in one jug with the other.

Add the facts real tasks need

A flight planner needs the current airport and time. Legal onward flights must leave late enough for the connection. Fare class or earlier legs also belong in the state when they affect future options or prices. Distance alone cannot represent an objective combining fares, waiting, flight duration and convenience; a cost model must define the trade-offs.

A touring problem must remember visited places. The traveling salesperson problem seeks a shortest tour visiting every city once and returning to the start; it is NP-hard, with no known efficient exact method for all large cases. Robot navigation may need continuous position and joint angles. VLSI layout handles component placement and connections; assembly sequencing must retain which parts are already fitted because an early choice can block a later step.

Before searching, test one ordinary action and one boundary case. A full receiving jug should accept no more water; an already departed flight should not appear as an available connection. These checks expose missing state or inconsistent action rules early.