11. Planning, Reinforcement Learning, Robotics, and Multi-Agent Systems

Introduction and Context

Intelligent behaviour is rarely a single-step classification problem. An autonomous vehicle must select a sequence of actions, a warehouse robot must coordinate movement with other machines, and a software agent must decide how to allocate limited resources over time. These tasks require sequential intelligence: the ability to perceive a changing environment, predict consequences, choose actions, learn from outcomes, and revise decisions.

This chapter examines four closely related areas of artificial intelligence. Planning represents action sequences explicitly, reinforcement learning acquires behaviour through interaction and feedback, robotics connects intelligent reasoning with physical bodies, and multi-agent systems distribute intelligence among several interacting entities. Although these areas use different formalisms, they address a common problem: how an agent can act effectively when decisions have delayed consequences, information is incomplete, and other agents may influence the outcome.

Classical planning is most effective when the world is sufficiently known and actions have predictable effects. Probabilistic planning and Markov decision processes become necessary when uncertainty is central. Reinforcement learning is useful when an agent can interact with an environment but does not know an appropriate policy in advance. Robotics introduces sensing, dynamics, embodiment, and safety constraints. Multi-agent systems add communication, cooperation, competition, negotiation, and distributed control.

Learning Objectives

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

1. Explain the relationship between planning, decision-making, learning, robotics, and multi-agent intelligence.

2. Formulate planning problems using states, actions, goals, transition models, and costs.

3. Distinguish classical planning from probabilistic planning and Markov decision processes.

4. Describe reinforcement-learning components, including policies, value functions, rewards, exploration, and temporal-difference learning.

5. Analyse the architecture of robotic systems from perception to control.

6. Explain coordination, communication, negotiation, and distributed decision-making in multi-agent systems.

7. Select appropriate methods for practical sequential-decision problems.

8. Evaluate technical, ethical, safety, and governance issues in autonomous systems.

Sequential Decision-Making as a Unifying Idea

A sequential decision problem can be represented by an agent interacting with an environment. At time t, the agent observes information about the current situation, selects an action, receives a reward or cost, and arrives at a new situation. The quality of a decision depends not only on its immediate result but also on its effect on future possibilities.

A useful abstraction is:

• State: A description of the relevant condition of the environment.
• Action: An operation available to the agent.
• Transition: The result of applying an action.
• Observation: Information available to the agent, possibly incomplete or noisy.
• Reward or cost: A numerical evaluation of an outcome.
• Policy: A rule that maps states or observations to actions.
• Objective: A criterion such as reaching a goal, minimizing cost, or maximizing expected cumulative reward.

The distinction between a state and an observation is important. A state contains all information required to predict future evolution, whereas an observation may reveal only part of it. A robot may observe camera images and lidar readings without directly observing its exact position, the intentions of pedestrians, or the condition of its motors. Such problems are partially observable and require estimation as well as control.

Classical Planning: Constructing Action Sequences

Classical planning assumes a discrete environment, a known initial state, clearly specified actions, predictable action effects, and a fully observable world. A planning problem is often expressed as a tuple consisting of an initial state, a set of actions, a goal condition, and sometimes a cost function.

An action is described by preconditions, which must be true before execution, and effects, which describe what becomes true or false after execution. For example, in a delivery domain, an action `Load(package, vehicle)` may require that the package and vehicle are at the same location and that the package is not already loaded. Its effects may include `In(package, vehicle)` and the removal of `At(package, location)`.

The resulting plan is a sequence or partial ordering of actions that transforms the initial state into a state satisfying the goal. A plan can be evaluated by length, monetary cost, energy consumption, risk, or a weighted combination of these factors.

State-Space Search

Forward state-space planning begins with the initial state and applies applicable actions until a goal state is reached. Backward planning begins with the goal and identifies actions that could achieve it, recursively establishing their preconditions. Search strategies include breadth-first search, depth-first search, uniform-cost search, and heuristic search.

A heuristic estimates the remaining cost to a goal. In the A* algorithm, the evaluation function is:

`f(n) = g(n) + h(n)`

where `g(n)` is the cost already incurred and `h(n)` estimates the cost remaining. If the heuristic never overestimates the actual remaining cost, A* can guarantee an optimal solution under standard conditions. In large planning problems, however, state spaces grow exponentially. Abstraction, hierarchical planning, landmark detection, and domain-specific heuristics are therefore essential.

