Transcript 020.Software-agents-for-mobile

Software Architectures
for Agents and Mobile Robots
Hans-Dieter Burkhard
Humboldt University Berlin
Institute of Informatics
www.ki.informatik.hu-berlin.de
Topics of the talk
Software Architectures
for Agents and Mobile Robots
• AI at Humboldt University
• Agents & Robots
• Architectures
• Mental states
• Control, Planning
• Double Pass Architecture
Artificial Intelligence at Humboldt University
Understanding emerges by doing.
Applied to the study of mental processes, this means
modeling of intelligent behavior by machines.
Artificial Intelligence has two aspects:
First modeling with the goal of better understanding,
and second engineering of useful machines.
Artificial Intelligence at Humboldt University
Case Based Reasoning
English
www.ki.informatik.hu-berlin.de version
Knowledge Management
Agent Oriented Techniques
Distributed AI
Socionics
Applications in Medicine
Intelligent Robotics
• Example:
Online Travel Agency
Travel Agent: How does it work
“Stimulus-Response”
Customer:
Specify wish
(fill in form)
Agent:
Prepare answer
(select and present
best matching offers)
Travel Agent: How does it work
“Stimulus-Response” Agent needs:
• Knowledge about
– offers (data base)
– similarity (acceptable alternative offers)
• Capabilities to
– Update offers
– Interaction with customer
– Search of best matching offers
(  Case Retrieval Nets)
Travel Agent: How does it work
CRN = CASE RETRIEVAL NET
Travel Agent: How could it work
Advisory agent
Customer
I would like to go
for holidays.
Agent
Travel Agent: How could it work
Advisory agent
Customer
I would like to go
for holidays.
Agent
Fine.
Do you like swimming?
Travel Agent: How could it work
Advisory agent
Customer
Yes, I like to be with
my friend on a white
strand,
no other tourists.
And I enjoy sports.
Agent
Fine.
Do you like swimming?
Travel Agent: How could it work
Advisory agent
Customer
Yes, I like to be with
my friend on a white
strand,
no other tourists.
And I enjoy sports.
Agent
Wonderful.
And in the evening?
Travel Agent: How could it work
Advisory agent
Customer
Good entertainment,
exclusive bars, etc.
Agent
Wonderful.
And in the evening?
Travel Agent: How could it work
Advisory agent
Customer
Good entertainment,
exclusive bars, etc.
Agent
Sounds fantastic,
is this like what you want?
(presents an offer)
Travel Agent: How could it work
Advisory agent
Customer
Looks fantastic.
But it is far behind of
my financial limits,
may be less exclusive.
Agent
Sounds fantastic,
is this like what you want?
(presents an offer)
Travel Agent: How could it work
Advisory agent
Customer
Looks fantastic.
But it is far behind of
my financial limits,
may be less exclusive.
Agent
So, let´s see. What´s about
that?
(presents another offer)
Travel Agent: How could it work
Advisory Agent needs:
• Needs of “Stimulus Response” Agent
(offers, capabilities, ...) as before
Dialog
Travel Agent: How could it work
Advisory Agent needs:
• “Dynamic” knowledge about dialog with customer
– History of dialog
– (Hypothetical) Model of current customer
• Wishes, intentions
• Capabilities
• Beliefs
– (Flexible) Plan for
• Discovering customer´s wishes, intentions, ...
• Selling most valuable products
Agent Oriented Techniques
“Agents work autonomously on behalf of their users.”
• Information agents
• Autonomous systems
• Cooperative systems
Autonomy: Following „own“ rules
(example: chess program)
• Autonomy w.r.t. somebody
• Complexity of decisions
• Socionics: humans + autonomous machines
– Cooperation
– Sociological requirements
– Organizational aspects
Control of Autonomous Mobile Robots
Problem: Dynamically changing environments
“Autonomous agents in real environments”
Problems: Localization, Movements, Control
Classical distinction of agents (robots)
• Reactive:
– Simple stimulus response behavior
– No planning
– No persistent states
• Deliberative
– Complicated deliberation
– Planning
– Persistent states
Sense-Think-Act-Cycle, Persistency
Environment
sense
execute
Persistent
states
Agent
think
Reactive Systems
execute
sense
A: xxx
B: yyy
C: zzz
select
Agent
think
Sensor-Actor-Coupling
• Obstacle avoidance by keeping distance
• Chess program ( ? - not “simple”)
Deliberative Systems
With 3 persistent states for worldmodel, goals, plans
update
execute
plan
worldmodel
means-ends
goal
Agent
select
Travel agent
Agent
Customer
update
Good
entertainment,
exclusive bars,
etc.
input
output
select
Worldmodel:
Discriminating customer
Goal:
Sell pricey
means-ends Plan:
Show attractive offers etc.
execute
Unfolding the cycle
update
execute
plan
meansends
Agent
update
Worldmodel
select
Goal
means-ends
Plan
execute
update
Worldmodel
select
Goal
means-ends
Plan
execute
worldmodel
goal
select
update
Worldmodel
select
Goal
means-ends
Plan
execute
Synchronization Problem
Simple Synchronization
update
select
means-ends
Problems for
•
dynamical environments
•
complex processes
update
select
means-ends
Conflict
Question
ROBOT = AGENT INSIDE A BODY ?
Simple architectures for physical agents
Stimulus-Response
– Immediate reactions to inputs from the real world.
– „The best model of the world is the world itself.“
Braitenberg
Vehicle
No need for a
complex agent
inside the robot
Soccer Playing Robots
By the year 2050,
develop a team of fully autonomous humanoid robots
that can win against the human world soccer champion team.
ENIAC
1946
Deep Blue
1997
Test field for
Goal driven research
Annual World Championships and Conferences
Simulation
Humanoid
Middle size
Rescue
www.robocup.org
Sony legged
Small size
Simple Stimulus-Response Behavior
Run to the ball
Simple Stimulus-Response Behavior
Run to the ball
Simple Stimulus-Response Behavior
Run to the ball
Simple Stimulus-Response Behavior
Run to the ball
LOOP
worldmodel := perceive (input);
commitment := deliberate (worldmodel);
output
:= execute(commitment);
execute
sense
A: xxx
B: yyy
C: zzz
select
Agent
think
Sensor-Actor-Coupling
Why are they acting: Triggering events
• Stimulus-Response
– recent events in the environment
• Goal-directed
– recent events in the environment
– internal goals
Goal-directed Behavior
Improvement:
Anticipate future situations:
x
Goal
Goal-directed Behavior
Improvement:
Anticipate future situations:
x
Goal
Goal-directed Behavior
Improvement:
Anticipate future situations:
Goal
Mental States
• Concerning past:
Worldmodel
• Concerning future:
Commitment (goal, intention, plan, ...)
Mental states are persistent states:
Keep information for more than one cycle
Stimulus-Response with Worldmodel
Simulate unobservable events: worldmodel
Stimulus-Response with Worldmodel
Simulate unobservable events: worldmodel
Stimulus-Response with Worldmodel
Simulate unobservable events: worldmodel
LOOP
worldmodel_new := update (input, worldmodel_old);
commitment
:= deliberate (worldmodel);
output
:= execute(commitment);
Worldmodel
• persistent state concerning the past:
Worldmodel (Belief)
Preprocessing of input from sensory signals
+
=
worldmodel_new := update (input, worldmodel_old);
Plan for Cooperation
Cooperation using joint intention (double pass)
Remark: Simulation of recent situation (world model )
needs knowledge about teammate´s intention
Plan for Cooperation
Cooperation using joint intention (double pass)
Remark: Simulation of recent situation (world model )
needs knowledge about teammate´s intention
Plan for Cooperation
Cooperation using joint intention (double pass)
Remark: Simulation of recent situation (world model )
needs knowledge about teammate´s intention
Plan for Cooperation
Cooperation using joint intention (double pass)
Remark: Simulation of recent situation (world model )
needs knowledge about teammate´s intention
Plan for Cooperation
Cooperation using joint intention (double pass)
Remark: Simulation of recent situation (world model )
needs knowledge about teammate´s intention
Plan for Cooperation
Cooperation using joint intention (double pass)
Remark: Simulation of recent situation (world model )
needs knowledge about teammate´s intention
Commitments: Goal-Directed Architecture
LOOP
worldmodel_new
:= update (input, worldmodel_old);
commitment_new := deliberate (worldmodel_new,commitment_old);
output
:= execute (commitment_new);
Difference to Stimulus Response:
• Persistent state concerning the future
(commitment: goal, plan ...)
+
Commitment_old
=
new alternatives
Commitment_new
AT Humboldt 98 (Simulation league)
• worldmodel
• intentions
• plans
Player
worldmodel
utilities
kick
pass
dribble
intercept
kick
pass
dribble
intercept
options
Pass to teammate
Kick to goal
Dribble
Go to position
Intercept
...
deliberation
options
skills
Utility
Time to reach the ball
(simulation of future)
Utility
Fastest player
to reach the ball
(simulation
of future)
Utility
Appropriate kick direction
(simulation of future)
Problems: Time Trade-Off
• Fast decision
– newest data
– rough criteria
sense
execute
A: xxx
B: yyy
C: zzz
select
think
think
Agent
Sensor-Actor-Coupling
• Complex deliberation
– detailed analysis, long term plans
– synchronization problem
update
update
execute
plan
worldmodel
means-ends
Agent
goal
select
select
means-ends
conflict
Problems: Time Trade-Off
– Fast decision
vs.
– Complex deliberation
Need for balance between
–low level (Stimulus-Response)
–high level (Goal-directed)
 Architectures with different levels (layers)
