Way Portals:
Efficient Multi-Agent Navigation with Line-Segment Goals
Sean Curtis Jamie Snape Dinesh Manocha
Department of Computer Science, University of North Carolina at Chapel Hill
ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games 2012
Abstract
It is a common artifact of multi-agent motion planning for groups of agents, following similar paths, to converge to a line. This occurs because the agents' immediate goals, a.k.a. waypoints, are frequently a shared point in space. Contention for the point goal causes agents to line up and generally interferes with agent motion. By extending the definition of an immediate point goal to a line segment, which we call a "way portal," we enable the agents to better utilize the space available to them in responding to dynamic constraints. We present a novel multi-agent navigation algorithm to efficiently compute the trajectories of autonomous agents using these way portals. We have incorporated the concept into a velocity obstacle-based local navigation model and present a new segment optimization algorithm that efficiently computes a new agent velocity with respect to the way portal. We show how way portal data is extracted from current global navigation data structures, such as navigation meshes. The algorithm is relatively simple to implement and has a small run-time cost (approximately 3 microseconds per agent.) We highlight its performance in different game-like scenarios and observe improved agent behavior and better utilization of free space.
Sean Curtis, Jamie Snape, and Dinesh Manocha, Way Portals: Efficient Multi-Agent Navigation with Line-Segment Goals, ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, 2012.
Paper (PDF, 0.5 MB)