Transcript Subsumption Theory.

For the exam next Thursday
1. Reactive architectures for robots, quantum and standard
Braitenberg Vehicles and their “emotions”
2. State machine architectures
3. GA and GP in all kinds of robotic applications.
4. Robot in labyrinth
5. Grammar generation of motion, dialog and behavior,
use of probabilistic grammars.
6. Use of probability and probabilistic state machines
7. Practical Control of mobile, walking and stationary
robots based on Finite State Machines. FSMs with
hierarchy and concurrency. Verification.
8. Use of counters and timers in behavioral robot
architectures.
For the exam next Thursday (cont)
1. Quantum controlled robots
2. Simple robot programs in LISP, use of GP to generate
them.
3. Decision Trees as a way of learning from examples.
4. Constructive Induction for learning and data mining in
robotics.
5. Learning from logic examples. SOP (DNF).
6. Logic other than binary (mv, fuzzy) used for robot
control.
7. Evolving behaviors of mobile robots
8. Neural Nets in Behavioral architectures
9. Subsumption architectures
Brooks and
Subsumption
Intelligent Robot Systems
Knowledge
AI control
Perception
Sensors
Supervision
Planning and
control
Basic level
control
Actuators
World
Typical Robot System
world
human
Actuators
Human interface
Sensors
Robot
Control
Execution of
program
Data acquisition
Tradition approach
• decomposition by function
Motor control
Task execution
Planning
Modeling
Perception
Sensors 
 Actuators
