Finding Paths for Coherent Groups using Clearance

Abstract

Virtual environment are often populated with moving units and the paths for these units should be planned. When multiple units need to exhibit coherent behavior in a cluttered environment, current techniques often fail, i.e. the resulting paths for the units in the group lack the coherence required. In this paper, we propose a novel approach to motion planning for coherent groups of units. The method presented uses a path for a single unit, called the backbone path, which can be generated by any motion planner. This backbone path is extended to a corridor using the clearance along the path. The units can move freely inside this corridor. By limiting the width of this corridor, and the extent along the corridor where the units can move to, the approach guarantees coherence of the group. Experiments show that the generated paths exhibit group coherence as required, like passing on the same side of obstacles and waiting for fellow group mates to catch up. Performance measurements show that the approach is capable of generating the paths in real-time. In our implementation, the method requires just a few percent of the processor time for groups consisting of up to 100 units.