Partial-Order and Hierarchical Planning

A totally ordered plan specifies every action in one fixed sequence. A partial-order plan specifies only necessary precedence relations. If two actions do not interfere, they may be executed in either order or in parallel. This representation is valuable in manufacturing, logistics, and autonomous task scheduling.

Hierarchical task-network planning decomposes a high-level task into subtasks. “Prepare a laboratory experiment” may be decomposed into obtaining materials, configuring instruments, conducting measurements, and recording results. Each task can be refined until executable primitive actions are obtained. Hierarchical planning improves scalability by using domain knowledge, although an inappropriate hierarchy can exclude valid solutions.

Planning Under Uncertainty

Real environments violate the assumptions of classical planning. Actions may fail, sensors may be unreliable, other agents may intervene, and the future may not be completely predictable. Probabilistic planning represents these uncertainties explicitly.

A Markov decision process (MDP) is commonly defined by the tuple `(S, A, P, R, γ)`, where `S` is the set of states, `A` the set of actions, `P(s'|s,a)` the probability of reaching state `s'` after action `a` in state `s`, `R(s,a,s')` the reward, and `γ` the discount factor. The Markov property states that the current state contains all information needed to predict the future; the history of earlier states is not additionally required.

A policy `π(a|s)` specifies the probability of selecting action `a` in state `s`. The value of a policy is the expected discounted return:

`Vπ(s) = Eπ[Rt+1 + γRt+2 + γ²Rt+3 + ... | St = s]`.

The optimal policy satisfies the Bellman optimality equation:

`V(s) = maxa Σs' P(s'|s,a)[R(s,a,s') + γV(s')]`.

Dynamic programming methods such as value iteration and policy iteration solve an MDP when its model is known and sufficiently small. Value iteration repeatedly applies the Bellman optimality update. Policy iteration alternates between evaluating a policy and improving it.

When the environment is partially observable, a partially observable MDP (POMDP) is more appropriate. The agent maintains a belief state, which is a probability distribution over possible physical states. Belief updating combines the previous belief, the selected action, and the new observation. POMDPs are expressive but computationally demanding because the belief state is continuous even when the physical state is discrete.

Reinforcement Learning: Acquiring Policies from Experience

Reinforcement learning (RL) concerns an agent that learns how to act through trial, feedback, and interaction. Unlike supervised learning, RL does not normally receive a correct action label for every situation. Instead, it receives rewards that may be delayed and must discover which actions produce desirable long-term outcomes.

The central elements are the environment, state or observation, action, reward, policy, value function, and learning algorithm. The state-value function estimates the expected return from a state under a policy. The action-value function, or Q-function, estimates the expected return from taking action `a` in state `s` and then following a policy.

Exploration and Exploitation

An agent faces a fundamental trade-off. Exploitation selects actions currently believed to be best; exploration tries uncertain actions to obtain information. An epsilon-greedy policy chooses the best-known action most of the time and a random action with probability epsilon. Other methods include softmax selection, optimistic initialization, confidence-based exploration, and posterior sampling.

Excessive exploration may be unsafe or inefficient, while insufficient exploration can trap the agent in a poor policy. In physical systems, exploration should often occur in simulation, within a constrained action set, or under human supervision.

Temporal-Difference Learning and Q-Learning

Temporal-difference methods learn from incomplete episodes by comparing successive predictions. A basic TD error is:

`δt = Rt+1 + γV(St+1) − V(St)`.

Q-learning is an off-policy algorithm whose update is:

`Q(s,a) ← Q(s,a) + α[r + γ maxa' Q(s',a') − Q(s,a)]`.

Here, `α` is the learning rate. The algorithm learns the value of an optimal policy while behaving according to a possibly exploratory policy. SARSA is an on-policy alternative and updates using the action actually selected in the next state.

For large or continuous state spaces, tabular methods are inadequate. Function approximation uses parameters to estimate values or policies. Deep reinforcement learning employs neural networks, but it introduces instability, sensitivity to data distribution, high computational requirements, and difficulties in explaining behaviour. Experience replay, target networks, policy gradients, actor–critic methods, and model-based learning are techniques used to address some of these challenges.

