2. Intelligent Agents and Problem Formulation

Introduction and Context

Artificial intelligence is concerned not merely with producing outputs, but with designing systems that perceive situations, reason about alternatives, and act in ways that support specified objectives. The central abstraction used to describe such systems is the intelligent agent. An agent may be a software program, a robot, a decision-support system, an autonomous vehicle, or a human-supported computational service. What makes an agent intelligent is not simply its complexity; it is its capacity to select actions rationally in relation to its percepts, knowledge, objectives, and environment.

Problem formulation is the companion activity to agent design. Before an algorithm can search, plan, diagnose, or optimize, the problem must be represented in a form that makes relevant states, actions, goals, constraints, and evaluation criteria explicit. A poorly formulated problem can make an easy task appear difficult, or produce a technically correct solution that is operationally useless. In expert systems and modern AI applications, formulation therefore connects abstract objectives with computable models.

This chapter develops the agent perspective and explains how environments are characterized, how rational action is defined, and how real-world tasks are converted into state-space and utility-based problems. These ideas provide a foundation for later study of search, knowledge representation, planning, machine learning, and multi-agent systems.

Learning Objectives

After studying this chapter, the learner should be able to:

1. Define an intelligent agent and distinguish agents from ordinary programs.

2. Explain the interaction between sensors, actuators, environments, and agent programs.

3. Construct PEAS descriptions for practical AI systems.

4. Classify task environments using relevant environmental properties.

5. Compare table-driven, reflex, model-based, goal-based, utility-based, and learning-agent architectures.

6. Formulate problems using states, actions, transition models, goals, costs, utilities, and constraints.

7. Distinguish rationality from omniscience and explain the role of performance measures.

8. Analyze practical and ethical consequences of agent design choices.

The Agent as a Rational Decision Maker

An agent perceives its environment through sensors and changes the environment through actuators. A software agent may receive user requests, database records, network messages, or camera images as percepts. Its actuators may be commands to a robot motor, messages sent to a user, updates to a database, or changes to a control system.

The formal mapping from percept histories to actions is called the agent function. If an agent has received a percept sequence p, its function determines an action a:

`f: P* → A`

where P* is the set of possible percept sequences and A is the set of available actions. An agent program implements this function on a physical or computational architecture. The distinction is important: the function is an abstract specification of behavior, whereas the program is the executable mechanism that produces it.

An agent is rational when, for each percept sequence, it selects an action expected to maximize its performance measure, given its percept history, built-in knowledge, available actions, and computational limitations. Rationality is therefore relative to information and resources. A rational agent is not necessarily omniscient: it cannot know future events with certainty, nor can it undo the effects of an action simply because the outcome was unfavorable.

A useful formulation of rational action is:

`a* = argmax_a E[U(Result(a)) | percept history, knowledge]`

Here, `a*` is the selected action, `U` is a utility or performance function, and the expectation represents uncertainty about consequences. In deterministic environments, the expected-value component may be unnecessary; in uncertain environments, it becomes central.

Performance measures must be specified from the perspective of the task, not merely from the internal operation of the agent. For example, a medical triage agent should be evaluated by safety, diagnostic support, timeliness, and appropriate escalation—not simply by the number of cases processed. A navigation agent should balance arrival time, safety, legality, comfort, and energy consumption.

PEAS: Describing an Agent’s Task Environment

A practical method for specifying an agent task is the PEAS framework:

• Performance measure: criteria used to judge success.
• Environment: the external world in which the agent operates.
• Actuators: mechanisms through which the agent acts.
• Sensors: mechanisms through which the agent obtains information.

Consider an autonomous warehouse vehicle. Its performance measures may include successful delivery, collision avoidance, energy efficiency, delivery time, and compliance with traffic rules. Its environment includes shelves, workers, other vehicles, loading stations, floor markings, and changing orders. Its actuators include wheel motors, steering, braking, lights, and communication interfaces. Its sensors may include cameras, lidar, wheel encoders, proximity sensors, and wireless messages.

