ai-class - Computer Science & Engineering

Download Report

Transcript ai-class - Computer Science & Engineering

Artificial Intelligence
Instructor: Monica Nicolescu
Outline
 Introduction
– Robotics: what it is, what it isn’t, and where it came from
– Key concepts
• Brief history
• Robot control architectures
– Deliberative control
– Reactive control
– Hybrid control
– Behavior-based control
Artificial Intelligence
2
Key Concepts
• Situatedness
– Agents are strongly affected by the environment and deal
with its immediate demands (not its abstract models)
directly
• Embodiment
– Agents have bodies, are strongly constrained by those
bodies, and experience the world through those bodies,
which have a dynamic with the environment
Artificial Intelligence
3
Key Concepts (cont.)
• Situated intelligence
– is an observed property, not necessarily internal to the
agent or to a reasoning engine; instead it results from the
dynamics of interaction of the agent and environment
– and behavior are the result of many interactions within the
system and w/ the environment, no central source or
attribution is possible
Artificial Intelligence
4
What is Robotics?
• Robotics is the study of robots, autonomous
embodied systems interacting with the physical
world
• A robot is an autonomous system which exists in
the physical world, can sense its environment and
can act on it to achieve some goals
• Robotics addresses perception, interaction and
action, in the physical world
Artificial Intelligence
5
Uncertainty
• Uncertainty is a key property of existence in the
physical world
• Physical sensors provide limited, noisy, and
inaccurate information
• Physical effectors produce limited, noisy, and
inaccurate action
• The uncertainty of physical sensors and effectors is
not well characterized, so robots have no available a
priori models
Artificial Intelligence
6
Uncertainty (cont.)
• A robot cannot accurately know the answers to the
following:
– Where am I?
– Where are my body parts, are they working, what are they
doing?
– What did I just do?
– What will happen if I do X?
– Who/what are you, where are you, what are you doing,
etc.?...
Artificial Intelligence
7
The term “robot”
• Karel Capek’s 1921 play RUR (Rossum’s Universal
Robots)
• It is (most likely) a combination of “rabota”
(obligatory work) and “robotnik” (serf)
• Most real-world robots today do perform such
“obligatory work” in highly controlled environments
– Factory automation (car assembly)
• But that is not what robotics research about; the
trends and the future look much more interesting
Artificial Intelligence
8
Classical activity decomposition
• Locomotion (moving around, going places)
– factory delivery, Mars Pathfinder, lawnmowers, vacuum
cleaners...
• Manipulation (handling objects)
– factory automation, automated surgery...
• This divides robotics into two basic areas
– mobile robotics
– manipulator robotics
• … but these are merging in domains like robot pets,
robot soccer, and humanoids
Artificial Intelligence
9
An assortment of robots…
Artificial Intelligence
10
Anthropomorphic Robots
Artificial Intelligence
11
Animal-like Robots
Artificial Intelligence
12
Humanoid Robots
QRIO
Asimo (Honda)
Robonaut (NASA)
Artificial
DB Intelligence
(ATR)
Sony Dream Robot
13
Outline
• Introduction
– Robotics: what it is, what it isn’t, and where it came from
– Key concepts
 Brief history
