Meso-scale planning for multi-agent navigation

We introduce a new concept; meso-scale planning in real-time multi-agent navigation. Whereas many traditional approaches to multi-agent navigation typically consist of two-levels - a macro-scale level providing agents with a global direction of motion around (large) static obstacles, and a micro-scale level in which agents seek to avoid collision with other agents - our approach adds a meso-scale level to give agents realistic behavior in scenarios where groups of other agents (e.g. families or crowds in a virtual world) form coherent entities. Rather than moving straight through such groups, our approach lets agents move around them. Our formulation considers each agent as an individual that may perceive sets of other agents as a group, and plans its motion accordingly. We base our approach on the velocity obstacle concept, and we show using simulation results that our method dramatically improves the quality of the trajectories computed for the agents.