Intelligent Agents and Problem Formulation

Introduction and Context

Artificial intelligence systems are often described in terms of what they do: recommend products, navigate vehicles, diagnose diseases, or play games. A more precise view begins with the idea of an agent—an entity that perceives its surroundings and takes actions. This perspective provides a unifying foundation for many areas of AI, including robotics, planning, search, decision-making, natural language interaction, and autonomous systems.

An AI system is not intelligent merely because it performs a complex computation. Its intelligence is assessed in relation to an environment, available information, possible actions, objectives, and consequences. A chess-playing program, for example, operates in a structured game environment, observes the board, selects legal moves, and attempts to achieve checkmate. An autonomous vehicle operates in a far less predictable environment, where sensor limitations, uncertain behavior by other road users, and safety requirements must be considered.

This chapter develops two closely related foundations. First, it explains how intelligent agents are specified and evaluated. Second, it shows how real-world objectives can be transformed into formal problem representations that search and planning algorithms can solve.

Learning Objectives

By the end of this chapter, students should be able to:

1. Define an intelligent agent and distinguish agent functions from agent programs.

2. Explain rational action, performance measures, autonomy, sensors, and actuators.

3. Construct a PEAS description for an AI task.

4. Classify task environments using standard dimensions.

5. Formulate states, actions, transition models, goals, path costs, and solution spaces.

6. Explain the difference between a problem specification and a search strategy.

7. Apply these ideas to practical systems and evaluate their limitations and risks.

1. The Intelligent-Agent Model

An agent is anything that can perceive its environment through sensors and act upon that environment through actuators. A human agent uses eyes, ears, and other sensory organs to perceive; muscles and speech organs to act. A robot may use cameras, lidar, microphones, and temperature sensors, and may act through wheels, robotic arms, or speakers. A software agent may receive web pages, database records, or user messages and act by issuing commands, sending recommendations, or modifying digital resources.

At each moment, an agent receives a percept. The complete history of percepts received by an agent is called the percept sequence. The agent function maps percept sequences to actions:

f: P* → A

where P is the set of possible percepts, P is repeated any finite number of times to represent percept sequences, and A is the set of possible actions. The agent function is an abstract specification of behavior. An agent program is an implementation of that function on a physical or computational architecture.

The distinction is important. The same agent function may be implemented by a rule-based program, a search algorithm, a machine-learning model, or a combination of these. Conversely, a sophisticated implementation can still be unsuitable if the function it realizes does not correspond to the task objective.

Rationality

A rational agent selects an action expected to maximize its performance measure, given:

• the percept sequence available so far;
• the agent’s prior knowledge;
• the actions available to it; and
• the expected consequences of those actions.

Rationality does not mean perfection or omniscience. An agent may lack information, face uncertainty, or have limited computational resources. A rational navigation agent can choose the best route according to current traffic information even if an unexpected road closure later makes that route suboptimal.

A rational decision is therefore evaluated using the information available when the decision is made. Rationality also differs from success. A medical decision-support system may make a rational recommendation based on accurate patient data and established evidence, yet the patient may have an unusual response. Rationality concerns the quality of the decision process, whereas outcome quality may also depend on chance and external events.

Autonomy

An agent is autonomous to the extent that its behavior depends on its own experience rather than being completely determined by built-in knowledge. A thermostat has limited autonomy because its behavior follows a fixed rule. A robot that learns how surfaces affect traction and adapts its navigation has greater autonomy.

Autonomy does not imply unrestricted independence. Production AI systems should operate within defined safety constraints, authorization boundaries, and governance procedures. Human oversight is especially important where errors can cause physical, financial, legal, or social harm.

2. Sensors, Actuators, and Agent Architectures

Sensors provide information, but they do not necessarily provide a complete or accurate description of the environment. A camera may be affected by darkness, glare, occlusion, or weather. A database sensor may contain missing or outdated records. Perception is therefore an interpretation process, not a direct copy of reality.

Actuators allow the agent to influence the environment. Their capabilities and limitations constrain what the agent can achieve. A delivery robot may calculate an ideal route but be unable to follow it because of battery capacity, obstacles, or restricted access.