• Robot control architectures
– Deliberative control
– Reactive control
– Hybrid control
– Behavior-based control
Artificial Intelligence
14
A Brief History of Robotics
• Robotics grew out of the fields of control theory, cybernetics
and AI
• Robotics, in the modern sense, can be considered to have
started around the time of cybernetics (1940s)
• Early AI had a strong impact on how it evolved (1950s-1970s),
emphasizing reasoning and abstraction, removal from direct
situatedness and embodiment
• In the 1980s a new set of methods was introduced and robots
were put back into the physical world
Artificial Intelligence
15
Cybernetics
• Pioneered by Norbert Wiener in the 1940s
• Combines principles of control theory, information
science and biology
• Sought principles common to animals and
machines, especially with regards to control and
communication
• Studied the coupling between an organism and its
environment
Artificial Intelligence
16
W. Grey Walter’s Tortoise
• Machina Speculatrix” (1953)
– 1 photocell, 1 bump sensor,
1 motor, 3 wheels, 1
battery, analog circuits
• Behaviors:
– seek light
– head toward moderate light
– back from bright light
– turn and push
– recharge battery
• Uses reactive control, with
behavior prioritization
Artificial Intelligence
17
Braitenberg Vehicles
• Valentino Braitenberg (1980)
• Thought experiments
– Use direct coupling between sensors and motors
– Simple robots (“vehicles”) produce complex behaviors that
appear very animal, life-like
• Excitatory connection
– The stronger the sensory input, the stronger the motor output
– Light sensor  wheel: photophilic robot (loves the light)
• Inhibitory connection
– The stronger the sensory input, the weaker the motor output
– Light sensor  wheel: photophobic robot (afraid of the light)
Artificial Intelligence
18
Example Vehicles
• Wide range of vehicles can be designed, by changing the
connections and their strength
Vehicle 1
• Vehicle 1: Being “ALIVE”
– One motor, one sensor
• Vehicle 2: “FEAR” and “AGGRESSION”
– Two motors, two sensors
Vehicle 2
– Excitatory connections
• Vehicle 3: “LOVE”
– Two motors, two sensors
– Inhibitory connections
Artificial Intelligence
19
Artificial Intelligence
• Officially born in 1956 at Dartmouth University
– Marvin Minsky, John McCarthy, Herbert Simon
• Intelligence in machines
– Internal models of the world
– Search through possible solutions
– Plan to solve problems
– Symbolic representation of information
– Hierarchical system organization
– Sequential program execution
Artificial Intelligence
20
AI and Robotics
• AI influence to robotics:
– Knowledge and knowledge representation are central to
intelligence
• Perception and action are more central to robotics
• New solutions developed: behavior-based systems
– “Planning is just a way of avoiding figuring out what to do
next” (Rodney Brooks, 1987)
• First robots were mostly influenced by AI (deliberative)
Artificial Intelligence
21
Outline
• Introduction
– Robotics: what it is, what it isn’t, and where it came from
– Key concepts
• Brief history
 Robot control architectures
– Deliberative control
– Reactive control
– Hybrid control
– Behavior-based control
Artificial Intelligence
22
Control Architecture
• A robot control architecture provides the guiding
principles for organizing a robot’s control system
• It allows the designer to produce the desired overall
behavior
• The term architecture is used similarly as
“computer architecture”
– Set of principles for designing computers from a
collection of well-understood building blocks
• The building-blocks in robotics are dependent on
the underlying control architecture
Artificial Intelligence
23
Robot Control
• Robot control is the means by which the sensing
and action of a robot are coordinated
• There are infinitely many ways to program a robot,
but there are only few types of robot control:
– Deliberative control
– Reactive control
– Hybrid control
– Behavior-based control
Artificial Intelligence
24
Spectrum of robot control
From “Behavior-Based Robotics” by R. Arkin, MIT Press, 1998
Artificial Intelligence
25
Thinking vs. Acting
• Thinking/Deliberating
– involves planning (looking into the future) to avoid bad
solutions
– flexible for increasing complexity
– slow, speed decreases with complexity
– thinking too long may be dangerous
– requires (a lot of) accurate information
• Acting/Reaction
– fast, regardless of complexity
– innate/built-in or learned (from looking into the past)
– limited flexibility for increasing complexity
Artificial Intelligence
26
Robot control approaches
• Reactive Control
– Don’t think, (re)act.
• Deliberative (Planner-based) Control
– Think hard, act later.
• Hybrid Control
– Think and act separately & concurrently.
• Behavior-Based Control (BBC)
– Think the way you act.
Artificial Intelligence
27
A Brief History
• Deliberative Control
(late 70s)
• Reactive Control
(mid 80s)
– Subsumption Architecture (Rodney Brooks)
• Behavior-Based Systems
(late 80s)
• Hybrid Systems
(late 80s/early 90s)
Artificial Intelligence
28
Outline
• Introduction
– Robotics: what it is, what it isn’t, and where it came from
– Key concepts
• Brief history
• Robot control architectures
 Deliberative control
