Adapted from a presentation given at the

AAAI Workshop on Robots, Softbots, Immobots:
Theories of Action, Planning and Control

Providence, RI    July 28, 1997
Contents:
Title
Reactive Agents
Nonlinear Dynamics
Phase Portraits and Basins of Attraction
Concepts
Activity Maps
The Simulator
Behavior Maps
Interaction Maps
Planning With Interaction Maps
Summary
slide 1 (contents)

Action Representation, Prediction
and Concepts



M.T. Rosenstein, P.R. Cohen, M.D. Schmill,
and M.S. Atkin



Experimental Knowledge Systems Lab

and

Interactive Intelligence Lab



Computer Science Department
University of Massachusetts, Amherst



As this title suggests, the focus of my talk is action representation. This work is just a piece of a larger puzzle about agent control, and so I'm not too concerned at this point about any specific agent architecture. For now, my goal is to provide some ideas about how to represent and utilize information from dynamic environments.
slide 2 (contents)

Reactive Agents


  • Enhancements:

  • Current work:



    Whether or not we settle on what's most important for agent design, I think we can agree on two things. In complex environments, effective agents must interleave things like action, sensing and goal selection. And in doing so, we want our agents to take advantage of knowledge. This requires the agent to have a conceptual structure about the environment.

    It's possible that the entire conceptual structure is built by the agent designers -- as in a subsumption architecture built entirely from pre-engineered behavior modules. Another possibility is to place some of the burden on the agent, and so I'd like to add the ability to learn from successes and failures. In other words, an agent should gain knowledge through interaction with its environment.

    Now part of my training is in nonlinear dynamics (NLD), so I'm especially interested in how agents acquire concepts about dynamics. And so for this work, I borrowed some ideas from NLD and developed representations called activity maps. My thesis for this talk is that activity maps are in fact concepts about dynamics.

    slide 3 (contents)

    Nonlinear Dynamics



    So what is NLD? One simple definition is that NLD is all about the behavior of nonlinear systems. Here, "system" refers to a set of rules that describes the changes in a corresponding set of state variables, such as velocity or actuator position. If we think of the state variables as the axes of a state space, then the system is like a particle moving through that space. And so "behavior" then refers to a characteristic pattern of the particle's trajectory.

    So why look to NLD for ideas about agent design? Well, perhaps the most compelling reason is that effective agents are dynamic. We often describe such agents with words like "interact, situated, plan" and "learn." These words describe ongoing processes where things change in accordance with a set of rules. Put simply, agents are dynamical systems.

    slide 4 (contents)

    Phase Portraits and Basins of Attraction


    basins


    For such a short presentation I'd like to avoid as much jargon as possible, but I should at least say a few words about phase portraits and basins of attraction.

    Phase portraits show one or more representative trajectories of a system through space. Essentially, a phase portrait captures a system's behavior and shows spatial patterns as well as temporal ordering. Such portraits make time implicit and place the emphasis on geometry. So to paraphrase the old saying, the idea behind phase portraits is that a picture is worth thousands of data points.

    Now some systems favor certain states called limit sets or attractors. Once we know about attractors, we also know about long-term outcomes. Similarly, a basin of attraction is just the set of states that lead to a particular attractor. So once we know about basins of attraction, we also know how to predict these long-term outcomes.

    As an example, I sketched a hypothetical phase portrait with a dozen or so representative trajectories. The two closed circles are the attractors and the regions in blue and green are the basins of attraction. So for example, if we find that the state of the environment falls in the blue region, then we predict the future occurrence of the state shown by the left-hand circle.

    slide 5 (contents)

    Concepts


    concepts


    As I suggested a few slides back, a conceptual structure is an important consideration for agent design. The working definition that I'd like to put forth is that "concepts are abstractions of experience that confer a predictive ability for new situations."

    There seems to be a natural distinction between two aspects of concepts: recognition and prediction. Recognition sets the stage for reasoning about categories and outcomes. It's like an abstraction process from raw observations to "situations." The second aspect is prediction -- where we make plausible inferences about "things that matter." "Things that matter" is just my catch-all phrase for both rewards and for interesting categories or outcomes.

    In some sense, recognition and prediction may be much the same process, since both involve an abstraction of some available data. The difference may be one of timing. Recognition occurs after a short-term observation, whereas prediction is for a long-term outcome that has yet to happen.

    slide 6 (contents)

    Activity Maps


    activity maps


    Now to bring all of this together -- phase portraits, basins of attraction, and concepts -- I propose a form of action representation called activity maps. Here I duplicated the schematic from the previous slide except I replaced recognition with behavior maps and prediction with interaction maps.

    Both types of activity maps are abstractions of sensorimotor experience. Behavior maps, like phase portraits, capture the state space patterns due to short-term behavior. Interaction maps, on the other hand, show long-term outcomes much like plots that show basins of attraction.

    slide 7 (contents)

    The Simulator

    screen shot
    (A Java version of the simulator is available.)


    To get some idea about the usefulness of activity maps, I developed a simple simulator. The two agents in this simulator were modeled after billiard balls that roll around on an infinite plane. The difference is that our special billiard balls can produce accelerations in response to the relative position and velocity of an opponent. The acceleration programs were hardwired into the simulator, and so you can think of these agents as Braitenberg vehicles with one of several possible behaviors. This screen shot shows two of the agent types in action. The red ball is a crash type that tries to contact its opponent, while the blue agent executes the avoid program and tries to escape.

    Next I'd like to give you a better feel for activity maps, and I ask that you have a look at the paper if you're interested in the implementation details or the quantitative results.

    slide 8 (contents)

    Behavior Maps


    avoid map crash map


    This slide shows the behavior maps for two of the possible agent types. The axes are labeled "proximity" and "divergence." Divergence is simply "relative velocity," or the first derivative of proximity. And so a point in one of these maps tells you how close the agents are to each other and whether they're getting further apart. The color gives an indication of an agent's attempt to change the distance between itself and its opponent: green for an attempt to increase the gap, and red for an attempt to make contact. As an example, the avoid program makes its greatest attempt when proximity is "near" and divergence is "closing." The crash agent has roughly the opposite behavior. Dark regions in both maps show relatively weak attempts, and white regions denote unobserved states.

    Now these maps were all built up over time by observing an agent interact with its environment. (For the current work the environment was very simple, but this approach could be helpful for more complicated domains.) So once you compile a library of behavior maps, you can make some sensor readings and compare those readings to the patterns contained in the library. The behavior maps that give the best match tell you what circumstances are at play. For the billiards simulator, this means you can recognize which agent types are the current participants. This then sets the stage for reasoning with interaction maps.

    slide 9 (contents)

    Interaction Maps


    crash & avoid map
    crash & avoid- map crash & avoid+ map


    Interaction maps are also built up over time. But now, the maps are colored by outcome rather than the acceleration of a particular agent type. For example, the upper plot gives a picture of the interaction of a crash type with an avoid agent. Whenever the agents find themselves in, say, a green cell, the interaction will end in a no-contact outcome unless one of the agents makes a special effort to change the current circumstances. For instance, the spiral trajectory represents one observed interaction where the agents settled in a state with zero divergence and non-zero proximity. This outcome is labeled "chase" because that's just how it looks when you watch the simulation in real time.

    The two lower plots show what happens if we change the intensity of the avoid agent. In the weak case (AVOID-), most of the map is red. This means that most combinations of proximity and divergence eventually end in contact. In the strong case (AVOID+), the avoid agent escaped in every observed interaction.

    slide 10 (contents)

    Planning With Interaction Maps


    planning maps


    Since activity representation was the focus of this work, the current simulator doesn't include any sort of planner. Instead, it has an external observer that tries to recognize the interaction type and predict the outcome. Given the encouraging results from activity maps, it would be an easy matter to turn this observer into a simple planning system. Such a planner could use interaction maps for two qualitatively different approaches to reactivity: state perturbation and parameter adjustment.

    As an example, consider the above maps from the previous slide, and imagine that I'm a weak avoid agent interacting with a crash type. This means that the map on the left represents the current circumstances. Now suppose I take some sensor readings and figure out that the current state of the world puts me at the point labeled A. As an avoid type, I'm clearly in trouble. Unless I react to the situation, I'm doomed to making contact with the crash agent.

    So I've got two choices. First, I can try to jump myself into a green part of the map such as the point labeled B. One way to do this might be to cut behind an obstacle that would slow my opponent just long enough to make a getaway. You could think of this in terms of subsumption: a short-term action temporarily interrupts my usual behavior. The other option is to change how I behave for the remainder of the interaction. I could crank up my intensity and bring another map into play. Without perturbing the current state I could put myself in the safe region as shown by the point A'.

    slide 11 (contents)

    Summary



    So one obvious drawback of this work is that I only have results for a simple simulator. Fortunately, our lab recently acquired a couple Pioneer mobile robots, so future work will involve a physical platform. Another drawback is that the activity map axes -- proximity and divergence -- were predetermined. An actual robot has many state variables and we want an abstraction, or low-dimensional projection of the high-dimensional state space. As one possible solution to this projection problem, Matt Schmill at UMass has done some promising work using decision trees to prune state spaces.

    Despite these, and possibly other drawbacks, activity maps do provide some insight about how an agent might build a conceptual structure of dynamics. Activity maps are also attractive because they can be built incrementally as an agent interacts with its surroundings. This could even be done in simulation before placing a robot in a potentially harmful environment.

    Now I have to admit, without modification, I don't think activity maps will scale up for use with a real robot. For this reason, I'm considering a variation called "experience maps." Experience maps are similar to activity maps, except that they use both state variables and actions for the axes. You could think of experience maps as vector field plots that show the change in state as a function of context and action.

    Finally, I'm most excited about the possibilities for combining dynamics with more traditional AI. There's a growing body of work using NLD and connectionism, side-by-side with symbolic methods. And another possibility is spatial aggregation, which could prove helpful in converting maps from spatial patterns to symbols.


    Copyright (c) 1997 Michael T. Rosenstein. All rights reserved.
    Home Pages: UMass | CS Dept. | ANW | MTR 
    Updated 26-May-99
mtr@cs.umass.edu