Abstract Behavior Representation for Dynamic Behavior Networks

Motivation

Approach

Experiments

Robots

Motivation

Behavior-based control has become one of the most popular approaches to embedded system control both in research and in practical applications. Behavior-based systems (BBS) employ a collection of concurrently executing behaviors, processes connecting sensors, effectors, and each other. An important property of BBS is their ability to contain state, and thus also construct and use distributed representations. This ability has been underused, so BBS are yet to be explored and extended to their full potential. This research is trying to address two current limitations of such systems, both having to do with the use of representation. The first motivation is the fact that behaviors lack the abstract representation that would allow them to be employed at a high level, like operators in a plan. Behaviors are typically envoked by buit-in reactive conditions, and as a consequence, BBS are typically unnatural for, and thus rarely applied to complex problems that contain temporal sequences. Since there is no intrinsic limitation within BBS construction that prevents this capability, we present a method for taking advantage of it. The second, and related, motivation for this work is that the vast majority of behavior-based systems are designed by hand for a single task. Yet behaviors themselves, once refined, are usually reused by designers, and this has enabled the gradual accumulation of behavior libraries. Unfortunately, the remainder of the system that utilizes such libraries is usually constructed by hand. We seek a behavior representation that would support behavior reuse for multiple tasks, each using different subsets of a given behavior repertoire. Our aim is to conserve the robustness and real-time properties of behaviors, but avoid cutomized re-design, at least within a class of related tasks. We describe how a paticular type of behavior representation makes this possible and practical. To address these issues, we introduce an abstract behavior representation, based on behaviors developed for any one or more specific tasks. It is critical that the practical, robust behaviors come first, and the representation is derived from them. This stands in sharp contrast to approaches that employed high-level sensors and operators assuming that the low-level controller will provide whatever information and action was needed by a high level planner. The abstract behaviors are used to specify one or more tasks, in the form of behavior networks, which can be generated by hand or by an automated planner, depending on task complexity. Any single network represents a task-specific BBS, much like standard BBS. However, the components of the networks are general, allowing for behavior reuse both off-line (for system specification) and on-line (for system adaptation to a new task or directive).

Approach

Adapting Behaviors for Representation

BBS behaviors typically consist of a collection of rules, taking inputs from sensors or other behaviors in the system, and sending outputs to the effectors, or other behaviors. The inputs determine the activation level of a behavior; whether it is on or not, and in some systems by how much. These are the activation conditions for behavior execution. In their operation, behaviors individually or as a group achieve and/or maintain the goals of the system, thus achieving the task. This methodology lends itself to the construction of highly effective special-purpose systems. This is thus both a strength and a weakness of the approach. In order to lend generality to a given system, we first looked for a way to make the behaviors themselves more general, while still assuring that they would achieve and/or maintain the goals for which they are designed. The key step in adapting specialized behaviors to more general use is in the separation of the execution conditions from the outputs or actions. By separating the conditions from the actions, we allow for a more general set of activation conditions for the outputs or actions. While this is not necessary for any single task, it is what provides generality to the system for other tasks. The pairing of a behavior's conditions and its effects, without the specification of its inner workings, constitute an abstract behavior. Intuitively, this is simply an explicit specification of the behavior's execution conditions (i.e., preconditions) of a given behavior, and its effects (i.e., postconditions). The result is a an abstract and general operator much like those used in classical deliberative systems. The behaviors that do the work that achieves the specified effects under the given conditions are called primitive behaviors, and may involve one or an entire collection of sequential or concurrently executing behaviors, again as is typical for BBS. Abstract and primitive behaviors can both be quite complex, just as they are within any system embedded in an environment. The abstract behavior conditions, as in any BBS, are typically far from low-granuarity states, but are instead abstracted, either by hand or through a generalization process. If they were not, the benefits of using behaviors as a high-level representation would be lost. Similarly, the primitive behaviors are no lower level than standard BBS behaviors, meaning they are typically time-extended sequences of actions (e.g., go-home), not low-granularity single actions (e.g., turn-left-by-10-degrees).