PEAS is valuable because it exposes assumptions that might otherwise remain hidden. If safety is omitted from the performance measure, an optimization system may favor speed at unacceptable risk. If moving workers are excluded from the environment, the state model becomes unrealistic. If sensor limitations are ignored, the proposed agent may depend on information that cannot actually be obtained.

Properties of Task Environments

Task environments differ in ways that strongly influence architecture and algorithm selection.

A fully observable environment provides the agent with all information relevant to action selection. Chess is approximately fully observable because the board is visible to both players. A medical diagnosis environment is often partially observable because the patient’s true condition cannot be directly inspected.

An environment is deterministic when the next state is completely determined by the current state and selected action. Many board-game moves are deterministic, whereas driving and financial forecasting are affected by uncertainty. In a stochastic environment, outcomes are described probabilistically. A strategic environment may also be described as nondeterministic when several outcomes are possible but no probability distribution is assumed.

A task is episodic when each decision is largely independent, as in classifying separate images. It is sequential when current actions influence future situations, as in navigation or treatment planning. An environment is static if it does not change while the agent deliberates; it is dynamic if changes continue during decision making. A crossword puzzle is relatively static, while air-traffic control is dynamic.

A discrete environment has distinct states, time steps, or actions. A continuous environment involves real-valued quantities such as velocity, temperature, or position. Finally, an environment may be single-agent or multi-agent. In multi-agent settings, other agents may cooperate, compete, or behave unpredictably. These properties are not merely descriptive. They determine whether the agent needs belief states, probabilistic models, real-time control, game-theoretic reasoning, or learning mechanisms.

Agent Architectures

The simplest architecture is the table-driven agent, which stores a response for every possible percept sequence. Although conceptually useful, this approach is impractical because the number of percept histories grows rapidly.

A simple reflex agent selects actions using condition–action rules. For example, a thermostat may use the rule “if temperature is below the threshold, switch on heating.” Such agents are efficient but operate reliably only when the current percept contains enough information to determine an appropriate action. They struggle with partial observability and long-term consequences.

A model-based reflex agent maintains an internal state. It uses a transition model describing how the world changes and an observation model describing how percepts relate to the world. This allows it to remember relevant aspects of the past and act when the current percept is incomplete.

A goal-based agent selects actions by considering whether they lead toward a goal. Search and planning algorithms commonly use this architecture. A route-planning system, for example, evaluates possible sequences of road movements in relation to reaching a destination.

A utility-based agent assigns degrees of desirability to outcomes. Goals alone may classify outcomes as achieved or not achieved, but utility allows trade-offs. A route planner may prefer a slightly longer route if it is safer, less expensive, or more reliable. Utility functions also support decision making under uncertainty through expected utility.

A learning agent improves its behavior from experience. A standard conceptual model contains a performance element, a learning element, a critic, and a problem generator. The performance element chooses actions; the critic evaluates results; the learning element modifies behavior; and the problem generator encourages useful exploration. Learning is especially valuable when the environment is too complex to model completely in advance, but it introduces concerns about data quality, distribution shift, interpretability, and control of exploration.

Architectures may be combined. An autonomous vehicle can use reflex rules for emergency braking, a world model for tracking nearby objects, goals for route planning, utilities for balancing travel time and safety, and learning components for perception.

From Real-World Tasks to Formal Problems

A problem formulation identifies the information required to search for or evaluate solutions. In a classical state-space formulation, a problem consists of:

1. An initial state.

2. A set of actions available in each state.

3. A transition model specifying the result of an action.

4. A goal test determining whether a goal has been reached.

5. A path-cost function assigning cost to a sequence of actions.

The state is an abstract description of the aspects of the world relevant to future decisions. It need not record every physical detail. In route planning, a state might be the current city; in robotic manipulation, it may include object positions, gripper status, and obstacle configuration. A good representation preserves information needed for action selection while excluding irrelevant detail.

The state space is the set of all states reachable from the initial state through available actions. A path is a sequence of states connected by actions. A solution is a path satisfying the goal test. The quality of a solution may be evaluated by total path cost, which is often expressed as:

`g(path) = Σ c(action_i)`

where each action has a cost such as time, distance, financial expense, energy use, or risk.

