Efficient multi-agent path planning

Abstract. Animating goal-driven agents in an environment with obstacles is a time consuming process, particularly when the number of agents is large. In this paper, we introduce an efficient algorithm that creates path plans for objects that move between user defined goal points and avoids collisions. In addition, the system allows “culling ” of some of the computation for invisible agents: agents are accurately simulated only if they are visible to the user while the invisible objects are approximated probabilistically. The approximations ensure that the agent’s behaviors match those that would occur had they been fully simulated, and result in significant speedups over running the accurate simulation for all agents