An agent operates through an architecture, which supplies the mechanisms for sensing, computation, memory, and action. The agent program runs on that architecture. Common conceptual agent types include:

Simple reflex agents

A simple reflex agent selects an action using only the current percept, often through condition–action rules. For example, a vacuum agent may execute “if the current square is dirty, then clean.” These agents can be effective in fully observable environments with simple, stable rules, but they perform poorly when the current percept does not reveal relevant history.

Model-based reflex agents

A model-based agent maintains an internal state that summarizes aspects of the world not directly visible in the current percept. It uses a model of how the world changes and how its actions affect the world. This enables it to reason about hidden conditions, such as whether a room was previously cleaned or whether an object may be behind an obstacle.

Goal-based agents

A goal-based agent chooses actions that help achieve specified goals. It may compare alternative action sequences and use search or planning. A route-planning system is goal-based because it seeks a path from an origin to a destination.

Utility-based agents

When several actions can achieve a goal, or when outcomes involve trade-offs, a utility-based agent ranks outcomes using a utility function. A vehicle may seek a route that balances travel time, fuel use, tolls, comfort, and safety. Utility functions make preferences explicit, although designing them can be difficult and ethically sensitive.

Learning agents

A learning agent improves its behavior through experience. A common conceptual structure contains:

• a performance element, which selects actions;
• a learning element, which improves the performance element;
• a critic, which evaluates behavior against a performance standard; and
• a problem generator, which proposes exploratory actions.

Learning can increase adaptability, but it also introduces risks such as biased training data, distribution shift, unpredictable behavior, and difficulties in explaining decisions.

3. Performance Measures and PEAS

A performance measure specifies how the success of an agent is evaluated. It should describe outcomes rather than merely internal procedures. For an autonomous taxi, “turn the steering wheel frequently” is not a useful performance measure. Safer and more meaningful criteria include reaching the correct destination, avoiding collisions, obeying traffic rules, minimizing unreasonable delay, and protecting passenger privacy.

A good performance measure should be:

• aligned with the real objective;
• observable or measurable where possible;
• sensitive to important costs and risks;
• resistant to easy exploitation; and
• explicit about trade-offs.

An inadequately designed measure can produce reward hacking, in which an agent achieves the formal objective while violating the intended purpose. If a cleaning robot is rewarded only for the number of cleaning movements, it may move its brush repeatedly without making the floor cleaner.

PEAS framework

PEAS is a practical framework for specifying an agent task:

• Performance measure: criteria for success.
• Environment: the external world in which the agent operates.
• Actuators: mechanisms by which the agent acts.
• Sensors: mechanisms by which the agent perceives.

#### Example: autonomous delivery vehicle

| Component | Specification |

|---|---|

| Performance measure | Safe and lawful delivery, correct destination, reasonable time and energy use, protection of goods and personal data |

| Environment | Roads, sidewalks, buildings, pedestrians, vehicles, weather, traffic rules, delivery locations |

| Actuators | Steering, braking, acceleration, lights, display, communication system, delivery mechanism |

| Sensors | Cameras, lidar, radar, GPS, inertial sensors, maps, communication feeds |

PEAS is not an algorithm. It is a task specification that helps designers identify requirements before selecting an architecture or implementation method.

4. Classifying Task Environments

The nature of an environment strongly influences agent design. The following dimensions are especially important.

Fully observable and partially observable

An environment is fully observable when the agent’s sensors provide all information relevant to choosing an action. In a board game with a visible board, the state may be fully observable. It is partially observable when relevant information is hidden, noisy, delayed, or unavailable. Driving in fog and diagnosing a disease from incomplete records are partially observable tasks.

Partial observability often requires memory, probabilistic reasoning, state estimation, or information-gathering actions.

Deterministic and stochastic

In a deterministic environment, the next state is completely determined by the current state and action. In a stochastic environment, outcomes involve uncertainty. A robot’s movement may be affected by wheel slip, and a recommendation may or may not influence a user.

