Nate Chu

Hierarchical control structures in robotics

Hierarchical control structures are a way of dealing with the problem of abstract problem-solving in autonomous robots.  the main idea behind hierarchical control is the decomposition of tasks into smaller, more manageable subtasks.  Each level of control decomposes its tasks into approximately the same number of subtasks as the level above, and passes each of those subtasks to the next level as tasks.  this is repeated on every level of the hierarchy, with the result that complex and abstract behaviors can be decomposed into exponentially more, but much simpler, individual actions to be carried out by actuators interacting with the real world.  this decomposition can be either done on-the-fly, or can be precomputed and stored in memory.  while storing behaviors in memory is less processor intensive, it is also less adaptable to unexpected circumstances.  on-the-fly generation is much more complex, however, there is an unlimited range of behaviors possible.  a good solution is to have a mixture of the two - provide machinery for generating behavior, but store many common behaviors in memory.  On-the-fly behavior generation is usually accomplished with a planner or feedforward mechanism.  these work by inputting a desired state into a reverse world model, and passing the output actions to the behavior generator.

A major role in hierarchical control structures is played by ELFs, or Elementary Loops of Functioning.  each of these loops includes sensors, a sensory processing unit, a world model, a behavior generation unit, actuators, and the world (real or virtual).  to begin, the sensors extract information from the wold with which they are interfacing.  on the lowest level these can be things like contact sensors, photocells, or sonar.  the information from these sensors is passed to the sensory processing unit, which takes all the information and interprets it into a more abstract form.  this information is passed to the world model, which compares the current state of the world to the desired state, and predicts the actions required to achieve that state.  these actions are fed to the behavior generator which decomposes the actions into single subtasks, and sends these to the actuators to be executed. the actuators actually interact with the world (virtual or physical), which then affects the sensors.  this loop is endlessly repeated, and forms the elementary unit in a hierarchical structure.  the sensory processing unit has another function as well.  Not only does the SP interpret the information passed to it from the sensors, but it also acts as a sensor to the next higher level of functioning.  the behavior generator also acts as an actuator for the next higher level, thus, level 1 acts as a virtual world for level 2, level 2 is a virtual world for level 3, and so forth.  for each of these levels, the theory of increasing resolution with decreasing scope applies.  this means that on the most basic level, there is a very high resolution - individual pixels, motor controls, etc., but there is not much breadth to the information.  on a higher level, the behavior generator need not deal with actual motors, but can deal with positions.  moving up the levels results, eventually in a level where there is a very broad spectrum of information, but it is not precise, e.g. a level that deals with entire objects rather than a single pixel.  this structure is very helpful for feedback control, because at lower levels feedback demands quick reaction time, whereas for higher more abstract levels, feedback can be dealt with in a more timely fashion.  

subsumption is an alternative approach to hierarchical control.  in a subsumption system, each behavior is assigned a unique priority.  only one behavior can be active at a time, so a higher priority action subsumes one of lower priority.  each behavior is triggered by certain sensors, or combinations of sensors, and each action controls the same set of actuators.  this approach does not generate behaviors at all, and so is much more limited in scope.  it can, however, be paired with a hierarchical system, in which certain levels implement subsumption internally, and lower levels receive commands as if from a upper level behavior generation unit.  this is the plan that i propose to implement for my senior project.