|
Rene presents an approach to programming reactive situated agents that's based on parallel functional decision trees. In the process, he introduces "InSitu," a C++ class library and run-time system he's developed and tested on mobile robots.
April 01, 1999
URL:http://www.drdobbs.com/cpp/parallel-functional-decision-trees-for-s/184410910
Rene completed his Ph.D. in computer science at the Artificial Intelligence Laboratory of the University of Zürich, Switzerland. He can be reached at schaad@ ifi.unizh.ch.
A "situated agent" is a controller located in a dynamic, complex, and relatively unstructured environment. Situated agents can be either hardware or software (or both). Software is almost always involved; hardware is needed to complete the agent if its environment is physical. Hardware then plays the role of the interface, although it can also be a part of the computation itself. Typical hardware-based situated agents include mobile robots, autonomous underwater vehicles, intelligent rooms, and the like.
Pure software situated agents, on the other hand, are located in virtual worlds. A software-based situated agent's environment is logical instead of physical. The interface consists of communication interfaces to this logical environment -- one that is dynamic, unpredictable, large, and complex. Situated software agents include load balancing in telecom networks, and virtual characters in storytelling systems and games.
In general, agents attempt to achieve a multitude of goals by interacting with their environment via their sensors and actuators. The goals are often in competition with each other, and it is up to each agent to autonomously find a way to deal with the conflicts that ensue. This is a difficult task. The complex and dynamic nature of the environment has the effect that the agent:
An agent must act coherently if it is to achieve its goals; that is, its actions must consistently lead toward its goal (if the agent is a mobile robot, for example, reaching a particular location in the environment). On the other hand, the agent must remain responsive and react appropriately to unexpected events that occur in the environment (for instance, if unexpected obstacles occur in the robot's path). However, it is usually impossible to devise rules for conflicting goals such as these, without assuming perfect knowledge and planning. To deal with this problem, designers of situated systems must be given tools to represent reactive rules as well as coherent actions in their plans (sequences).
Because an agent does not usually have all the information it needs, it must act to gain information (as opposed to acting to reach its primary goals).
Finally, using instructions sensibly in a given situation involves checking whether or not the application of these instructions makes sense (guarded interpretation) and in what way they bear upon the current situation (context-dependent interpretation).
Due to a shift of emphasis in this field from building disembodied minds (chess players, for instance) to creating more embodied forms of intelligence ("elephants," as described by Rodney A. Brooks in "Elephants Don't Play Chess," Robotics and Autonomous Systems 6, 1990), these types of control problems have recently gained interest in the field of Artificial Intelligence (AI). The effect of this shift is that some areas of AI have begun to overlap aspects of embedded-systems programming.
Many areas apply and test techniques from situated-agent design. Probably the most recognized area is that of mobile robotics. NASA's Sojourner Mars rover has arguably been the most prominent (semi-autonomous) situated agent in recent years. But there are also other more down-to-earth applications -- network load balancing, intelligent rooms, intelligent artificial creatures for virtual reality, and more.
In this article, I will present an approach to programming reactive situated agents that is based on parallel functional decision trees. In the process, I will present "InSitu," a C++ class library and run-time system for situated agents that addresses the aforementioned problems and requirements. An alpha version of InSitu is available electronically; see "Resource Center," page 5. This early version of InSitu is written in Watcom C++ for the QNX 4 real-time operating system.
In my approach to the problem of programming reactive situated agents, the first design decision I made was to implement a reactive run-time system in C++ and then create C++ classes to add functionality for coherence, active perception, and situated instruction use. The result was InSitu. Most environments for embedded systems are designed the other way around -- they use a sequential programming language (such as C++) and add multithreading, interrupt, and event-handling mechanisms to achieve reactive behavior in that sequential (coherent) framework.
InSitu was developed and tested on a mobile robot called Rufus T. Firefly (see Figure 1 and http://www.ifi.unizh.ch/ailab/projects/rufus/) that was tasked to patrol a floor in an office building and report human intruders back to a base station via a radio link. I have found InSitu to be a modular, efficient, and robust tool for the development of control laws for this type of situated agent. The decision tree-based architecture is particularly well suited for the incremental and fast development of situation-dependent control rules.
A run-time system for reactive situated agents (or any embedded system) may be implemented according to one of two types of execution models. The system either uses interrupts to produce events, which then steer event loops, finite state machines, and other such constructs to control the agent; or the system may regularly poll its sensors, categorize the sensed situation, and produce outputs accordingly. Mainly for efficiency reasons, most systems use an event-driven approach. However, in the AI arena, situated agents are most often based on polling. The AI community has adopted the rather general term "reactive systems" for these types of polling-based situated agents so that they can be distinguished from traditional AI planning and control systems that emphasize coherence over reactivity and are often rather unresponsive.
Control following the polling-based execution model, which I will call the "stepped execution model," proceeds in a loop with three steps:
1. Based on sensor readings, a simple internal model of the environment is updated.
2. The state of this model is categorized into one of a number of situations. A situation is a set of states.
3. The situation is mapped to some actuator output, and the loop recommences.
It is important that the types of modelings and mappings that are employed in this loop be limited to those that can be computed incrementally during the time of one loop, and that outputs are produced at each incremental step. Long or unpredictable computation times must be avoided. Algorithms based on lookup tables, neural networks, fuzzy logic, or decision trees are ideal candidates for this type of computation.
At first glance, polling seems to be a bad choice. Event-driven control is usually more efficient because computations are carried out only when important events happen. In addition, by employing multitasking, other tasks can be tended to if no events are being processed, thereby taking full advantage of each processor cycle. Event-driven control is also more convenient to program because it is usually not necessary to divide the computation into short incremental steps. When an event occurs, all the computation associated with that step is carried out at once; long running processes are automatically sliced by the multitasking mechanism.
However, polling has a critical advantage. Interesting events in the environment cannot always be assumed to be producing events because, as I've outlined earlier, a situated agent does not have continuous access to all the important information. Hence, it is not sufficient for the agent to passively react to events and create outputs only in response to these events. It must pursue the acquisition of information. Furthermore, it must produce actuator commands at regular intervals even if nothing interesting has happened. Event-driven execution is okay for passive reactive systems that have constant access to all relevant information, but polling is necessary for systems that must initiate action or deal with incomplete information.
An execution system for this model can seem almost trivial. It consists of a loop with a call to the input (sensors to input buffers), mapping (input to output buffers), and output functions (output buffers to actuators), with a delay statement. All the interesting computations take place in the mapping function.
The most important abstraction in InSitu is "Steppables" -- objects that encapsulate mapping algorithms executed in a step-wise fashion, but produce coherent sequential behavior over the course of many steps. Thus, Steppables are designed to address the coherence-reactivity problem. According to Erich Gamma et al. in Design Patterns: Elements of Reusable Object-Oriented Software (Addison-Wesley, 1995), encapsulating algorithms in objects follows a design pattern called "Strategy" and serves to make different algorithms compatible and interchangeable. Steppables are implemented as classes derived from the abstract class Steppable, which defines their basic interface. This interface consists of the Step, Reset, Abort, and IsDone member functions:
Data *Step(void);
void Abort(void);
void Reset(void);
Fuzz *IsDone(void);
The Step member function advances the algorithm by one step, produces side-effects to other Steppables and returns a result to the caller. Reset and Abort set the algorithm's progress to its beginning and end, respectively. IsDone returns a fuzzy Boolean value, indicating the algorithm's status (either it has not yet started, it is in progress, or it has terminated). A stepped algorithm may take an arbitrary number of calls to the Step member function for its completion. Thus, Steppables offer support for combining reactive and coherent aspects of execution by uniting the stepped execution model with the abstraction of sequential algorithms.
As an example, consider TimedIf, a Steppable from the InSitu class library:
Steppable *a = new TimedIf
(Steppable *cond,
Steppable *then,
Steppable *else,
int stick_delay);
TimedIf is a class derived from Steppable. Its purpose is to encapsulate the following behavior: On each time step (that is, on each call of the run-time system to TimedIf's Step member function), TimedIf calls the Step member function of the Steppable pointed to by the constructor's argument cond. If that call returns a Data object of type Fuzz (a kind of fuzzy Boolean value), and if that return value evaluates to a true statement, the Step function of the Steppable pointed to by then is executed. Otherwise, the Step function of else is executed. In addition, after a successful execution of cond's Step function, a countdown timer is initiated to stick_delay milliseconds. While this timer is running, then's (rather than else's) Step function continues to be executed on each consecutive time step. Hence, TimedIf implements a kind of debounced if statement.
TimedIf is an example of a Steppable intended to produce actions by calling another Steppable's Step functions. These types of Steppables are called "Action-Steppables" and are derived from the abstract class Action, which is itself derived from Steppable. Aside from Action-Steppables, there are also Data-Steppables, intended to passively store data. To this end, each Data-Steppable has a Step member function that does nothing more than return a pointer to itself. Abort and Reset are degenerated functions that do nothing, and IsDone always returns a pointer to a Fuzz object, which evaluates to True. In addition to the standard interface, Data-Steppables add functions for duplication, printing, accessing instance variables, and managing run-time type information. Data-Steppables may be passed around between Action-Steppables as results or parameters. They may be used in place of Action-Steppables (because their interfaces are compatible), and they may be used from the InSitu Script (ISS) online instruction compiler.
Programming in the stepped-execution model can be tedious. Steppables are intended to make this task easier by providing a uniform framework, a run-time system, a uniform set of interface functions, and a library of premade components for developing, assembling, and running such stepped programs. Furthermore, Steppables can be dynamically allocated, deleted, inserted, and removed from a running program. InSitu uses this feature to allow the ISS compiler to add and remove parts of a program at run time. Finally, using objects to encapsulate algorithms allows multiple copies of the algorithms with different local states (for example, multiple copies of TimedIf with different values of the countdown timer). These are the advantages of implementing stepped algorithms as objects instead of plain functions.
The constructors of Steppables accept pointers to other Steppables as arguments. These pointers are kept in instance variables and are used by the objects' member functions (Step, Abort, Reset, and IsDone) throughout their lifetimes to access the referenced objects' member functions. In this way, nested structures of Steppables referencing other Steppables can be constructed at run time by allocating and cross-linking objects.
In essence, assemblages of linked Steppables implement a kind of decision tree. Indeed, each Steppable itself can be thought of as implementing a part of a decision tree, called a "decision subtree." In this analogy, the root of a subtree implemented in a Steppable is represented by the call to its Step member function. The leaves of the subtree, which are at the same time the roots of connecting subtrees, correspond to the exits of the Steppable. An exit of a Steppable is a pointer to another Steppable that is passed to its constructor. In other words, the exits of a Steppable are those arguments in its constructor that are pointers to other Steppables.
But Steppables are not pure decision trees. They are enhanced in several ways. Their first enhancement concerns their decision functions -- the functions in the nodes of the decision tree that select one of the branches for traversal. In simple binary decision trees, this function is a Boolean expression, such as door == open. Depending on the outcome of this expression (True or False), one of the branches emerging from that node is traversed, and execution continues at the node at the end of that branch.
However, the problem with this approach in situated agents is that it is generally not known whether the decision function (door == open) evaluates to True or False, as the agent will simply not have sufficient information to answer this question. Thus, it is necessary to allow the agent to answer the question by interacting with the environment (active perception). Since Steppables control interaction with the environment, the decision function itself must be implemented as a decision subtree consisting of Steppables. From this, several requirements for the so-called parallel functional decision trees follow:
All of these requirements are met by Steppables, which, in effect, implement subtrees of parallel functional decision trees.
Example 1, a simple reactive program implemented as a collection of decision trees, is a fragment of a C++ program that allocates five objects which are all derived from the abstract class Steppable: StickyIf, BumpedQ, Prog, Moveby, and Turnby. It is a simple solution to the problem of getting a mobile robot around an obstacle. The program basically says: If you get bumped against an obstacle, perform the following steps to completion: Move the robot backwards by 0.1 meter, and then turn the robot by 90 degrees to the left. After this, or if the robot is not bumped against an obstacle, continue with the decision tree pointed to by do_the_other_stuff as a control program. The_robot is a pointer to a plant proxy; that is, an object representing the controlled robot that handles all input and output. The plant proxy is also derived from Steppable.
After the assignment, unbump is a pointer to a parallel functional decision tree consisting of a number of objects derived from Steppable, which can be stepped to execute the desired actions. This is usually done by passing unbump to the run-time system, which then inserts it into a larger decision tree in a suitable spot.
Remember that even though this fragment looks sequential and each Steppable controls a sequential process, it is executed in a purely reactive, step-wise manner. The Steppables serve to reintroduce sequentiality and coherence into a basically reactive scheme. To this end, they store the local sequential state that survives calls to their Step functions; that is, the Prog class (a member of the InSitu standard class library) is designed to execute its exits in sequence. This means that when Prog is stepped, it propagates the call to one of its exits. Each exit keeps being stepped until its IsDone methods returns True, indicating its completion, at which time the program counter in Prog is incremented to the next exit. After stepping all exits (in the example a Moveby and a Turnby object), the default exit (in the aforementioned example set to NULL) is stepped until a call to Prog's Reset function restarts the sequential process. Similar classes exist in InSitu's class library for loops, sequences with conditional increments, finite state machines, and many other temporally coherent types of behaviors.
Decision trees classify data. When decision trees are used to control an agent, their purpose is to classify the state of the world as they encounter it and assign programmed actions to this class of world states. I'll call classes of world states "situations." With decision trees, this classification is recursive; that is, each branch in the decision tree adds accuracy to the classification, and the number of states in the resulting situation decreases with each branch. Each node in the decision tree thus corresponds to a particular situation in the world. By attaching a decision subtree to a particular node in the tree, you tell the system that this subtree implements a good strategy for this particular situation. Hence, when an agent stops being used, and another more appropriate one is used.
Another way of looking at Steppables is that they allow you to provide a prefabricated system decision tree, called a "default tree," where a situated agent defines a default classification, and thus a default behavior. You may then incrementally add decision trees to handle certain situations differently, or add new distinctions to handle subsituations in different ways. This possibility of incrementally adding modular handlers for situations is a powerful tool for building reliable situated agents.
With InSitu, it is even possible to add such handlers (also known as "decision trees" or "clusters of Steppables") during the run time of the system. The InSitu Script (ISS) compiler is an object within the InSitu run-time system that accepts commands from an online user during run time via a number of input channels (for instance, a wireless radio link on a mobile robot). ISS's syntax is based on LISP. But in addition to pure LISP functions, InSitu also provides a mechanism called "factory functions." Factory functions allocate new Steppables inside the InSitu system. Other system functions allow you to add or remove these allocated Steppables to and from the running system; see Example 2.
The first nested call to the LISP functions creates a nested cluster of Steppables. Each of these LISP functions (except for setq) is a factory function that creates an object of the corresponding type and returns a reference to that object. The resulting reference is stored in the LISP variable y. The function calls (Do y "some location") and (Stop y) insert and remove the new subtree into and from the default decision tree at a location designated with a so-called "Dock-Steppable," which bears the name "some location," respectively. Dock-Steppables are specifically designed to serve as named location for subtree insertion. All Docks in a system are managed by a Dock manager object.
In this way, a running system may be changed and its dynamic behavior debugged by observing its actual interaction with the real world. ISS can also be regarded as a high-level command language for real-time man-machine communication.
Decision subtrees are able to return data to their callers (functional extensions). This facility was introduced to allow decision functions to acquire information through action (that is, through active perception) and use this information to select branches in decision trees. This type of active perception is often said to be about achieving knowledge goals. It is the goal of the agent to gather knowledge. But there is also another type of active perception that is supported by this mechanism -- symbol registration. InSitu uses objects called "Markers" (a type of Data- Steppable) as references to objects in the real world. For instance, an object storing the coordinates of a dog in the camera image of a mobile robot might be such a Marker. Markers must be registered and tracked -- their initial and changing values must be determined. Both registration and tracking may involve actions; for instance, it might be necessary to pan the robot's camera, turn its base, or move forward to keep the dog in its field of view. InSitu has Steppables to support both registration and tracking.
The programs to implement such registering and tracking behavior are, of course, also implemented as Steppables, and the results (the markers) are communicated to their callers as return values of their Step member functions.
A number of ideas for extending or modifying this scheme, however, have come up as well. For example, decision trees are an ideal basis for a development environment based on visual programming. But to support visual programming, the representation of the decision tree structure should be separated from the Steppables responsible for the executable code. Currently, the representation of the decision tree structure, the traversal algorithm for the decision tree, and the representation of the executable code are all the responsibility of the Steppables. To have better access to these data structures, visual programming would require the separation of these responsibilities. Furthermore, ideas are in the pipeline for languages based on the aforementioned ideas, for the integration of planning algorithms (automatic program generation), and for natural language interfaces based on the types of active perception reported here.
Parallel functional decision trees as implemented by InSitu are a simple yet powerful way to program reactive situated agents. It tackles problems of the coherence-reactivity trade-off and of active perception in a pragmatic way, and offers a modular and efficient programming paradigm.
DDJ
Steppable *unbump =
new StickyIf(
new BumpedQ(the_robot),
new Prog(
NULL,
new Moveby(the_robot, -0.1),
new Turnby(the_robot, PI/2)
),
do_the_other_stuff
);
(setq y
(StickyIf
(BumpedQ)
(Prog
(Noop)
(Moveby -0.1)
(Turnby 1.7)
)
(Noop)))
(Do y "some location")
(Stop y)
Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.