A formulation is complete with respect to a task when it represents all distinctions necessary to find acceptable solutions. It is also useful to distinguish the physical state from the belief state. Under partial observability, an agent may not know the exact physical state; it instead maintains a set or probability distribution over possible states. A diagnostic agent may therefore reason about possible diseases rather than a single confirmed disease state.

Goals, Utilities, and Constraints

Goals specify desired conditions, but they do not always specify which successful outcome is preferable. A goal such as “deliver the package” leaves open questions about time, cost, carbon emissions, and reliability. Utility functions address these trade-offs by assigning values to outcomes or trajectories.

A multi-criteria utility may be represented conceptually as:

`U = w1(Safety) + w2(Time) + w3(Cost) + w4(Comfort)`

where the weights express the relative importance of criteria. In real systems, such expressions require careful validation. Numerical precision does not make subjective preferences objective, and poorly chosen weights can produce harmful behavior.

Constraints limit permissible states or actions. Hard constraints must never be violated, such as legal restrictions, maximum physical load, or access permissions. Soft constraints represent preferences that may be relaxed at a cost. For example, a scheduling system may prefer balanced workloads but allow imbalance during an emergency.

Problem formulation should make constraints explicit. Treating a safety requirement as a soft preference can permit unacceptable solutions. Conversely, treating every preference as an absolute constraint may make the problem infeasible. Constraint satisfaction problems generally specify variables, domains of possible values, and constraints governing combinations of values. Scheduling, timetabling, configuration, and resource allocation are common examples.

A Structured Formulation Example: Emergency Vehicle Dispatch

Consider an illustrative emergency-dispatch system for a metropolitan area. The system receives incident reports and recommends which available vehicle should respond.

The initial state includes the locations and statuses of ambulances, road conditions, hospital capacities, incident location, and estimated severity. Actions include assigning a vehicle, selecting a route, rerouting a vehicle, or requesting assistance. The transition model represents travel, vehicle arrival, hospital admission, and changing availability. The goal may be to ensure that every high-priority incident receives an appropriate response. The path cost may combine response time, fuel use, congestion exposure, and missed coverage of other regions.

The environment is partially observable because reports may be incomplete and traffic conditions uncertain. It is dynamic because incidents and road conditions change while computation occurs. It is multi-agent because human dispatchers, drivers, hospitals, and other emergency services influence outcomes. A utility-based formulation can balance rapid response against maintaining city-wide coverage.

A purely time-minimizing system might send the nearest ambulance to every incident, leaving another district unprotected. A better formulation includes a constraint requiring minimum emergency coverage and a utility penalty for excessive risk or delayed high-severity cases. The example demonstrates that algorithmic performance depends on the quality of the model and not only on the efficiency of the search procedure.

Case Study: Intelligent Hospital Bed Allocation

Background

This illustrative case concerns a hospital that must allocate beds among emergency, surgical, infectious-disease, and recovery patients. Bed availability changes continuously as patients are admitted, transferred, discharged, or delayed.

Situation and Problem

A rule-based system that assigns the first available bed may create downstream congestion. For example, placing a patient in a bed unsuitable for isolation can require later transfers, while allocating all flexible beds to low-priority cases may prevent treatment of urgent arrivals. The hospital requires a decision-support agent rather than an autonomous system that disregards clinical authority.

Analysis

The performance measure should include patient safety, clinical suitability, waiting time, infection-control compliance, efficient use of beds, and fairness among patient groups. The environment is dynamic, partially observable, stochastic, and multi-agent. Relevant percepts include patient condition, bed attributes, cleaning status, predicted discharge time, staffing levels, and isolation requirements.

The state representation includes occupied and available beds, patient needs, care-team capacity, and pending admissions. Actions include assigning, reserving, transferring, or delaying a placement. Hard constraints include isolation regulations, equipment requirements, and authorization rules. Soft preferences include minimizing transfers and reducing waiting time.

Approach and Strategy

A model-based, utility-aware agent can generate feasible allocations and rank them according to validated institutional priorities. Predictive models may estimate discharge likelihood, but recommendations should display uncertainty and allow clinicians to override them. The system should record the information used, the recommendation produced, the person accepting or rejecting it, and the eventual outcome.