Reward Design and Learning Objectives

Reward design is not a minor implementation detail. If an objective is incomplete, the agent may optimize a proxy rather than the intended outcome. A delivery system rewarded only for speed may ignore safety; a recommender rewarded only for immediate clicks may reduce long-term user satisfaction. Reward functions should therefore represent safety, fairness, constraints, and long-term effects where appropriate.

Reward shaping can accelerate learning by providing intermediate feedback, but poorly designed shaping may change the desired solution. Constrained reinforcement learning treats safety or resource limits as explicit constraints rather than hoping that penalties will be sufficient.

Robotics: Embodied Intelligence

Robotics places AI in a physical or simulated body. A robot must sense the world, estimate its state, decide what to do, and control actuators while coping with noise, delays, mechanical limitations, and unexpected events. The standard robotics loop is often described as sense–estimate–plan–act, although modern systems execute these functions concurrently.

Robotic Perception and State Estimation

Sensors include cameras, depth cameras, lidar, radar, inertial measurement units, encoders, force sensors, and microphones. Perception converts raw measurements into useful representations such as objects, surfaces, poses, obstacles, and human activities.

State estimation combines a motion model with sensor observations. The Kalman filter is appropriate for linear Gaussian systems. Extended and unscented Kalman filters handle certain nonlinear models, while particle filters represent non-Gaussian beliefs through samples. Sensor fusion improves robustness, but correlated errors and calibration faults can produce confident yet incorrect estimates.

For mobile robots, simultaneous localization and mapping (SLAM) estimates the robot’s position while constructing a map. Localization and mapping are mutually dependent: a map helps determine position, while accurate position helps construct the map. Loop-closure detection reduces accumulated drift by recognizing previously visited places.

Motion Planning and Control

A robot’s configuration describes the positions of its joints or body pose. Configuration-space planning transforms collision avoidance into a geometric search problem. Sampling-based methods such as probabilistic roadmaps and rapidly exploring random trees are effective in high-dimensional spaces, although they may require smoothing and dynamic feasibility checks.

Control converts a desired trajectory into actuator commands. Feedback control compares the desired state with the measured state and corrects deviations. Proportional–integral–derivative control is widely used for simpler systems. Model predictive control repeatedly optimizes future actions over a moving horizon while incorporating dynamics and constraints. Reinforcement learning can learn control policies, but deployment requires rigorous validation and safety limits.

Robotic autonomy is therefore not equivalent to installing a single learning algorithm. It usually involves layered architecture: low-level stabilization, localization and mapping, obstacle avoidance, task planning, behaviour selection, and human or fleet supervision.

Multi-Agent Systems and Distributed Intelligence

A multi-agent system (MAS) consists of two or more autonomous agents that interact in a shared environment. Agents may cooperate, compete, or combine both behaviours. Examples include robot fleets, smart-grid controllers, automated trading systems, traffic-management agents, and software agents coordinating cloud resources.

The defining difficulty is strategic interdependence. The best action for one agent depends on the actions, information, and objectives of others. A centralized controller may produce globally coherent decisions but can become a bottleneck or single point of failure. Distributed architectures improve scalability and resilience but require coordination and may produce inconsistent local decisions.

Coordination and Communication

Coordination aligns agent actions so that tasks are completed without harmful interference. It may involve shared plans, role assignment, resource reservation, formation control, or consensus. Communication can be explicit through messages or implicit through observation of environmental effects.

Protocols should specify message formats, timing, authority, failure handling, and conflict resolution. Communication has costs: bandwidth is limited, messages may be delayed or corrupted, and revealing information may benefit competitors. Robust systems therefore avoid assuming perfect communication.

Consensus algorithms allow agents to converge on a common estimate or decision. Distributed task allocation methods assign tasks according to capabilities, costs, deadlines, and location. Contract-net-style mechanisms use announcements and bids, while market-based mechanisms allocate resources through prices or utilities.

Negotiation and Strategic Behaviour

Negotiation occurs when agents have partially compatible but not identical preferences. A negotiation protocol defines the possible offers, acceptance rules, deadlines, and termination conditions. Utility functions measure the desirability of outcomes for each participant. Cooperative negotiation may seek Pareto improvements, whereas competitive negotiation may require strategic reasoning about incentives and private information.

