Problem Formulation — Reading Notes

1.Intelligent Agents & Environments

The central unifying concept of modern Artificial Intelligence is the intelligent agent. Rather than defining AI in terms of human thought processes or internal subjective consciousness, AI is formulated as the computational science of designing systems that act rationally. An agent interacts with an environment through a closed perceptual-action loop: it perceives the environment via sensors and alters that environment via actuators.

1.1Agents, Percepts & Actions

Formally, an agent is anything that can view its environment through sensors and act upon that environment through actuators. A human agent has eyes, ears, and other organs for sensors; hands, legs, vocal tract for actuators. A robotic agent might substitute cameras, infrared range finders, and lidars for sensors, and electric motors or hydraulic joints for actuators. A software agent (or softbot) receives keystrokes, network packets, or file contents as sensor inputs and acts upon the environment by sending network packets, writing files, or displaying graphics.

We use the term percept to refer to the agent's perceptual inputs at any given instant. An agent's percept sequence is the complete history of everything the agent has ever perceived:

Mathematically, an agent's behavior is described by the agent function f, which maps any given percept sequence to an action a ∈ A:

The agent function is an abstract mathematical description. The agent program is the concrete implementation of f that executes on a physical architecture (a computing device with physical sensors and actuators):

1.2Good Behavior: The Concept of Rationality

What does it mean for an agent to behave well? A rational agent is one that does the right thing — conceptually, every entry in the table for the agent function is filled out correctly. To make this precise, we define a performance measure that embodies the criterion for success.

Formally, rationality is defined by four factors:

1. The performance measure that defines the criterion of success.
2. The agent's prior knowledge of the environment.
3. The actions that the agent can perform.
4. The agent's percept sequence to date.

Three critical distinctions must be maintained when discussing rationality:

• Rationality vs. Omniscience: An omniscient agent knows the actual outcome of its actions and can act accordingly; but omniscience is impossible in reality. Rationality maximizes expected performance, whereas perfection maximizes actual outcome. If an agent looks both ways, sees a clear street, steps out, and is hit by an unforeseen meteorite falling from orbit, the agent was fully rational even though the outcome was tragic.
• Information Gathering & Exploration: Doing actions in order to modify future percepts (e.g., looking both ways before crossing, exploring unfamiliar terrain) is a fundamental part of rationality.
• Autonomy: An agent is autonomous to the extent that its behavior is determined by its own experience (with ability to learn and adapt), rather than solely by the built-in knowledge of its designer. A truly autonomous agent should be able to operate across different environments given sufficient time to learn.

1.3Specifying Task Environments: PEAS

In designing an AI agent, the very first step is always to specify the task environment as fully as possible. AIMA organizes this specification under the PEAS framework:

• Performance Measure: The objective metrics used to evaluate the agent's behavior.
• Environment: The external world, context, physical systems, or software ecosystem the agent operates in.
• Actuators: The devices or interfaces through which the agent acts.
• Sensors: The devices or interfaces through which the agent receives percepts.

1.4Environment Characteristics & Dimensions

The nature of the environment largely dictates the design of the agent program and the feasibility of different problem-solving methods. AIMA classifies task environments along seven primary dimensions:

Fully Observable vs. Partially Observable

An environment is fully observable if the agent's sensors give it access to the complete state of the environment at each point in time (e.g., Chess, 8-Puzzle). It is partially observable if sensors are noisy, inaccurate, or missing state data (e.g., Poker, Driving in fog). An environment is unobservable if the agent has no sensors at all.

Single-Agent vs. Multi-Agent

An agent solving a Crossword puzzle is in a single-agent environment. Chess is a multi-agent competitive environment (zero-sum game). Autonomous driving is a multi-agent partially cooperative / partially competitive environment (avoiding collisions is cooperative; claiming a parking spot is competitive).

Deterministic vs. Stochastic

If the next state of the environment is completely determined by the current state and the action executed by the agent, the environment is deterministic (e.g., 8-Puzzle, Maze). If randomness or probabilities affect outcomes, it is stochastic (e.g., Backgammon dice rolls, Taxi driving). If the environment cannot be predicted deterministically but lacks explicit probabilities, it is nondeterministic.

