Literature
Survey
on
Existing Robotic Control Architectures |
- Schemas: A Formal Model of
Computation for Sensory-Based Robotics. Damian Lyons,
Michael
Arbib, IEEE Transactions on Robotics and Automation, Vol. 5, No. 3,
pages 280-293, June 1989.
- Subsumption: A Robust Layered Control System
for
a Mobile Robot. Brooks, R.
A. IEEE Journal of Robotics and Automation, Vol. 2, No. 1, March 1986,
pp.
14–23
- Potential
Fields: Real-Time
Obstacle Avoidance for Manipulators and
Mobile Robots. Oussama
Khatib. The
International Journal of Robotics Research, Vol. 5, No. 1, Spring 1986.
- DD&P: Concurrency in
the DD&P Robot Control Architecture. Hertzberg,
Joachim ; Schönherr, Frank. In:
Proceedings of The International NAISO Congress on Information Science
Innovations, 2001. - S. 1079-1085.
- 3-Tiered: Experiences with an architecture
for intelligent, reactive agents. Bonasso,
R. P., Firby, R. J., Gat, E., Kortenkamp, D., Miller, D., & Slack,
M. (1997). Journal of Experimental and
Theoretical Artificial Intelligence, 9 (1-2), p237-256.
- AuRA: AuRA: Principles and practice in
review. R. C. Arkin
and
T. Balch. Journal of Experimental and Theoretical AI, 2-3:175--189,
Apr--Sep 1997.
- Saphira: The
Saphira Architecture: A Design for Autonomy. Konolige, K., Myers, K., Ruspini,
E., and Saffiotti, A. (1997). Journal
of Experimental and Theoretical Artificial Intelligence, Vol. 9.
pp.215--235.
- DAMN: DAMN: A
Distributed Architecture for Mobile Navigation. J.
Rosenblatt.
doctoral dissertation, tech. report CMU-RI-TR-97-01, Robotics
Institute, Carnegie Mellon University, January, 1997.
- RHINO: The mobile robot RHINO. J. Buhmann, W. Burgard, A.B.
Cremers, D. Fox, T. Hofmann, F. Schneider, J. Strikos, and S. Thrun.
AI Magazine, 16(2):31–38, Summer 1995.
- SOMASS: The SOMASS
System: a Hybrid Symbolic and Behaviour-based System to Plan and
Execute Assemblies by Robot. C.A.
Malcolm. Proc. of AISB conf.
Sheffield, April 1995
- CIRCA: World modeling
for the dynamic construction of real-time control plans.
Musliner,
D. J., Durfee, E. and Shin, K. Artificial
Intelligence, 74. 1995.
- Animate
Agent: Task Networks
for Controlling Continuous Processes. R. James Firby.
Proceedings of the Second International Conference on AI Planning
Systems, Chicago IL, June 1994.
- TCA: Structured
control for autonomous robots. Reid
G. Simmons. IEEE Transactions on
Robotics and Automation, 10(1):34-43, February 1994.
- ATLANTIS: Integrating
planning and reacting in a heterogeneous asynchronous architecture for
controlling real-world mobile robots. Gat,
E. (1992). In Proceedings of the
Tenth National Conference on Artificial Intelligence (AAAI-92). pp.
809-815.
- SSS: SSS: A Hybrid Architecture Applied
to Robot Navigation. J.H. Connell, Proc. IEEE Int'l Conf.
Robotics and Automation, IEEE Comp. Soc. Press, Los Alamitos, Calif.,
1992, pp. 2,719- 2,724.
- SFX: SFX: An Architecture for
Action-Oriented Sensor Fusion. Murphy,
R.R., and Arkin, R.C., 1992.
Proc. 1992 Int. Conf. on Intelligent Robotics and Systems (IROS),
Raleigh, N.C., July 1992
- IPDI: A computer architecture for
intelligent machines. D.
R. Lefebvre and G. N. Saridis. In Proceedings 1992 IEEE International
Conference on Robotics and Automation, pages 2745--2750, Nice, France,
May 1992
- ICARUS: An architecture
for persistent reactive behavior. Choi,
D., Kaufman, M., Langley, P., Nejati, N., & Shapiro, D. (2004).
Proceedings
of the Third International Joint Conference on Autonomous Agents and
Multi Agent Systems (pp. 988-995). New York: ACM Press.
- RCS: RCS: A Cognitive Architecture for
Intelligent Multi-Agent Systems. Albus, J.S., Barbera, A.J.
Proceedings of the 5th IFAC/EURON Symposium on Intelligent Autonomous
Vehicles, IAV 2004, Lisbon, Portugal, July 5 - 7, 2004.
- Soar: Soar
: an architecture for general intelligence. Laird,
J. E., Newell, A. and Rosenbloom, P. S. (1987) Artificial
Intelligence, 33.
- Software Architectures for
Hardware Agents. Henry
Hexmoor, David Kortenkamp, and Ian Horswill. Journal
of Experimental and Theoretical Artificial Intelligence (JETAI) 9
(1997) 147-156.
- On three-layer
architectures. Erann
Gat. In:
Artificial Intelligence and Mobile Robots: Case Studies of Successful
Robot Systems,D.Kortenkamp, R. Bonasso and R. Murphy(Editors), MIT
Press, 1998, pp. 195-210.
- Robot Plan Execution:
Logical
sensor/actuator:
knowledge-based robotic plan execution. John
Budenske, Maria L. Gini. JETAI
9(2-3): 361-374 (1997)
- ESL: ESL: A Language for Supporting
Robust Plan Execution in Embedded Autonomous Agents. Ron Garret.
Proceedings of the IEEE Aerospace Conference, 1997.
- The challenges
of real-time AI. Musliner,
D. J., Hendler, J. A., Agrawala, A. K., Durfee, E. H., Strosnider, J.
K. and Paul, C. J. (1995), IEEE
Computer, 28.
- Reactive Planning: Planning as Incremental Adaptation
of a Reactive System. Lyons,
D.M. and Hendriks, A. Journal
of Robotics & Autonomous Systems 14, 1995, pp.255-288.
- Reactive Planning: Reactive
Planning. Lyons,
D.M. and Hendriks, A.
Encyclopedia of Artificial Intelligence, 2nd Edition, Wiley & Sons,
December, 1991.
- RAPs: Adaptive Execution in Complex
Dynamic Worlds. James Firby. Ph.D. Thesis, Yale University
Technical Report, YALEU/CSD/RR #672, January 1989.
|
| REACTIVE ARCHITECTURES |
A Formal Model of
Computation for Sensory-Based Robotics.
Damian Lyons, Michael
Arbib
- The aim is the construction of a special-purpose robot
programming language, in robot domain,
which implies a special computational
model, Robot Schemas (RS). Instead of general
purpose PL's with modified versions, authors formalized the key
computational characteristics of robot programming into a single mathematical model, not only
a specific programming language. The advantages of such an approach is:
- the potential of direct task-level specification
- efficient run-time behavior
- formal level at which robot behavior can be specified and
analyzed.
- Basic characteristics of a robot programming are:
- Robot programs interact
with the world.
- must contain some facility for world model
- The central paradigm is that sensory input is linked with
knowledge to produce appropriate behavior (sensori-motor computation).
- Robot programs should have flexible (dynamically
reconfigurable), hierarchical
sensorimotor structure.
- Robot programs are defined recursively using a schema or class structure.
- Robot programs are inherently distributed. ie. parallel execution
of actuator groups.
- Literature on
general schema discussions.
- Schema is
a generic specification of computing agents in RS. Computation is performed by the
interaction
of a number of concurrent
computing agents. A computing agent is created by instanstiating a schema, Schema Instance (SI). Each SI is
instansiated with initial parameters and input and output ports, which are communication
objects with other SI's. Associated with each schema, a behavioral description defines how
an instance will behave in response to communications. My own note: This is similar to
'situation-driven execution' RAPs
model. But only parameters are selected according to communication in
this model.
- An RS program is
a network of SI's, some of which collect sensory data, and some of
which control robot motion, and some other locate in middle (process
sensory data). Some agents are the only sensory input and motor output
channels allowed. For example one agent reads sensor values, and output
that value from one port, and other subsequent agent takes that value,
process it, and output a value, and another agent take that output and
transfer it to motor actuators.
- Assemblage mechanism,
and assemblage SI's enable contruction of complex programs, and used as
basic SI's, with their input/output ports. Port equivalance map
defines porting relation between assemblage and its components.
- Task-specific object models
consist of teams of SI's which cooperate to generate an analysis for
the object state, and used in high level robot programming, because
high-level robot programming deals with objects rather that parts or
manipulators.
- A Task plan is a
set of instructions for a goal, and described as a relationship between
task-specific object model and a set of actions. It is represented in a
structured assemblage: a set of sensory SI's (task-spesific object
model), a set of motor SI's, and a set of task SI's.
- Different precondition,
sequential, selection, resource precondition schemas,
and and schemas which are concurrent and in groups are employed.
- A detailed formal
mathematical model, for verification and concise specification
of task plans is described. I will skip the formal model.
- At the end of paper, a case study on centered grasping task with
n fingers is given, there are two major task networks : grip and
compensate, and they use primitive schemas like close ith finger etc.
- In summary, RS is
a nested network of concurrent schemas, which are
connected in a flexible manner.
|
A Robust Layered
Control System
for
a Mobile Robot.
Brooks, R.
A.
- It is a radical break of from traditional approaches. The subsumption architecture is
described, which is based on:
- incremental
construction, which implies layers of control system with increasing level of competence.
- instead of horizantal functional decomposition, vertical behavioral decomposition
- No central
control, low bandwidth communicating parallel computation units.
- Advantages of vertical decomposition: robustness,
buildability, and testability.
- A number of requirements of autonomous mobile robots are
defined:
- Dealing with conflicting multiple goals.
Subsumption: no early decision, individual levels can be working on
individual goals, concurrently.
- Dealing with noisy and incosistent multiple sensors. There is
an interesting example from biological multiple sensor usage. In pigeons have four independent
orientations sensing systems, but interestingly, sensors are not seemed
to be combined, but depending on environment conditions, the data from
one sensor tends to dominate.
Subsumption: Independent and concurrent sensor processing.
- Robustness.
Subsumption: When higher layer cannot produce output in a timely
fashion, the lower layers still produce sensible results.
- Extensibility.
Subsumption: Each layer run on its own processor.
- Mobile robot is designed based on 9 dogmatic principles:
- Complex behavior
need not necessarily be a product of an extremely complex control
system. It may be reflection of a complex environment, and complexity
may be in the eyes of the observer. My own note: similar to braitenberg.
- Things should be simple. (Should not be in a position
dealing with ill-posed problems.)
- Cheap robots that are in human-inhabited space without
human intervention. Additionally, should do useful work.
- Modelling should be in three-dimensional.
- Instead of absolute coordinate systems, relational maps are more useful.
- No artificial environment.
- Sonar data used in low-level interactions, but visual
data is much better in intelligent interactions.
- For robustness, self-calibration.
- Robots must be self-sustaining.
- Following are levels of
competence, where higher level implies more specific desired
class of behaviors: avoid contact with objects, wander aimlessly,
explore the world, build map and plan routes, notice 'static' changes,
... Only first 3 competence levels are described in paper in detail.
- Layers are debugged
thoroughly and never changed. No handshaking or acknowledgement
messages, each processor run asynchronously.
- Each module is a Finite
State Machine, who has input and output lines, which affect
change in states. There is a starting state, and reset signal for each module.
- Outputs may be inhibited,
the message sent in that line is lost for a certain period. Inputs may
be supressed, the message sent
in that line is overwritten by supressing higher layer module, for a
certain period.
- The 3 levels of competence are described in detail, and the
method is applied in simulated and real robots.
|
| HYBRID ARCHITECTURES |
|
Concurrency in
the DD&P Robot Control Architecture.
Hertzberg,
Joachim ; Schönherr, Frank.
- Tightly coupled two-layered architecture. DD stands for Dual Dynamics which is a framework
for specifying a set of robot behaviors as a continuous dynamical
system, expressed as ordinary
differential equations. DD&P
stands for planning component which gives directions
to behaviors which locate in different levels, as well as it should
define the way in which a chosen operator from the currently active
plan influences the current working of the DD&P part, and it should
define how information from DD and the sensors goes into the planner's
world model.
- Modern robot control
architectures are hybrid ,
References to books:
- Behavior Based Robotics (Arkin 98')
- Mobile Robot Architectures (Bonasso 98')
- Dual Dynamics:
- Behaviors are leveled and interact through shared
variables.
- Every individual behavior is regulated by its activation dynamics, which
describes its degree of activation, is calculated by some sensor
values, some other behaviors and the influence from planning (in ++ or
-- way).
- Only behaviors at the bottom level are allowed to
directly influence actuators by output of their target dynamics.
- For every control variable of some actuator, the product term combines target and activation dynamics for all
level-0 behaviors.
- Activation of a motor
is done by summation of the control variables, where product term is
used as gain.
- Direct influence from higher level is restricted to next
lower level, behaviors are regulated by input from peers and
next-higher level.
- hysteresis effect: prevents
behaviors from oscillaion which can arise ie. from fluctuating sensor
values.
- DD&P:
- Plan modules can affect any behavior in any level.
- Even highest behaviors should obey the structure of activation, target dynamics. But there
is no restriction for planning
- off-the-shelf
propositional planner is used here: IPP. Given a set of mission goals by
human user, the planner is supposed to generate and keep updated an
ordered set of abstract
actions as the current plan and to determine at each of its time
cycles the operator of that plan that
proposes to execute, given its current knowledge about the environment
(in the KB - Knowledge Base)
- Executing an operator
means biasing behaviors
rather than exerting hard control. An operator chosen for execution stimulates (++) or mutes (--).
- Information flow from the DD part to the deliberative
part in form of the activation history
of the behaviors, yielding an image of the environment as perceived
through the eyes of the useful behavior.
- The Flip-Tick Architecture
(FTA) is a framework
of organizing principles and generic functions that are available as a
software platform for implementing autonomous intelligent control
systems for applications in robotics and automation, and FTA is
employed in this studies.
- The main components that DD&P
adds to DD
are: (working concurrently)
- a standard propositional planner,
- a component which is needed to update permanently the
propositional world including the goals (KB)
- a component which monitors
the state of executing the current plan. (current plan)
- Planner: Whenever
idle, the planner picks the current world state plus a current goal
amond those with highest priority from KB,
and works on that problem until a plan is finished. When it finishes,
it is published on the plan tagboard.
Planner is unaware
of the changes on the KB tagboard.
- Monitor: Whenever
idle, the monitor copies the current plan from the plan tagboard, and starts to work
on executing it. Monitor determines the operator whose preconditions
hold but postconditions do not hold, and it publishes that operator on the current-operator tagboard, thus
corresponding behavior's activation
dynamics is ++ or --, operator executed as long as its
postconditions satisfied.
- How to detect robot is stuck? 1- global time-out values,
2- re-execution of the same operator
- KB: A basic world
model consisting of unchangable facts by the domain modeller. At each
cycle, the KB reas first current sensor tagboards, the current value of
fluents, and the
current activation histories of all behaviors. Consistency is looked
for, new state description is then published on the KB tagboard.
|
Experiences with an architecture
for intelligent, reactive agents.
Bonasso,
R. P., Firby, R. J., Gat, E., Kortenkamp, D., Miller, D., & Slack,
M.
- 3T is a three-layered (tiered) architecture,
with skills, sequencing and planning layers.
- Planner constructs
partially ordered plans, listing tasks for the robot to perform
according to some goals. It can reason in depth about goals, resources,
and timing constraints by using a system, Adversarial Planner (AP). It is the
Planner's job to select a RAP to execute the corresponding task.
- Sequencing tier
includes RAPs, each of the
tasks that are constructed by Planner, corresponds to one or more sets
of sequenced actions or RAPs. The job of the Sequencing tier is to
decompose selected RAP into other RAPs, and when it is indivisible,
corresponding set of skills are activated in Skills tier. Additionally,
a set of event monitors are
activated in skills tier to notify sequencing layer of the occurance of
certain conditions.
- Skills (Reactive) tier
includes dynamically reprogrammable set of reactive skills coordinated
by a skill manager. Sequencing
tier will terminate or replace actions, according to enabled event
monitor or timeouts.
- Skills for the
robot-specific interface with the world, handling the real-time
transformation of desired state into continuous control of motors and
interpretation of sensors. Skill development should be
robot-independent because physical properties of robots change and all
interface between Skills and Sequencing tier should remain same. Skills
should be capable of being enabled and disabled in any combination from
sequencing tier. To provide this, skill
manager is employed.
- Sequencer is the
RAPs interpreter, where RAP is
simply a description of how to accomplish a task in the world under a
variety of conditions using discrete steps. Some statements may
cause RAP interpreter to block a branch (while expanding) of the task
execution until a reply is received from skills manager. Replies are
produced by special skills, called events
(event
monitors).
- Planner should
operate at the highest level of abstraction possible so as to make its
problem space as small as possible. Thus it should not have to deal
with tasks that can be routinely specified as sequences of common
robotic skills.
- Applications of 3T: A mobile robot that recognizes people,
and a trash-collecting robot without
any planner, but recovery mechanisms in RAP and memory in
RAP enabels robot not to stuck or shock in any situation. A mobile
robot that navigates office buildings where planner is used for ie.
finding a path to elevator, or replan its own path if a doorway is
blocked and reevaluated plan if no deadlines are violated.
- The dimensions for
which tasks are divided are time,
bandwidth, task requirements, and modifiability.
- Literature work and comparisons with other
architectures:
- 2 broad categories
- designed for physically embedded agents, like TCA,
subsumption, AURA, 3T
- designed for general intelligence and later adapted to
real-robots, like SOAR.
- Discuss subsumption
architecture, where decomposition is based on tasks rather than
functionality, where deveopment is done on behaviors rather than
general functional modules. Most architectures decompose problem into
functional modules, such as planning, sensor processing, execution
monitoring etc. Thus subsumption architecture is homogeneous, where
there is no architectural support for abstraction, planning or resource
management.
- In SSS by
Connell, subsumption makes up the middle layer. It is not at the bottom
layer, so repons to contingencies is limitted by subsumption's finite
state machine model, and handled by contingency
table, which makes design cunbersome. SSS is demonstrated only
in navigation tasks.
- In TCA by
Simmons, there are no essential tiers, a task net is constructed for
the robot which is similar to task-net in RAPs (decomposable). There is
a central message
processing unit, no explicit representations for expressing
relationships among tasks. Additionally, since TCA lacks representation
for task trees, it is cumbersome to employ a generic planner. Cognizant
failure is dealt in one level, where in 3T, it is dealt with in all
layers, environmental variations, variations in routine activities, and
variation in time and resources of planner.
- AURA by Arkin,
is specific to mobile robot navigation, and superficially similar to
3T. Motor schemas are combined for vector addition, and a second tier
enables combination of these vector fields to run concurrently for
desired effects but it lacks many of the context unlike RAPs.
- NARSEM by Albus
et al., is a multi-tiered structure where abstraction layers
corresponds tiers. There is no global world model, but except that can
provide all data and control paths that are presented in 3T.
- In IPDI by
Saridis, the emphasis is increasing precision with decreasing
intelligence. But intelligence does not stem from hierarchical
structure, but 1- probability models of task decomposition and
execution, and 2- function that minimize a measure of entropy at each
layer. Additionally, there is neurol network planner?
- Literature on
non-robotic agent architectures: Guardian,
Soar, Cypress, CIRCA.
|
AuRA: Principles
and practice in review.
R. C. Arkin and T. Balch.
- AuRA was developed in mid-80's as a hybrid approach to
robot navigation, but as can be seen, not limitted to navigation in
later applications. It is a two-layered architecture with hierarchical and reactive components.
- Hierarchical component
includes:
- Mission Planner:
Highest level, where to date, it has acted primarily as an interface to
human commander
- Spacial Reasoner:
uses cartographic knowledge to construct a sequence of path legs, for
example using A* search.
- Plan Sequencer:
refered as Pilot in earlier
work, translates each path leg generated by the Spatial Reasoner into a
set of motor behaviors for execution. My own note: it seems similar to
Sequencing layers of three layered architectures. The collection of
schemas then sent to robot for execution.
- In reactive component,
schema manager is
responsible for controlling and monitoring behavioral process at
run-time. Action-oriented perception.
Initiated collection of schemas, each produce a response vector in a
manner analogous to the potential
fields method, where schemas operate asynchronously. A homeostatic control system is
integrated additionally. Once reactive execution begins, the
deliberative component is not reactivated unless a failure is detected
(ie. lack of progress [evidenced by zero velocity of time-out])
- The strengths of AuRA:
- It is highly modular
by design. Components of the architecture can be replaced with others
in a straightforward manner. A number real examples are given (in
planner or lower levels).
- It is flexible,
it provides means for adaptation and learning methods.
- It is generalizable
to a wide range of problems. (navigation, vacuuming, mobile
manupilation)
- Use of hybridization.
- Biological connections:
- schema theory
- potential fields methods
(toad navigation, frog limb control)
- justification of hybridization, Normal & Shallice and
Neisser from psyhology.
- Action-oriented
perception, affordances
of Gibson.
- References to other robot architectures: Atlantis, SSS, Planner-Reactor, RPS.
- Some primitive motor schemas are presented, and a low-level
behavior to avoid from local minimas (of problem of potential fields)
is given. Primitive behaviors are combined in meaningful ways to form assemblages of behaviors. Outputs of
these behaviors are encoded in vector form, and by means of gains, they are summed to one output
vector. There is no layering of behaviors and consists
of dynamic collection of schemas instantiated for the current context.
- Most implementations are focused on lower levels of AuRA.
Several robot have demonstrated additional higher level reasoning.
Examples of large number of robots that AuRA is implemented is given,
where recovery from failures in low and high levels is accomplished.
- A case study is given, trash-collecting
robots for 1994 AAAI competition. My own note: In this part,
the distinction between behavior
assemblages and schema
assemblages is more clear. Schemas are not detailed, and
behavioral assemblages are defined as concurrent running group of
schemas. There is no task plan
either, as desribed in Lyons&Arbib paper.
- In this case study, task plan is encoded by humans as Finite State Acceptors, which
includes behavioral assemblages and perceptual triggers. Reasoning is
not included.
- The Plan Sequencer
will terminate any assemblage and instentiate a new one when a signal
has acquired. Links between schemas permit use of generic schemas (ie.
color is input to move-to-goal schema).
FSA runs in Plan Sequencer module.
- Three robots cooperating to collect trashes is described
later.
|
The
Saphira Architecture: A Design for Autonomy.
Konolige, K., Myers, K., Ruspini,
E., and Saffiotti, A.
- Saphira
architecture is a hybrid architecture which has no well-defined
hierarchy or complexity layers, and is focused on mainly three
features:
- coherence deals
with construction and maintainance of internal representations of the
outwide world,
- coordination of
behaviors or determination of output of actions are accomplished using fuzzy logic and context dependent blending.
- coordination with
other agents using natural language or gestures.
- Flakey of SRI is
used as real robot and the task is Flakey is introduced to the office
environment as a new employee, and then asked to perform delivery
tasks. It may have a priori map and it should follow a human who
introduces the office. It can additionally take advices on map-making
or potential hazards. Some delivery task will be accomplished by
planning the route and recovering errors when needed.
- Coordination: It
says that a layered abstraction approach makes complexity manageable
but I think there are no contraints defined in the architecture to
accomplish this.
- Coherence: As
complexity increases, agents must have a conception of their
environment, in contrast to Connell,
who says environment is the
model, or others say world
is its own representation.
- Communication: A
mobile agent will be of greater use if it interact effectively with
other agents, understand task commands. Not a big step for this scheme.
- Saphira architecture
is an integrated sensing and control system, which includes Local Perception Space (LPS) at its
center which contains different levels of representation (from
occupancy grids, to geometric representation and to high level
artifacts of the world). Internal artifacts (like it is a chair, doorway etc.) are
viewed as beliefs of robot
about the environment. Perception and
action modules in
levels of complexity, all interact with LPS. As another central module,
Procedural Reasoning System
(PRS) is used in more
complex behaviors and in interaction with modules like speech input, schema library, topological
planner.
- At control level Saphira is behavior based, behaviors are
written and combined using techniques based on fuzzy logic. These rules produce desirability function for each
behavior, the fuzzy connectives are used to combine different behaviors
based on their contexts (context depending blending), and defuzzification is used to choose
preferred control among selected behaviors, generally taking average.
- Basic behaviors take their inputs from the LPS and use
information like occupancy data. More complex behaviors like goal-seeking behaviors (which are
again basic behaviors), take input from artifacts. For example, the
behavior cross-door uses the
coordinates of a door artifact in the LPS as an input.
- Basic behaviors are combined to form complex behaviors, where outputs of
desirability functions for behaviors are combined (for example through
a minimum operation as defined by context dependent blending and
defuzzification). In such a way for example if there is an onbstacle
ahead, and there are two choices, turn
left or right, the
selection is done according to the overall goal position.
- This coordination mechanism is very similar to potential fields method, but two
main advantages over it:
- In context-depending blending, first behavioral
preferences combined and then one summary control is chosen, but in potential fields, first preference
summaries are combined and combined force is the combination of
summaties. Potential fields is not mathematically formal, thus ad hoc.
- Complex conditions can often described more easily in a
logical form, and this makes integration of with symbolic planner
easier.
- PRS-Lite:
Management process involves determining when to activate/deactivate
behaviors as part of execution of a task, as well as coordinating them
with other activities in the system. It provides the smooth integration
of goal-driven and event-driven activity, while remaining responsive to
unexpected changes in the world. The representational basis of PRS-Lite
is the activity schema, a
parameterized finite-state-machine whose arcs are labelled with goals
to be achieved. Each schema embodies procedural knowledge of how to
attain some objective via sequence of subgoals, perceptual checks,
primitive actions, and behaviors.
- When schemas instantiated -> they will be intentions. The details are inside,
they can invoke other instentians, block behaviors etc. For example, there is a plan-and-execute schema that first
invokes a topological path planner to generate a plan, then launches
both an intention to execute the plan and a monitoring intention that
oversees the execution to determine when problems have arisen.
- Coherence: Reactive
behaviors take their inputs directly from sensor readings and more
goal-directed behaviors such as wall-following can often benefit from
using artifacts (corridor artifact).
This is especially true when sensors give only sporadic and uncertain
information.
- Feature extraction and anchoring
is described in detail. Anchoring is a process where current
artifacts are kept coherent with the environment by matching against
features or object hypothesis. For example, when artifact not found but
some features are matched (like corner of a doorway), it may be assumed
that artifact is found. For example, artifact say something about the
orientation of the corridor is false in LPS, it can be adjusted by
sonar readings.
- Anchoring thus helps to correct uncertain prior
information by using perception, and keep the robot localized on a map
as it navigates. However, when environment is complex, features are
complex, and robot may be confused.
TOP
|
DAMN: A
Distributed Architecture for Mobile Navigation.
J. Rosenblatt.
- DAMN dates back to 1986 (not in paper).
- Earliest wok in robot architectures, Shakey, pure logic
reasoning
- In hierarchical
architectures, since expectations are difficult to meet, monitoring shuold become an
important part, with environment dynamics this introduces additional
complexity. Therefore, higher level modules should be designed such
that they should not assume their commands will be strictly followed.
- Rather than top-down hybrid approaches, DAMN modules
concurrently run, send votes to be combined.
- In the architecture, there is a DAMN ARBITER control module, where
various behaviors in various working speeds such as avoid obstacle (in
10 Hz.) and path plan (0.1 Hz.) give votes. Then DAMN ARBITER commands
low level control. Each behavior, who is responsible from particular
aspect of the vehicle control, is assigned a weight, and this weight is
varied by Mode Manager module.
- In Brooks words, "the world is its own best model",
agent cannot benefit from different scenes, and whole world is not in
the immediate sensing of the robot.
- For deliberative and reflexive modules, behaviors run in
different rates. Thus deliberation is achieved by:
- Different rate behaviors, without any hieararchy
- Modifying voting weights of the behaviors by Mode Manager.
- Hierarchical control architectures should perform sensor fusion in order to construct
global world models. Bottleneck:
- all sensor data should be accumulated and integrated
before each use.
- single monotlithic world model is difficult to develop
from very different sources.
- Conversely, in behavior based, no need to fuse because each
behavior use sensory data which is relevant to it.
- He put and suggest command
fusion instead of sensor
fusion: "By appropriately
fusing behavior commands through arbitration, a robot control system
can respond to its environment without suffering problems inherent in
sensor fusion. Instead of performing sensor fusion, the system must
combine command inputs to determine an appropriate course of action".
- All behavior based architectures use winner-take-all
strategy, ie. subsumption architecture. But Rosenblatt says there is a huge
information loss since the outputs of supressed behaviors are simply
ignored. Arkin's Motor Schemas use potential fields, but there
is local optima problem, and "arbitration
via vector addition can result a command which is not satisfactory" states
Rosenblatt.
- DAMN arbitation does
not average, but it applies the command which gets the most votes from various behaviors.
- For example turn arbiter
is a DAMN arbiter. Each behavior, for each command option, generates a
vote between [-1, 1]. Normalized and weighted sum of these votes is
taken, and interpolated to resulting command.
- Arbiter periodically sums
all the latest votes of asynchronous, parallel behavior commands.
- Particular turn commands:
Harf Left, Soft Left, Straight etc. For each turn command, there is a fused vote. Max vote is tunned.
- Behaviors:
- Safety behaviors: obstacle
avoidance, vehicle dynamics,
limit turn, limit speed
- Road Following: A neural
net, ALVINN is used where each output node corresponds to evaluation of
a particular turn command.
- Goal Directed:
Subgoals: a number of points are defined by user or planner. Desired turn
radius is transformed into a
seried of votes by applying Gaussian.
- Voting strengths are specified by user. Top-down planning,
Mode Manager is used in Hughes Research Lab, and CMU annotated maps.
- In order not to lose trace of goal, while avoiding
obstacle, a speed arbiter might
be used to slow down.
- My
comments:
- YES, there exists high level behaviors, and by the help
of behavior rates, they work. However I think an architecture should
impose some constraints in all levels.
- This architecture is very specializedto navigation, I
have no idea, how can it be applied to non-navigational tasks.
- The usage of Mode Manager might be very difficult, since
lots of weights, and learning these weights is very difficult in
Rosenblatt's own words.
|
Structured
control for autonomous robots.
Reid
G. Simmons.
- Task Control Architecture
(TCA) is a "hybrid" architecture, which is composed of
robot-specific modules which
communicate through a general purpose central
control module which is common in all systems. This central
control module includes a task tree, where task sequences and
concurrency is planned, and
modules are activated/deactivated according to various constraints. TCA has a major emphasis on
contraints on coordination of control
of planning, perception, action, and monitoring processes.
- Another emphasis is on the incremental construction of the
system, where TCA is viewed
as a high level operating
system, that provides an integrated set of commonly needed mechanisms
to support distributed communication, task decomposition, resource
management, execution monitoring, and error recovery.
- The control of interaction
between modules are critically constrained in TCA because as complexity
increases, interaction between behaviors emerge in unpredictable
results (Also a critique to behavior
based approach). The term task
control stands for the problem of coordination of perception,
planning, and execution. Reactivity means
that the system detects and makes appropriate responses to changes in
its environment fast enough.
- Deliberative approach is the
top-down decomposition of tasks into sub-tasks, specifying current and
future activities and constraints. A limitation on deliberative approach is that
strict top-down constraints may prevent the system from being
responsive to changes in the environment.
- The design of the TCA is similar to deliberative method,
first basic deliberative components that handle nominal situations are
designed and then system reliability is increased by incrementally
layering on reactive behaviors to handle exceptions. (Relaxing
contraints).
- Most of the TCA control constructs can be incrementally
added in existing system. ie. exception handlers and monitors without
change, and new task modules with little change.
- TCA provides an engineering basis because of 1- system
understandability 2- system managebility and 3- incremental process in
construction.
- Literature on
deliberative and reactive systems, and compare them with TCA:
- Systems of Albus and
Meyster
- NARSEM is a
strict hierarchical framework for task decomposition, perception, and
world modelling. The hierarchy is based on temporal abstraction
(level-slowness). In contrast with TCA,
task decomposition is based on the functionality and degree of
interaction between them subtasks, based on task-complexity.
- BB1 blackboard
architecture is compared with TCA.
- Reactive architectures, subsumption
based and other behavior base approaches.
- RAPs is similar
to TCA in concept. While RAPs is more concerned with reactive behaviors
and real-time response, TCA is more concerned with structuring interactions to handle
complex tasks. My own note: It seems to hard and complex of this
structuring process.
- Different types of messages are sent and received between
modules and central control, and details are given in the article. For
a six-legged walking system, robot-specific modules are Real-time Controller, Gait Planner,
Footfall Planner, Leg Recovery Planner, Error Recovery Module, User
Interface, Local Terrain Mapper, Scanner. The central control includes Message Routin Table, Resource Schedules
and Task Trees. The execution of TCA is explained in the
six-legged walking example. To summarize:
- There seems no hierarchy among modules. Only hierarchy
seems to exist in Task Trees.
- All information transfer among modules are in the form of
messages.
- The modules receive messages according to other modules'
messages and Task Tree
contents.
- From Graphical User
Interface series of waypoints are given.
- Deliberation is
accomplished inside central control via:
- task-tree (which contains tasks as nodes, and sub-tasks
as children of nodes)
- There are constraints on the links between nodes.
- Two nodes linked in temporal contraint
should be executed sequentially, but could be planned concurrently.
- Two nodes linked in delay-planning
contraint should be planned and executed sequentially.
- Several time intervals are used in running constraints.
- Another deliberative method is resource
allocation, that is controlled by limiting or locking TCA
resources (a set of message
handling procedures).
- Reactivity is
accomplished by the help of several contructs that monitor changes in the environment.
- A TCA monitor
is a message that performs some action when a specified condition is
triggered. A point monitor tests
if some condition holds or not, and useful for determining whether
tasks have been executed according to plan. For example if robot is
trying to hold a can, and monitor finds out that it is unsuccessful, it
may give a message to replan the robot. Polling and Interrupt-driven monitors are used
to detect unexpected changes and operate concurrently with planned
actions.
- Reactive
behaviors are applicable should be constrained to minimize both
unexpected interactions and the load on perception. My own note:
should be action-oriented.
- Monitors and message handlers detect exceptions
in TCA. If an exception occurs, message handlers signal by raising the
exception. Exception messages are handled, in the task tree. If one
level cannot handle the exception, higher level task try to deal with
it, for example by changing the plan being executed. Task tree
modification include resending
messages, terminating tasks, inserting new nodes and adding additional [temporal] constraints.
- The six-legged Ambler system
was successfully run over 700 steps (300 m), by recovering the
exceptional situations which arise 18% of steps.
- The general advise for design of TCA is:
- Initially overconstrain the system
- Then slowly relax
- temporal
- delay-planning constraints
- Thus increase speed.
|
Integrating
planning and reacting in a heterogeneous asynchronous architecture for
controlling real-world mobile robots.
Erann Gat
- ATLANTIS is an heterogenous and asynchronous control architecture,
which takes its roots from RAPs
system. It is a three layered architecture where controller is a reactive mechanism
which controls primitive activities,
sequencer is a
special purpose operating system which control initiation and
termination and parametrization of primitive activities (and directions
to planner) and deliberator makes time-consuming
computations like planning and world modelling. The difference of ATLANTIS from RAPs is ATLANTIS controls activities
rather than atomic actions? Additionally, in RAPs, control flows
top-down from the symbolic planner which installs tasks in the task
queue.
- Differences between ATLANTIS
and SSS:
- ATLANTIS provides a complete framework for engineering
controller,
- Middle layer is based on RAPs
and subsumption respectively,
- Symbolic layer of SSS is in the control loop, where in
ATLANTIS it provides advice to sequencer. Thus real-time response is
affects in SSS, a mechanism is required for contingencies, contingency table.
- Autonomous robotics
is difficult for:
- time available to decide what to do is limitted,
- many aspects of real world is unpredictable thus planning
a complete course is impossible,
- sensor information is not accurate and complete.
- In the paper, there is no description or reference to RAPs task expansion when required
viewpoint.
- Controller: A
language called ALFA is used
which is similar to the spirit of REX.
There are modules which are connected as network, but insertion or
deletion of these modules do not require restructuring of
communications network. ALFA provides both dataflow and state-machine
computational models and can be compiled for parallel processors.
- Sequencer: controls
sequences of primitive actions, where similar to RAPs system, tasks are
stored in a queue, sequencer extracts tasks, and according to the
current situation, it activated some methods or sub-tasks. cognizant failure is emphasized
again. While methods are activated, controller modules are initiated or
terminated and parametrized. Activities may be interrupted, thus the locking mechanism corresponding to
that activity should be released. Locking mechanism is used to control
concurrent activation of interfering activities, in RAPs no such
problem exists, because in RAPs atomic actions are controlled by
sequencer.
- Deliberator: Traditional
AI planning is employed, all deliberative computations are initiated by
sequencer, and results are placed in a database
(not a queue?) for sequencer. The
output of the planner is used only as advice by the sequencer, it does
not matter at all what the planner's internal representation is. The
only requirement is that the output of the planner contains come
information which the sequencer can effectively use. I think
this means, between sequencer and planner, there is no constrained communication
mechanism. Guide but not control robot's actions directly. Agre and Chapman's plans-as-communications
theory.
- While designing the modules in a bottom-up fashion,
computations of higher levels should be abstracted from environment,
unpredicted aspects of the environment should be dealt with lower
layers.
- In the experiments JPL
Mars Rover is used in outdoor experiments, and a kinematics
simulator is used for richer experiments. First, simulator is tested
and compared with physical robot in a simple task, and proved to be
consistent. Some complex tasks are given to the robot. For example,
task planner may determine the fuel is low, and it advised the
sequencer to go homebase to refuel before collecting rocks.
|
SSS: A Hybrid
Architecture Applied
to Robot Navigation.
J.H. Connell
- In this paper, a three layered architecture is used for
indoor navigation and mapping. SSS is an acronym for servo-subsumption-symbolic which
corresponds each layer. 'It required using a subsumption approach to competently
swerve around obstacles, a symbolic
map system to keep robot on track, and a number of servo controllers to make the robot
move smoothly'.
- From servo to subsumption, space is discretized and from
subsumption to symbolic time is discretized.
- Some setpoints are
given from subsumption to servo layer, and certain situation recognizers provide
discrete situations to subsumption.
- Symbolic layer has the ability to turn each behavior on
or off selectively, parameterize subsumption modules. In return,
subsumption has event detectors, and provides events like 'path blockes' to
symbolic layer, to make new plans. Contingency
table is used to deal with such events in real-time.
- Literature links
on architectures.
- It is emphasized in the paper that the tasks like swerving around obstacles, maintaining a
straight path, and wall-following
is performed easily by subsumption.
- In navigation, instead of depending on solely on odometry
maps, a very coarse map is stored (for solving looping problem).
Because of the nature of the office environments, robots turns are
forced to be times of 90 degrees, and symbolic maps are constructed by
this structured approach. Relevant places, like corners are nodes, and
robot paths are (straight edges). Environment may be varying and
dynamic so only distance and orientations are stored.
- Tactical navigation
is handled by servo (acceleration limits) and subsumption layes
(wall-following, straight and smooth navigation etc). Strategical navigation is handled
by sybolic layer. The landmarks used in the coarse map are the sudden
appearance and disappearance of side walls. Once map created, an
efficient route is calculated, to traverse this route, parameterize the
subsumption modules for first segment.
It does not constantly fiddle with subsumption layer, only in events!
- SSS is compared with other three-layered architectures,
mostly ATLANTIS. It critisize
others for
- Detecting true failures in overall is difficult at low
level. In SSS, external occurances, not internal states of
sub-processes, determine when the behavior-based system is
reconfigured. (My own note: both
systems are based on similar principles about failure detections,
little internal state is employed.)
- In other systems, symbolic system is completely out of
the control loop during actual performance of task. In contrast,
contingency table in SSS only decouples the symbolic system from most
rapid form of decision making - the symbolic system must still
constantly replan the strategy
and monitor the execution of each step. (My own note: I could not see any
emphasis through the paper. As far as I see, only routing is performed
by symbolic layer, and it does not contain such a superiority over
other systems.)
- My own note: The system is different from RAPs because it
does not restrict the interface between sequencer and deliberator. But
there is not sufficient detail to deduce conclusions on this.
|
SFX: An Architecture for
Action-Oriented Sensor Fusion.
Murphy,
R.R., and Arkin, R.C.
- In this paper, not a full control architecture is
described, but rather an architecture for sensor fusion and sensor
error handling is described as SFX.
In the experiments, there is no control of robot, but pre-defined
perceptual processes, where based on pre-defined certainties of certain
sensors, the perception is performed and if necessary some automated
(and limited) recalibration.
is performed.
- Authors says that a generic architecture which is
task-independent (or wide variety tasks) is required for sensor fusion,
where the aim is to deal with inabilities/malfunctions of/in sensor
systems. The key aspects of implementation are : sensing plan, uncertainty management,
feedback to sensors, dealing with exceptions in sensing plans.
- Sensor Fusion: 'Process
which has the ability to define its own perceptual objectives and
sensing strategy, to adapt to sensing malfunctions and changes in the
environment.' Literature work on
sensor fusion is given, and it should have 6 attributes:
- process information from real world,
- facilitates the use of sensors in complex interactions,
- supports combination of quantitative and qualitative
observations,
- permits sharing of perceptual information,
- provides exception handling,
- exploits environmental knowledge whenever possible to
reduce processing.
- For managing uncertainty: Bayesian
and Dempster-Shafer mechanism
is used (SFX employs preceding one because..).
- Action-oriented perception
is used, which implies the perceptual activity constrained by the motor
activity, robot should perceive only what it needs to. (My own note: similar to Gibsonian
approach) Perception consists of two parts: percept and its measure of certainty. A sensing plan is
generated for the corresponding process, and using data from
environment, uncertainty manager
produce percept and certainty to parent motor behavior.
If an error bound is exceeded
exception handling module use
heuristics to response this (ie. by dropping corresponding sensor or
finding commonalities among sensors which produce error).
- Knowledge representation for sensing plan is done by a
directed acylic graph, which includes percept
at its root, description/sensor
in level 1, and evidence-interaction-feedback rules
embedded into lower layers. In execution,
evidences are
collected for each sensor and description, then quality of the evidence
is checked and at last step fusion
is performed. (fused-belief for
that percept found). At last
exception handling is done.
- Details of plan representation and execution can be found
in paper and a cited another paper. The case study was to detect
changes in a complex environment. During experiments, one can found the
recalibration step of
one sensor during plan execution.
|
COGNITIVE ARCHITECTURES
|
An architecture
for persistent reactive behavior.
Choi,
D., Kaufman, M., Langley, P., Nejati, N., & Shapiro, D.
- ICARUS architecture is
a rule-based system, which
includes
long-term memories for hierarchical concepts and skills, and short-term
memories feeding from perception. Additionally there are skills, which
are applied according to short-term memories in a reactive fashion. A
'2D kinematik' simulator is used for city driving and package delivery
tasks. The architecture locates closer to 'agent-based' size on the
situated-not situated or embodied-not embodied spectrum line. ICARUS
has a knowledge-based / case-based approach.
- Agent architecture is specified as the infrastructure for an intelligent
system that remain constant across different domains and knowledge bases.
The infrastructure includes:
- formalisms
representing knowledge,
- memories for storing
data and domain content,
- processes that utilize
the knowledge,
- and learning
mechanisms to acquire it.
- City-driving domain:
- ICARUS agent has
limitted perception, may perceive distance and angle, or its own
distance.
- It is provided with
top-level intentions to deliver packages to specific destinations.
- They allege that task
is
challenging since agent shold drive safely while staying on the right
side, making necessary turns and avoiding collisions
- Authors discuss ICARUS
memories and representations, they are represented in two-main
granularity:
- Long-Term Conceptual Memory:
is used for Boolean concepts that encodes its knowledge of familiar
situations. Descriptions of categoris for isolated objects, like types
of vehicles etc. Each entry specifies the concept's name and its
arguments: percepts
(perceptual entities), positives (lower-level
concepts it must match), negatives (lower-level
concepts, it must not match), tests (numeric
relations). For example the concept in-lane
matches situations in which the agent is on the right side of the road,
it perceives a lane line to its left.
- Long-Term Skill Memory:is
used as a complementary part of conceptual memory. It encodes knowledge
about ways to art and achieve goals. It includes specifications for
skills that apply in certain situations and that produce desired
effects (behaviors). ICARUS skills include:
- ordered or unordered set of sub-skills
- situations that must
hold after and later
- opaque actions that
are directly executable.
- An expected value, or function.
- Short-Term Memories:
to generate behavior, the architecture requires short-term stores that
can change rapidly. These should make contact with long-term concepts
and skills.
- Perceptual Buffer contains
descriptions of physical entities that correspond to the output of
sensors.
- Short term conceptual memory
contains instances of concepts that are defined in long-term concept
memory.
- Short term skill memory contains
instances of skills the agent intends to execute.
- Categorization and belief update:
concept instances remain in short-term memory only if they have direct
support from the perceptual elements upon which they appear.
- Selection and execution of skills:
ICARUS considers all such acceptable paths downward through the skill
hierarchy, returning the path with the highest expected value for each
instance in short-term skill memory.
- Reactivity and persistance:
Authors defined a persistance factor.
If it is zero, the agent behaves exactly as a reactive agent. The
higher the persistance factor, the greater the agent's bias toward
continuing to select the skills it picked on the previous time step.
For example, in experiments, the agent with zero persistance factor
tends to shift among its top-level intentions, attempting to deliver on
package but shifting to another even when nearing to its initial
objective. In contrast, with high persistance factor, agent selects a
target, and it pursues this task doggedly. The medium setting is most
successful. This persistance factor
is applied to expected values when path's value is calculated.
- Authors linked ICARUS
with various approaches:
- they discuss cognitive
architectures like SOAR.
- sensor-driven
execution in response to changing environmental situations, as
Georgeoff et. al. 1985
- Shares ideas with
Albus and Meystel's RCS
architecture, which organizes knowledge hieararchically and makes a
clear distinction between logical structure and value judgments.
- ICARUS is first
architecture to incorporate a flexible notion of persistance that
modulates rather than overrides its activity.
|
| DISCUSSION |
Software Architectures for
Hardware Agents.
Henry
Hexmoor, David Kortenkamp, and Ian Horswill.
- This article is the introduction part of the special issue
of Journal of Experimental and Theoretical Artificial Intelligence
which is devoted to robot
architectures.
- Authors say that architectures are important and should
deal with noise, real world conditions, failures, change in worlds, and
all other AI related issues like vision or configuration spaces.
- Definition of architecture of James Albus, "an architecture is a description of how a
system is constructed from basic components and how those components
fit together to form the whole".
- Some issues that should be stated explicitly are enumerated:
- representation:
unified, heterogeneous, multiple or no representation.
- control and coordination:
centralized or distributed control
- learning: defined
as changing an agent's internal structure. For example in three-tiered,
all layers should learn, ie. top layer should increase performance of
cognitive abilities.
- timely performance:
deal with real-time constraints. In general, there is no guarantee for
execution, execute as fast as possible. But for example CIRCA architecture is able to
guarantee execution times. A new subfield of AI for real-time control, link to Musliner.
Literature on
careful design for real-time execution.
- biological and
psychological inspiration
- evaluation: Link
to Erann Gat
- A brief overview of autonomous robotics, Tortoises, Hopkins Beast, Shakey..
- reactive: direct connection of sensors and control, and
guaranteed response times.
- Tiered
architectures: flexible
because of their symbolic components, good
performace because based on different time scales in different
layer. Simpler and more serial tiered idea was first applied with
Shakey.
- Brooks oppose tiered architectures, by layered architecture (1986),
increasing abstraction.
- Overview of papers in the special issue:
- RCS, presented
by Albus, strongest which
maintains internal world models.
- AuRA, presented
by Arkin and Balch.
- CSM, presented by Murphy and Mali, two layered architecture.
- 3T, by Bonasso
- LICA (Locally
Intelligent Control Agent), by Brandy
and Hu.
- LSA (Logical
Sensors/Actuators), by Budenske coordination
of variety of sensors and actuators.
- Multiple robots..
- Impact of perception on agent architecture, by Horwill.
- Saphira, by Konolige
- Behavior-based systems, an
overview by Mataric.
- Command Fusion, by Rosenblatt, arbitration, preference
ratings for different actions.
- Construction of hierarchies of behaviors without clear
divisions between the tiers, by Seeliger
and Hendler.
- SOAR resists tiered approach,
by Laird et. al.
|
|
|
On three-layer
architectures.
Erann
Gat.
- In this article, an overview of general three layer
architectures is given. Three components are:
- the controller: a
reactive feedback control mechanism
- the sequencer: a
reactive plan execution mechanism
- the deliberator:
a mechanism for performing time-consuming computations.
- Starts with Sense-Plan-Act (SPA)
approach, two significant architectural features: unidirectional data flow and similarity to execution of a computer
program. In 1985, some important shortcomings: Planning and
world modeling is very hard and open-loop
plan execution is inadequate in uncertain environments.
- Subsumption is
given as a departure from SPA in 1986, and author discuss subsumption a
little. He says with Connell's robot Herbert,
subsumption reached its peaks, and the reason of this capability ceiling is that
architecture lacks managing complexity and not sufficiently modular
since higher layers are very dependent to every bit of lower layer
details. Evaluation of subsumption architectures with examples is
given. Tooth and Rocky III robots create breakthrough
in subsumption architecture, where higher layers interfaced with lower
layers by advising not suppressing. Although they were reliable, they were not taskable.
- Connell, Gat and Bonasso find similar solutions to
same problem in 1991, by introducing three
layered architectures, SSS,
ATLANTIS, and
Gat's 3T. 3T system was based on Firby's RAPs. In Firby's thesis, it was
important the shift from reactive
planning to reactive execution
in RAPs, and RAPs contained earliest description of three layered
architectures. Main differences between ATLANTIS and 3T.
- Role of the internal
state is very important since:
- Difficulty of SPA: when world change, slow planning may
not synchronize
- Difficulty of SPA: Running
researcher syndrome
- Difficulty of Reactive: If readings false, unreliable
sensors: collision.
- No internal state: controller,
Memory about past: sequencer,
Memory about future: deliberator.
- The controller: Hand-crafted,
sensor-motor tight coupling, transfer functions, as Primitive Behaviors.
- Should have constant complexity
- Should fail cognizantly
- Should avoid internal states (exceptions ie. stop for 10
seconds)
- Internal state should not introduce discontinuities.
- The sequencer: Select
which primitive behaviors are active, and give parameters to them.
Instead of linear sequence of primitive behaviors, it should respond
conditionally to situations. One approach is to construct a mapping
from possible situations to primitive behaviors. However the history
should play role, therefore conditional
sequencing is employed. The sequencer should not perform long
time computations relative to the rate of environmental change at the
level of abstraction presented by controller.
- The deliberator: Exponential
search-based algorithms, planning etc. Two approaches: either produce plans for sequencer or respond to specific queries from the
sequencer.
- Author gave a case study
on implementation of three-layered architecture, on robot Alfred. He
has Rotatable Sonar Sensors.
Sequencer makes extensive use of internal
states, but does not perform any search.
- There was a view that planning is not sufficient which
may lead it is unnecessary. Author alleges, instead, it is necessary.
|
|
Planning as
Incremental Adaptation
of a Reactive System.
D. M. Lyons
- The planner-reactor approach
is described, which integrated deliberative capabilities to reactive
capabilities. Solution is to cast
planning as the incremental adaptation of a reactive system to suit
changes in goals or the environment. Reactor is a real-time system,
which is described using a formal framework, RS model. Planner is a seperate and concurrent
system that incrementally tunes the
behavior of the reactor. Robot-kitting
is selected as a test-bed, where kit assembly orders could be performed
off-line, but manageral instructions should be handled on-line.
- Literature on
hybrid approaches:
- Robo-SOAR: applies
interleaved planning and execution, not able to respond emergent
situations while in planning phase.
- Shoppers and Xiaodong&Bekey suggest off-line plan generators for
reactive systems, but being on-line is important.
- Connell's SSS: reactive and deliberative
components are asycronously
linked, which is a must. However, it is resricted to enabling/disabling
behaviors, but in Lyon's work, new behaviors should be generated.
- Arkin's AuRA: first produce reactive plan in
complete form, and load it into executer. But it might generate very
long planning delays. Lyon's prefered an incremental adaptive approach.
- Bresina &
Drummond's ERE and McDermott's XFORM are
primarly once-off activities,
not repititive.
|
|
Reactive
Planning.
D. M. Lyons
- Reactive Planning contradictory
term is used as a priori design of
reactive machines, and denotes a number of different
architectures which use both concepts from reactor and planning
techniques. The motivation is on creation of intelligent behavior, in uncertain and dynamic environments, where former
defines both uncertainty in world knowledge and effects of action's.
With dynamic environments, independent events are intended. Planning is
insufficient in real world domains like robotics.
- Literature on classical planning: STRIPS, NONLIN,
MOLGEN, DEVISER, SIPE, TWEAK. Planning problem: domain description +
initial state + goal state.
- The characteristics:
- Reactivity:
Ready for interruptions, and able to continue its plan afterwards. This
implies doing more than pre-constructed plans.
- Timely Activity: Time
must play role in planning. (which is straightforward?)
- Uncertainty: Uncertainty
in state and actions too large, a priori production of set of actions
is out of question.
- Improvisation and
Interaction: A good plan is not a sequence of actions carried
out by the agent on a passive environment, but rather continual
interaction between agent and world.
- As techniques for reactive planning, authors discuss
research in 3 parts. Architectures and design are motivated by making
reactive systems more formal, robust, flexible etc. Planning part
discusses work on integration of reaction and planing.
- Architectures: Here,
important issue is that reactive approaches are critisized for there
are solely hard-wired. To exhibit intelligent behavior, architectures may be employed to
add intelligence?
- Brook's subsumption
is described in detail.
- Nilsson's goals and
beliefs are described, where in Nilsson's approach a network is
constructed whose purpose is to deal with changing environmental
conditions.Networks are constructed by tying goals, preconditions etc.
Subgoals are linked in the network.
- Hendler's DR is described where monitoring change is emphasised.
- Design: Automated design is
imporant because intelligence in reactive machines depends on skills of
the programmer. (art more than science). The literature on formally correct machines is given.
- Universal plans
of Schoppers which resembles RAPs, where actions are selected at
execution time is described. BUT I
cannot find any notion of automated planning.
- Situated automata of
Rosenschein and
Kaelbling is
given as formally correct machines, which result in the language REX.
- Planning: In
order to be able to rise above local responses to the environment,
integration of planning component with reactive machines.
- Importance of time-constraints on planning in Dean & Boddy.
- Hendler integrates planing
and reaction in a hierarchy of file levels: sensory/motor, spatial,
temporal, cause, and conventional (APE),
where problem solving is propagated to higher levels.
- Based on net theory, Bresina
& Drummond reachts to current environment with the ability
to plan ahead, where in ERE,
arcs join conditions and events. There are different nets for different situations, and
there are chosen non-deterministically.
- Planner and Reactor,
of Lyons & Hendriks, is
discussed, which is en extention of robot schemas. Processes can be
defined in terms of networks of other processes, grounding out with a
set of atomic, pre-defined processes.
|
Adaptive
Execution
in Complex
Dynamic Worlds.
James Firby.
INTRODUCTION
- His main criticism on traditional approaches is that
planning is done in infinitely many details. However real-world is complex
and dynamic, and prediction of future is impossible. Therefore
instead of detailed plans, sketchy plans should be made, with
unspecified actions. Details of actions will be specified when required
(from direct observations). RAP execution system fills in gaps
in the plan details at run-time. He gave an example of taking a
cup of water from kitchen.
- Additionally, interruptions and emergencies should
be dealt with. Main emphasis is on uncertainty of the
environment.
- He suggests a three-layered system: Planner
-> Execution System <-> Robot Controller. There is no
feedback from Execution System
to Planner.
- Situated-driven execution: Process of muddling
through a sketchy plan in a relatively benign environment. Plan: A
set of partially ordered tasks for the robot to perform. A method
is a set of actions, and assume that for each task, there is a
prescribed method according to current situation.
- A time window together with a satisfaction
criteria is used in tasks. For task execution to adapt to
changing situations: different methods for different situations
designed.
- No Learning in the thesis.
- Basic algorithm is
- Select an active task to execute
- Depending on the current situation, select a method
from library
- Execute the method.
- Supports flexible, adaptable response to method failure.
- Allows task interruption and resumption.
- All sensing is incorporated into task methods. Task
methods specialized in sensing for i) execution, ii)
feedback. One reason is the clever usage of resources. Sensory
information buffer updated : sensory memory.
- As an example, a method pick-up fuel-drum becomes
with sensory operations, "scan", "move", "grasp", "lift", and "check
result".
- Robustness stems from:
- sensing is incorporated with methods, updated in a
timely manner,
- methods are chose based on assessment, adapt behavior
as situation changes.
- methods contain own satisfaction checks.
- My idea: In the example, when drum is
re-located, "pick" step do not stop until recognition of failure. But
there should be a mechanism which says, there is a change.
- Reactive Action Packages (RAPs): basic
building blocks for building situated-driven execution systems. Tasks
are instantiations of RAPs. RAP is a complete description for execution
of tasks, time-window excluded. Each RAP defined task is independent
and may work concurrent.
- RAP include:
- Goal
- Success criteria
- Methods for tasks which contain
- context (corresponding situation)
- steps
- Tasks has two parts:
- goal (index)
- satisfaction test
- satisfaction test
- time-window
- Methods in RAP may call other Tasks. From sketchy plan,
tasks are coordinated in Task Agenda. RAP Interpreter
initiates tasks according to RAP Memory (context), new
subtasks may be generated, by defined goals from RAP Library.
- Coordination among different tasks and subtasks is
a problem. Additionally, a mechanism should be explicitly inserted in
order to avoid infinite loops for certain tasks.
- Not only a programming language, since it seriously
restricts the way behaviors represented and interacted with each other.
Defines well-structured mechanisms.
- The thesis is based on not real world, but simulated
world. Two ways of research:
- Choose abstract, high level behavior that exhibit in
simple domain, than expand scope to real world conditions.
- Start with simple, low-level activities in real world,
make behaviors more complex.
- First is applied by planning research,
second is for robotics, sensing research.
- The Delivery Truck simulator is much more detailed
than Block World. But not physical, very abstract..
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|