Game theory provides tools for analysing such interaction. A Nash equilibrium is a profile of strategies in which no agent can improve its payoff by changing strategy alone. Equilibrium analysis does not automatically guarantee fairness, efficiency, or safety; a stable outcome can still be socially undesirable.

Distributed Architectures

A MAS may use a centralized, decentralized, or hybrid architecture. Centralized systems simplify global optimization and policy enforcement. Decentralized systems support local autonomy and fault tolerance. Hybrid systems retain central coordination for high-level objectives while allowing agents to make local real-time decisions.

Distributed partially observable decision processes are more difficult than single-agent MDPs because each agent has incomplete information and the joint action space grows rapidly. Practical systems use abstractions, hierarchical roles, mean-field approximations, learned communication, or limited coordination windows.

An Illustrative Case: Cooperative Warehouse Robots

Background

Consider a distribution centre in which autonomous mobile robots transport storage bins between shelves and human or robotic packing stations. The illustrative system contains dozens of robots, shared aisles, charging stations, dynamic obstacles, and changing order priorities.

Situation and Problem

A purely shortest-path strategy causes congestion near popular shelves. Independent robots may select the same narrow passage, and a robot with low battery may accept a task it cannot safely complete. Delays increase when a charging station becomes unavailable.

Analysis

The problem combines classical planning, probabilistic decision-making, robotics, and multi-agent coordination. At the task level, orders must be decomposed into transport jobs and assigned to robots. At the motion level, each robot must localize itself and plan collision-free paths. Travel time is uncertain because of congestion and human movement. The global objective includes throughput, energy, safety, and fairness among robots.

Approach and Strategy

A hybrid architecture is appropriate. A supervisory scheduler assigns jobs using estimated travel time, battery state, and workload. Each robot uses a local planner for immediate navigation and reserves critical aisle segments through a lightweight coordination protocol. A probabilistic model estimates travel-time distributions rather than relying on fixed distances. Reinforcement learning may improve dispatching policies using historical interaction data, but a rule-based safety layer prevents collisions, forbidden-zone entry, and operation below a safe battery threshold.

When communication fails, robots switch to conservative local behaviour and reduce speed. The scheduler periodically replans instead of assuming that an earlier plan remains valid. Performance is evaluated using order completion time, collision and near-miss rates, energy per delivery, congestion, recovery time after failures, and distribution of workload.

Outcome

The hybrid approach is more appropriate than either full centralization or completely independent learning. Central scheduling provides global visibility, local planning provides responsiveness, and explicit safety constraints reduce the consequences of prediction errors. The main lesson is architectural: sequential intelligence in a physical multi-agent environment requires integration of estimation, planning, learning, coordination, and control.

Applications and Professional Relevance

Planning and learning methods are applied in logistics, healthcare scheduling, industrial production, telecommunications, finance, energy management, cybersecurity, autonomous transport, agriculture, and service robotics. In organizations, the choice of method should reflect the structure of the decision problem. If rules and outcomes are well known, classical optimization or planning may be preferable. If uncertainty is substantial but a model is available, MDP methods are useful. If the model is unknown and interaction data can be collected safely, reinforcement learning may be considered.

Professionals must also distinguish laboratory performance from operational readiness. A policy that performs well in simulation may fail because of sensor mismatch, distribution shift, latency, adversarial behaviour, or rare events. Deployment requires monitoring, rollback procedures, incident logging, simulation testing, staged release, and clear responsibility for decisions.

Challenges, Risks, and Common Mistakes

The principal technical challenges include state-space explosion, sparse or delayed rewards, sample inefficiency, partial observability, non-stationary environments, multi-agent credit assignment, and sim-to-real transfer. In multi-agent learning, another agent’s policy may change during training, making the environment appear non-stationary. A reward that encourages local success may damage global performance.

Common mistakes include treating an observation as a complete state, ignoring action duration and latency, optimizing only average performance, assuming communication is reliable, and evaluating only successful episodes. Other failures arise from poorly calibrated sensors, unsafe exploratory actions, untested edge cases, and plans that lack recovery behaviour.

Safety should be addressed through layered defenses: formal constraints where feasible, conservative fallback policies, runtime monitoring, human override, redundancy, and testing under degraded conditions. A system should be able to recognize uncertainty and request assistance rather than produce unjustified confidence.