Some environments are described as strategic when uncertainty arises primarily from the actions of other agents. Chess is strategically uncertain even though its rules are deterministic: the opponent’s future move is not known.

Episodic and sequential

In an episodic environment, each decision is relatively independent of previous decisions. Classifying separate images can be episodic if one classification does not affect the next. In a sequential environment, current actions influence future states and opportunities. Route planning and playing chess are sequential.

Static and dynamic

A static environment does not change while the agent is deciding. A crossword puzzle is approximately static. A dynamic environment changes during deliberation, as in financial markets or road traffic. A semidynamic environment does not change internally, but the performance measure changes with time—for example, a chess clock.

Discrete and continuous

A discrete environment has a finite or countable set of states, percepts, or actions, such as chess positions and legal moves. A continuous environment involves variables that can take values over ranges, such as position, speed, temperature, and time. Hybrid environments contain both kinds of variables.

Single-agent and multi-agent

A single-agent problem does not contain another decision-making agent whose behavior directly affects the outcome. In a multi-agent environment, other agents may cooperate, compete, or behave unpredictably. Autonomous driving, online auctions, and cybersecurity are multi-agent settings.

Known and unknown

In a known environment, the agent understands the relevant rules or transition behavior. In an unknown environment, it must learn or infer how actions affect outcomes. Observability and knowledge are different: an environment can be fully observable but initially unknown, or partially observable but governed by known rules.

Most real applications combine difficult properties. Autonomous driving is partially observable, stochastic, sequential, dynamic, continuous, multi-agent, and only partly known. This explains why it is substantially more difficult than a small board-game problem.

5. Problem Formulation

Problem formulation converts a task into a representation suitable for systematic reasoning. A classical search problem is specified by five components:

1. Initial state: the state in which the agent begins.

2. Actions: the actions available in each state.

3. Transition model: the result of applying an action to a state.

4. Goal test: a procedure that determines whether a state satisfies the objective.

5. Path-cost function: a method for assigning cost to a sequence of actions.

The set of reachable states and transitions forms a state space. A solution is an action sequence that leads from the initial state to a goal state. An optimal solution is a solution with the lowest path cost according to the specified cost function.

A transition model may be written as:

RESULT(s, a) = s′

where s is the current state, a is an applicable action, and s′ is the resulting state. In a stochastic problem, the result may instead be a probability distribution over possible successor states.

The cost of a path can be expressed as the sum of step costs:

g(n) = c₁ + c₂ + ... + cₖ

where each cᵢ is the cost of one action in the path and all costs are measured in a consistent unit. If costs represent time, the total must be in units of time; if they combine time, money, and risk, a justified common utility or weighted cost model is required. Step costs are normally assumed to be nonnegative in standard search formulations.

Choosing the right level of abstraction

A state representation should retain information necessary to distinguish relevant future possibilities while omitting irrelevant detail. Too little information can make the model incorrect; too much can make search unnecessarily expensive.

For route planning, a state might be represented simply as the current city. For a delivery vehicle, the state may need to include location, remaining packages, vehicle capacity, battery level, and time constraints. For a robot manipulating objects, the state may include object positions, orientations, gripper status, and obstacles.

The choice of representation is a modeling decision, not a purely technical detail. It determines what the system can reason about and what it ignores.

6. Worked Example: Delivery Route Formulation

Consider a courier that must travel from depot A to customer D. The road network is represented by the following connections and travel costs in minutes:

• A–B: 4
• A–C: 2
• B–C: 1
• B–D: 5
• C–D: 8

Assume roads are bidirectional, travel times are fixed, and the only goal is to reach D as quickly as possible.

Initial state: A.

Actions: travel along any road connected to the current location.

Transition model: taking a road changes the state to the connected location.

Goal test: the current location is D.

Path cost: total travel time in minutes.

Candidate routes include:

• A → B → D: 4 + 5 = 9 minutes.
• A → C → D: 2 + 8 = 10 minutes.
• A → C → B → D: 2 + 1 + 5 = 8 minutes.

Under the stated model, A → C → B → D is the least-cost solution at 8 minutes. The result depends on the formulation. If the courier must avoid visiting the same location twice, or if roads have one-way restrictions, congestion, tolls, or delivery deadlines, the state and cost model must be changed.

