Intelligent Agents, Reasoning, and Search

Introduction

Artificial intelligence systems act in environments, interpret information, select actions, and pursue objectives. A navigation application, a medical decision-support tool, a warehouse robot, and a conversational assistant differ in their tasks, but each can be understood as an agent: a system that perceives its environment and acts upon it.

This chapter develops the foundations required to design such systems. It examines rational agents, task environments, knowledge representation, logic and inference, state-space search, heuristic methods, constraint satisfaction, planning, and decision-making under uncertainty. These topics remain important even when modern systems use machine learning, because learning systems still require objectives, representations, search procedures, constraints, and mechanisms for evaluating decisions.

Learning Objectives

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

• describe an intelligent agent and distinguish rationality from omniscience;
• analyse an environment using the PEAS framework and environment properties;
• compare reflex, model-based, goal-based, utility-based, and learning agents;
• explain knowledge representation, propositional logic, first-order logic, and inference;
• formulate problems as state-space search problems;
• compare uninformed and informed search algorithms;
• formulate and solve basic constraint satisfaction problems;
• explain planning and decision-making under uncertainty;
• evaluate practical, ethical, and governance issues in agent design.

1. Rational Agents and Task Environments

An agent receives percepts through sensors and affects its environment through actuators. A robot may use cameras and proximity sensors as inputs and motors as outputs. A software agent may receive web requests, database records, or user messages and produce API calls, recommendations, or text responses.

The agent function maps a percept sequence to an action:

Here, P* is the set of all possible percept sequences and A is the set of available actions. The agent program implements this function on a physical or computational architecture.

A rational agent chooses an action expected to maximise its performance measure, given the percept history, available knowledge, and computational resources. Rationality is not the same as perfection. An agent cannot know hidden facts or future events with certainty. It is rational when its action is appropriate relative to the information and objectives available at the time.

A useful formalisation is expected utility:

In this expression, a is a candidate action, e is the agent’s evidence, oᵢ is a possible outcome, P(oᵢ | a, e) is the probability of that outcome given the action and evidence, and U(oᵢ) is its utility. The expression applies when outcomes are represented probabilistically and utilities are defined on a common scale. A rational decision selects an action with maximal expected utility, subject to constraints such as safety, time, and resources.

The PEAS framework

PEAS describes a task environment through four elements:

A performance measure must be specified carefully. If a delivery robot is judged only by speed, it may drive dangerously. A better measure includes safety, legality, delivery accuracy, energy use, and customer satisfaction. Poorly designed objectives can produce technically successful but socially harmful behaviour.

Properties of environments

Environment properties influence agent architecture and algorithm choice.

• Fully observable versus partially observable: In a fully observable environment, the relevant state is available to the agent. In a partially observable environment, sensors provide incomplete or noisy information.
• Deterministic versus stochastic: In a deterministic environment, an action and current state determine the next state. In a stochastic environment, several outcomes are possible.
• Episodic versus sequential: In an episodic environment, each decision is relatively independent. In a sequential environment, present actions affect future opportunities.
• Static versus dynamic: A static environment does not change while the agent deliberates; a dynamic one may change continuously.
• Discrete versus continuous: States, actions, and time may be countable or may vary over continuous ranges.
• Single-agent versus multi-agent: Other agents may be absent, cooperative, competitive, or strategically unpredictable.
• Known versus unknown: The agent may or may not know the rules governing the environment.

Real-world environments are commonly partially observable, stochastic, sequential, dynamic, continuous, multi-agent, and only partly known. This explains why robust AI systems combine perception, prediction, planning, learning, and monitoring.

2. Agent Architectures

A simple reflex agent selects an action from the current percept using condition–action rules. For example, “if temperature exceeds the limit, activate cooling.” Such systems are fast and interpretable but fail when the current percept does not reveal the relevant state.

A model-based reflex agent maintains an internal state. It uses a model of how the world changes and how actions affect it. Internal state is essential when objects are temporarily hidden or observations are noisy.

A goal-based agent evaluates actions by asking whether they lead toward a specified goal. A route planner, for example, searches for a sequence of movements that reaches a destination.

A utility-based agent compares desirable outcomes rather than merely checking whether a goal is achieved. It can trade off travel time, cost, risk, comfort, and energy consumption.

A learning agent improves through experience. Its principal components are often described as:

