Introduction to AI - Week 10
Reactive Systems - Rational Agents
- Reactive Systems: (as antithesis to
classical AI): no explicit representation of knowledge, simple
reactive code exhibits complex seemingly intelligent behaviour.
- Rational Agents: Proactive software systems
with agenda of their own.
Classical AI: Build systems based on carefully selected
knowledge representation to model parts of the world
- Antithesis to classical AI:
Obtain complex, apparently goal directed and
intentional behaviour in a system which has no long term internal
state and no internal communication.
"Intelligence without Reason" [Rodney Brooks, 1991]
- Situatedness: The world is its own best model
- Embodiment: The world grounds regress
- Intelligence: Intelligence is determined by the dynamics of
interaction with the world
- Emergence: Intelligence is in the eye of the observer
Inspired by biological systems:
- Study complete integrated intelligent autonomous agents.
- Agents embodied as mobile robots in unmodified worlds.
- Agents should be situated, e.g. operate equally well when
visitors walk through their workspace.
- Timescales are commensurate with those used by humans.
Principles of Computation
- Computation is organised as an asynchronous network of active
computational elements (augmented finite state machines).
- Messages sent over connections have no implicit semantics -
they are small numbers (typically 8 or 16 bits). Meaning dependent
on the dynamics designed into both the sender and receiver.
- Sensors and actuators are connected to this network, usually
through asynchronous two-sided buffers.
- The system is reactive, but not purely
reactive (may have state).
- Any search space must be quite bounded in size.
- There is no separation of data and computation (both
distributed over the same network).
- There is no central model of the world.
- There is no central locus of control.
- There is no separation into perceptual, central, and
- Behavioural competence improves by adding more
specific network to the existing one.
- There is no hierarchical arrangement.
- The layers, or behaviours, all run in parallel (conflict
resolution may be necessary).
- The world is often a good communication medium for
processes within a single robot.
Reactivity - Example
Herbert - a robot to find soda can-like objects:
- Task: wander around looking for soda cans and bring them
to the starting point.
- laser scanner for detecting objects,
- infrared proximity sensors to navigate by following walls and
going through doorways,
- magnetic compass to maintain a global sense of orientation,
- sensors in the arm to reliably pick up cans.
- no state longer than three seconds.
- no internal communication between behaviour generating
- Actuators driven by an arbitration network (fixed
- World as model and communication medium:
- Laser-based soda can object finder drove the robot so that its
arm was lined up in front of the soda can, but didn't tell the arm
controller to pick.
- The arm monitors the motion. No body motion ==> motion of
the arm so that soda can between fingers. Independently, grasp
reflex that operated whenever something broke an infrared beam
between the fingers.
- By this kind of encoding it is possible that a human hands a
soda can to the robot.
- Try to model onto-genesis (individual development) by
phylo-genesis (development of the species), i.e. the development of
intelligence rather than the end product.
- It is possible to model low level animals like ants that way.
- Emergence: How to predict global behaviour of
set of robots?
- Synthesis: Given a task, how to automatically derive a
program for a set of robots?
- Communication: Which amount of communication?
- Cooperation & Interference: How to coordinate?
- Density dependence: How many robots?
- Individuality: Different individuals?
- Learning: What & how to learn?
Compromise: Reaction-First Search
Assume situated agent: system consists of a planner and
- Principle of independent competence, i.e., reactor is able
to take action with and without a plan:
- When the reactor is told to act, it executes the currently
available plan and then falls back on a reactive program.
- If complete plan: reactor executes plan.
- If no plan: reactor follows a programmer-provided reactive
program (e.g. minimise Manhattan distance).
- If a prefix plan available: the plan takes the reactor part
of the way, the reactive program takes over at the plan's end.
- If the reactor executes a prefix plan before that plan is known
to lead to a solution, how can we be sure that this will not impair
the reactor's performance?
(Note: Search is an essential part of problem solving since there is
no purely "local" way to guarantee that any given prefix plan can
be extended to a solution.)
- Solved by
, monotonically increase goal satisfaction
probability of the reactor, no matter how much time is spent
searching. Planner releases prefix plans computed in the time
- A trajectory is a sequence of operator applications, each
trajectory models one possible behaviour of the reactor.
- A prefix plan for a problem is a trajectory in which the
first actions are specified by a prefix.
The Principles of Reaction First Search
That is, the planner knows the policy and explores the search space
searching in the policy first.
- All states in the policy-defined subtree must be expanded
before all other states in the search space.
- After selecting a level in the search tree by any means, a
policy state in that level must be randomly chosen for
- In any given policy state, policy-recommended operators must be
randomly chosen for application.
Then: Performance of
is monotonically increasing.
Task: phase A - start at I go to G, grasp
something, and phase B - go back to I.
Policy: in phase A and B reduce Manhattan distance between
current position and G and I respectively.
Note: non-deterministic behaviour, in particular the reactor
might be trapped.
The Planner in the Example
- Calculate probability that the policy will lead the agent into a
dead-end. The procedure accepts an initial and goal location and
return the probability that the agent will become trapped in a
dead-end via the execution of the policy. Minimise probability to be
trapped by prefix plan.
- Biological systems suggest that reactivity and
deliberation play a significant
In particular in
humans both aspects are important (the first for short term goals
and fast reaction, the latter for long term goals and slow
reaction). Hence a more complicated architecture is necessary.
The concept "agent" is very wide and its usage varies. It may mean:
- A system that perceives and acts [Russell-Norvig].
- A proactive system with its own goals and intentions.
Depending on the level of sophistication an agent should have, we need
different architectures. We will look at the architecture of a
learning agent, a more sophisticated single-agent architecture, and a
Russell-Norvig: An Agent is anything that perceives its environment through
sensors and acts upon that environment through effectors.
Learning agent has learning element and performance element
- The learning element is responsible for making improvements.
It takes knowledge about the performance element & some feedback,
determines how to modify performance element.
- The performance element takes in percepts and decides on external actions.
- The critic tells learning element how well the agent is
doing (and has itself a fixed standard of performance).
- The problem generator suggests actions that will lead to new
& informative experience.
Russell/Norvig's Learning Agent
A General Agent Architecture by A. Sloman
Characteristics of Intelligent Agents
[Shaun Abushar, Naoki Hirata]
- "Autonomy: Agents should be able to do most
of their tasks without any direct assistance from an outside
- "Social Ability: Agents should be able to
interact with, when they deem appropriate, other software agents and
- "Responsiveness: Agents should respond in
a timely fashion to perceived changes in the environment, including
changes in the physical world, other agents, or the Internet."
- "Proactiveness: Agents should be able to
exhibit goal-directed behaviour."
Agents May Coordinate their Actions
Assume a set of agents, which make plans. and a
centralised coordinator which negotiates with agents about how to
coordinate their distributed plans.
Example: Assume a transportation task of
delivering 10,000 flowers from New Jersey to New York City. The task
may be performed by several trucks or by a single helicopter, a
lift-truck is necessary in both cases. A coalition of trucks and
lift-trucks will probably be cheaper than a coalition of a helicopter
It is possible to automatically allocate the tasks by the
formation of coalitions.
A coalition is a group of agents that have decided to cooperate
in order to achieve a common task.
Planning in Coalitions
- Calculate coalition values, i.e. determine the values of the
possible coalitions in order to choose the preferred ones.
- In an iterated greedy process the agents decide upon the
preferred coalitions and form them.
- The benefits of the cooperation may be disbursed among the
agents (by fair methods).
- Communication is reduced to agents in the coalition.
Why Mobile Agents?
[Danny B. Lange and Mitsuru Oshima 1999]
- They reduce the network load:
Distributive systems often rely on communication involving
multiple interactions. Mobile agents allow users to package
conversation and dispatch it to a place with local communication.
- They overcome network latency:
They can better meet real time requirements.
- They encapsulate protocols:
They allow for easy upgrades (no legacy problem).
Why Mobile Agents? (Cont'd)
- They execute asynchronously and
- They adapt dynamically: They can sense
their environment and react.
- They are naturally heterogeneous: They
provide optimal conditions for seamless system integration.
- They are robust and fault-tolerant: Mobile
agents' ability to react dynamically to unfavourable situations and
events makes it easier to build robust and fault-tolerant
- Agent-based systems play an increasing role
in e-commerce, computer games, and other fields.
- Agents form a framework for flexible, robust, proactive
- Agents are realised using a wide variety of
There is a lot of material on-line, e.g.
© Manfred Kerber, 2004, Introduction to AI
The URL of this page is http://www.cs.bham.ac.uk/~mmk/Teaching/AI/Teaching/AI/l10.html.
URL of module http://www.cs.bham.ac.uk/~mmk/Teaching/AI/