– Reactive control
– Hybrid control
– Behavior-based control
Artificial Intelligence
29
Deliberative Control:
Think hard, then act!
• In DC the robot uses all the available sensory information and
stored internal knowledge to create a plan of action: sense 
plan  act (SPA) paradigm
• Limitations
– Planning requires search through potentially all possible plans 
these take a long time
– Requires a world model, which may become outdated
– Too slow for real-time response
• Advantages
– Capable of learning and prediction
– Finds strategic solutions
Artificial Intelligence
30
Early AI Robots
• Shakey (1960, Stanford Research Institute)
• Stanford Cart (1977) and CMU rover (1983)
• Interpreting the structure of the environment from
visual input involved complex processing and
required a lot of deliberation
• Used state-of-the-art computer vision techniques
to provide input to a planner and decide what to
do next (how to move)
Artificial Intelligence
31
Outline
• Introduction
– Robotics: what it is, what it isn’t, and where it came from
– Key concepts
• Brief history
• Robot control architectures
– Deliberative control
 Reactive control
– Hybrid control
– Behavior-based control
Artificial Intelligence
32
Reactive Control:
Don’t think, react!
• Technique for tightly coupling perception and action to provide
fast responses to changing, unstructured environments
• Collection of stimulus-response rules
• Limitations
• Advantages
– No/minimal state
– Very fast and reactive
– No memory
– Powerful method: animals
are largely reactive
– No internal representations
of the world
– Unable to plan ahead
Artificial Intelligence
33
Vertical v. Horizontal Systems
Traditional (SPA):
sense – plan – act
Subsumption:
(Rodney Brooks)
“The world is its own best model.”
Artificial Intelligence
34
The Subsumption Architecture
• Principles of design
– systems are built
incrementally
– components are task-achieving
actions/behaviors (avoid-obstacles, find-doors, visit-rooms)
– all rules can be executed in parallel, not in a sequence
– components are organized in layers, from the bottom up
– lowest layers handle most basic tasks
– newly added components and layers exploit the existing
ones
Artificial Intelligence
35
Subsumption Layers
• First, we design, implement and debug
layer 0
level 2
• Next, we design layer 1
level 1
– When layer 1 is designed, layer 0 is
taken into consideration and utilized, its
existence is subsumed
– Layer 0 continues to function
level 0
sensors
actuators
• Continue designing layers, until the
desired task is achieved
inhibitor
s
• Higher levels can
inputs
– Inhibit outputs of lower levels
– Suppress inputs of lower levels
Artificial Intelligence
AFSM
outputs
I
suppressor
36
Subsumption Architecture
Validation
• Practically demonstrated on navigation, 6-legged
walking, chasing, soda-can collection, etc.
Artificial Intelligence
37
Outline
• Introduction
– Robotics: what it is, what it isn’t, and where it came from
– Key concepts
• Brief history
• Robot control architectures
– Deliberative control
– Reactive control
 Hybrid control
– Behavior-based control
Artificial Intelligence
38
Hybrid Control:
Think and act independently & concurrently!
• Combination of reactive and deliberative control
– Reactive layer (bottom): deals with immediate reaction
– Deliberative layer (top): creates plans
– Middle layer: connects the two layers
• Usually called “three-layer systems”
• Major challenge: design of the middle layer
– Reactive and deliberative layers operate on very different
time-scales and representations (signals vs. symbols)
– These layers must operate concurrently
• Currently one of the two dominant control paradigms
in robotics
Artificial Intelligence
39
Reaction – Deliberation Coordination
Flakey
• Selection:
Planning is viewed as configuration
• Advising:
Planning is viewed as advice giving
• Adaptation:
Planning is viewed as adaptation
TJ
• Postponing:
Planning is viewed as a least
commitment process
Artificial Intelligence
40
Outline
• Introduction
– Robotics: what it is, what it isn’t, and where it came from
– Key concepts
• Brief history
• Robot control architectures
– Deliberative control
– Reactive control
– Hybrid control
 Behavior-based control