Outcome

In an illustrative deployment, the principal benefit is not complete automation but improved coordination and earlier identification of bottlenecks. The system can warn that a locally optimal assignment would reduce capacity for an expected emergency surge. Its effectiveness depends on accurate data, integration with hospital workflows, and governance of exceptions.

Learning Points

The case shows that agent design begins with performance measures and constraints, not with an algorithm. It also shows why human oversight, explainability, audit trails, and fairness are integral to rational decision making in high-impact environments.

Professional Applications and Design Considerations

Agent-based problem formulation is used in robotics, intelligent transportation, cybersecurity, recommendation, logistics, finance, industrial control, public administration, and software operations. In organizations, the formulation process often requires collaboration among domain experts, data engineers, AI developers, legal specialists, and end users.

Common mistakes include defining a vague goal, confusing available data with complete knowledge, ignoring costs of sensing and computation, omitting exceptional cases, optimizing a proxy rather than the real objective, and failing to model other actors. A system may achieve high prediction accuracy while making poor decisions if its actions are not connected to appropriate utility and constraints.

A further risk is reward hacking or specification gaming: an agent maximizes the formal measure while violating the intention behind it. If a cleaning robot is rewarded only for visible cleanliness, it may move dirt out of view rather than remove it. Robust design therefore requires adversarial testing, scenario analysis, monitoring, and periodic review of objectives.

Ethically significant systems require attention to privacy, discrimination, accountability, transparency, security, and human control. Sensors may collect personal information beyond what is necessary. A utility function may disadvantage vulnerable groups if fairness is not represented. Autonomous action may be inappropriate where decisions affect liberty, health, employment, or access to essential services. Professional practice should therefore apply data minimization, access control, documentation, impact assessment, and meaningful escalation procedures.

Current Developments

Modern agents increasingly combine symbolic models with machine learning. Large language model agents can interpret instructions, use tools, maintain short-term context, and plan sequences of actions; however, their outputs may be uncertain and require verification. Digital twins provide simulated environments for testing decisions before deployment. Reinforcement learning supports policy acquisition through interaction, while constrained and safe reinforcement learning attempts to prevent unacceptable behavior during exploration.

Another important direction is uncertainty-aware and human-centered autonomy. Rather than presenting a single unexplained action, advanced systems may present alternatives, confidence estimates, predicted consequences, and reasons for escalation. Multi-agent systems also require coordination protocols, communication models, and mechanisms for resolving conflicts among objectives.

Best Practices for Problem Formulation

A disciplined formulation process should:

• define the decision-maker, users, and affected stakeholders;
• specify performance measures before selecting an algorithm;
• separate hard constraints from preferences;
• model uncertainty, partial observability, and time-dependent change;
• identify what the agent can sense and what it cannot know;
• choose the simplest state representation that preserves decision-relevant information;
• test the formulation against normal, rare, adversarial, and ethically sensitive scenarios;
• include human override, logging, monitoring, and review mechanisms;
• validate utility weights and assumptions with domain experts; and
• reassess the model when the environment, policy, or organizational objective changes.

Chapter Summary

An intelligent agent perceives an environment and acts through actuators in pursuit of objectives. Rationality means selecting actions expected to produce the best outcomes according to a specified performance measure, available information, and resource limits. PEAS provides a practical framework for describing performance measures, environments, actuators, and sensors. Environmental properties such as observability, determinism, dynamism, continuity, and the presence of other agents influence architecture and algorithm choice.

Agent architectures range from simple reflex systems to model-based, goal-based, utility-based, and learning agents. Problem formulation converts a real task into states, actions, transition models, goals, costs, utilities, and constraints. Effective formulation is often more important than choosing a sophisticated algorithm because it determines what the system is actually optimizing. Practical systems must also address uncertainty, safety, fairness, privacy, accountability, and human oversight.

Key Terms

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

Agent function: An abstract mapping from percept sequences to actions.

Agent program: An implementation of an agent function on an architecture.

Rational agent: An agent that selects actions expected to maximize its performance measure.

Percept: An observation received through an agent’s sensors.

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

State: An abstract description of a situation relevant to future decisions.

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

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

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

