Literature Survey
on
Existing Robotic Control Architectures
    1. 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.
    2. 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
    3. 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.
    1. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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
    8. CIRCA: World modeling for the dynamic construction of real-time control plans. Musliner, D. J., Durfee, E. and Shin, K. Artificial Intelligence, 74. 1995.
    9. 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.
    10. TCA: Structured control for autonomous robots. Reid G. Simmons. IEEE Transactions on Robotics and Automation, 10(1):34-43, February 1994.
    11. 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.
    12. 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.
    13. 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
    14. 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
    1. 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.
    2. 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.
    3. Soar: Soar : an architecture for general intelligence. Laird, J. E., Newell, A. and Rosenbloom, P. S. (1987) Artificial Intelligence, 33.
    1. Software Architectures for Hardware Agents. Henry Hexmoor, David Kortenkamp, and Ian Horswill. Journal of Experimental and Theoretical Artificial Intelligence (JETAI) 9 (1997) 147-156.
    2. 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.
    3. Robot Plan Execution: Logical sensor/actuator: knowledge-based robotic plan execution. John Budenske, Maria L. Gini. JETAI 9(2-3): 361-374 (1997)
    4. ESL: ESL: A Language for Supporting Robust Plan Execution in Embedded Autonomous Agents. Ron Garret. Proceedings of the IEEE Aerospace Conference, 1997.
    5. 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.
    6. 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.
    7. Reactive Planning: Reactive Planning. Lyons, D.M. and Hendriks, A. Encyclopedia of Artificial Intelligence, 2nd Edition, Wiley & Sons, December, 1991.
    8. 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.
TOP
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:
    1. 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.
    2. Things should be simple. (Should not be in a position dealing with ill-posed problems.)
    3. Cheap robots that are in human-inhabited space without human intervention. Additionally, should do useful work.
    4. Modelling should be in three-dimensional.
    5. Instead of absolute coordinate systems, relational maps are more useful.
    6. No artificial environment.
    7. Sonar data used in low-level interactions, but visual data is much better in intelligent interactions.
    8. For robustness, self-calibration.
    9. 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.
TOP
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
    1. 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)
    2. Executing an operator means biasing behaviors rather than exerting hard control. An operator chosen for execution stimulates (++) or mutes (--).
    3. 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.
TOP
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
      1. designed for physically embedded agents, like TCA, subsumption, AURA, 3T
      2. 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.
TOP
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.
TOP
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:
      1. 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.
      2. 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:
    1. Different rate behaviors, without any hieararchy
    2. 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.

TOP
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.
TOP
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.
TOP
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.
TOP
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.
TOP
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.
TOP
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:
    1. representation: unified, heterogeneous, multiple or no representation.
    2. control and coordination: centralized or distributed control
    3. 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.
    4. 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.
    5. biological and psychological inspiration
    6. 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.
TOP
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.
TOP
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.
TOP
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.
    1. 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.
    2. 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.
    3. 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.
TOP
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
    1. Select an active task to execute
    2. Depending on the current situation, select a method from library
    3. 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:
    1. Choose abstract, high level behavior that exhibit in simple domain, than expand scope to real world conditions.
    2. Start with simple, low-level activities in real world, make behaviors more complex.
    3. 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..
TOP