Introduction to Rodney Brooks Subsumption Architecture:

The subsumption architecture is a layered methodology for robot control systems. It consists of coupled components and their hierarchical behaviours. One component is superimposed on the other as single layers. Each layer disposes of an arbitration scheme which empowers higher layered behaviours to manipulate the input and output of lower behaviours by suppressing the input or inhibiting the output (see fig. 01). Also visible in fig. 01 is that each layer component receives data from the sensors and the actuator receives one calculated output for the control, independent from the number of registered layers.

(For detailed information about the subsumption architecture please note the following references [5], [6], [7], [8])

Motivation

The idea of Brooks’ subsumption architecture is from 1986, why is it still interesting today? In reactive robotic paradigms the subsumption architecture is still very relevant. Many instances of robots and autonomous systems are still build using this philosophy. Today’s environment puts high requirements on a reactive system. For example it has to be extremely performant, needs to be flexible and especially safe under all circumstances. The subsumption architecture has the distinction of being very reactive and robust. Therefore it has a significance to implement the architecture according to new standards and modern views. According to the increased requirements this new implementation of the subsumption architecture concentrates on the memory management by taking advantage of C++14, the modularity (therefore testability) and the use of effectively modern patterns which reduce the complexity.

The following article gives an overview of the functions of this new implementation, the used composite pattern and offers a description how to use it for own scenarios.

Subsumption Diagram with Implementation Labels

This diagram fig.02 is based on the subsumption model as described in the first chapter. The annotations are related to the implementation to simplify the understanding of the architecture. It illustrates the inputs and outputs of each function with its correct labels. Note that each level has its own local attribute such as “actuatorOutput” and “sensorInput” and they are not the same although the label is identical.

Subsumption Class Diagram

The class diagram (fig. 03) consists of four components “SensorData”, “ActuatorData”, “Level” and “Controller”. Moreover it is freely expandable by a number of levels (e.g: “Level2”). The component “Level” represents an interface for all levels. Levels derive from “Level” and implement the three virtual functions. Each Level has its own local “SensorData” for the input and for the output its own local “ActuatorData” object. According to the composite pattern (see chapter “Excursion – Composite Pattern”) all derived levels except for the highest level (here fig. 03 “Level2”) are having a “Level” object as higher level (see fig.03 “Level0” “Level1”). The levels are not aware of the “Controller”. The “Controller” has a pointer to the root level with which it is able to control the subsumption procedure.

Subsumption in this Implementation

The idea of this implementation is to represent the structure of Rodney Brooks’ behaviour based subsumption architecture. Brooks’ idea of the structure has already been explained in the chapter “Introduction to Rodney Brooks Subsumption Architecture”, besides Brooks explained his idea of the architecture in [5] and [6].

As visible in fig. 01 the subsumption architecture is composed of following components:

• Sensor, it offers the pure input data.
• Suppressors (see fig. 01: S_0 and S_1), they are a part of the layered components and they influence the input data for the current level by suppressing it by the higher layered level.
• Levels (see fig. 01: level_0, level_1, level_2), they are a part of the layered components and they include the main behaviour. As an input functions it has either the pure data input (fig. 02 sensorData) or the suppressed input (fig. 02 sensorInput). It has two outputs, one is for the input of the suppressor of the lower layer (fig. 02 suppressControl)) and the other one calculates the level output for the actuator (fig. 02 actuatorOutput).
• Inhibitors (see fig. 01: I_0, I_1), they are a part of the layered components, they influence the output data from the current level by the level output from the higher layered components.
• Actuator, it receives the calculated output from the lowest level

This implementation is based on these components. Sensor, Level and Actuator are implemented as classes whereas “Level” represents an interface for all levels (see fig. 03). Different than the composition in fig. 01, each level includes their suppressor and inhibitor as functions as well as a level function. For example in fig. 02 “S_1”, “Level_1” and “I_1” are functions of the class “Level1” which is derived from “Level” (see also fig. 03).