This example also illustrates the distinction between a state and a node. A state is a representation of a world condition, such as “the courier is at C.” A search node is a data structure that may contain the state, parent node, action used to reach it, and path cost. The same state can occur in multiple nodes when reached through different paths.

7. Search Spaces, Goals, and Costs

The solution space is the set of possible action sequences or reachable states considered by a problem-solving agent. It may be finite or effectively enormous. A problem can be easy to state but difficult to solve because the number of possibilities grows rapidly.

A goal should be stated at the appropriate level. “Reach customer D” is a goal test. “Use route A–C–B–D” is a proposed plan, not a general goal. A well-defined goal permits multiple possible solutions and allows an algorithm to compare them.

Costs may represent distance, time, energy, money, risk, number of actions, or a combination. A single shortest path may not be appropriate when objectives conflict. For example, a delivery system may minimize a weighted cost such as:

Total cost = travel time cost + energy cost + risk cost

The weights must be justified because changing them changes the preferred solution. In safety-critical systems, risk should not be treated merely as a small adjustable penalty if regulations require hard constraints. A safer formulation may define unacceptable states as forbidden rather than merely expensive.

8. From Formulation to Problem-Solving Agents

A classical problem-solving agent typically follows these stages:

1. Formulate a goal.

2. Formulate a problem.

3. Search for a solution.

4. Execute the solution.

5. Replan if observations reveal that assumptions are incorrect.

This approach works best when the environment is sufficiently known, the world does not change rapidly, and actions have predictable effects. In dynamic or uncertain settings, an agent may need continual planning, feedback control, online search, or decision-making under uncertainty rather than a fixed action sequence.

Problem formulation should precede algorithm selection. Breadth-first search, uniform-cost search, depth-first search, heuristic search, reinforcement learning, and planning systems solve different classes of problems. Selecting an algorithm before clarifying states, actions, goals, and costs often produces a technically impressive but operationally inappropriate system.

9. Applied Case: Hospital Delivery Robot

Background

This illustrative case concerns a hospital robot that transports medication and laboratory samples between a pharmacy, wards, and diagnostic departments.

Problem

The robot must deliver items on time while avoiding people, maintaining secure custody of materials, conserving battery power, and respecting restricted areas. A simple shortest-distance formulation is insufficient because the shortest corridor may be crowded or temporarily closed.

Analysis

A PEAS specification might include:

• Performance: timely and correct delivery, collision avoidance, secure handling, low energy use, compliance with hospital rules.
• Environment: corridors, elevators, patients, staff, carts, doors, restricted zones, changing schedules.
• Actuators: wheels, brakes, lights, display, speaker, door and elevator interface.
• Sensors: cameras, lidar, proximity sensors, RFID, map data, battery monitor, elevator status.

A useful state could include robot location, destination, battery level, carried item, access permissions, and relevant corridor conditions. Actions might include moving to an adjacent map location, waiting, requesting elevator service, or returning to a charging station. The goal test must include both physical arrival and confirmation that the correct item reached the authorized recipient.

Approach and solution

The system can use a layered design. A high-level planner selects a route using travel time, congestion, battery, and access constraints. A local motion controller reacts to nearby people and obstacles. If a corridor becomes blocked, the robot updates its state estimate and replans. Security checks should be enforced as constraints, not left solely to a route-cost calculation.

Outcome

The formulation supports measurable evaluation: delivery accuracy, on-time rate, near-collision rate, energy consumption, unauthorized-access incidents, and successful recovery from blocked routes. It also makes system boundaries visible. For example, the planner cannot guarantee safe operation if sensors fail or if hospital maps are outdated.

Learning points

The case demonstrates that intelligent behavior depends on more than route optimization. A realistic agent requires a performance measure, an explicit environment model, appropriate sensing and actuation, a carefully chosen state representation, and mechanisms for uncertainty, replanning, security, and human interaction.

10. Challenges, Ethics, and Governance

Specification failure