1. a performance element that selects actions;
2. a learning element that improves the performance element;
3. a critic that evaluates behaviour;
4. a problem generator that proposes exploratory actions.

Learning does not remove the need for rational design. The objective, data, feedback, safety constraints, and deployment conditions still determine what is learned.

3. Knowledge Representation and Reasoning

An intelligent agent requires a representation of relevant entities, properties, relationships, events, and rules. Knowledge representation is the process of encoding information so that a machine can use it to derive conclusions and guide action.

A representation should provide:

• representational adequacy: ability to express relevant facts;
• inferential adequacy: ability to derive new facts;
• inferential efficiency: ability to derive them with manageable computation;
• acquisitional efficiency: ability to add new knowledge effectively.

Common representations include feature vectors, tables, semantic networks, ontologies, production rules, probabilistic graphical models, and logical languages. The appropriate representation depends on the problem. A relational database may be ideal for exact records, while a probabilistic model is more suitable for uncertain diagnosis.

Propositional logic

Propositional logic represents statements that are either true or false. If Rain means “it is raining” and WetRoad means “the road is wet,” then a rule may be written as:

The symbols include conjunction ∧, disjunction ∨, negation ¬, implication →, and biconditional ↔. A knowledge base contains facts and rules. Inference derives conclusions that follow from them.

A valid inference is one in which every model satisfying the premises also satisfies the conclusion. This property is called entailment. If a knowledge base contains Rain and Rain → WetRoad, it entails WetRoad. However, from Rain → WetRoad and WetRoad, one cannot validly infer Rain; this would be affirming the consequent.

First-order logic

Propositional logic cannot naturally express general relationships among objects. First-order logic adds predicates, variables, functions, and quantifiers. For example:

This means that every object that is a bird has wings. The universal quantifier ∀ means “for every,” while the existential quantifier ∃ means “there exists.”

A relation can be represented as Owns(Amina, Laptop). Rules can connect relations, such as:

The rule is useful only if the predicates are defined consistently. Logical systems generally use a closed-world assumption in some databases—what is not recorded is treated as false—or an open-world assumption in knowledge graphs—what is not recorded is merely unknown. Confusing these assumptions can lead to unsafe conclusions.

Inference methods

Forward chaining begins with known facts and repeatedly applies rules whose premises are satisfied. It is data-driven and useful when many consequences must be generated.

Backward chaining begins with a query and searches for rules that could establish it. It is goal-driven and can avoid deriving irrelevant facts.

Resolution is a general proof procedure that converts formulas into a suitable normal form and derives contradiction from the negation of a query. In practice, automated theorem provers often use restricted or optimised forms of resolution.

Logical inference has important limitations. Classical logic is monotonic: adding facts does not invalidate previous conclusions. Real environments contain defaults, exceptions, inconsistent reports, and changing information. Non-monotonic logic, belief revision, fuzzy logic, and probabilistic reasoning address some of these limitations, but they introduce additional modelling choices.

4. State-Space Search

Many AI tasks can be formulated as search problems. A problem specification consists of:

1. an initial state;
2. a set of actions or successor function;
3. a transition model describing action effects;
4. a goal test;
5. a path-cost function.

A solution is a sequence of actions that transforms the initial state into a goal state. The state space is the graph formed by states and transitions. Search algorithms construct or explore this graph without necessarily generating it in advance.

For a path containing actions with costs c₁, c₂, …, cₖ, the total path cost is:

This assumes additive costs. If costs represent time, energy, or money, they must be measured consistently. The optimal solution is the least-cost solution among all valid solutions.

Uninformed search

Breadth-first search (BFS) expands the shallowest unexpanded node first. With equal step costs, it is complete and optimal. Its principal weakness is memory consumption: it stores a broad frontier.

Depth-first search (DFS) expands the deepest node first. It uses less memory than BFS but is not generally optimal and may fail to terminate in infinite or cyclic spaces unless controlled.

Uniform-cost search (UCS) expands the node with the smallest path cost g(n). With non-negative action costs, it is complete and optimal under standard conditions. It is preferable to BFS when step costs differ.

Depth-limited search imposes a maximum depth. Iterative deepening search repeatedly applies depth-limited search with increasing limits. It combines the low memory requirement of DFS with the shallow-solution property of BFS when step costs are equal.

Informed search and heuristics

A heuristic h(n) estimates the cost from node n to a goal. Greedy best-first search selects a node with the lowest heuristic value, while A* evaluates:

