Behavior-Based Robotics and Evolutionary Computation, EVAL group vision

In this document, we explain (on example of a football playing robot) how the EVAL subgroup understands the behavior-based architectures of complex robotic systems and possible uses of learning and evolutionary robotics in robotic systems.

There are 2 kinds of basic approaches to building systems. First, the top-down approach specifies the overall system from a black-box perspective and divides it into smaller and smaller subsystems, components, and parts. These parts are later assembled together to compose the whole system. A good football player should for example have

Second, the bottom-up approach is an answer to problems inherent in the top-down approach: technological, physical, logical and all kinds of other constraints might limit the possibilities to successfully build the top-down specified components and parts and result into a failure to build a working system. In the bottom-up approach, the overall purpose of the system is kept more as a vision and motivation of progression. The system is built incrementally by adding higher layers in the abstraction hierarchy from simple but working early versions to more complete versions. For example, when a vision and legs of a top-down built football player are finally combined, it can be found that the movements of legs are interfering with the vision and cause ghost balls to be detected around the robot. A bottom-up football player will first learn to walk, run and kick and the vision system will be added afterwards, to stear the player in the right direction.

Behavior-based architectures (for example Brook's Subsumption architecture) are traditionally pure bottom-up systems. We believe that a successful robotic system has to be developed in an interaction of top-down and bottom-up approaches. The tendency in building robotic systems in the last decade shows increase in the use of hybrid (top-down combined with bottom-up) architectures.

Every robotic system consists of robot's body, sensors, actuators, and a controller. A robot is built for certain purpose, in our case to play football. While a robot operates in its environment, it has set of goals, that are configurable - possibly also during its operation. A football player is pretty simple and it has just 4 goals: to score in the opponent's gate, to avoid the opponent to score, to survive, and to play according to the rules. From these basic goals, a robot can infer (or has hard coded) strategies. Our football player can be equipped with various offensive, defensive, goal keeping, and cooperating strategies. During operations, robot observes the situation and applies the strategies. There might be more strategies that compete for use at the same time. The active strategy generates intentions (activities that the agent plans to execute in the near future) of the robot. A football player's intentions would be to block the opponent, to pass the ball to its company that is reaching a promising offensive position, to fool opponent player by pretending to kick the ball, etc. Intentions are fed into the controller's behavior-based architecture and here the top-down approach ends.

The bottom-up BB-architecture is layered into 3 levels:

  1. plan
  2. assamblage
  3. behavior
Plan is typically generated from purpose, goals and current intentions of the agent as described above. It can be represented in various forms: a state diagram, linear sequence of commands, parallel program, etc. In the plan, states, commands, etc. (all smallest non-dividable elements) are assemblages. In the example of football playing robot, a naive plan can be a sequentially executed list

Assemblages represent various activities that the robot can perform and the smallest non-dividable elements in their specifications are behaviors. Assemblage controls which behaviors are active and how they are coordinated. The output from behaviors can be used in 'programs' of assemlages. There can be more assemblages active at the same time. In those cases, however, the plan has to contain a coordinator of assemblages.

Behaviors are basic low-level activities that the robot is able to perform. They can be hard coded, programmed, or even learned during robot's lifetime. Behaviors are autonomous pieces of code that can run in parallel. They have access to direct and/or preprocessed sensory inputs and can control robot's actuators directly and/or through behaviors coordinator specified by the responsible assemlage. Examples of a football player behaviors are: test the presense of ball in front, move forward avoiding collision, move forward with a ball, locate opponents goal, move to the middle of the field, etc.

Evolutionary computation can be used in Behavior-Based robotics at the following places:

The above can be combined and more parts of the robot can be evolved simultaneously. In addition, evolution of assemblages and behaviors is often done in parallel in Genetic Programming, although it is very implicit. That is, one cannot locate the assemblages. On the other hand, GP does evolve hierarchical structures in which the lower levels may be similar to behaviors, while the S-expression (program) as a whole has a functionality similar to that of an assmeblage. See also Koza's Automatically Defined Functions (ADF).

Evolutionary computation used for BB-robotics brings several challenging problems:

Here is one of the possible classification of Evolutionary Robotics:

  1. Off-board evolution
    1. on-line evolution - remotelly controlled robot: evolution is run on the workstation while the real robot is performing its task in the environment. The result of the computation is sent by remote transmission.
      1. short-term: The evolution in this case can solve a single problem, run once for relatively short time and send the solution to the robot afterwards. The fitness function can either be some objective measure or can be tested in a simulator of the robot.
      2. continuous: The evolution runs during the whole lifetime of the robot. In this case evolution should generate a new candidates to solutions to problems solved by the robot. The basic assumption is that the robot can afford to test these candidates and risk that they are the wrong solution without possibly harming the result of its mission.
    2. off-line evolution - used to design the robot (optimization). Once the robot is designed, evolution is not used further.
    3. simulated execution - in this case there is no real robot, only a simulator of a robot and the simulated robot solves a problem using Evolutionary Computation while it executes its task.
  2. On-board (embedded) evolution
    1. training: evolution is used only to train the robot before it is sent to a real environment and performs the task. I.e. it is used as a learning algorithm. This method is very time consuming, but might be useful in certain situations.
    2. execution: evolution runs on the robot while it is performing its task in the real environment
      1. short-term: see above, except the solution doesn't have to be sent to the robot. Here, the robot can contain a simulator of itself.
      2. continuous: see above

If you have any comments, ideas, suggestions, cooperation proposals, critique, or interest, please contact the EVAL group by e-mail.

Document created: January 2000.