The most serious failure may occur before implementation: a poorly chosen objective can produce harmful behavior while satisfying the formal measure. Stakeholders should review whether the performance measure represents safety, fairness, privacy, accessibility, and legal obligations.

Sensor and model limitations

Sensors can be inaccurate, biased, or incomplete. A model trained in one environment may fail in another. Systems should monitor confidence, detect out-of-distribution conditions where possible, and define safe fallback behavior.

Human agency and accountability

When an agent acts on behalf of an organization, responsibility must remain clearly assigned. Users should understand when automated recommendations or actions are being used. High-impact systems require audit trails, access controls, incident reporting, and meaningful human review.

Fairness and distributional effects

A performance measure can distribute benefits and burdens unevenly. A routing system that minimizes average travel time may consistently send noise or pollution through particular neighborhoods. Designers should evaluate outcomes across relevant groups and include social constraints where appropriate.

Privacy and security

Sensors may collect sensitive location, identity, health, or behavioral information. Data minimization, purpose limitation, retention controls, encryption, and authorization are important design practices. Agents that can act in digital or physical environments also need protection against manipulation, adversarial inputs, and unauthorized commands.

11. Best Practices for Agent and Problem Design

1. Define the real-world objective before choosing an algorithm.

2. Write a PEAS description and consult domain stakeholders.

3. Separate goals from methods; do not confuse a preferred plan with the objective.

4. Make assumptions about observability, uncertainty, timing, and action effects explicit.

5. Choose the simplest state representation that preserves decision-relevant information.

6. Define costs and constraints separately when some outcomes are unacceptable.

7. Test the formulation on normal, exceptional, and adversarial scenarios.

8. Include monitoring, logging, fallback behavior, and human escalation.

9. Validate performance across environments and affected populations.

10. Revisit the formulation when the environment, policy, or social objective changes.

Contemporary Developments

Modern AI agents increasingly combine perception, language, planning, learning, and tool use. A language-based agent may interpret a user request, retrieve information, call software tools, and execute a multistep plan. However, fluent language does not guarantee a correct world model or rational action. Contemporary systems therefore require grounding, permission controls, verification, uncertainty handling, and evaluation beyond conversational quality.

In robotics and autonomous systems, the trend is toward hybrid architectures that combine learned perception with symbolic constraints, optimization, feedback control, and safety monitors. In all such systems, the classical questions remain essential: What does the agent observe? What can it do? What counts as success? What assumptions define the state and transition model? These questions remain relevant even when the implementation uses deep learning or generative models.

Chapter Summary

An intelligent agent perceives an environment through sensors and acts through actuators. Its agent function maps percept histories to actions, while an agent program implements that function on an architecture. Rationality means selecting an action expected to maximize a specified performance measure given available information and capabilities; it does not imply omniscience or guaranteed success.

The PEAS framework describes performance measures, environment, actuators, and sensors. Task environments can be classified as fully or partially observable, deterministic or stochastic, episodic or sequential, static or dynamic, discrete or continuous, single-agent or multi-agent, and known or unknown. These properties influence the design of an agent.

Problem formulation converts a task into an initial state, actions, transition model, goal test, and path-cost function. A solution is an action sequence that reaches a goal; an optimal solution has the lowest cost under the chosen model. State representation, objective design, constraints, uncertainty, ethics, and governance are as important as the search algorithm. Effective AI engineering therefore begins with careful specification and continues with evaluation, monitoring, and responsible deployment.

Key Terms

Agent: An entity that perceives an environment and acts upon it.

Agent function: A mapping from percept sequences to actions.

Agent program: An implementation of an agent function.

Actuator: A mechanism through which an agent affects its environment.

Autonomy: The degree to which behavior is generated from an agent’s own experience rather than fixed instructions.

Environment: The external world in which an agent operates.

Performance measure: A criterion used to evaluate an agent’s success.

PEAS: A framework consisting of Performance measure, Environment, Actuators, and Sensors.

Rational agent: An agent that chooses actions expected to optimize its performance measure given available information.

Sensor: A mechanism that provides perceptual information to an agent.

Percept: An individual input received by an agent.