Episodic vs. Sequential

In an episodic environment, the agent's experience is divided into atomic episodes; the choice of action in each episode depends only on the episode itself, and current decisions do not affect future episodes (e.g., classifying defective parts on an assembly line). In a sequential environment, current decisions affect all future decisions (e.g., Chess, Route Finding).

Static vs. Dynamic

If the environment can change while the agent is deliberating, it is dynamic (e.g., Taxi driving, real-time strategy games). If it does not change with the passage of time, it is static (e.g., Crossword puzzle, 8-Puzzle). An environment is semidynamic if the environment itself doesn't change, but the agent's performance score decreases over time (e.g., timed Chess).

Discrete vs. Continuous

Pertains to the state of the environment, the way time is handled, and the percepts and actions. Chess has a discrete state space and discrete turns; Taxi driving has continuous states (locations, speed, angles) and continuous time and actions.

Known vs. Unknown

Refers to the agent's knowledge of the laws of physics or rules of the environment. In a known environment, the outcomes for all actions are known (e.g., standard Solitaire); in an unknown environment, the agent must learn how the world works in order to make good decisions.

1.5Agent Architectures: From Reflex to Learning

AIMA defines five canonical agent program structures, arranged in increasing order of generality and sophistication:

1. Simple Reflex Agents: Select actions based only on the current percept, ignoring the history of percepts. Implemented using condition-action rules (e.g., if car-in-front-is-braking then initiate-braking). Only effective in fully observable environments; unrecoverable infinite loops occur in partially observable environments.
2. Model-Based Reflex Agents: Maintain an internal state to track parts of the world they cannot see right now. They maintain two models: transition model ("how the world evolves independently and how my actions change it") and sensor model ("how the state of the world reflects into my percepts").
3. Goal-Based Agents: Combine current state information with a goal description to select actions that achieve the desired outcome. This enables search and planning — the central topic of Chapter 3 and Topic 01.
4. Utility-Based Agents: Use a real-valued utility function U(s) ∈ ℝ to measure how desirable a state is. Allows rational decision-making when goals conflict, when trade-offs must be made (e.g., speed vs. safety), or when multiple goals can only be achieved with uncertainty.
5. Learning Agents: Can operate in initially unknown environments and become more competent than their initial programming. Divided into four components:
   • Learning Element: Responsible for making improvements based on experience.
   • Performance Element: Responsible for selecting external actions (corresponds to the entire agent in the previous structures).
   • Critic: Evaluates how well the agent is doing against an external, fixed performance standard.
   • Problem Generator: Suggests exploratory actions that lead to new experiences and improved long-term performance.

2.The Formal Problem Formulation Framework

When an agent cannot simply react to its immediate environment with a single hard-coded reflex rule, it must look ahead and formulate a plan. A problem-solving agent is a goal-based agent that decides what to do by finding sequences of actions that lead to desirable states.

2.1Problem-Solving Agents & Goal Formulation

The problem-solving cycle follows a rigorous four-phase sequence:

1. Goal Formulation: Organize objectives into a concrete target based on current situation.
2. Problem Formulation: Decide what actions and states to consider, given the goal.
3. Search: Simulate action sequences in the abstract state space until a goal path is found.
4. Execution: Execute the planned actions one by one in the real physical world.

Crucially, search is performed offline: the agent explores hypothetical paths within its mental model of the world before executing a single physical action. Once a solution is found, the execution phase begins.

2.2The 5 Components of a Search Problem

Formally, a search problem is defined by five mathematical components — often packaged as a formal 5-tuple (s₀, ACTIONS, RESULT, IS-GOAL, STEP-COST):

1. Initial State

The state that the agent starts in, denoted s₀ ∈ S.

2. Actions

A function ACTIONS(s) that returns the set of legal actions that can be executed when in state s. If a ∈ ACTIONS(s), action a is applicable in state s.

3. Transition Model

A function RESULT(s, a) = s′ that returns the state s′ that results from doing action a in state s. We say that s′ is a successor of s.