Ethical, Governance, and Regulatory Considerations

Autonomous systems can affect safety, employment, privacy, access to services, and accountability. Designers should identify who is responsible for decisions, how data are collected, whether affected persons can contest outcomes, and whether the system distributes benefits and risks fairly.

Robotic perception may capture personal information. Multi-agent systems may share data across organizational boundaries. Reinforcement-learning agents may discover strategies that are efficient but unacceptable, such as exploiting loopholes in reward definitions. Governance therefore requires documented objectives, data controls, audit trails, access management, model-change procedures, and incident-response plans.

Human oversight should be meaningful rather than symbolic. Operators need sufficient information, authority, time, and training to intervene. In safety-critical domains, autonomy should be bounded by validated operating conditions and explicit fail-safe behaviour.

Current Developments and Best Practices

Contemporary research combines model-based planning with learned components. World models attempt to predict environmental dynamics, while hierarchical agents combine high-level reasoning with low-level control. Offline reinforcement learning learns from previously collected data and can reduce dangerous exploration, although dataset bias and distributional limitations remain important.

Other active directions include multi-agent reinforcement learning, learned communication, foundation models for robotic task interpretation, differentiable planning, sim-to-real adaptation, safe exploration, and formal verification of learned policies. These developments do not eliminate the need for domain modelling and engineering discipline.

Effective practice includes:

• Define states, observations, objectives, constraints, and failure conditions explicitly.
• Use the simplest method that adequately represents the problem.
• Separate performance objectives from non-negotiable safety constraints.
• Test in simulation, controlled environments, and progressively realistic settings.
• Measure tail risks, recovery behaviour, fairness, energy use, and robustness—not only average reward.
• Combine learned components with interpretable planning and verified control where possible.
• Maintain reproducible logs, versioned policies, and mechanisms for rollback.
• Design coordination protocols for delay, loss, conflicting objectives, and agent failure.

Chapter Summary

Sequential intelligence concerns decisions whose consequences unfold over time. Classical planning represents actions through preconditions and effects and searches for plans that achieve goals. Probabilistic planning and MDPs model uncertain transitions, rewards, policies, and value functions; POMDPs extend this reasoning to partial observability. Reinforcement learning learns policies from interaction and must balance exploration with exploitation while addressing reward design, sample efficiency, and safety.

Robotics embeds planning and learning in physical systems that require perception, state estimation, localization, motion planning, and feedback control. Multi-agent systems add distributed information, coordination, communication, negotiation, and strategic interdependence. Effective autonomous systems generally use hybrid architectures combining learned prediction with explicit planning, local control, safety constraints, and monitoring. Technical success must be accompanied by ethical governance, accountability, privacy protection, and robust evaluation.

Key Terms

State: Information sufficient to characterize the situation relevant to future decision-making.

Action: An operation selected by an agent.

Policy: A rule or probability distribution mapping states or observations to actions.

Classical planning: Planning with known, deterministic actions in a fully observable environment.

Precondition: A condition that must hold before an action can be executed.

Effect: A change in the world produced by an action.

Heuristic: An estimate used to guide search toward a solution.

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

POMDP: An MDP in which the agent receives incomplete or noisy observations.

Value function: Expected cumulative return associated with a state or state–action pair.

Reinforcement learning: Learning behaviour through interaction and reward feedback.

Exploration: Trying uncertain actions to obtain information.

Temporal-difference learning: Learning by updating predictions from the difference between successive estimates.

Reward shaping: Adding intermediate feedback to facilitate learning.

SLAM: Simultaneous localization and mapping by a robot.

Sensor fusion: Combining measurements from multiple sensors to improve estimation.

Model predictive control: Repeated optimization of future control actions over a moving horizon.

Multi-agent system: A system containing multiple autonomous interacting agents.

Consensus: Distributed convergence toward a common estimate or decision.

Negotiation: Interaction through which agents seek an acceptable allocation or agreement.

Review Questions

Short Answer Questions

1. What assumptions distinguish classical planning from probabilistic planning?

2. Define the Markov property and explain its importance in an MDP.

3. What is the exploration–exploitation trade-off in reinforcement learning?

