Real Time Motion Planning Of Multiple Agents And Formations In Virtual Environments PDF Download

In this thesis, we studied the problem of real-time motion planning of multiple agents and multiple formations in virtual environments and games. In many such applications, agents move around and their motion must be planned. We are especially interested in motion planning in Real-time Tactical (RTT) games because they offer a challenging problem setting due to the following aspects: multiple agents, real-time, dynamic obstacles, complex environments, coherence of the agents (e.g., formations), and inexpensive pre-processing. We use the (basic) continuum model (a real-time crowd simulation framework based on the Fast Marching Method (FMM)) extensively in this thesis, because it unifies global planning and local planning (e.g., collision avoidance). Since the basic model may fail to generate collision-free paths in certain constrained situation (e.g., when agents pass through narrow passages) due to deadlocks amongst the agents, we propose to use a principled and efficient AI technique for decision making and planning (i.e., Coordination Graph (CG)) to avoid such deadlocks in the narrow passages. Next, we present the adaptive multi-resolution continuum model to plan motion of multiple agents. It allows each agent to have its own goal compared to the basic model, where agents have to be grouped into a few groups, while retaining the advantages of the basic model. Finally, we present a flexible virtual structure approach to the multi-agent coordination problem. The approach conceives of agents in a formation as if they lie on an elastic shape, which is modeled using the Boundary Element Method (BEM). Due to the BEM's boundary-only nature, even a formation with a large number of agents can be deformed in real-time. This approach for formation control is then combined with the continuum model to plan motion of multiple formations in virtual environments. To the best of our knowledge, this motion planning algorithm for multiple formations is the first one that does not use ad-hoc and local approaches and hence agents in a formation do not split easily from the formation. We believe that these three algorithms can be used as basic motion planning toolkits toward enhancing the capabilities of RTT games.