Path cost: The accumulated cost of actions along a path.

Utility: A numerical or ordered representation of outcome desirability.

Constraint: A condition limiting permissible states, values, or actions.

Belief state: A representation of possible physical states under partial observability.

Simple reflex agent: An agent that selects actions from current percepts using rules.

Model-based agent: An agent that maintains an internal representation of relevant world state.

Goal-based agent: An agent that evaluates actions by their contribution to goal achievement.

Learning agent: An agent that improves its behavior through experience or feedback.

Reward hacking: Optimization of a formal objective in a way that defeats its intended purpose.

Review Questions

Short Answer Questions

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

2. Explain the four elements of PEAS.

3. Why is rationality different from omniscience?

4. What is the role of a transition model in problem formulation?

5. Distinguish a hard constraint from a soft constraint.

Long Answer Questions

1. Explain the major agent architectures and discuss the circumstances in which each is appropriate.

2. Describe the principal properties of task environments and analyze their effect on agent design.

3. Explain how a real-world task is converted into a state-space problem.

4. Discuss the roles of goals, utilities, costs, and constraints in decision-making.

5. Explain the ethical and professional responsibilities involved in designing agents for high-impact domains.

Analytical / Application Questions

1. Construct a PEAS description for an AI-based university course-scheduling agent and classify its environment.

2. Formulate an intelligent waste-collection system using states, actions, goals, costs, and at least two constraints. Explain possible specification-gaming risks.

3. A delivery agent must choose between a fast route with high accident exposure and a slower route with reliable safety. Propose a utility-based formulation and explain how uncertainty should be handled.

22. Multiple Choice Questions with Answers

Question 1

Which statement best describes a rational agent?

A. It always predicts the future correctly.

B. It selects the action expected to optimize its performance measure given available information.

C. It follows the same action for every percept.

D. It avoids acting whenever the environment is uncertain.

Correct Answer: B. It selects the action expected to optimize its performance measure given available information.

Question 2

In PEAS, which element specifies how success will be judged?

A. Performance measure

B. Environment

C. Actuators

D. Sensors

Correct Answer: A. Performance measure

Question 3

A diagnostic system cannot directly observe a patient’s true disease and must reason over alternatives. Which property is most relevant?

A. Fully observable

B. Static

C. Partially observable

D. Episodic

Correct Answer: C. Partially observable

Question 4

Which architecture maintains an internal representation to cope with incomplete current percepts?

A. Table-driven agent

B. Simple reflex agent

C. Model-based agent

D. Random agent

Correct Answer: C. Model-based agent

Question 5

What distinguishes a utility-based agent from a purely goal-based agent?

A. It cannot use goals.

B. It ranks different desirable outcomes and trade-offs.

C. It acts without sensors.

D. It requires a fully observable environment.

Correct Answer: B. It ranks different desirable outcomes and trade-offs.

Question 6

Which item is not normally one of the elements of a classical state-space problem formulation?

A. Initial state

B. Transition model

C. Goal test

D. Programming language syntax

Correct Answer: D. Programming language syntax

Question 7

A hospital allocation system must never place an infectious patient in a non-isolation bed. This requirement is best represented as a:

A. Soft preference

B. Hard constraint

C. Path heuristic

D. Percept sequence

Correct Answer: B. Hard constraint

Question 8

Why might a nearest-vehicle dispatch rule produce poor city-wide performance?

A. It necessarily violates every transition model.

B. It may optimize local response time while ignoring coverage of other areas.

C. It cannot use actuators.

D. It makes the environment fully observable.

Correct Answer: B. It may optimize local response time while ignoring coverage of other areas.

Question 9

What is reward hacking?

A. Improving a reward function through human feedback only

B. An agent achieving a formal objective while defeating its intended purpose

C. Reducing all actions to reflex rules

D. Using a state space with no goals

Correct Answer: B. An agent achieving a formal objective while defeating its intended purpose

Question 10

Under partial observability, an agent may need to represent:

A. Only the last action taken

B. A belief state containing possible physical states

C. The complete future percept sequence

D. No state information at all

Correct Answer: B. A belief state containing possible physical states