Here, g(n) is the cost from the start to n, and h(n) estimates the remaining cost. A heuristic is admissible if it never overestimates the true remaining cost:

where h*(n) is the actual least cost from n to a goal. Under admissibility and non-negative step costs, tree-search A is optimal. For graph-search A, consistency is the stronger commonly used condition:

for every edge from n to n′. A consistent heuristic is admissible when the goal heuristic is zero, and it supports efficient graph-search implementations that do not need to reopen closed nodes.

A heuristic can be obtained by relaxing constraints, solving a simplified problem, using domain expertise, or learning from data. For the eight-puzzle, Manhattan distance—the sum of the horizontal and vertical distances of tiles from their target positions—is admissible because each tile must make at least that many moves, ignoring interference from other tiles.

Worked search example

Suppose a route problem has the following edges: Start–A with cost 2, Start–B with cost 5, A–Goal with cost 7, and B–Goal with cost 1. BFS may prefer the two-edge route through B or A depending on queue order, but it does not compare costs. UCS compares cumulative costs: the route through A costs 2 + 7 = 9, while the route through B costs 5 + 1 = 6. Therefore, UCS returns Start → B → Goal as the optimal route. The example shows why shallowest does not necessarily mean cheapest.

5. Constraint Satisfaction Problems

A constraint satisfaction problem (CSP) consists of variables, domains, and constraints. A solution assigns a value to every variable while satisfying all constraints.

For a map-colouring problem, variables are regions, domains are colours, and a constraint requires neighbouring regions to have different colours. For scheduling, variables may be activities, domains may be time slots and rooms, and constraints may express availability, capacity, and precedence.

A CSP can be represented as:

• variables X₁, X₂, …, Xₙ;
• domains D₁, D₂, …, Dₙ;
• constraints restricting allowable combinations.

Useful strategies include:

• Backtracking search: assign values incrementally and return to an earlier variable when a constraint is violated.
• Minimum remaining values (MRV): choose the variable with the fewest legal values.
• Degree heuristic: break ties by selecting the variable involved in the largest number of constraints.
• Least-constraining value: try the value that leaves the greatest flexibility for remaining variables.
• Forward checking: remove inconsistent values from unassigned variables after each assignment.
• Arc consistency: repeatedly remove a value when no compatible value remains in a neighbouring variable’s domain.

These methods reduce search by detecting failure early. They are especially useful in timetabling, configuration, resource allocation, routing, and scheduling.

6. Planning and Decision-Making Under Uncertainty

Search generally treats a problem as a route through a known state space. Planning uses actions with preconditions and effects to construct a sequence or policy. An action such as “dispatch vehicle” may require a charged vehicle and an available driver, and may produce the effect “package in transit.” Planning systems must consider interacting subgoals, resource limitations, temporal duration, and unexpected events.

Classical planning assumes a known, deterministic, static environment. Real applications often violate these assumptions. A delivery plan may be disrupted by traffic, a manufacturing action may fail, and a medical treatment may have uncertain outcomes.

A probability model assigns probabilities to possible states or outcomes. Bayes’ rule updates a belief when evidence is observed:

Here, H is a hypothesis, E is evidence, P(H) is the prior probability, P(E | H) is the likelihood, and P(H | E) is the posterior probability. The denominator P(E) is the probability of the evidence and ensures that posterior probabilities sum correctly. The rule applies when the probabilities are well-defined and P(E) > 0.

For sequential decisions, a Markov decision process (MDP) uses states, actions, transition probabilities, rewards, and a discount factor. The Bellman optimality equation is:

V*(s) is the optimal value of state s, a is an action, R(s,a) is the immediate reward, P(s′ | s,a) is the transition probability, and γ satisfies 0 ≤ γ < 1 when infinite-horizon discounted returns are used. The value of an action combines immediate reward with the expected discounted value of future states.

When the state is not directly observable, a partially observable MDP represents the agent’s belief—a probability distribution over possible states. The agent then plans over belief states. This is computationally difficult, but the framework clarifies why perception, prediction, and action cannot always be separated.

7. Applied Case: Illustrative Emergency-Department Triage Agent

Background

Consider a fictional hospital developing an AI assistant to help prioritise patients arriving at an emergency department. The system is not authorised to replace clinicians; it provides ranked recommendations and explanations.

Problem

