This page contains supplementary material for the following paper:

General Notes

The supplementary material includes multi-agent animations, CHARON output, and additional descriptions. The multi-agent animations were implemented and generated using CHARON, a general-purpose tool for the specification and simulation of hybrid systems.

In the animations, actors (colored yellow) navigate around obstacles (red) to reach targets (green).

Low-level Navigation

Crowd simulation

Using CHARON, we created a simple crowd simulation animation as something of a proof of concept: This crowd simulation is similar to other animations used to demonstrate low-level navigation strategies, suggesting that a hybrid system approach is comparably expressive to standard methods. In this animation (MPEG, size: 1.1M), a crowd of actors moves from the bottom of the screen to a target at the top, navigating around a crowd of actors simultaneously crossing from the top of the screen to a target at the bottom.

Three-segment animation

In our paper, we mention a three-segment animation (MPEG, size: 1.1M) in which an agent: uses complex steering to avoid obstacles in segment 1; uses simple linear steering in segment 2; and celebrates in segment 3. The celebration consists of waiting, then moving off the final target and changing size. (We chose a simple celebration. For the purpose of demonstrating discrete transitions between behaviors, a more complex celebration would have been no more effective.)

We generated a similar animation (MPEG, size: 1.3M) to demonstrate how the agent's course would differ if it did not switch to the simpler linear steering in segment 2.

High-level Navigation

In our paper, we describe a system for high-level navigation. This short (8 sec) animation (MPEG, size: 1.28M) demonstrates that high level animation in a grid of targets, representing a grid city. Eight actors more from a corner near the lower left of the city to a corner near the upper right. All actors are instantiations of the same general strategy, just instantiated with different initial weights. As a result, they all take different, individual paths to reach their shared goal intersection. Several of them travel some path-component (i.e., "city street") more than once; this is typically because that street is so attractive (compared to other local options) that they wish to see it repeatedly. Note that not only do they all eventually emerge from these "tourist traps," but the individual actors find different locales to re-visit, depending on their individual modes and evolutions.

The goal of this animation is to demonstrate the functionality and flexibility of the strategy. We realize that it is difficult to absorb the individual paths of all eight actors in just a single viewing. To assist in recognizing paths and understanding the navigation behavior, we also present several files of text data. We know they may be a bit hard to follow; we are still working on a standardized presentation format.

A transitions file shows the various transitions among eager mode, sightseer mode, and simple-path mode that the actors make. Of particular interest is the time at which a transition is made (not pre-specified or according to any pre-determined pattern) and the agent making that transition (which is the # is the expressions that conclude each block -- for instance, the first one is about agent 3, which we know because of the 3 in "A3.top.walking.simplepath").

To make it easier to follow the multiple actors' motions in our MPEG animation, or simply to analyze their path selections without viewing the animation, we provide a text file that gives their paths in a Cartesian coordinate representation (i.e., lower left = (0,0), upper right = (7,7), etc.). In addition, we present a text representation of the virtual city that emphasizes its world-attributes. Together, these files make it easier for readers/viewers to see what paths the actors choose and the world-attributes that influence actors' choices.

In the paper, we provide a brief overview of the differential equation forms that govern the evolution of attribute weights for our actors. A comprehensive explanation of the implementation of the high-level navigation system is beyond the scope of even this supplementary material, but we do provide more detail here. In particular, we present an example high level mode from our CHARON implementation, which is further augmented by the Java code that fully describes an example differential form. We give just the one example; all other cases are similar.

Graphical output from CHARON demonstrates the evolution of weights that actors place on various world-attributes. In general, those weights are standardized to be values in [-10..10]. This graphical output file (PostScript format) from CHARON shows the evolution of the weights for agent 1 in the high-level animation presented above. The two sudden, jagged changes in weight values correspond to mode transitions (at roughly 3 units and 11.15 units of simulation time into the animation, respectively, according to the transitions file). The flatlines just before 15 units of time indicate that the agent reached its final goal; the system then essentially stopped.

Verifying collision-avoidance for a race-style game

As reported in the paper, we specified the rudiments of a race-like game in the hybrid system model checking tool HyTech.

Our game contains three agents, two racing actors and one obstacle, each moving at constant speed around a square, two-lane track. The rules of the race encode that each actor (naturally) prefers to race on the inside lane, and must do so whenever possible. Because one racer is slower than the other and the obstacle is slower than both, racers may move to the outside lane to pass slower agents, moving promptly back to the inside lane when they are done passing.

Consider an infinite race, an endless execution of this animation system. Will the two racers ever collide? As described in the paper, collisions were indeed possible the way we specified it in HyTech. We thought we had specified collision-avoidant behavior, but HyTech demonstrated our mistake.

We here present an animation (MPEG, size: 2.3M) of a system similar to the one we specified in HyTech. As with our other animations, we generated this by specifying and simulating an animation system in CHARON and then supplying the simulation output (in altered form) to a graphical viewer. The CHARON specification of the race, however, differs in significant ways from the HyTech one. The racers in CHARON are spheres, not cubes. Further, due to differences in the specification languages of HyTech and CHARON, racers in our CHARON animation do not collide; it would have required significant contrivance to create collisions in the CHARON animated race.

Even though this animation system is not completely identical to the one we implemented in HyTech, it does demonstrate a closely related race-like scenario about which we can reason using logics of hybrid systems.

For curious readers, we also present the HyTech trace that we did not include in our paper. By manually backtracking through the trace, we can expose aspects of our HyTech system, such as the location where a collision occurs. The trace displays values of certain variables (x1, y1, etc.) at certain times in the race-system execution; a full explanation of how to interpret the trace is beyond the scope of this supplementary material.

Back to Eric Aaron's home page
Eric Aaron, eaaron@cs.rutgers.edu