Path Planning for Crowds: From Shared Goals to Individual Behaviors

Abstract

This paper presents a novel approach for path planning in the context of crowds animation. The solution produces several paths joining each user-defined pair of locations in the environment. Pairs are possible initial/goal locations for the virtual characters. The obtained paths diversity enables individual behaviorial diversity, while ensuring the achievement of potentially complex goals. The solution is general, derives from the Probabilistic Roadmap motion planning technique developed in Robotics, and proceeds in two stages. First a dense roadmap is build from the 3D definition of the environment and individual s bounding box, then, given a specific problem, a set of feasible paths is extracted from the roadmap using a Diskstra s algorithm implementation and an edge deletion technique. Resulting paths are plausible, and covers widely the environment given that short paths are found as well as less optimal ones. The method is illustrated and demonstrated all along the paper with a generic example.