Motion Planning of Multiple Agents in Virtual Environments using Coordination Graphs

Motion planning of multiple mobile agents in virtual environments is a very challenging problem, especially if one wants to plan the motions of these agents in real-time. We propose a two layered approach to plan motions of multiple mobile agents in real-time. The mobile agents are moving in a 2-dimensional static environment with open spaces connected to each other by narrow corridors. The global path of each agent is computed by a decoupled planner during the preprocessing process with minimum delay. Each agent’s local path is generated in real-time by combining steering behaviors and a new, principled and efficient AI technique for decision making and planning cooperative multi-agent dynamic systems, Coordination Graph (CG). With CG, we can not only avoid deadlocks in narrow corridors, but also achieve more complicated behavior such as leader-and-followers behavior. We show, via some preliminary examples, real-time performance of our approach, for instance, several robots avoiding deadlocks and successfully navigating a corridor.

I. Introduction

Virtual environment is widely used in computer entertainment, where multiple agents are moving around in the virtual environment and their motions have to be coordinated. There are two different planning frameworks one can use to solve motion planning problems, centralized planning and decoupled planning. In centralized planners, all agents are considered to be part of a robotic system with many degrees of freedom. These planners have difficulties (in that the run time is impractically slow) to solve motion planning problems of multiple agents when the number of agents is much larger than 36 [1]. If a number of agents behave as a few coherent groups, one can plan motions of a larger number of agents by modeling each group by a deformable shape and planning global motions of the deformable shapes instead of individual agents [2]. Probabilistic roadmap method (PRM) [3] is then used to plan the global motions of the shapes. Local motions of the agents inside a deformable shape are determined by group potential fields. However, one cannot always assume that most agents in the virtual environment behave as coherent groups. Decoupled planners plan the motions of all agents individually and then try to coordinate the motions over time. Therefore, it is relatively easier to plan motions of a large number of agents with decoupled planners. Virtual environments used in computer entertainment are often generated by computer. When a new virtual environment is generated, it could take a few minutes to build roadmap using a centralized planner, such as PRM, for multiple agents. In [2], running times for completion of the roadmap building range between 6.5 seconds and 19.1 seconds for one of the four test scenes (tree path) depending on chosen sampling technique. For a computer game, delays longer than a few seconds in the preprocessing phase are not acceptable. Decoupled planning techniques are generally faster than centralized planning, however, they are not complete and may fail to return valid paths for all agents due to deadlock.