Option Hierarchy
PlaySoccer
Offensive
Score
Defensive
DoublePass/1
Dribble
DoublePass/2 ... ChangeWings/1
...
Kick
...
Pass
...
...
...
...
Run
...
Reposition
...
...
Intercept
...
...
...
...
...
...
...
Attack
...
OffsideTrap
...
...
...
Choice-Option (“OR-Branching”)
State (Place)
condition
Transition
with condition
Current State (marked Place)
Offensive
MaxUtility
MaxUtility
Score
ball out of
kickrange
MaxUtility
DoublePass/1
finished or
canceled
finished or
canceled
...
DoublePass/2
...
Sequence-Option (“AND-Branching”)
State (Place)
condition
Transition
with condition
Current State (marked Place)
Dribble
Teammate
free
Pass
Run
Pass
finished
Reposition
Teammate
passes
Intercept
Teammate
finished Pass
Extension for “unexpected” situation
Additional transitions (with simple conditions)
Offensive
MaxUtility
Score
ball out of
kickrange
MaxUtility
ball control
& goal free
finished or
canceled
MaxUtility
DoublePass/1
finished or
canceled
...
DoublePass/2
...
problem with
team mate
Problems: Stability Trade-Off
?
+
commitment_old
=
new alternatives
• Stabile behavior
+ achieve goals
+ reliability in cooperation
 fanatism