4. Why is state estimation necessary in robotics?

5. Distinguish centralized and decentralized multi-agent architectures.

Long Answer Questions

1. Explain classical planning using preconditions, effects, search, heuristics, and hierarchical task decomposition.

2. Describe the MDP framework and derive the role of the Bellman optimality equation in decision-making.

3. Compare Q-learning, SARSA, and policy-based reinforcement-learning approaches.

4. Explain how perception, SLAM, motion planning, and feedback control interact in a mobile robot.

5. Discuss coordination, communication, negotiation, and strategic behaviour in multi-agent systems.

Analytical / Application Questions

1. Design a sequential decision model for an autonomous hospital-delivery robot. Specify its states, actions, observations, rewards, constraints, and likely sources of uncertainty.

2. A fleet of robots performs well in simulation but frequently collides after deployment. Analyse at least five possible causes and propose a staged validation and safety strategy.

3. For the warehouse case in this chapter, compare a fully centralized planner, independent reinforcement-learning agents, and a hybrid architecture. Recommend one and justify the choice using scalability, safety, communication, and performance criteria.

22. Multiple Choice Questions with Answers

Question 1

Which assumption is characteristic of classical planning?

A. Actions have stochastic effects and observations are incomplete

B. The environment is fully observable and action effects are known

C. The agent learns all actions only through rewards

D. Other agents continuously change the transition model

Correct Answer: B. The environment is fully observable and action effects are known

Question 2

In an MDP, what does the transition function P(s'|s,a) represent?

A. The reward for selecting action a

B. The policy probability of selecting a

C. The probability of reaching s' from s after action a

D. The estimated remaining cost to the goal

Correct Answer: C. The probability of reaching s' from s after action a

Question 3

Why does a POMDP require a belief state?

A. Because the agent cannot directly observe the complete physical state

B. Because actions are always deterministic

C. Because rewards cannot be represented numerically

D. Because the environment contains no transition model

Correct Answer: A. Because the agent cannot directly observe the complete physical state

Question 4

What is the main purpose of exploration in reinforcement learning?

A. To guarantee immediate maximum reward

B. To avoid updating the value function

C. To discover information about uncertain actions

D. To remove the need for a policy

Correct Answer: C. To discover information about uncertain actions

Question 5

Which update is associated with Q-learning?

A. Q(s,a) is updated toward r + γ max Q(s',a')

B. Q(s,a) is updated only when the episode terminates

C. Q(s,a) is replaced by the observation probability

D. Q(s,a) is independent of the next state

Correct Answer: A. Q(s,a) is updated toward r + γ max Q(s',a')

Question 6

What is the primary function of SLAM in mobile robotics?

A. To negotiate task prices among agents

B. To estimate a robot’s position while constructing a map

C. To replace all low-level feedback controllers

D. To assign rewards to reinforcement-learning actions

Correct Answer: B. To estimate a robot’s position while constructing a map

Question 7

Why can independent action selection by warehouse robots cause congestion?

A. Each robot necessarily has a complete global plan

B. Robots may choose locally attractive routes without accounting for others

C. Classical planning prohibits movement through shared spaces

D. Sensor fusion guarantees identical routes

Correct Answer: B. Robots may choose locally attractive routes without accounting for others

Question 8

Which feature best characterizes a hybrid multi-agent architecture?

A. Only one agent is allowed to make every decision

B. Agents never communicate or share objectives

C. High-level coordination is combined with local agent autonomy

D. All decisions are learned without constraints

Correct Answer: C. High-level coordination is combined with local agent autonomy

Question 9

Why is reward design a safety concern in reinforcement learning?

A. An agent may optimize a proxy objective while violating the intended goal

B. Rewards prevent the agent from exploring any action

C. Rewards make the environment fully observable

D. A reward function eliminates the need for monitoring

Correct Answer: A. An agent may optimize a proxy objective while violating the intended goal

Question 10

Which practice is most appropriate for deploying a learned robotic policy?

A. Deploy it immediately after successful simulation episodes

B. Remove fallback controls to maximize autonomy

C. Use staged testing, runtime monitoring, constraints, and rollback procedures

D. Evaluate only average reward during normal operation

Correct Answer: C. Use staged testing, runtime monitoring, constraints, and rollback procedures