The department must allocate limited clinical resources while patients present with incomplete information. Symptoms may be ambiguous, measurements may be noisy, and delays can have unequal consequences.

Analysis

The PEAS description includes patient safety and waiting-time fairness as performance measures; the emergency department and hospital resources as the environment; electronic records and physiological sensors as inputs; and alerts, queue recommendations, and requests for additional tests as outputs. The environment is partially observable, stochastic, dynamic, sequential, and multi-agent.

Knowledge representation combines structured patient facts, clinical ontologies, and probabilistic relationships. Logical rules can encode hard safety constraints, such as requiring immediate escalation when a confirmed critical indicator is present. Probabilistic models can estimate possible conditions, but an estimate must not be presented as certainty.

The scheduling component can be formulated as a CSP with variables for clinician assignment and treatment slots, domains of available resources, and constraints involving qualifications, capacity, and isolation requirements. Planning can represent alternative care pathways. Decision-making can use expected utility, but the utility function must give appropriate priority to severe harm prevention rather than merely maximising throughput.

Approach and safeguards

The assistant should display the evidence supporting a recommendation, identify missing data, preserve clinician override, log decisions, monitor performance across demographic groups, and undergo validation on data from different hospitals. Human review is required for high-risk or low-confidence cases. Data access must follow applicable health-privacy law and institutional governance.

Outcome and learning points

In this illustrative case, the most responsible system is not the one with the most complex algorithm. It is the one that combines appropriate representation, uncertainty handling, search or scheduling methods, transparent interfaces, monitoring, and clearly assigned accountability. The case demonstrates that rational action depends on both technical performance and the consequences of errors.

8. Limitations, Ethics, and Best Practices

AI agents can fail because sensors are incomplete, models are misspecified, data are biased, environments change, or objectives encourage undesirable shortcuts. Search can become computationally intractable as branching factor and depth increase. Logic may be brittle when knowledge is incomplete. Probabilistic models may be poorly calibrated. Learning agents may exploit weaknesses in a reward function.

Important governance principles include:

• define objectives and unacceptable behaviours before deployment;
• distinguish facts, assumptions, predictions, and recommendations;
• test under distribution shift and adversarial conditions;
• protect privacy through data minimisation, access control, and retention limits;
• document data provenance, model versions, and decision logs;
• provide meaningful human oversight for consequential decisions;
• evaluate accuracy, calibration, robustness, fairness, latency, and safety—not accuracy alone;
• establish monitoring, incident reporting, rollback, and appeal procedures.

Contemporary AI increasingly combines symbolic reasoning with machine learning. Neuro-symbolic systems may use learned perception together with logical constraints. Retrieval-augmented systems connect language models to external knowledge, but retrieved information still requires verification. Autonomous agents may use tool calls and planning loops, making access control, sandboxing, and action confirmation essential.

Chapter Summary

An intelligent agent perceives an environment and acts according to objectives. Rationality means selecting an action expected to perform well given available information and resources, not possessing perfect knowledge. PEAS provides a systematic way to specify an agent’s task, while environment properties guide architecture and algorithm selection.

Knowledge representation enables agents to store facts and relationships. Propositional and first-order logic support precise inference, but their assumptions must be understood. Search formulates problem solving as movement through a state space. BFS, DFS, UCS, and iterative deepening differ in completeness, optimality, and resource use. Heuristics guide search; A* is optimal under appropriate admissibility or consistency conditions. CSP methods solve assignment problems by combining backtracking with variable and value ordering. Planning extends search to actions with preconditions and effects. Probability, expected utility, and MDPs support decisions when outcomes are uncertain.

Professional AI development requires more than selecting an algorithm. Objectives, data quality, uncertainty, safety, fairness, privacy, explainability, monitoring, and accountability must be designed into the complete agent system.

Key Terms

Agent: A system that perceives an environment and takes actions.

Rational agent: An agent that selects actions expected to maximise its performance measure given available information.

PEAS: Performance measure, environment, actuators, and sensors.

Percept: An observation received by an agent.

Knowledge representation: Encoding information so that an agent can reason with it.

Propositional logic: Logic of statements that are true or false.

First-order logic: Logic using objects, predicates, variables, relations, and quantifiers.

Inference: Deriving conclusions from facts and rules.

Entailment: A relationship in which a conclusion is true in every model satisfying the premises.

State space: The set of states and transitions relevant to a search problem.

Breadth-first search: Search that expands the shallowest nodes first.