For the purposes of the representation, we distinguish the following two types of behavior preconditions: In standard BBS behaviors, both types of preconditions are tested together, and without discrimination, thus hard-coding a particular solution. To change tasks and goals, one often makes the most changes to these preconditions, which much of the rest of behaviors remain unchanged. The ability to manipulate and change these conditions at an abstract representation level, separate for the behavior repertoire/library, is achieved by the introduction of abstract behaviors. With those, behaviors are treated as high-level operators, and without loss of robustness can be employed to generate various strategies or plans for specific tasks. However, classical planning requires a specific initial state, while BBS provide general controllers that can handle a variety of initial conditions. With the use of abstract behaviors, we generate networks that are BBS, being triggerred by whatever condition the environment presents. Behavior networks then are a means of specifying strategies or general "plans" in a way that merges the advantages of both abstract representations and behavior-based systems. The nodes in the networks are abstract behaviors, and the links between them represent precondition and postcondition dependencies. The task plan or strategy is represented as a network of such behaviors. As in any BBS, when the conditions of a behavior are met, the behavior is activated. Similarly here, when the conditions of an abstract behavior are met, the behavior activates one or more primitive behaviors which achieve the effects specified in its postconditions. The network topology at the abstract behavior level encodes any task-specific behavior sequences, freeing up the primitive behaviors to be re-used for a variety of tasks. Thus, since abstract behavior networks are computationally light-weight, solutions for multiple tasks can be encoded within a single system, and dynamically switched, as will be demonstrated in our implementation. In the next sections we present the structure and functionality of abstract and primitive behaviors, then the contruction of networks and their use.

Abstract Behaviors

As mentioned above, adapting specialized behaviors to general use requires separation between the execution condition and actions. We group the execution conditions and the behavior effects into abstract behaviors which have the role of activating the primitive behavior(s) that achieve the specified effects. The information about the task-specific preconditions can be automatically obtained from the behavior network preconditions-postconditions dependences and dynamically changed if networks are swtiched at run-time. This allows for obtaining multiple solutions, while using the same behaviors and maintaining the goals for which they have been designed. Thus, one of the rules of including the behavior effects into the abstract representation is to provide information about the behavior's goals and a means of signaling their achievement to other behaviors that may utilize (and in fact rely on) these effects. As with operators in a plan, behaviors can undo each other's actions while trying to achieve their own goals. In BBS, such undesirable competition is handled either by mutually-exclusive behavior execution conditions, or by the behavior coordination mechanism. In this work, we take the former approach, and use inhibition between behaviors, a common BBS tool, to prevent destructive competition. This methodology directly fits into the behavior network representations: the network topology includes inhibitory links between competitive behaviors. In our implementation behaviors run at a predifined rate and this is the rate at which they continuously check or send their inputs and outputs that we will further describe. In a discrete implementation, single activation and deactivation messages could be used per behavior, but this would not be as robust. Our system, as most BBS, uses continual messaging, in order to remain reactive to any changes that may occur (in the environment, the preconditions, etc.)

Thus, abstract behaviors (see Figure 1) receive inputs from:

Figure 1 - Structure of the inputs/outputs of an abstract behavior

Abstract behaviors have the following two outputs: Abstract behaviors continuously check a series of conditions to determine their activation level, as follows:
  1. Check the UseBehavior input to see whether the behavior is used in the current task network. If true, go to the next step, otherwise return.
  2. Check the postconditions and set the IsPostcondTrue output accordingly.
  3. Check the Inhibition input to see whether the behavior is inhibited. If false, go to the next step, otherwise return.
  4. Check the Continue input. If true, set Active to 1 and return.
  5. Check the preconditions. If met, go to the next step, otherwise return.
  6. Check the postconditions of all the behaviors in the PreconditionList. If met, set Active to 1, otherwise set to 0.
Informally, an abstract behavior will send an activation signal to its associated primitive behavior(s) if it is being used in the current controller, it is not inhibited by another competitive behavior, if its own postconditions are not yet met, and if its preconditions and the preconditions of its "predecesor behaviors" are met.

Primitive behaviors

Primitive behaviors (see Figure 2) are activated by abstract behaviors. They receive inputs from:

Figure 2 - Structure of the inputs/outputs of a primitive behavior

Primitive behaviors send outputs to: A primitive behavior will be executed if it is Active.

Network construction

From a task plan, build by a planner or constructed by hand, a behavior network can be automatically generated by connecting all the nodes in the graph whose postcondition match the preconditions of other behaviors. A backtracing process is involved in generating the topology for the behavior networks. Like a planner, the system must search backwards from the goal, linking behavior that achieve the goal and those that achieve its preconditions, and so on. Figure 3 shows a general example of a behavior network obtained from a task plan.

Figure 3 - Structure of a general behavior network with activation and inhibitory lins between abstract behaviors and activation links from the abstract to the primitive behaviors

At initialization, according to a network specification (see Figure 3), each behavior receives a list of its precursor behaviors used to specify the network topology. Once the network is constructed, whichever abstract behavior has all of its preconditions met activates its corresponding primitive behavior(s), thus initiating the system. The system will proceed by having both sets of behaviors in concurrent operation. Abstract behaviors activate (and sequence) primitive ones, and in turn, primitive behaviors can notify abstract ones about their execution. Note that this is not a hierarchical arrangement, in that both sets of behaviors depend on each other, and have the power to influence each other's execution. This also conserves the spirit of BBS systems, which do not tend to employ top-down hierarchies.