• Adaptation to new situation
+ flexibility
 oscillation
 re-planning
?
commitment_new
Oscillation (Noisy Sensory Data)
?
+
=
?
Adaptation (Changing Plan)
?
+
=
?
Adaptation (Changing Plan)
?
+
=
?
Adaptation (Changing Plan)
?
+
=
?
Adaptation (Changing Plan)
?
+
=
?
Adaptation (Changing Plan)
?
+
=
?
Problems: Stability Trade-Off
• Stabile behavior
vs.
• Adaptation to new situation
Need for balanced re-deliberation
– persistent state concerning future
– bias for old behavior (preventing from oscillation)
Problems: Context Problem
PlaySoccer
Offensive
Score
Defensive
DoublePass/1
Dribble
DoublePass/2 ... ChangeWings/1
Kick
...
Attack
OffsideTrap
Example:
...
... ...
...
(Opponent behaves in unexpected way)
• Active Behavior:
inside Dribbling
... for:
... Double Pass
• Invalid Condition
...
Pass
...
...
...
...
Run
...
Reposition
...
Need for re-consideration
on all levels
... ...
Intercept for stack oriented runtime systems
 Problem
...
...
...
...
Stack oriented architectures
• Classical architectures are stack oriented
– Only the procedure on top of stack is active
i.e., only low level behavior
– Higher level behavior can become active only when
lower levels are finished/interrupted
Intentions may change on any level
- caused by external events
Travel agent
•
Intentions may change on any level
- caused by external events
Ooops – no chance
to sell pricey ...
Customer
Looks fantastic.
But it is far behind of
my financial limits,
may be less exclusive.
Agent
Worldmodel:
No Discriminating customer
Goal:
Sell pricey
Plan:
Show attractive offers etc.
Problems: Least Commitment
• Start: Partial Plan
• Later: Exact Parameters
Needs consideration on all levels
?
Option Hierarchy
Double Pass Architecture
PlaySoccer
Offensive
Score
• Predefined Option Hierarchy
Defensive
DoublePass/1
Dribble
DoublePass/2 ... ChangeWings/1
Attack
Kick
...
Pass
...
...
...
...
...
...
...
...
Run
...
Reposition
• Choosen Part of it:
Intention subtree
(choosen by Deliberator)
...
Intention Subtree (chosen by Deliberator)
Intercept
...
...
OffsideTrap
...
...
...
...
...
...
...
PlaySoccer
H.D.Burkhard, HU Berlin
MOCA 2002
Defensive
Offensive
Score
DoublePass/1
Dribble
DoublePass/2
...
ChangeWings/1
...
Attack
Kick
...
Pass
...
Run
...
...
...
...
Reposition
...
...
...
...
...
...
Software Architectures
for Agents and Mobile Robots
58
OffsideTrap
...
...
...
...
...
Intercept
...
H.D.Burkhard, HU Berlin
MOCA 2002
...
Activity Path: Active Options
75
Software Architectures
for Agents and Mobile Robots
PlaySoccer
• Active Part of it:
Activity path
(updated by Executor)
Offensive
Score
Defensive
DoublePass/1
Dribble
DoublePass/2
...
ChangeWings/1
...
Kick
...
Pass
...
...
...
Run
...
...
Reposition
...
...
...
...
...
...
Attack
...
OffsideTrap
...
...
...
...
Intercept
...
H.D.Burkhard, HU Berlin
MOCA 2002
...
Software Architectures
for Agents and Mobile Robots
76
Intention Subtree (chosen by Deliberator)
PlaySoccer
Offensive
Score
Defensive
...
DoublePass/2
DoublePass/1
Dribble
ChangeWings/1
...
Kick
...
Pass
...
Run
...
...
...
...
Reposition
...
...
Intercept
...
...
...
...
...
...
...
Attack
...
OffsideTrap
...
...
...
Activity Path: Active Options
PlaySoccer
Offensive
Score
Defensive
DoublePass/1
Dribble
DoublePass/2
...
ChangeWings/1
...
Kick
...
Pass
...
...
...
Run
...
...
Reposition
...
...
Intercept
...
...
...
...
...
...
...
Attack
...
OffsideTrap
...
...
...
“Doubled One-Pass-Architecture”
– Deliberator-Pass (“goal-oriented”)
builds Intention Subtree
one deliberator pass may work over several cycles
– Executor-Pass
(“stimulus-response”)
traverses and adjusts Activity Path
limited search space by Intention subtree
one executor pass per cycle
• Differences to “classical” programming
– Control flow by deliberation (“agent oriented”)
– Double Pass Runtime Organization (not by stacks)
Deliberator: Constructs Intention Subtree
PlaySoccer
Offensive
Score
Defensive
...
DoublePass/2
DoublePass/1
Dribble
ChangeWings/1
...
Kick
...
Pass
...
Run
...
...
...
...
Reposition
...
...
Intercept
...
...
...
...
...
...
...
Attack
...
OffsideTrap
...
...
...
Construction may need longer time
Executor-Pass through all levels
PlaySoccer
Offensive
Score
Defensive
DoublePass/1
Dribble
DoublePass/2
...
ChangeWings/1
...
Kick
...
Pass
...
...
...
Run
...
...
Reposition
...
...
...
...
...
...
Attack
...
OffsideTrap
...
...
...
...
Intercept
in each cycle through all levels
...
...
Executor-Pass through all levels
PlaySoccer
Offensive
Score
Defensive
DoublePass/1
Dribble
DoublePass/2
...
ChangeWings/1
...
Kick
...
Pass
...
...
...
Run
...
...
Reposition
...
...
...
...
...
...
Attack
...
OffsideTrap
...
...
...
...
Intercept
in each cycle through all levels
...
...
Executor-Pass through all levels
PlaySoccer
Offensive
Score
Defensive
DoublePass/1
Dribble
DoublePass/2
...
ChangeWings/1
...
Kick
...
Pass
...
...
...
Run
...
...
Reposition
...
...
...
...
...
...
Attack
...
OffsideTrap
...
...
...
...
Intercept
in each cycle through all levels
...
...
Executor-Pass through all levels
PlaySoccer
Offensive
Score
Defensive
DoublePass/1
Dribble
DoublePass/2
...
ChangeWings/1
...
Kick
...
Pass
...
...
...
Run
...
...
Reposition
...
...
...
...
...
...
Attack
...
OffsideTrap
...
...
...
...
Intercept
in each cycle through all levels
...
...
Executor-Pass through all levels
PlaySoccer
Offensive
Score
Defensive
DoublePass/1
Dribble
DoublePass/2
...
ChangeWings/1
...
Kick
...
Pass
...
...
...
Run
...
...
Reposition
...
...
...
...
...
...
Attack
...
OffsideTrap
...
...
...
...
Intercept
in each cycle through all levels
...
...
Double Pass Architecture
Option Hierarchy
PlaySoccer
Offensive
Score
Defensive
DoublePass/1
Dribble
DoublePass/2 ... ChangeWings/1
...
Kick
• Predefined Option Hierarchy
• Deliberator
...
Pass
...
...
...
...
...
...
...
...
Run
...
Reposition
...
...
Attack
...
OffsideTrap
...
...
...
...
Intercept
...
H.D.Burkhard, HU Berlin
MOCA 2002
...
Software Architectures
for Agents and Mobile Robots
– long term deliberation (not time critical)
– commitment for intentions: intention subtree
• Executor
– short term reconsideration (time critical)
– performs intentions on the activity path
Both working top-down from root to leaves
58
Synchronization (parallel work)
Sensors
Perception
Deliberation
Plan
Deliberator
Sensors
Perception
Activity path
Actions
Executor
Synchronization (sequential work)
Sensors
Perception
Deliberation
Plan
Deliberator
Sensors
Perception
Activity path
Actions
Executor
Double Pass Architecture: Objectives
• Balance between low level/high level
- Time Trade-off
• Balanced Re-deliberation
- Stability Trade-Off
• Re-consideration on all levels
- Context Problem
- Least Commitment Problem
Long Term Research Goal:
Learning of complex behavior (Case Based Reasoning)
In Progress
• Double Pass Architecture
– Formal specification
– Implementation
• Skills & Behaviors
THANK YOU !