Traditional AI model
R. Brooks, “Cambrian Intelligence”
Supervision/Control of a robot
Human Interface
Control of
high levels
Supervision
Control of low level
Control of low
levels
Robot
Hierarchical Architecture
Hierachical Architecture
Strategic
This level generates goals and strategies
for achieving those goals which result in
the achievement of an overall objective
Tactical
This level generates the tactics by which a
goal is to be achieved
Executive
This level execute the tactical plan
Three Level Architecture
Where to
go
how
execute
Context
• Physical symbol system hypothesis
– PSS: Has physical patterns called symbols and collections of these
symbols called expressions
– PSSH: A PSS has the necessary & sufficient means for general
intelligent action
– Important assumption
• Intelligence occurs via reasoning
• E.g., searching for operators; logical inference
• Thinking vs. acting
– PSSH type approaches emphasize thinking
– But what about intelligence based on acting?
– E.g., some nonhuman animals may act more than think but they
seem to have a kind of intelligence
The Brooks School
Reactive Robotics
Behavioral Robotics
Subsumption architectures
for walking machines
Rodney Brooks, Connell
Brooks, R. A. (1999). Cambrian Intelligence: The
Early History of the New AI.
Cambridge, MA MIT Press.
Who is Rodney Brooks?
• Adelaide born. Flinders, Stanford, …, MIT
• Fujitsu Professor of Computer Science and
Engineering (EECS Dept) at MIT.
• Director of the Artificial Intelligence Laboratory
at MIT.
• Companies: Lucid, IS Robotics Inc., Artificial
Creatures.
• Claims he is a pragmatist.
The early years of subsumption
• Aware of the failure of mobile robotics to
live up to its potential.
• Autonomous vehicles were not that
autonomous and weren't even very good
vehicles.
• Brooks identified various aspects of mobile
robotics which he considered to be
important and obvious
Key Topics of
Behaviour-based
Approach
• Situatedness
• Embodiment
• (animal or insect) Intelligence
• Emergence
Situatedness
A situated automaton is a finite-state machine
whose inputs are provided by sensors connected to the
environment, and
whose outputs are connected to effectors.
The world is its own best model
Traditional AI, working in symbolic abstracted domain.
Problem solvers which are not participating in the world as
agents.
Dealing with model world - no real connection to external
world.
Why situatedness is better for mobile robot
behaviors?
• Alternative approach, to use a mobile robot which
uses the world as its own model, referring to
information from sensors rather than internal
world model.
• Representations are developed which capture
relationships of entities to robot.
• Situated agent must respond in timely fashion to
inputs; but much information from the world.
Embodiment
Embodiment: Physical grounding of robot in real world.
According to Brooks (1991), embodiment is critical for two
reasons.
• Only an embodied agent is validated as one that can
deal with real world.
• Only through a physical grounding can any internal
symbolic system be given meaning.
Emergence
Intelligence emerges from interaction of components of the
system.
Behaviour-based approach - intelligence emerges from
interaction of simple modules.
e.g. Obstacle avoidance, goal finding, wall following modules.
Level 3
Level 2
Level 1
Sensors
Level 0
Actuators
Main Ideas of Behavior-based
Approach
Main ideas
• No central model maintained of world
• No central locus of control
• No separation into perceptual system, central system and
actuation system
• Behavioural competence improved by adding one more
behaviour specific network to existing network.
– Crude analogy to evolutionary development
• No hierarchical development
• Layers or behaviors run in parallel
Model of Brooks: the perceptual and
action subsystems are all there really is:
Cognition is only in
the eye of an
observer
A. Brooks, “Cambrian Intelligence”
Brooks Criticizes
traditional robotics
Intelligence is determined by the dynamics of interaction with the
world = he says
Some activities we think of as intelligent have only been taking place
for a small fraction of our evolutionary lineage.
‘Simple’ behaviors to do with perception and mobility took much
longer to evolve.
Would make sense to begin by looking at simpler animals.
- looking at dynamics of interaction of robot with its environment.
Example of Criticisms of traditional
approach - Brooks
• We should take evidence from biology and
evolution.
• SPA systems highly constrained.
– Early work: formal systems, Blocks World.
• Funding forced relevance and new slogan.
– But this ignores knowledge acquisition!
• Introspection is misleading.
• Brooks rejects symbol system hypothesis.
Key Brooksian Ideas
• Situatedness and embodiment, as discussed.
• Approximate evolution
– Incremental additions improve performance
– Layers
– Each layer
•
•
•
•
Corresponds to new behavior
Relies upon existing layers
Has minimal interaction with other layers
Is short connection between perception & actuation
• Advantages of this paradigm.
Brook's General Robot Requirements
• He identified a number of requirements of a control
system for an intelligent autonomous mobile robot.
• Multiple Goals:
– Some conflict, context dependent
• Multiple Sensors:
– All have errors, inconsistencies and contradiction.
• Robustness:
– The robot must by fault-tolerant.
• Extensible:
– You have to be able to build on whatever you built
Subsumption architecture - the Brooks’
approach
– levels of competence
• example competences
– layers of control
• subsumption
– structure of layers
– extensions
– finite state machines
What were the weaknesse of traditional
approaches?
•
•
•
•
•
•
•
•
Can’t account for large aspects of Intelligence
Reliant on representation
In real problems we have rapidly changing
boundary conditions
Hard to map sensor values to physical
quantities
Not robust
Relatively slow response
Hard to extend
Hard to test
Brook’s Dogma
• Brooks also introduced, what he called,
"9 dogmatic principles",
– 1) Complex (and useful) behavior need not
necessarily be a product of an extremely complex
control system.
– 2) Things should be simple: Interfaces to
subsystems etc.
– 3) Build cheap robots that work in human
environments
– 4) The world is three-dimensional therefore a
robot must model the world in 3 dimensions.
Dogma (cont)
• 5) Absolute coordinate systems for a robot are the
source of large cumulative errors.
• 6) The worlds where mobile robots will do useful
work are not constructed of exact simple polyhedra.
• 7) Visual data is useful for high level tasks. Sonar
may only be good for low level tasks where rich
environmental descriptions are unnecessary.
• 8) The robot must be able to perform when one or
more of its sensors fails or starts giving erroneous
readings.
Dogma (cont)
• 9) "We are interested in building "artificial
beings"
– --robots that survive for days, weeks and months,
• without human assistance,
• in a dynamic complex environment.
– Such robots must be self-sustaining
Solution: Subsumption
• Brooks and his group eventually came up with a
computational architecture.
• Model arrived at by continually refining attempts to
program a robot to reactively avoid collisions in a
people-populated environment.
• Not intended as a realistic model of how neurological
systems work.
• The model is called "subsumption architecture”.
• Its purpose is to program
– intelligent,
– situated,
– embodied agents.
new architecture:
subsumption
• Introduced in Brooks’ seminal 1986 paper
• Consists of layered behaviors,
– from simple to complex,
– with simple interfaces
• Layers can “override” each other
• Each layer has a control program that is
capable of working at the speed of
environmental change
• Each layer now can do:
– the appropriate model building,
– sensor fusion,
– etc.
• 1. No central model of
world.
• 3. No separation into
perception, central
processing, and
actuation.
• 3. Layering increases
capabilities.
• 4. No hierarchical
arrangement.
• 5. Messages on input
ports when needed.
• 6. Behaviors run in
parallel.
Basic Architecture of an autonomous
agent
Sensors
Vision, range, touch
Cognition
Effectors
Decides actions and
Carry out actions
commands effectors
Subsumption Architecture
• Control Problem for an autonomous robot
• Traditional Approach:
–
functional decomposition
• A new approach
–
decomposition by activity
Main difference in
the decomposition
type
Motivation
To achieve cooperation and
coordination among different robots
and self governance with human like
performance in a common work
space.
Key Problems for Subsumption-based
mobile robots.
Cooperation
Coordination
Learning
Vision
Localization
Subsumption Architecture
• 1. Reactive robotics approach, which Brooks calls “behavioral
robotics.”
• 2. The central idea of Brooks’ approach is that more
sophisticated robot competencies should be built on top of
simpler ones.
• Instead of all robot inputs feeding into a sensory perception unit,
which creates a “world model” of the robot’s environment, which
feeds into a planning module, Brooks has argued that:
– robot perception and action should be closely linked,
– complex behaviors can be built from the interactions of simple ones.
• Example:
– a robot that must walk should first learn to stand.
– Then later behaviors can “exploit” earlier ones: a task which causes a
legged robot to move its legs can make use of the knowledge embedded in
the behavior that allows the robot to simply stand.
Subsumption Architecture:
Massiveness
• Brooks has proposed that future unmanned interplanetary missions should
be performed by hundreds—or thousands—of simple, insect-like robots
that act in teams to accomplish work, rather than a large and complicated
monolithic device.
• Individual robots could be considered expendable without jeopardizing
the success of the entire mission, whereas if a single large robot had a
failure, the mission would be over.
• Homework (not this year):
• Read:
• Rodney Brooks’s paper on “Fast, Cheap, and Out of Control”
Behavior-based Robotics started earlier,
in about 1984
• Groups at MIT and SRI independently began rethinking
how to organise intelligence (around 1984).
• Requirements:
– Reactive to dynamic environment
– Operate on human time scales
– Robustness to uncertainty/unpredictability
• They implemented simple systems with similar features.
Subsumption Priciples: Network
Construction
• 1) Computation is organized as an asynchronous network of
active computational elements:
– they are augmented finite state machines,
– with a fixed topology of unidirectional connections.
• 2) Messages sent over connections have no implicit
semantics:
– they are small numbers (typically 8 or 16 bits, but on some robots
just 1 bit),
– their meanings are dependent on the dynamics designed into both the
sender and receiver
• 3) Sensors and actuators are connected to this network,
– usually through asynchronous two-sided buffers.
Subsumption Architecture:
Incrementally build network of state
machines
• Incremental method for building robots
• Network of finite state machines links sensors
to actions
• Internal timers
• Control system built in layers of state machines
• Model: Message passing augmented finite state
machines
Finite State Machines
• In Brooks’ original work, each module was implemented as
a finite state machine
– augmented with some instance variables
• A finite state machine has
– a set of states
• a start state; (one or more stop states)
– a set of symbols
– a set of transitions
• For example
– an FSM for a light switch
• An FSM can be implemented in C
– using a state variable and switch statement
switch
off
on
switch
Let us look again to more limitations
of Conventional Approaches
• Perception takes too long
• Perception is not a solved problem, nor will it be
solved in the near future.
• Modeling/planning component assumes complete
models are available
• Overall system cannot respond in real-time
• Most robots built this way have failed
– (or run very slowly)
And the response of the Behavior-based
Approach
• Decompose overall control system into a layered
set of reactive behaviors
• Each behavior represents a complete mapping from
sensors to motor commands
• Low-level behaviors (e.g. avoid) can run in realtime since they use little computation
• High-level behaviors are invoked only when
necessary
• Requires arbitration strategy to choose among (or
combine) conflicting behaviors
What does it mean that behaviors run in
parallel and control directly?
• The control system is broken down into horizontal
modules, or behaviors, that run in parallel
– each behavior has direct access to sensor readings and
can control the robot’s motors directly
observe changes
build maps
sense
explore
wander
avoid objects
act
Brooks’ Assumptions for mobile robots:
Complex behaviors from simple controls
• Complex and useful behavior need not necessarily
be a product of an extremely complex control system
• Things should be simple
– if a single module is getting too big: rethink the design
– unstable or ill-conditioned solutions are not good
• Ability to wander in real environments is crucial
• Absolute coordinate systems are a source of error
– relational maps are more useful to a mobile robot
Brooks’ Assumptions for mobile robots:
sensors integration and autonomy • The real world is not constructed of exact shapes
– models may be useful, but should not be used alone
• Sonar data, while easy to collect, do not lead to rich
descriptions of the world
– visual data is much better
• For robustness, the robot must be able to function when
one or more of its sensors fails or starts giving erroneous
readings
– recovery should be quick (self-calibrating)
• Robots should be autonomous and self-sustaining (able to
survive weeks without human assistance)
Robot Architecture
how much / how do we represent the world internally ?
Just what we need.
Motor Schemas
Subsumption paradigm
• Subsumption composes simple reactions (behaviors) by
letting one take control at an appropriate time.
• World state is computed in order to perform a specific task.
Larger example -- Genghis
1) Standing by tuning the parameters of two behaviors:
the leg “swing” and the leg “lift”
2) Simple walking: one leg at a time
3) Force Balancing: incorporated force sensors on the legs
4) Obstacle traversal: the legs should lift much higher if need be
5) Anticipation: handles touch sensors (whiskers) to detect obstacles
6) Pitch stabilization: uses an inclinometer to stabilize fore/aft pitch
7) Prowling: uses infrared sensors to start walking when a human
approaches
8) Steering: uses the difference in two IR sensors to follow
57 FSM’s wired together !
Genghis -- The Approach
– Don’t use logic-based description of percepts
– Don’t apply search operators or logical inference or
planning operators
• Goal formalized, but not generalized
– Arrive at a next action, not operator sequence
– Apply that operator sequence to world (detail)
• Respond based on contingencies & interaction
Levels for the Genghis Robot
• Level-1: standup
– 2 modules per leg; control alpha (advance) & beta (balance)
motor
• Level-2: simple walk
– does not compensate for rough terrain
• Level-3: force balancing
– Compensates for rough terrain
•
•
•
•
Level-4: leg lifting
Level-5: whiskers
Level-6: pitch stabilization
Level-7: steered prowling
Layers and modules
• Each layer consists of a number of modules
• Modules
– Module is a hardware component
•
•
•
•
CPU + memory + specialized hardware + program
Modules connect to other h/w components via physical wires
Connections are fixed by design; not dynamic
Connections between modules are low bandwidth
• Modules within a layer
– Interconnect with data inputs & outputs
– Modules are asynchronous
• No centralized clock
• No central memory
Conflict resolution on a path from sensors to actuators
A Behaviorbased
Architecture
for museum
robot
Module
Example of
suppression
A Behavior-based
Architecture
for Box Pushing
Local
Reward
s on all
levels
Global
reward
Suppression
is build in
hardware
Connections between layers
• Layer0 is lowest
– Layer1 is next
– Etc.
• Layers are designed to have separate goals
– Lower layers deal with more important goals
– E.g., important = survival
• Connections across layers
–
–
–
–
Layer1 connects to Layer0; layer2 layer 1 etc.
Connections always from higher level to lower level
Lower layer cannot detect this connection
Connections are fixed by design (not dynamic)
• Established by physical wires
Suppression and Inhibition in modules
• These connections across layers are of two types
– Suppression: Input lines
• When layer1 sends a message on this connection, layer1 input replaces
layer0 output
– Inhibition: Output lines
• When layer1 sends a message on this connection, layer1 causes the layer0
output to be stopped (for an interval)
• No output replacement
• Modules are callable sub-functions (or procedures)
– Can’t make a procedure call and invoke a module
– Can send a message to a module if you have a wire from one
module to another module
– Connections are for message passing (within layers) and
suppression/inhibition (across layers)
Explanation of the layers for a
mobile robot
Avoid contact with objects (moving or static)
•
Wander aimlessly around without hitting things.
•
“Explore” the world by seeing places in the distance which look
reachable and heading for them.
•
Build a map of the environment and plan routes from one place
to another
•
Notice changes in the “static” environment
•
Reason about the world in terms of identifiable objects and
perform tasks related to certain objects.
•
Formulate and execute plans which involves changing the world
in some desirable way
•
Reason about the behavior of the objects in the world and
modify plans accordingly
Emergent Behaviors in a Subsumption
Architecture
• If the sensory inputs satisfy a precondition specific
to that module, then a certain behavior program, also
specific to that module, is executed
• One behavior module can subsume another behavior
• Complex behaviors can emerge from the interaction
of a relatively simple reactive machine with
complex environment
Advantages of Subsumption
Architecture
•
•
•
•
Robustness
Reactive and real-time response
Flexible: multi-goal, easy to extend
The robot interacts with the real world, not
symbols
• No explicit representation of goals needed
• No central control unit needed
• No mapping from sensor values to physical
quantities needed
Questions concerning limits of
Subsumption
Architecture
our approach
• How many layers can be built?
• How complex can a behavior be?
• Can higher level functions such as
learning be achieved by this approach?
Subsumption Architecture is a novel idea
about mobile robots in history.
1.
It brings some brand new ideas to all kind of robotics, not only
mobiles.
2.
It breaks the traditional solely sequencing mode to a parallel
mode.
3.
To some extent, it has actually affected the standard control
architecture today.
…. it affected also the AI…..
“New” Artificial Intelligence
• Reactive vs. Representational
– Emergent approaches (implicit)
–Braitenburg vehicles
–swarming, flocking …
– Behavioral approaches (explicit)
–Brooks, Steels …
• Physical Embodiment
Levels
(layers) of
Control
Another example of extended subsumption:
Communication among competencies
1. different
sensors can
be read by
different
competencies
observe
bump sensors
avoid obstacles
IR sensor
follow line
Here information
can also go up.
This is not classical
subsumption
2. competencies
such as
observe can
read outputs
from other
competencies
forage
S
3. competencies
can also write
values into
input of other
competencies
S
S
motors
Augmented Finite State Machine
Sensor
S
I
R
R
R
Finite State
Machine
This state machine is
augmented with
registers, timers and
suppression circuits
Layers are composed of modules
An example of module is shown below:
Inhibitor
Inputs
S
10
Suppressor
Behavioral
module
Suppression
of inputs from
bottom to top
Inhibition of
outputs from
top to bottom
1
3
Outputs
Suppression and
Inhibition
More general behavior
interactions: suppression
and inhibition can be on
both inputs and outputs
reset
A simple three-layered robot from Brooks
arbitrates among layers
in an ad-hoc way
Other examples of Subsumption Architectures
Layer 0
robot
robot
collide
halt
motor
sonar
command
feelforce force runaway
Dock
Operate
Highest
priority
Find
Wander
Avoid
Lowest
priority
We will discuss all layers
from bottom up adding one
layer at a time
Layer0+Layer1
robot
robot
collide
halt
sonar
command
S
15
motor
feelforce force runaway
wander
heading
avoid
We can
suppress
runaway
behavior
Layer 1
Another extension:
Layer 0
turn
We removed avoid but added
turn behavior
Layer
0
Subsumption
Architecture
runaway
behavior
FSM / DFA
Layer 1 added
wander
behavior
Il livello
2
Layer
2 added
navigate
behavior
wander
behavior
runaway
behavior
Another
Example of
Subsumption
Architecture
Mapping
robot
Another Example of
Subsumption
Subsumption Architecture
7
General
purpose
reasoning
approach on
the top level
Levels of competence
•
A number of levels
of competence are
defined
Reason about objects behavior
6
– an informal
specification of
a desired class
of behaviors for
a robot over all
environments it
will encounter
formulate plans to
change the world
5 identify objects
4 observe changes
3 build maps
2 explore
•
A higher level of
competence
implies a more
specific desired
class of behaviours
1 wander
sensors
0 avoid objects
• Control is layered, with higher level layers subsuming the roles of lower
level layers when they wish to take control.
• The system can be partitioned at any level, and the layers below form a
complete operational control system.
actuators
Example Competencies in more detail
7 reason about the behavior of objects in the world and modify plans
accordingly
6 formulate and execute plans that involve changing the state of the
world in some desirable way
5 reason about the world in terms of identifiable objects and perform
tasks related to certain objects
4 notice (observe) changes in the “static” environment
3 build a map of the environment and plan routes from one place to
another
2 explore the world by seeing places in the distance that look
reachable and heading for them
1 wander aimlessly around without hitting things
0 avoid contact with (stationary or moving) obstacles
Step-by-step building of Layers of
Control
• The key idea of levels of competence is that layers
of a control system can be built to correspond to
each level
– a control system can be built to achieve level zero
competence (avoid obstacles)
• it is programmed, debugged and then fixed in operation
– another layer is then added (first-level control)
• it is able to examine data from the level-0 system
• it is able to inject output, to suppress the level-0 output
• level-0 is unaware of the suppression and continues to
run
Structure of Layers
• How is each level built?
– does each have to be structured in horizontal manner?
• This is true to a certain extent, but the key difference is
that not all desired perceptions need to be processed by
each competence
– different decompositions can be used for different sensor-set
task-set pairs
• Layers can be built on a set of small processors
– each one sends (small) messages to others
– no message acknowledgement is required
– there is no need for central control (or synchronisation)
subsumption details
• Each layer has one function, conceptually
• Lower layers tend to be more “reactive”
– closed loop controls
– inputs tightly coupled to outputs
• Higher layers are more “deliberative”
– do higher-level sensor fusion & modeling
– keep more state
– planning further in the future
• Layers can fake the inputs or outputs of other
layers
subsumption advantages
•
•
•
•
(according to Brooks)
Provides a way to incrementally build and test a
complex mobile robot control system
Supports parallel computation in a straightforward,
intuitive way
Avoids centralized control; relies on self-centered
and autonomous modules
Leads to more emergent behavior -- “Complex (and
useful) behavior may simply be the reflection of a complex
environment”
–
Compare with SPA - intelligence is entirely in the design
of the planner (the programmer)
subsumption successes
• Early efforts were a dramatic success, zipping around like
R2D2 instead of pondering their plans
• “Pinnacle” was Herbert, who found soda cans in an office
Criticism of Subsumption
• Herbert didn’t work very repeatably
• No subsumption-based robot since Herbert -- or is there?
• Is “classical subsumption” still in use?
– Cog is based on subsumption?
– Brooks’ publications, however, mainly describe imitation of human
cognitive models and do not explicitly mention “subsumption”
– But, these models also stress non-monolithic control; subsumption might be
there implicitly
Criticism of Subsumption
1. More complex behaviors?
•
This approach won’t necessarily lead to system capable of more
complex behaviors. A new controller is needed for each task.
2. Is it an evolution?
–
–
–
The experimenter is deciding on what modules to add, and what
environment and task the robot should be exposed to. - not the
same as evolution.
But in terms of evolution, new behaviors and new mental
structures are learnt in response to the environment, not added by
an experimenter.
Similarly, in the development of an individual, new
representational structures are developed in response to the
environment, not added by an experimenter.
Criticism of Subsumption
3. It would be more impressive if the robot learnt new
behavior modules in response to the environment.
– This possibility is discussed by Brooks (1991), but not yet
successfully tackled.
4. Emphasis in this approach on reacting to the environment.
– And it is the case that apparently quite sophisticated behaviors can
result from simple reaction to the environment.
– But representations are needed for more complex tasks.
• e.g. ‘Find an empty can and bring it back to the starting point’ requires the
formation of an internal representation corresponding to a map.
• Need to provide an account of the development of representations.
Other
Reactive
Approaches
Other Reactive Approaches
• Two other reactive approaches that are popular
• Potential field methods
– a potential field is a concept from physics
• two examples are the gravitational field
– you do not need to be told which way to fall
– planets do not need to plan how to move around the sun
• and electromagnetic fields
– mobile phones, television, radio, etc.
• e.g. obstacles exert hypothetical repulsive forces on the robot
• Motor schema navigation
– multiple, concurrent schema generate separate behaviors which are
summed to produce output
• schema are dynamically created/destroyed as needed
“Embedding not intelligence,
but capabilities,
in everyday objects is one
crucial part of the solution.”
--Pattie Maes
Reactive vs. Algorithmic Control
•
•
•
Algorithmic Control: robot’s program is fundamentally a series of steps or actions to
be taken in a predetermined order.
– Most effective when the robot’s world and its interactions with it are wellstructured
• Manipulator arms in factories typically use algorithmic control with great
success
– Loses its appeal when the robot must deal with unexpected situations
– When it is extended to deal with error situations, the algorithmic method becomes a
complicated tree of branching decisions that is hard to design and debug
Reactive Control: robot’s program is organized around a collection of separate miniprograms, all running at once and able to take control of the robot as they see fit
– For a very simple, minimal HandyBug program, there might be
– a touch sensor process, which monitored the robot’s touch sensors and caused the
robot to back up and turn when it hit something
– a periodic turn process, that caused the robot to take a turn every now and then
– and a wander process, that caused the robot simply to move
Reactive control excels in complex situations with many unpredictable interactions
Behaviour-based Robotics
Idea of building autonomous mobile robots.
New approach, where robots operate in the world, and use
‘…highly reactive architectures, with no reasoning
systems, no manipulable representations, no symbols, and
totally decentralized computation’ (Brooks, 1991)
‘…I wish to build completely autonomous mobile agents that
co-exist in the world with humans, and are seen by those
humans as intelligent beings in their own right. I will call
such agents Creatures...’ (Brooks, 1991)
Brooks, R. (1991) Intelligence without Representation
Artificial Intelligence, 47, 139-159.
See “Elephants don’t play chess”, (1990 paper by Brooks)
Brooks, Rodney A. (1990) “Elephants don’t play chess”. In
Pattie Maes (Ed) Designing autonomous Agents,
Cambridge, Mass: MIT Press.
Because elephants don’t play chess, no reason to assume they
are not intelligent.
Emphasis on kind of behaviour exemplified by elephants,
rather than on more abstract human behaviours (e.g.
games, speech recognition, problem solving).
• A Creature must cope appropriately and in a timely fashion
with changes in its dynamic environment.
• A Creature should be robust with respect to its
environment: minor changes in the properties of the world
should not lead to total collapse of the Creature’s
behaviour; rather one should only expect a gradual change
in the capabilities of the Creature as the environment
changes more and more.
• A Creature should be able to maintain multiple goals and,
depending on the circumstances it finds itself in, change
which particular goals it is actively pursuing; thus it can
both adapt to surroundings and capitalize on fortuitous
circumstances.
• A Creature should do something in the world: it should
have some purpose in being.
Set of principles (Brooks, 1991)
• The goal is to study complete integrated intelligent
autonomous agents.
• The agents should be embodied as mobile robots situated
in unmodified worlds found round laboratory.
(embodiment).
• Robots should operate under different environmental
conditions - e.g. in different lighting conditions, when
sensors and actuators drift in calibration (situatedness).
• Robots should operate on timescales commensurate with
timescales used by humans (situatedness).
Hybrid
Control
Architectures
Robot Architecture
how much / how do we represent the world internally ?
4
As much as possible.
SPA architecture
• Sense -- plan -- act : design of Shakey and the Stanford Cart
• Some tasks do require a deliberative approach, i.e.,
reasoning about the world.
• Current robots incorporate both reaction and reasoning.
(sometimes termed hybrid systems)
Standard Approach - 1
world
world
perception
cognition
action
Standard Approach - 2
• Agent design we have been considering
– Sequential flow
– Percepts are obtained from sensors in world
(somehow)
– Get a logic-based or formal description of percepts
• E.g., wumpus world percepts
– We apply search operators or logical inference or
planning operators
• General (replaceable) formal goal
– Arrive at some operator or operator sequence
– Apply that operator sequence to world (somehow)
Taxonomy of Control Architectures:
hybrid
• A variety of different approaches have been tried for
implementing the sense-plan-act control cycle
• These approaches
reactive
model
can be
based
behavior
categorised as
based
– model-based
– reactive
– hybrid
hybrid
Three-Layer Architecture is an
example of hybrid system
Examples of Hybrid Approaches
• The SSS three-layer architecture
– the servo-subsumption-symbolic
architecture combines Brooks’
architecture with a lower-level servo
control level and a higher-level
symbolic system [Connell]
symbolic
subsumption
servo
sensors
actuators
• Fuzzy logic and neural network controllers
– fuzzy logic rule-base(s), neural network(s) and
combinations of both take inputs from sensors and
process the data to generate output to actuators
Learning Approaches
• Traditional learning techniques
– rather than attempt to predefine and predict a symbolic
model of the ‘real-world’, the robot learns how to operate
and how to behave by
• supervised learning
– desired output is known for each set of input settings (e.g. ANN’s)
• reinforcement learning
– learning by trial and error through performance feedback
• Evolutionary algorithms
– using genetic algorithms to find good network weights
– significant problems with evolving real solutions in
reasonable time on current mobile robot hardware
Control Problems for an
autonomous robot
•
•
•
Rapidly changing boundary conditions
Real-time response
Information collected over noisy
channels
The Control Cycle
• A fundamental methodology derived in the early days of
robotics from engineering principles is the sense-think-act
cycle
– the principle is to continuously attempt to minimise the error
between the actual state and the desired state
• based on control theory
sense
compute
(think)
act
Model Based
• A symbolic internal ‘world-model’ is maintained
– the sub-tasks are decomposed into functional layers
– similar to ‘classical’ artificial intelligence approach
sense
perception
modelling
planning
task execution
motor control
act
Problems with Models
• An adequate, accurate and up-to-date model must be
maintained at all times
– this is very difficult in practice!
– suppose, for example, the sensors detect an object that we
have not got a symbol for (a novel object)
• A model-based system is extremely brittle
– if one of the functional layers fails (e.g. hardware
problems, software bugs), then the whole system fails
• Significant processing power is required
– maintaining the model takes time, so slow responses!?
• Despite much effort, little progress was made!
Reactive Controllers
• In order to try to overcome the shortcomings of
model-based robots, modern approaches have
centred predominantly on simple reactive systems
with minimal amounts of computation
– ‘model-free systems’
• More correctly, the models are simple and implicit
– the systems do not use symbolic models but, for example,
a rule-set which tells a robot how to react to a corner
when following a wall may be considered to be a simple,
implicit model fragment
• it implicitly encodes assumptions about the environment
Behavior Based
• The control system is broken down into horizontal
modules, or behaviors, that run in parallel
– each behavior has direct access to sensor readings and
can control the robot’s motors directly
identify objects
build maps
sense
explore
wander
avoid objects
act
Three-layer
architectures
(TLA)
Three-layer architectures (TLA)
• “Response” to subsumption, simultaneously and
independently developed by >3 groups
• TLA design seems to implicitly:
– Agree that different processing models are needed to
react to events on different time scales
– Agree with loose asynchronous interfaces
– Disagree with the “infinite regression” of layers
– Disagree with the subsumption mechanism itself -i.e. overriding of inputs/outputs
• But is this the essence of subsumption?
the role of state
• SPA:
– Uses extensive internal state
– Plans slowly and infrequently
– Gets into trouble when its internal state loses synchronicity
with the world
• Reactive:
–
–
–
–
“The World is its Own Best Model”
No internal state
Tight sensor to actuator coupling
Runs headlong into the problem of extracting state information
from the world using sensors
• Hybrid/Three Layer
– Can’t we all just get along?
the three-layer architecture
• Consists of (surprise!) 3 layers
– Reactive layer (Controller)
• Stateless, sensor-based
• Short time scale actions
– “Glue” Layer (Sequencer)
• Has a memory of the past
• Selects primitive behaviors for Controller
– Planning Layer (Deliberator)
• Plans for the future
• Time-consuming operations (search, complex vision, etc.)
Behavior Advantages
• It supports multiple goals and is more efficient
– there is no functional hierarchy between layers
• one layer does not call another layer
– each layer can work on different goals in parallel
– communication between layers is achieved via message passing
which need not be synchronised
• The system is easier to design, debug and extend
– each module can be designed and tested individually
• The system is robust
– if one module fails, e.g. wander, then other layers, e.g. avoid
obstacles, still function and behave correctly
Behavior Limitations
• It is extremely difficult to implement plans
– in pure form a behaviour-based robot has no memory
(not even an internal state memory) and so is unable
to follow an externally specified sequences of actions
• It can be very hard to predict how a large number of
multiple behaviours may interact
– emergent behaviour is the term given to unexpected
behaviour that comes about through these interactions
• sometimes it is useful, sometimes it is not!
• The robot can get trapped in a limit cycle
– trapped in a dead-end, repeatedly turning left then right
The new approach
A robust layered control system based on task
(activity) achieving
• What is the layer?
A class of behavior
•
Requirements
Multiple goals
Multiple sensors
Robustness
Extensibility
Conclusions & Implications
• A kind intelligent action can be generated without
– Specific logical representation
– Logical reasoning or search
• Intelligence without [typical] representation
• Can planning, and other traditional AI goals be
met?
Background on Agents
Agent – an entity with domain
knowledge, goals and actions.
 Chess playing programs
 Sojourner Mars Exploration Robot