Experiments

To validate the proposed concepts, we implemented them on a physical mobile robot given an object delivery task. The delivery task consists of a mobile robot in an enclosed environment divided into two sections, separated by a swinging door. The robot must find a box, which may be in either section, and push it to the delivery point (see Figure 5). The BBS controller must accommodate various initial conditions: the robot may initially be in the same section as either the box and/or the delivery point, and the box may or may not be in the same section as the delivery point. Note that this is not a large state space, which is why it lends itself to BBS solutions, but it is sufficient versatile that it would require several different plans if pursued in a deliberative fashion. Our approach generates two networks which, together, account for all possibilities, and, as any BBS, adapts to uncertainty and changes that may occur (i.e., the robot or the box or both can be moved at any point). The experiments were performed on a Pioneer 2-DX mobile robot, equipped with two rings of sonars (8 front and 8 rear), a pan-tilt-zoom camera, a PC104 with an Intel2 processor at 233MHz and 32Mb memory. All behaviors are sensor-based; the robot uses its camera to detect the box, the door and its state (open/closed), and the delivery point.

Behavior Networks for Delivery

The solution for the delivery task was constructed by hand from the following repertoire of behaviors: Two different task plans have been developped by hand for the delivery task and have been translated into behavior networks (Figure 4) that use the behavior set above. The robot automatically switches between the networks at run-time, according to predifined changes in the robot's internal state. This is the only built-in specific information in our system; it could have been avoided if external cues that could be sensed directly were available, as described next.

Figure 4 - Structure of the behavior networks for the delivery task

It is important to notice the fact that since our networks rely on real behaviors which can handle a variety of initial conditions we do not need to have a ``plan'' and thus a behavior network for each initial condition. Our solution makes use of only two alternate ``plans'' for the four possible initial conditions. This, of course, is not the only solution for the task, but we have chosen it because it captures the important aspects of the representation that we want to validate. The robot begins with the localization behavior (the only one for which all the execution conditions are met at that point) in order to determine in which room it is. Its goal of knowing the current location is a task precondition for all other behaviors (as can be seen by the network links from Localize to all other behaviors. Once localized, the robot starts looking for the box. If it finds it within a predetermined time, it continues to execute the current behavior network. If it fails to find the box, timeout is signaled, and the robot switches to another ``plan'', represented by the second behavior network. The alternate solution is to go to the other room, and look for the box there. The same GoToDoor, OpenDoor, GoThroughDoor behaviors are used in both networks, but the conditions they are testing are different. For example, the second network need not test the status of GetBox in order to go to the door and through it, as it would if the box had been found. Another network switching condition is the completition of the alternate ``plan'' represented by the second network: when this occurs the robot switches back to its initial network.

Competitive behaviors

In the delivery task, behavior competition arises between the GetBox and OpenDoor behaviors. While the former drives the robot to the box if it does not have it yet, the latter requires pushing the box aside in order to open the door. After getting the box, the GetBox behavior is no longer active and no longer inhibits OpenDoor. When OpenDoor becomes active, it inhibits GetBox until the door is opened. At that point it deactivates and in turns stops inhibiting GetBox, allowing the robot to again find the box and take it home through the opened door.

Results

To demonstrate the validity of our representation, and the capability to dynamically switch between behavior networks, we tested the delivery task from all four different initial conditions. For each of them we ran the robot four times, in some cases with the door opened, in others with it closed. We found that irrespective of the initial conditions, the robot adapted itself to the state of the environment, activated the correct behavior network for that state, and executed its actions accordingly. We used a marker-based overhead vision system to capture the robot's movement. Figure 5 shows the trajectory (X and Y coordinates with respect to the low left corner of the enclosure) of the robot in a run for which initially both the robot and the box are in the section different from the one with the delivery point. The robot wanders around to localize itself with respect to the delivery point, then gets the box, pushes it to and through the door, and takes it to the delivery point. As another validation of the generality and a demonstration of behavior reuse that the abstract representation provides to behaviors, we have run an experiment with the opposite task of cleaning (i.e. taking the box out from the room where the delivery point is), using the same set of behaviors and a slightly changed version of the behavior networks in which for the first network we no longer need the GoHome behavior, the goal of GoThroughDoor becomes other than Home and for the second network the goal of GoThroughDoor becomes Home. Irrespective of the two initial positions of the robot and the box that we have tested (the first with both the robot and the box in the section with the delivery point, the second with the box in the delivery section and the robot in the other), the robot was able to push the box out of the delivery section.