4. Goal Test

A predicate IS-GOAL(s) that determines whether a given state s is a goal state. The goal can be an explicit set of enumerated states {g₁, g₂, …} or an abstract property test (e.g., no_two_queens_attack_each_other(board)).

5. Path Cost & Step Cost

A function c(s, a, s′) that assigns a numeric cost to taking action a in state s to reach s′. The total path cost g(n) of a sequence of actions is the sum of the individual step costs along the path.

2.3States vs. Physical World: The Art of Abstraction

A physical environment is overwhelmingly complex, continuous, and filled with infinite irrelevant details. An agent navigating a city does not need to model the current tire air pressure, the song playing on the radio, the temperature of the asphalt, or the color of the adjacent vehicle. Including these details would make the state space infinitely large and completely unsearchable.

Abstraction is the process of removing irrelevant detail from the state representation while preserving everything required to find a valid solution:

An abstraction is valid if any abstract action sequence can be translated into a sequence of physical actions that actually succeeds in the real world. An abstraction is useful if carrying out actions in the abstract representation is computationally easier than searching the raw physical environment.

2.4State Space & Reachability

Together, the initial state, actions, and transition model implicitly define the state space S of the problem. The state space is the set of all states reachable from the initial state by any sequence of valid actions.

The state space forms a directed graph in which the nodes are states and the directed edges (links) between them are actions. A path in the state space is a sequence of states connected by a sequence of actions.

2.5Solutions, Path Costs & Optimality

A solution to a search problem is an action sequence that leads from the initial state s₀ to any state s satisfying IS-GOAL(s) == true.

An optimal solution is a solution that has the lowest path cost among all possible solutions. The cost of the optimal solution is denoted C*:

3.Benchmark Problem Formulations

AI problems are traditionally divided into toy problems (intended to illustrate or exercise various problem-solving methods, with concise, exact descriptions) and real-world problems (whose solutions people actually care about, often requiring complex domain engineering). Below are the classic formulations from AIMA and the interactive lecture.

3.1The Two-Room Vacuum World

The Two-Room Vacuum World is the quintessential toy problem introduced in AIMA Chapter 2. The environment consists of two locations: Room A (left) and Room B (right). Each room can be either Clean or Dirty. The vacuum agent is located in either Room A or Room B.

States

Determined by agent location and status of both rooms: 2 × 2 × 2 = 8 discrete states: (Location, RoomA_status, RoomB_status).

Initial State

Any of the 8 states (e.g., (A, Dirty, Dirty)).

Actions

{Left, Right, Suck}.

Transition Model

Left moves agent to A; Right moves agent to B; Suck cleans the current room. Moving into a wall has no effect.

Goal Test

Both rooms are clean: RoomA == Clean ∧ RoomB == Clean (States 7 and 8).

Path Cost

Each step costs 1 (number of actions taken).

3.2The 8-Puzzle & Sliding Tile Puzzles

The 8-puzzle consists of a 3 × 3 board with 8 numbered tiles and one blank space (represented by 0). A tile adjacent to the blank space can slide into the blank space.

States

A configuration specifying the location of each of the 8 tiles and the blank in the nine squares. Total permutations: 9! = 362,880. Exactly half (9! / 2 = 181,440) are reachable from any initial configuration due to the permutation parity invariant.

Initial State

Any designated valid board configuration.

Actions

Move the blank space Left, Right, Up, or Down (conventionally modeled as moving the blank rather than moving tiles, which keeps the action set fixed to ≤ 4).

Transition Model

Swaps the blank with the tile in the target direction, returning the new board state.

Goal Test

Board matches the target solved configuration (e.g. [1,2,3, 4,5,6, 7,8,0]).

Path Cost

Each step costs 1 (total moves).

3.32D Grid & Maze Navigation

An agent navigates a discrete 2D grid from a starting cell to a goal cell, avoiding obstacles and walls.

States

Grid coordinate (x, y) or (row, col) representing the agent's current location.

Initial State

Designated start coordinate (row₀, col₀).

Actions

Move {North, South, East, West} to adjacent in-bounds, non-wall cells.