The reason for this abstracted implementation is that within this structure the adding of single levels is easier than for example with an implementation in which each component is a single class. For adding a new level to the architecture the new level must simply derive from “Level” and has to overwrite three functions (see chapter “creating a new subsumption level”).

Because of the controller the registration of the new created level became very dynamic and flexible, only one line for example “controller.registerLevel (new Level_X);” (see also code lines 76 – 78) is necessary to add the new level. There is no further changing of already existing code, therefore the other levels still function as they would without the new one which also leads to the testability. Each level can be tested individually. Consequently this ensures the functionality of the architecture and facilitates the debugging if a problem occurs.

Excursion – Composite Pattern

Composite Pattern - General

The composite pattern allows treating different objects uniformly. The pattern describes hierarchical data structures and composes objects into a tree structure. A revision of tree structures with a connection to composite pattern can be found [3]. The pattern consists of following elements:

• Component,
• Leaves,
• Composites.

A component is an interface which represents the main behaviour of the pattern. Leaves and composites derive from the component. A leaf represents a node without any children. It defines the behaviour of primitive objects (see fig. 05).

A composite has 0…* children. Those children can be leaves and also other composites. (See fig. 04).

The composite pattern uses the benefit of the tree structure such as the recursive call of the children from composite elements. For traversing through the structure only the root object needs to be called. A detailed example as an explanation of this pattern is given in [4]. Additional structure explanation can be found at [1] and [2].

Advantage of the composite pattern is that because of the component interface the use of the structure is based on the abstraction and not on the implementation of the single composites and leaves. Therefore the differences between the primitive objects and composite objects can be ignored. Another advantage is the flexibility of integrating new object (both composites and leaves) into the structure. New object only need to implement the component interface and can be added to the tree structure, there is no need for further code changings.

Composite Pattern - Applied in the Subsumption Architecture

The composite objects in this case are all levels except for the highest level, which attribute “higherLevel” is the null pointer. So the highest level represents a simple leaf at which the recursion call will end. A child of a composite corresponds to the higher layered level. In difference to the outlined before composite pattern with the regular tree structure with a number of children for each node, this representation of the levels is more likely a singly linked list since each level has one child at maximum (see fig. 06). It does not change the meaning of the composite pattern, the benefits are still ensured since a tree data structure generalizes lists. As long as the “higherLevel” is not the null pointer, the level represents a composite. That means that there is always one leaf in this design and 0-n composites.

The registration of the levels takes place at the controller function “registerLevel”. Within this registration function the single levels are linked by a reference to their higher level (see code line 61) and the last added level, which represents the lowest level, is set as the root level (see code line 62). To ensure this the single levels need to be registered from the highest to the lowest level.

One of the reasons why the composite pattern is very profitable for this implementation is the “arbitrate” function in the controller. The controller does not have to manage a whole list of levels, it only needs to know the root leaf (the root composite), the other levels are calling themselves recursively. Another advantage is the memory release. The controller deletes the root level while its deconstruction and each level deletes its higher level.

Subsumption Call Procedure

The main process of the subsumption architecture is implemented in the “startLevel” of the “Level” class (see fig. 07). The basic progress is from the highest level to the lowest and from left to right.

Therefore the calling order for all levels except for the highest should look like this:

Suppressor (“suppressInput(…)”), Level (“executeLevel(…)”), Inhibitor (“inhibitOutput(…)”) (See code line 37-39).

The highest level solely calls the “executeLevel” method (see code line 32-34). Since the highest level has no higher level as consequence “higherlevel” is a null pointer. Another consequence is that no suppressed inputs or inhibit outputs exist. Lines 32-34, according to the composite pattern, are for the primitive object which hasn’t any children. In lines 35-40 is the progress for all composite level objects.

The procedure starts with the root level. This can be either a leaf (in case there’s only one level), then the procedure will simply execute the level (see code line 33) or it can be a composite (if more than one level). If the root level is a composite, is the first thing to do calling the “startLevel” procedure for its higher level in line 36. This calls recursively all higher lever from the root level until the highest leaf, is reached. From that point on the previously described function calling order is employed (lines 37-39).