Uniform-cost search: Search that expands the lowest path-cost node first.

Heuristic: An estimate of the cost from a state to a goal.

Admissible heuristic: A heuristic that never overestimates the true remaining cost.

Constraint satisfaction problem: A problem involving variables, domains, and constraints.

Planning: Constructing actions that achieve goals under specified conditions.

Expected utility: The probability-weighted utility of possible outcomes.

Markov decision process: A model of sequential decisions using states, actions, rewards, and transition probabilities.

Belief state: A probability distribution over possible current states.

Human oversight: Deliberate human review, intervention, or accountability in an AI system.

Review Questions

Short Answer Questions

1. What is the difference between a rational agent and an omniscient agent?
2. Identify the four components of PEAS.
3. Why can a model-based agent operate more effectively than a simple reflex agent in a partially observable environment?
4. Define an admissible heuristic.
5. What are the variables, domains, and constraints in a constraint satisfaction problem?

Long Answer Questions

1. Compare simple reflex, model-based, goal-based, utility-based, and learning agents.
2. Explain how propositional logic and first-order logic differ in expressive power and inference use.
3. Compare BFS, DFS, UCS, and A* in terms of strategy, completeness, optimality, and memory.
4. Explain how Bayes’ rule supports reasoning under uncertainty and define every term in the equation.
5. Discuss why ethical governance is part of rational AI-agent design rather than an optional addition.

Analytical / Application Questions

1. Design a PEAS description for an autonomous warehouse vehicle and classify its environment properties. Justify each classification.
2. A search problem contains a low-cost deep route and a high-cost shallow route. Explain which algorithm should be used to guarantee the least-cost solution and why.
3. Propose a CSP formulation for university examination timetabling, including at least four variables, domains, and constraints. Recommend two strategies for reducing search.

Multiple Choice Questions with Answers

Question 1

Which statement best defines a rational agent?

A. An agent that always knows the future state of its environment

B. An agent that selects actions expected to maximise performance given available information

C. An agent that chooses the fastest action regardless of consequences

D. An agent that performs only predetermined actions

Correct Answer: B. An agent that selects actions expected to maximise performance given available information

Question 2

In PEAS, which item describes how an agent acts on its environment?

A. Performance measure

B. Environment

C. Actuators

D. Sensors

Correct Answer: C. Actuators

Question 3

Which inference is valid from Rain and Rain → WetRoad?

A. ¬WetRoad

B. Rain → ¬WetRoad

C. WetRoad

D. ¬Rain

Correct Answer: C. WetRoad

Question 4

Which search algorithm expands the node with the lowest cumulative path cost?

A. Depth-first search

B. Uniform-cost search

C. Greedy best-first search

D. Depth-limited search

Correct Answer: B. Uniform-cost search

Question 5

In A*, what does f(n) = g(n) + h(n) represent?

A. Estimated total solution cost through node n

B. Only the cost already paid to reach n

C. The branching factor at n

D. The depth limit of n

Correct Answer: A. Estimated total solution cost through node n

Question 6

A heuristic is admissible when it:

A. Always overestimates the remaining cost

B. Equals zero for every non-goal state

C. Never overestimates the true remaining cost

D. Ignores the current path cost

Correct Answer: C. Never overestimates the true remaining cost

Question 7

Which CSP heuristic selects the variable with the fewest legal values remaining?

A. Degree heuristic

B. Minimum remaining values

C. Least-constraining value

D. Forward reward selection

Correct Answer: B. Minimum remaining values

Question 8

In Bayes’ rule, P(H | E) denotes:

A. The prior probability of H

B. The likelihood of E given H

C. The probability of H given evidence E

D. The probability that H and E are impossible

Correct Answer: C. The probability of H given evidence E

Question 9

Which condition is required for the displayed discounted MDP Bellman equation with an infinite horizon?

A. γ must be greater than 1

B. γ must satisfy 0 ≤ γ < 1

C. All rewards must be negative

D. The environment must be fully observable

Correct Answer: B. γ must satisfy 0 ≤ γ < 1

Question 10

Why is human oversight especially important in high-risk AI applications?

A. It guarantees that the algorithm has no errors

B. It removes the need for testing and monitoring

C. It provides review, intervention, and accountability when consequences are significant

D. It makes uncertainty mathematically impossible

Correct Answer: C. It provides review, intervention, and accountability when consequences are significant