Transition Model

RESULT((r, c), North) = (r - 1, c), etc.

Goal Test

(r, c) == (r_goal, c_goal).

Path Cost

1 per movement step (or Manhattan/Euclidean distance in weighted terrain).

3.4Route Finding & Road Networks

The canonical route-finding problem from AIMA: an agent is in the city of Arad, Romania, and wishes to travel to Bucharest along a road network with specified distances.

States

The name of the current city (e.g., Arad, Sibiu, Bucharest).

Initial State

In(Arad).

Actions

Go(c) for any city c directly connected to the current city by a road.

Transition Model

RESULT(In(Arad), Go(Zerind)) = In(Zerind).

Goal Test

s == In(Bucharest).

Path Cost

Sum of the road distances in kilometers (e.g., c(Arad, Go(Zerind), Zerind) = 75 km). Note: Unlike the previous examples, step costs are non-unit, so number of actions and total path cost diverge!

3.5The 8-Queens Problem

The goal of the 8-Queens problem is to place 8 queens on a chessboard such that no queen attacks any other queen (no two queens share the same row, column, or diagonal).

This problem highlights the critical design choice between two formulation styles:

3.6Real-World Problem Formulations

While toy problems provide clean conceptual models, real-world problems drive industry applications:

• Traveling Salesperson Problem (TSP): A touring problem where every city on a map must be visited exactly once with minimal total mileage. Total candidate tours for n cities is (n - 1)! / 2 — NP-hard.
• VLSI Layout Design: Positioning millions of transistors and routing connecting wires on a silicon chip without wire overlap, minimizing chip area and electrical capacitance delay.
• Robot Navigation: Moving a continuous kinematic manipulator or autonomous vehicle through 3D space with continuous angles and obstacles — discretized into configuration spaces.
• Automatic Assembly Sequencing: Finding a valid order to assemble complex mechanical components (e.g., jet engines) without parts colliding during assembly.
• Protein Design & Folding: Finding a sequence of amino acids that folds into a target 3D structure that cures disease or catalyzes a chemical reaction.

4.Analyzing & Comparing Formulations

Formulating a problem is not merely about writing down definitions; it is about choosing the mathematical representation that makes searching for a solution computationally tractable.

4.1State Space Size & Branching Factor

Two metrics govern the difficulty of a search problem:

• State Space Size |S|: The total number of reachable distinct configurations. If |S| is small (e.g., 8 states in Two-Room Vacuum), exhaustive enumeration is trivial. If |S| is massive (e.g., 10²⁰ in 15-puzzle, 10¹²⁰ in Chess), clever heuristics and pruning are mandatory.
• Branching Factor b: The number of legal actions available from a typical state. In an 8-puzzle, b ranges from 2 (corners) to 3 (edges) to 4 (center), with an average b ≈ 3. In chess, average b ≈ 35; in Go, average b ≈ 250.

4.2State Space Graph vs. Search Tree

A frequent point of confusion is the distinction between the state space graph and the search tree:

• The state space graph has exactly one node per unique physical state in S. Edges represent reversible or irreversible action transitions between states. If a graph has cycles (e.g., Left → Right → Left), the state space graph remains finite.
• The search tree is a tree of unrolled paths generated by a search algorithm starting at the initial state. Because the same state can be reached by infinitely many paths in a cyclic graph, the search tree can be infinite even when the state space is tiny! Graph search maintains a reached table to prune these redundant paths.

4.3Atomic, Factored & Structured States

AIMA Chapter 2 introduces the three fundamental paradigms for representing states:

4.4Problem Formulation Comparison Matrix

The table below summarizes the formal 5-component formulation across our benchmark domains:

5.Practice Exercises

The eight exercises below provide deep conceptual and analytical practice on intelligent agents, PEAS task specifications, environment classification, state-space combinatorics, and rigorous 5-component problem formulation. Each problem is stated first; click Show Answer to view the complete worked mathematical solution.

1  2  3
8  _  4  →  Sequence: (1, 2, 3, 8, 4, 7, 6, 5)
7  6  5