Artificial Intelligence
41
Behavior-Based Control
Think the way you act!
• An alternative to hybrid control, inspired from biology
• Behavior-based control involves the use of
“behaviors” as modules for control
• Historically grew out of reactive systems, but not
constrained
• Has the same expressiveness properties as hybrid
control
• The key difference is in the “deliberative” component
Artificial Intelligence
42
What Is a Behavior?
Rules of implementation
• Behaviors achieve or maintain particular goals
(homing, wall-following)
• Behaviors are time-extended processes
• Behaviors take inputs from sensors and from other
behaviors and send outputs to actuators and other
behaviors
• Behaviors are more complex than actions (stop, turnright vs. follow-target, hide-from-light, find-mate etc.)
Artificial Intelligence
43
Principles of BBC Design
• Behaviors are executed in parallel, concurrently
– Ability to react in real-time
• Networks of behaviors can store state (history),
construct world models/representation and look into
the future
– Use representations to generate efficient behavior
• Behaviors operate on compatible time-scales
– Ability to use a uniform structure and representation
throughout the system
Artificial Intelligence
44
Behavior Coordination
• Behavior-based systems require consistent
coordination between the component behaviors for
conflict resolution
• Coordination of behaviors can be:
– Competitive: one behavior’s output is selected from
multiple candidates
– Cooperative: blend the output of multiple behaviors
– Combination of the above two
Artificial Intelligence
45
Competitive Coordination
• Arbitration: winner-take-all strategy  only one
response chosen
• Behavioral prioritization
– Subsumption Architecture
• Action selection/activation spreading (Pattie Maes)
– Behaviors actively compete with each other
– Each behavior has an activation level driven by the robot’s
goals and sensory information
• Voting strategies
– Behaviors cast votes on potential responses
Artificial Intelligence
46
Cooperative Coordination
• Fusion: concurrently use the output of multiple
behaviors
• Major difficulty in finding a uniform command
representation amenable to fusion
• Fuzzy methods
• Formal methods
– Potential fields
– Motor schemas
– Dynamical systems
Artificial Intelligence
47
Example of Behavior Coordination
Fusion: flocking (formations)
Arbitration:  foraging (search, coverage)
Artificial Intelligence
48
Example of representation
• A network of behaviors representing spatial
landmarks, used for path planning by messagepassing (Matarić 90)
Artificial Intelligence
49
Behavior-Based
Control summary
• Alternative to hybrid systems; encourages uniform
time-scale and representation throughout the
system
• Scalable and robust
• Behaviors are reusable; behavior libraries
• Facilitates learning
• Requires a clever means of distributing
representation and any potentially time-extended
computation
Artificial Intelligence
50
Robotics Challenges
• Perception
– Limited, noisy sensors
• Actuation
– Limited capabilities of robot effectors
• Thinking
– Time consuming in large state spaces
• Environments
– Dynamic, impose fast reaction times
Artificial Intelligence
51
Lessons Learned
• Move faster, more robustly
• Think in such a way as to allow this action
• New types of robot control:
– Reactive, hybrid, behavior-based
• Control theory
– Continues to thrive in numerous applications
• Cybernetics
– Biologically inspired robot control
• AI
– Non-physical, “disembodied thinking”
Artificial Intelligence
52
Background Readings
• Ronald Arkin, “BehaviorBased Robotics”, 2001.
Artificial Intelligence
53