Our one year of research addressed multiagent motion planning. We distinguish high- and low-level aspects of motion planning. The low-level aspects involve laying out paths with explicit metric properties. The high-level aspects involve task structures, agent intentions, and generally more abstract features. Our goals were to extend the low-level implementation we had begun, translate C code to Java, address high-level planning, and integrate high- and low-level aspects as much as possible. We held weekly meetings to formulate algorithms and to review code. Standard sources on planning were consulted.

Starting with the low-level aspects, path planning is handled differently in static and dynamic environments. When we began, we had already implemented in C a significant part of a visibility-graph approach to static path planning. This code has been completed and most of it has been translated into Java. We also completed Java code for dynamic environments where objects have constant linear motions. This code used an accessibility-graph approach. A start has been made on a graphical user interface for the dynamic case.

We have developed algorithms for special cases of multiagent path planning, which apply in the first instance to static environments. We assume that agents are associated into groups. All the agents in a group are assumed to have start and destination points near to each other and to move in roughly the same directions (generally linear) with roughly the same speed. We also assume that the environment is sparse, that agents are prioritized within groups, and that the groups are prioritized among themselves. We approach such a problem hierarchically. For each group, we find a rectangular envelope with a constant linear motion that encloses all the agents throughout. This envelope should be as small as possible. After the paths of the individual agents are computed (disregarding the other agents), collisions among agents within a group a found. A collision between two agents is resolved by delaying the agent with lower priority just enough to avoid the collision. Once all collisions within groups are resolved, the possibility of collisions between agents in different groups is eliminated by resolving collisions between pairs of envelopes. When two envelopes collide, the envelope corresponding to the group with the lower priority is delayed just enough to avoid the collision. This delay is added to the delays already imposed on its members. The generalization of this approach to dynamic environments can be done rather straightforwardly by treating obstacles as highest-priority agents.

For high-level aspects of motion planning, we have worked with Statechart representations of multiagent plans that are being used in Dr. Esterline's research. We have written Java code that interprets the concurrent behavior of a system of agents which have been assigned roles in a plan Statechart. The code exploits Java's monitors.

Not much progress was made on integrating high- and low-level aspects of motion planning. The key to this integration would appear to involve developing ways for high-level decisions to impose constraints on the low-level planning algorithms. It would also be helpful to have some way to classify low-level configurations in ways that are meaningful to a high-level planner.

We feel fortunate that we took an incremental approach with a topic with which we already had some experience. Motion planning was found to be an excellent topic for advanced undergraduate research. It is manageable yet offers unlimited opportunities for developing sophisticated techniques.

We presented our research at the North Carolina Alliance for Minority Participation Conference (North Carolina Central University, Raleigh) in April. We also have a paper in the Proceedings of the NASA ACE/PURSUE Student Conference, also held in April.