Autonomous Agent – uses sensors and
effectors to independently achieve goals.
Mobile Robots and Vehicles
Box-Pushing
Task
• Consider the following task: design a behaviorbased robot to “push boxes”
• What should the design look like?
• What are the behaviors?
• How should they be combined?
Behaviors for Box-Pushing Task
• FINDER:
– Goal: Locate an object that might be a box
– Strategy: Wander around till the sonars detect an object
– Priority: Lowest (default behavior)
• PUSHER:
– Goal: Push an object
– Strategy: Move forward while bumped and not stuck
– Priority: Override FINDER when active
• UNWEDGER:
– Goal: Recover from stalled situations where PUSHER failed
– Strategy: Turn and move forward to open space
– Priority: Highest (override all other behaviors)
Control Flow Among Behaviors
Recycling Task
• Consider designing a behavior-based robot to
recycle soda cans into trash bins
• What sensors would you use?
• What features would you design?
• What kinds of behaviors would be necessary?
• Don’t peek at Connell’s paper yet!
Behaviors for Recycling
•
•
•
•
•
•
Find soda cans
Pick up a soda can
Navigate the environment
Avoid obstacles
Find trash cans
Head for home
HERBERT: A Coke Can Collecting
Robot
• Herbert was designed by Jonathan Connell for his Ph.d.
thesis at MIT
• Herbert was one of the first demonstrations of behaviorbased robots
• This robot demonstrated that a distributed “colony” of
behaviors could be combined to do a nontrivial robotics
task
• There is no central coordinator or “master” process
underlying Herbert
Strategies for Combining
Behaviors
• Subsumption:
– One behavior “subsumes” another (overrides it)
– Easy to implement
– Combination may result in thrashing or jerky motions
• Bitwise:
– Each behavior modifies action command bits
• Vector sum (schema approach):
–
–
–
–
Each behavior proposes a certain motion vector
The motion vectors are combined through vector addition
The resultant vector is the direction of motion of the robot
Smooth combination of behaviors
Conflicting Behaviors
“Find box”
“Avoid”
“Wall”
Bitwise Combination of Behaviors
1
0
0
0
Turn Turn Turn Turn Trans.
fast left right med. fast
1
Forward
1
0
1
Back
ACTION COMMAND = 1 BYTE
Trans.
slow
Each behavior modifies certain fields of the action command
logical BIT & and logical BIT OR.
Vector Sum Combination of
Behaviors
Potential field motion planning: obstacles
are repulsive , goals are attractive
AVOID
GOAL
OBSTACLE
MOVE
to GOAL
Limitations of Behavior-Based
Robots
• No easy way to incorporate global knowledge (symbolic
maps, rules etc.)
• Hardwired behaviors -- robot cannot adapt to new
unforeseen situations
• Lacks a planning/reasoning component -- cannot predict
consequences of actions
• Extensions:
– New behaviors can be learned using neural networks and
reinforcement learning
– Global knowledge and planning achieved using a higher level
deliberative system on top of behavior-based system
A Layered Robot Navigation
Architecture
Sensor Reports
Neural Net
Features
Planning and Execution
Layer (POSMDP)
Action
Local Occupancy Reports
Grids
Raw Sensor
Values
Behavior-based
Layer
Action
Commands
Motor
Commands
Limitations of Reactive Systems
•
•
•
•
Action computed depends on current sensor values only
State history is not captured
Hard to write complex monolithic reactive systems
Solution:
– Decompose overall system into a number of “behaviors”
– Use “small” amounts of state information as memory
• Many robots have been successfully built using this
approach
Hybrid Architecture
symbolic
events
relevant
situations
sensors
Parameterization of
processes
Control
values
actuators
Hybrid architecture for
navigation
Future Work
• Short Term
– Galloping of Legged Robots
– Humanoid Robots for Soccer
• Long Term
– Creation of highly skilled Robots
– Search and Rescue Operations
Research
Problems
Vision
• Fully Colored Environment
– Teams (Red & Dark Blue)
• Identify Teammates
– Ball (Orange)
– Goals (Light Blue)
– Poles
• 6 combinations of Yellow, Pink, and Green
• Localization
Vision
• YUV color model
– Y represents luminance
– U and V represents chromacity
• Color classification algorithm
– 20 images used for training
– Convergence in less than one hour
– High accuracy
Localization
• Bayesian Probabilistic Localization
– Bayes’ Theorem:
P(Si|O) =
P(Si) P(O|Si)
j P(Sj) P(O|Sj)
.
– Movement Algorithm
P(Si|M) = j P(Sj) P(Sj  Si|M)
RoboCup Agents
Look to how agents for robot soccer are
programmed
Vortrag von Martin Lötzsch und Matthias Jüngel
[email protected]
[email protected]
Ideas
• Evolve state machines
• Learn State Machines
• Combinational (mv, fuzzy,arithmetic logic)
functions are special cases of state machines
• They can be learned using Constructive Induction
– formal optimal construction methods based on logic
synthesis programs which are very efficient
• Neural Nets can be included in layers
These ideas are all used much in robot
soccer
SUMMARY continues
• Robotics is challenging field for to reasons:
– First , it requires hardware(sensors and effectors) that
actually work, a real challenge for mechanical
engineering
– Second, robots have to work in the physical world,
which is more complex than most of the simulated
software worlds that we have used for our examples in
other chapters
• But modern autonomous robots with sophisticated
sensors and effectors provide a challenging testbed for
determining what it takes to build an intelligent agent
Summary
• FIRA
– Since 1996
– MiroSot, NaroSot, KheperaSot, RoboSot
• RoboCup
– Since 1997
– Simulation league, Small size league,
Middle size league, Sony legged robot league
Summary
• Summary of this lecture
– background
• the behaviour based approach
• Brooks’ assumptions about mobile robot design
– subsumption architecture
• levels of competence
– example competences
• layers of control
– subsumption
• structure of layers
• extensions; finite state machines
• Next lecture
– Brooks’ subsumption architecture: practice
7. SUMMARY
•
•
•
•
•
•
•
•
•
The Physical World
Industry applications
Body with rigid links connected to each other by joints
Sensors like vision, force, tactile, sonar
The problem of moving a complex-shaped object( i.e., the robot and anything it is carrying)
through a space with complex-shaped obstacles is a difficult one. The mathematical notation
of configuration space provides a framework for analysis.
Cell decomposition and skeletonization methods can be used to navigate through the
configuration space. Both reduce a high dimensional, continuous space to a discrete graphsearch problem.
Some aspects of the world, such as the exact location of a bolt in the robot’s hand, will always
be unknown. Fine-motion planning deals with this uncertainty by creating a sensor-based plan
that will work regardless of exact initial conditions.
Uncertainty applies to sensors at the large scale as well. In the landmark model, a robot uses
certain well-known landmarks in the environment to determine where it is, even in the face of
uncertainty.
If a map of the environment is not available, then the robot will have to plan its navigation as
it goes. Online algorithms do this. They do not always choose the shortest route, but we can
analyze how far off they will be.
Conventional Approach vs. BehaviorBased Robots (Brooks)
“new AI”
Reading
Autonomous Robot Teams in Dynamic and Uncertain Environments
Prof. Manuela Veloso, Dr. Tucker Balch, and Dr. Brett Browning
Carnegie Mellon University
R. A. Brooks, “A Robust Layered Control System for a Mobile
Robot”, Cambrian
Intelligence, The MIT Press
J. O. Gray, D. G. Caldweel, “Advanced Robotics & Intelligent Machines”
R. A. Brooks, “Cambrian Intelligence”, The MIT Press
Book
Computational Principles of
Famous paper, read
Gregory Dudek and Michael Jenkin
the original!
Mobile Robotics
Papers
Achieving Artificial Intelligence through
Rodney Brooks
Building Robots
Subsumption Architecture
A Robust Layered Control System
for a Mobile Robot
Rodney A. Brooks
IEEE Journal of Robotics and Automation
Vol. RA-2, No. 1, March 1986
links
Walking machines:
• http://www.fzi.de/ids/WMC/OtherWM.html
• http://www.plustech.fi
• http://www.ai.mit.edu/projects/leglab/robots/robots.html
AI
• http://www.ai.mit.edu/
• http://www.ai.mit.edu/projects/cog/motor_video.htm
Sources
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
•
Rodney Brooks
Maja Mataric
Nilsson’s book
Jeremy Elson
Norvig’s book, chapter 2. Good. Stimulus-Response
Agents
English PH.D thesis, recent
Jon Garibaldi
Prof. Bruce Donald, Changxun Wu, Dartmouth College
Leo Ilkko
Prof. Manuela Veloso, Dr. Tucker Balch, and Dr. Brett
Browning
Carnegie Mellon University
Rabih Neouchi , Donald C. Onyango and Stacy F.
President
Axel Roth
Ramon Brena Pinero ITESM
Rhee, Taik-heon, Computer Science Department,
KAIST
Brian R. Duffy, Gina Joue
Jon Garibaldi , De Montfort University
Lucy Moffatt, Univ of Sheffield
Yorick Wilks, Computer Science Department,
University of Sheffield
Cecilia Laschi,
Connell, Brooks
Maja Mataric
Nilsson book
Jeremy Elson
Norvig’s book
English PH.D thesis, recent
Rhee, Taik-heon, Computer Science
Department, KAIST
Axel Roth
Ramon Brena Pinero ITESM
Rabih Neouchi
Donald C. Onyango and Stacy F.
President