Jamie Snape and Dinesh Manocha
Department of Computer Science, University of North Carolina at Chapel Hill
We present the goal velocity obstacle (GVO) for the spatial navigation of multiple autonomous robots or virtual agents, such as are found in mobile robotics, video games, and simulated environments, to planar goal regions in the two-dimensional workspace. Our approach uses the notion of velocity obstacles not only to compute collision-avoiding velocities with respect to other agents, but also to specify velocities that will direct an agent toward its spatial goal region. The goal velocity obstacle provides a unified formulation that allows for goals specified as points, line segments, and bounded, planar regions in two dimensions that may be static or moving. An agent may have multiple goal regions without requiring an explicit goal allocation algorithm that would choose a particular goal region to navigate toward in advance. We have applied our approach to experiments with hundreds of agents, demonstrating shorter path lengths and fewer collisions with only microseconds of additional computation per agent per time step than when using velocity-based methods that optimize on a single, preferred velocity toward the goal of each agent.
Multiagent planning; motion planning; robot coordination; collective behaviors; implicit cooperation.
Jamie Snape and Dinesh Manocha, "Goal velocity obstacles for spatial navigation of multiple autonomous robots or virtual agents," Autonomous Robots and Multirobot Systems, St. Paul, Minn., 2013.
Jamie Snape and Dinesh Manocha, "Goal velocity obstacles for spatial navigation of multiple virtual agents," extended abstract at 12th Int. Conf. Autonomous Agents and Multiagent Systems, St. Paul, Minn., 2013.
This work was supported by ARO under Contract W911NF-04-1-0088, by NSF under Award 1000579 and Award 1117127, and by Intel.