In line 41 the output of the lowest level will be returned. It is the output on which each hierarchical level had an influence. Because of the recursion the controller simply needs to call this function one time to provide the whole subsumption procedure.

Subsumption Controller

The class “Controller” is the component which organises the registration of the levels and starts the arbitration for the actuator output. It has a pointer to the root level or to put it another way to the lowest level in the architecture, therefore it can address any registered level because of the composite pattern (for further information see chapter “Composite Pattern - Applied in the Subsumption Architecture”).

In the function “registerLevel” (see fig. 08) the attribute “higherLevel” of the new level is set as the known registered root level of the controller (see code line 61). And the root level pointer will be updated and receives a pointer to the new level (see code line 62). In the end all levels are linked to each other by knowing their upper level and the controller sorely needs a pointer to the lowest level. This data structure of a singly linked list is much more efficient than for example maintaining a list of levels, because the controller sorely needs to know one level and no loops are required.

The arbitrate function (see fig. 09) is the start method for the whole progress of arbitration. As explained the controller only needs to know the root level, it simply calls up the “startLevel” procedure which handles as in chapter “Subsumption Call Procedure” described the progress of the actuator output arbitration of all levels.

The controller also processes the communication with the actuator for the level by offering a “getOutput” function which has the output of the subsumption architecture as return value (see code line 68 – 70). For this function is also only the root level necessary, because as shown in fig. 02 all upper levels make an impact on the output of the lower levels thus the output of the root level is the output which is supposed to be used for the actuator.

Creating a New Subsumtion Level

To create a new subsumption level which shall be added to the structure/architecture the user need to derive from the abstract class “Level” (see fig. 03 and also code lines 50 - 52). For each level the following functions denoted by “virtual”, which implies that that the method is implemented at another location, must be implemented:

suppressInput (see fig. 10 lines 20 - 22) executeLevel (see fig. 10 lines 23 - 25) inhibitOutput (see fig. 10 lines 26 - 29)

a) The function “suppressInput” represents the suppressor of the level (see in fig. 02 the “S_x”). The task of this function is to evaluate the input for the level (see fig. 02 “data”) by the influence of the suppression from the higher level (see fig. 02 the “suppressControl”) on the current sensor data. An explicit algorithm depends on the intentional use for the architecture and needs to be added by the user. Note that this function won’t be called if the level is the top level. The top level gets directly the unsuppressed data from the sensors (see code line 32-34).

b) “executeLevel” includes the main algorithm for the data processing and depends on the use case. As an input argument it gets the pure data from the sensors if top level or the suppressed data from the suppressor.

c) The function “inhibitOutput” is similar to “suppressInput”. It represents the inhibitor of the level (see in fig. 02 the “I_x”) and it evaluates the actuator output in conjunction with the current level output and the output of the higher level (see fig. 02 the “actuatorDataFromHigherLayer”). Note that this function won’t be called if the level is the top level. The top level sets the uninhibited data from the layer (see code line 32-34) directly as actuator output.

To add the new level to the architecture use the method “registerLevel” and add an instance of the new level as argument (see fig. 11). How that works in detail is described at the chapter “Subsumption Controller”.

References

About Composite Design Pattern:

[1] E. Gamma, R. Helm, R. Johnson, J. Vlissides: Design Pattern [2] Alexander Shvets: Design Patterns Explained Simply [3] M. Wirsing: Dynamische Datenstrukturen – Listen und Bäume [4] Philipp Hauer - Das Composite Design Pattern

About the Subsumption Architecture:

[5] Rodney A. Brooks: How to Build Complete Creatures Rather than Isolated Cognitive Simulators [6] Rodney A. Brooks: A robust control system for mobile robot, IEEE Journal of Robotics and Automation [7] G. Butler, A. Gantchev, P. Grogono: Object-Oriented Design of the Subsumption Architecture [8] J. Simpson. C. L. Jacobsen, M. C. Jadud: Mobile Robot Control