Autonomous Mobile Robots
CPE 470/670
Lecture 8
Instructor: Monica Nicolescu
Review
Control Architectures
• Languages for robot control
• Computability
• Organizing principles
• Architecture selection criteria
• Reactive control
CPE 470/670 - Lecture 8
2
Reactive Control
• Reactive control is based on tight (feedback) loops
connecting a robot's sensors with its effectors
• Purely reactive systems do not use any internal
representations of the environment, and do not
look ahead
– They work on a short time-scale and react to the current
sensory information
• Reactive systems use minimal, if any, state
information
CPE 470/670 - Lecture 8
3
Collections of Rules
• Reactive systems consist of collections of reactive
rules that map specific situations to specific actions
• Analog to stimulus-response, reflexes
– Bypassing the “brain” allows reflexes to be very fast
• Rules are running concurrently and in parallel
• Situations
– Are extracted directly from sensory input
• Actions
– Are the responses of the system (behaviors)
CPE 470/670 - Lecture 8
4
Mutually Exclusive Situations
• If the set of situations is mutually exclusive:
 only one situation can be met at a given time
 only one action can be activated
• Often is difficult to split up the situations this way
• To have mutually exclusive situations the controller
must encode rules for all possible sensory
combinations, from all sensors
• This space grows exponentially with the number of
sensors
CPE 470/670 - Lecture 8
5
Complete Control Space
• The entire state space of the robot consists of all
possible combinations of the internal and external
states
• A complete mapping from these states to actions is
needed such that the robot can respond to all
possibilities
• This is would be a tedious job and would result in a
very large look-up table that takes a long time to
search
• Reactive systems use parallel concurrent reactive
rules  parallel architecture, multi-tasking
CPE 470/670 - Lecture 8
6
Incomplete Mappings
• In general, complete mappings are not used in handdesigned reactive systems
• The most important situations are trigger the
appropriate reactions
• Default responses are used to cover all other cases
• E.g.: a reactive safe-navigation controller
If left whisker bent then turn right
If right whisker bent then turn left
If both whiskers bent then back up and turn left
Otherwise, keep going
CPE 470/670 - Lecture 8
7
Example – Safe Navigation
• A robot with 12 sonar sensors, all around the robot
• Divide the sonar range into two zones
1
2
12
3
– Danger zone: things too close
11
4
– Safe zone: reasonable distance to objects
10
5
9
6
8
7
if minimum sonars 1, 2, 3, 12 < danger-zone and not-stopped
then stop
if minimum sonars 1, 2, 3, 12 < danger-zone and stopped
then move backward
otherwise
move forward
• This controller does not look at the side sonars
CPE 470/670 - Lecture 8
8
Example – Safe Navigation
• For dynamic environments, add another layer
if sonar 11 or 12 < safe-zone and
sonar 1 or 2 < safe-zone
then turn right
if sonar 3 or 4 < safe-zone
1
2
12
3
11
4
10
5
9
6
8
7
then turn left
• The robot turns away from the obstacles before getting
too close
• The combinations of the two controllers above 
collision-free wandering behavior
• Above we had mutually-exclusive conditions
CPE 470/670 - Lecture 8
9
Action Selection
• In most cases the rules are not triggered by unique
mutually-exclusive conditions
– More than one rule can be triggered at the same time
– Two or more different commands are sent to the actuators!!
• Deciding which action to take is called action selection
• Arbitration: decide among multiple actions or
behaviors
• Fusion: combine multiple actions to produce a single
command
CPE 470/670 - Lecture 8
10
Arbitration
• There are many different types of arbitration
• Arbitration can be done based on:
• a fixed priority hierarchy
– rules have pre-assigned priorities
• a dynamic hierarchy
– rules priorities change at run-time
• learning
– rule priorities may be initialized and are learned at runtime, once or continuously
CPE 470/670 - Lecture 8
11
Multi-Tasking
• Arbitration decides which one action to execute
• To respond to any rule that might become triggered
all rules have to be monitored in parallel, and
concurrently
If no obstacle in front  move forward
If obstacle in front  stop and turn away
Wait for 30 seconds, then turn in a random direction
• Monitoring sensors in sequence may lead to missing
important events, or failing to react in real time
• Reactive systems must support parallelism
– The underlying programming language must have multitasking abilities
CPE 470/670 - Lecture 8
12
Designing Reactive Systems
• How to can we put together multiple (large number)
of rules to produce effective, reliable and goal
directed behavior?
• How do we organize a reactive controller in a
principled way?
• The best known reactive architecture is the
Subsumption Architecture (Rod Brooks, MIT,
1985)
CPE 470/670 - Lecture 8
13
Vertical v. Horizontal Systems
Traditional (SPA):
sense – plan – act
Subsumption:
CPE 470/670 - Lecture 8
14
Biological Inspiration
• The inspiration behind the Subsumption Architecture
is the evolutionary process:
– New competencies are introduced based on existing ones
• Complete creatures are not thrown out and new
ones created from scratch
– Instead, solid, useful substrates are used to build up to
more complex capabilities
CPE 470/670 - Lecture 8
15
The Subsumption Architecture
• Principles of design
– systems are built from
the bottom up
– components are task-achieving
actions/behaviors (avoid-obstacles, find-doors, visit-rooms)
– components are organized in layers, from the bottom up
– lowest layers handle most basic tasks
– all rules can be executed in parallel, not in a sequence
– newly added components and layers exploit the existing
ones
CPE 470/670 - Lecture 8
16
Subsumption Layers
• First, we design, implement and debug
layer 0
• Next, we design layer 1
– When layer 1 is designed, layer 0 is
taken into consideration and utilized, its
existence is subsumed (thus the name of
the architecture)
– As layer 1 is added, layer 0 continues to
function
sensors
level 2
level 1
level 0
actuators
• Continue designing layers, until the
desired task is achieved
CPE 470/670 - Lecture 8
17
Suppression and Inhibition
• Higher layers can disable the ones below
– Avoid-obstacles can stop the robot from moving around
• Layer 2 can either:
– Inhibit the output of level 1 or
– Suppress the input of level 1
• The process is continued all the way to the top level
level 2
inhibitor
s
level 1
inputs
level 0
AFSM
outputs
I
suppressor
sensors
actuatorsCPE 470/670 - Lecture 8
18
Subsumption Language and AFSMs
• The original Subsumption Architecture was
implemented using the Subsumption Language
• It was based on finite state machines (FSMs)
augmented with a very small amount of state (AFSMs)
• AFSMs were implemented in Lisp
inhibitor
s
inputs
AFSM
outputs
I
suppressor
CPE 470/670 - Lecture 8
19
Subsumption Language and AFSMs
• Each behavior is represented as an augmented finite state
collide
machine (AFSMs)
inhibitor
• Stimulus (input) or response
sonar
(output) can be inhibited or
s
inputs
AFSM
outputs
halt
I
suppressor
suppressed by other active behaviors
• An AFSM can be in one state at a time, can receive one or
more inputs, and send one or more outputs
• AFSMs are connected communication wires, which pass
input and output messages between them; only the last
message is kept
• AFSMs run asynchronously
CPE 470/670 - Lecture 8
20
Networks of AFSMs
• Layers represent task achieving behaviors
– Wandering, avoidance, goal seeking
• Layers work concurrently and asynchronously
level 2
• A Subsumption Architecture controller,
level 1
using the AFSM-based programming
level 0
language, is a network of AFSMs divided into
layers
• Convenient for incremental system design
CPE 470/670 - Lecture 8
21
Wandering in Subsumption
• Brooks ‘87
CPE 470/670 - Lecture 8
22
Layering in AFSM Networks
• Layers modularize the reactive system
• Bad design:
– putting a lot of behaviors within a single layer
– putting a large number of connections between the layers, so
that they are strongly coupled
• Strong coupling implies dependence between modules, which
violates the modularity of the system
• If modules are interdependent, they are not as robust to
failure
• In Subsumption, if higher layers fail, the lower ones remain
unaffected
CPE 470/670 - Lecture 8
23
Module Independence
• Subsumption has one-way independence between
layers
– With upward independence, a higher layer can always use
a lower one by using suppression and inhibition
• Two-way independence is not practical
– No communication between layers is possible
• Do we always have to use these wires to
communicate between parts of the system?
CPE 470/670 - Lecture 8
24
Using the World
• How can you sequence activities in Subsumption?
• Coupling between layers need not be through the
system itself (i.e., not through explicit
communication wires)
• It could be through the world. How?
CPE 470/670 - Lecture 8
25
Collecting Soda Cans
• Herbert collected empty soda cans
and took them home
• Herbert’s capabilities
– Move around without running into
obstacles
– Detect soda cans using a camera and a
laser
– An arm that could: extend, sense if there
is a can in the gripper, close the gripper,
tuck the arm in
CPE 470/670 - Lecture 8
26
Herbert
• Look for soda cans, when seeing one approach it
• When close, extend the arm toward the soda can
• If the gripper sensors detect something close the
gripper
• If can is heavy, put it down, otherwise pick it up
• If gripper was closed tuck the arm in and head home
• The robot did not keep internal state about what
it had just done and what it should do next: it
just sensed!
CPE 470/670 - Lecture 8
27
More on Herbert
• There is no internal wire between the layers that
achieve can finding, grabbing, arm tucking, and
going home
• However, the events are all executed in proper
sequence. Why?
• Because the relevant parts of the control system
interact and activate each other through sensing the
world
CPE 470/670 - Lecture 8
28
World as the Best Model
• This is a key principle of reactive systems &
Subsumption Architecture:
– Use the world as its own best model!
• If the world can provide the information directly
(through sensing), it is best to get it that way, than to
store it internally in a representation (which may be
large, slow, expensive, and outdated)
CPE 470/670 - Lecture 8
29
Subsumption System Design
• What makes a Subsumption Layer, what should go
where?
• There is no strict recipe, but some solutions are
better than others, and most are derived empirically
• How exactly layers are split up depends on the
specifics of the robot, the environment, and the task
CPE 470/670 - Lecture 8
30
Designing in Subsumption
• Qualitatively specify the overall behavior needed
for the task
• Decompose that into specific and independent
behaviors (layers)
• Determine behavior granularity
• Ground low-level behaviors in the robot’s sensors
and effectors
• Incrementally build, test, and add
CPE 470/670 - Lecture 8
31
Genghis (MIT)
• Walk over rough terrain and follow a human (Brooks ’89)
– Standup
• Control leg’s swing position and lift
– Simple walk
– Force balancing
• Force sensors provide information about the ground profile
– Leg lifting: step over obstacles
– Obstacle avoidance (whiskers)
– Pitch stabilization
– Prowling
– Steered prowling
CPE 470/670 - Lecture 8
32
The Nerd Herd (MIT)
• Foraging example (Matarić ’93)
– R1 robots (IS robotics)
• Behaviors involved:
– Wandering
– Avoiding
– Pickup
– Homing
CPE 470/670 - Lecture 8
33
Tom and Jerry (MIT)
Tom
• fsdf
Jerry
CPE 470/670 - Lecture 8
34
Pros and Cons
• Some critics consider the lack of detail about
designing layers to be a weakness of the approach
• Others feel it is a strength, allowing for innovation
and creativity
• Subsumption has been used on a vast variety of
effective implemented robotic systems
• It was the first architecture to demonstrate many
working robots
CPE 470/670 - Lecture 8
35
Benefits of Subsumption
• Systems are designed incrementally
– Avoid design problems due to the complexity of the task
– Helps the design and debugging process
• Robustness
– If higher levels fail, the lower ones continue unaffected
• Modularity
– Each “competency” is included into a separate layer, thus
making the system manageable to design and maintain
– Rules and layers can be reused on different robots and for
different tasks
CPE 470/670 - Lecture 8
36
Readings
• F. Martin: Chapter 5
• M. Matarić: Chapter 10
CPE 470/670 - Lecture 8
37
Descargar

Analysis of Algorithms CS 465/665