Behaviours, arbitration and the subsumption architecture

1. Behaviour-based control

Four statements define the field:

• Behaviour-based control involves the use of behaviours as modules for control.
• Behaviour-based controllers are implemented as collections of behaviours.
• It is inspired by animal behaviour.
• There is an emphasis on embodiment.

The lectures give a list of examples, which is worth reading slowly because it spans a much wider range of abstraction than students expect:

2. What is a behaviour?

Chapter 1 left this as an open question ("how would you define a behaviour or an action?"). Here is the course answer, in four clauses:

And the one-line contrast to memorise: behaviours are more complex than actions.

Four observations

1. Behaviours can be designed at a variety of levels of detail or description (level of abstraction).
2. Parallel execution and distributed control are often required.
3. The network of behaviours can store states and can be used to construct a model of the world. It can store history and look ahead into the future.
4. Behaviours are usually designed so that they operate on compatible time-scales.

Observation 4 is a practical trap. If one behaviour reacts in 10 ms and another needs 2 seconds, composing them produces an incoherent robot: the slow behaviour never gets to finish anything. Designing for compatible time scales is a real constraint in the lab, not a footnote.

3. Behaviour coordination: arbitration and fusion

Once you have a collection of behaviours, you face the problem of deciding what behaviour to perform next — and more generally the problem of composing behaviours. Several architectures have been proposed. The course organises them all under two headings:

4. Arbitration and its implementations

Arbitration is the process of selecting one behaviour among possible candidates. The lectures list four ways to implement it:

5. Finite state automata: an example and an assessment

The FSA for random walk + collision avoidance

The worked example from the lectures composes three behaviours — Random Walk, Phototaxis and Collision avoidance — driven by three percepts, with the priority ordering:

obstacle  ≺  light  ≺  no percepts

Read ≺ as "has higher priority than" in the sense used in the slide: an obstacle percept dominates a light percept, which dominates the absence of percepts. The resulting automaton:

The lectures state explicitly what this construction is: this FSA implements an arbitration based on the priorities of the signals coming from the sensors. The priority is not written anywhere as a number — it is encoded in the transition table, which is both the strength and the weakness of the approach.

Considerations on FSA

And one addition that will matter twice later in the course: probabilistic FSA are useful for avoiding cycles, and in swarm robotics contexts. Chapter 9 uses a probabilistic FSA for adaptive prey retrieval and for aggregation; Chapter 11 has AutoMoDe generate probabilistic finite state machines automatically.

6. The subsumption architecture

The headline definition:

• Decompose the robot architecture into task-achieving behaviours or competences.
• Control is parallel and distributed.
• A different approach than the classical sense-think-act cycle.
• Proposed by Brooks and others. Terminology in the field is not uniform; the course sticks to Brooks's.

Requirements for a real robot

Brooks motivates the architecture from four requirements that a real robot must satisfy:

1. Multiple goals, possibly conflicting — e.g. obstacle avoidance and block pushing.
2. Multiple sensors.
3. Robustness.
4. Extendibility.

Two decompositions of the same robot

The central figure of Brooks's A robust layered control system for a mobile robot is a pair of diagrams: the traditional decomposition of a mobile robot control system into functional modules, versus a decomposition based on task-achieving behaviours.

7. Competences and layers

Two words in that definition carry weight. Informal: a competence is not a formal specification, and Brooks does not pretend otherwise. Over all environments it will encounter: a competence must hold across the robot's whole niche (Chapter 3), not just in the arena where you debugged it.

From the definition follows the main idea:

We can build layers of a control system corresponding to each level of competence, and simply add a new layer to an existing set — incremental design.

8. Properties of the subsumption architecture

Four properties, stated in the lectures. Learn all four; the third is the one that decides exam answers.

1. Higher layers assume the existence of lower layers and the goals they are achieving, so they can use lower ones to achieve their own goals — either by using them while they are running or by inhibiting them selectively.
2. Higher level layers subsume the roles of lower level layers when they wish to take control. (This is where the architecture gets its name.)
3. Crucial property to be guaranteed: at every time instant, any actuator receives signals from at most one level.
4. The system can be partitioned at any level, and the layers below form a complete operational control system.

-- lab activity 3: subsumption WITHOUT a central dispatcher
-- each layer takes the command produced so far and may override it

function step()
  local cmd = { vl = 0, vr = 0, taken = false }
  cmd = layer0_avoid(cmd)        -- lowest competence, runs first
  cmd = layer1_phototaxis(cmd)   -- may override only if layer0 did not take control
  cmd = layer2_halt_on_black(cmd)
  robot.wheels.set_velocity(cmd.vl, cmd.vr)
end

function layer1_phototaxis(cmd)
  if cmd.taken then return cmd end          -- subsumed by a higher-priority layer
  local l, r = light_left_right()
  if l + r < EPS then return cmd end        -- this competence has nothing to say
  return { vl = BASE + K * r, vr = BASE + K * l, taken = true }
end

Note how the taken flag implements property 3 mechanically: once a layer has claimed the actuators, no other layer can write to them in the same control step.

9. Augmented FSMs and Genghis

Augmented finite state machines

The first implementations of this architecture were in hardware, with each level made of augmented FSMs. An AFSM may also have auxiliary data structures and memory such as registers, queues and clocks.

The registers and clocks are not a detail. They are what allows a subsumption layer to be time-extended and to hold a little state — exactly observation 3 of section 2 — without any central world model.

Genghis

The worked example is Brooks, R. A., A Robot That Walks; Emergent Behaviors from a Carefully Evolved Network, MIT AI Lab Memo 1091, February 1989. Genghis is a six-legged walking robot whose control system is built as eight layers:

Considerations on Genghis

Four conclusions are drawn:

• Robust walking behaviours can be produced by a distributed system with very limited central coordination.
• Higher level competences can be seamlessly integrated over lower level competences.
• Coherent macro-behaviours can arise from many independent micro-behaviours.
• There is no need to postulate a central repository for sensor fusion.

10. Summary and final observations

Summary of the subsumption architecture

• Systems are built from the bottom up.
• Components are task-achieving actions/behaviours, not functional modules.
• Components can be executed in parallel (multitasking).
• Components are organised in layers.
• Lowest layers handle the most basic tasks.
• Newly added components and layers exploit the existing ones.
• There is no use of internal models: "the world is its own best model".

Final observations

The subsumption architecture was proposed as an engineering approach to intelligent systems design, and should be considered a successful practical example of behaviour-based robotics. However, it contributes a number of relevant ideas for intelligent systems design and cognitive science in general:

• it is based on development/evolution considerations;
• it realises sensor-actuator couplings with little internal processing;
• it conceptualises intelligence emergent from a large number of loosely coupled parallel processes.

The wider argument behind these slides is Brooks's, in Elephants Don't Play Chess (Robotics and Autonomous Systems 6, 1990): there is an alternative route to Artificial Intelligence that diverges from the direction pursued for thirty years. The traditional approach emphasised the abstract manipulation of symbols whose grounding in physical reality has rarely been achieved; the alternative — nouvelle AI, or situated activity, based on the physical grounding hypothesis — emphasises ongoing physical interaction with the environment as the primary source of constraint on the design of intelligent systems. Where the traditional methodology decomposes intelligence into functional information processing modules whose combinations provide overall system behaviour, the new one decomposes it into individual behaviour generating modules whose coexistence and co-operation let more complex behaviours emerge. As Brooks notes, in classical AI none of the modules themselves generate the behaviour of the total system — you must combine many of them to get any behaviour at all.

Check your understanding