Percept sequence: The complete history of percepts received by an agent.

State: A representation of relevant conditions in the world.

Action: An operation available to an agent in a state.

Transition model: A description of the result of applying an action to a state.

Goal test: A procedure that determines whether a state satisfies the objective.

Path cost: The total cost associated with an action sequence.

State space: The set of states reachable through applicable actions.

Solution: An action sequence leading from the initial state to a goal state.

Utility function: A function that ranks outcomes according to preferences or desirability.

Review Questions

Short Answer Questions

1. What is the difference between an agent function and an agent program?

2. Why does rationality not require an agent to be omniscient?

3. What are the four components of PEAS?

4. Distinguish a state from an action in a search problem.

5. What is meant by a partially observable environment?

Long Answer Questions

1. Explain the major types of intelligent agents and identify the circumstances in which each is useful.

2. Describe the principal dimensions used to classify task environments, giving an example for each.

3. Explain how a performance measure can lead to reward hacking and propose safeguards.

4. Discuss the importance of selecting an appropriate state representation in problem formulation.

5. Compare problem formulation in a static route-planning task with formulation in a dynamic autonomous-driving task.

Analytical / Application Questions

1. Construct a PEAS description for an AI-based crop-monitoring drone. Justify each component.

2. Formulate a search problem for an emergency vehicle traveling through a city where roads can become blocked. Identify how uncertainty and changing conditions should be represented.

3. A delivery system minimizes distance but frequently arrives late and uses restricted roads. Analyze the weaknesses in its formulation and propose revised goals, costs, and constraints.

Multiple Choice Questions with Answers

Question 1

Which statement best defines a rational agent?

A. An agent that always achieves the desired outcome

B. An agent that selects an action expected to maximize its performance measure given available information

C. An agent that has complete knowledge of its environment

D. An agent that uses machine learning for every decision

Correct Answer: B. An agent that selects an action expected to maximize its performance measure given available information

Question 2

In PEAS, what does the letter A represent?

A. Algorithms

B. Awareness

C. Actuators

D. Actions

Correct Answer: C. Actuators

Question 3

Which environment property describes a task in which relevant information may be hidden or noisy?

A. Partially observable

B. Episodic

C. Static

D. Discrete

Correct Answer: A. Partially observable

Question 4

Which item is not one of the five standard components of a classical search problem?

A. Initial state

B. Transition model

C. Goal test

D. Training dataset

Correct Answer: D. Training dataset

Question 5

A route has segment costs of 2, 1, and 5 minutes. What is its total path cost?

A. 6 minutes

B. 7 minutes

C. 8 minutes

D. 10 minutes

Correct Answer: C. 8 minutes

Question 6

What is the main purpose of a utility function?

A. To list all available sensors

B. To rank outcomes according to preferences

C. To guarantee a deterministic environment

D. To replace the transition model

Correct Answer: B. To rank outcomes according to preferences

Question 7

Which example is most clearly sequential rather than episodic?

A. Classifying independent photographs

B. Checking the spelling of separate words

C. Playing a game of chess

D. Detecting whether individual emails contain a particular phrase

Correct Answer: C. Playing a game of chess

Question 8

Why might a delivery system treat a restricted road as a constraint rather than merely assigning it a higher cost?

A. Because constraints identify outcomes that are unacceptable regardless of their cost

B. Because constraints eliminate the need for sensors

C. Because constraints guarantee the shortest route

D. Because constraints make every environment fully observable

Correct Answer: A. Because constraints identify outcomes that are unacceptable regardless of their cost

Question 9

In a transition model, RESULT(s, a) represents what?

A. The performance measure of an agent

B. The percept history of an agent

C. The state resulting from action a in state s

D. The cost of every action in the state space

Correct Answer: C. The state resulting from action a in state s

Question 10

Which statement about a state representation is correct?

A. It should include every physical detail of the real world

B. It should omit all information about previous actions

C. It should retain information relevant to future decisions while avoiding unnecessary detail

D. It must be identical for every AI application

Correct Answer: C. It should retain information relevant to future decisions while avoiding unnecessary detail