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.

REFERENCES

• 1: {BH00} Balch T., Hybinette M.: Social potentials for scalable multi-robot formations. In IEEE International Conference on Robotics and Automation (ICRA '00) (April 2000), vol. 1, pp. 73--80.
• 2: {BLA04} Bayazit O., Lien J.-M., Amato N.: Better flocking behaviors using rule-based roadmaps. In Algorithmic Foundations of Robotics V, Springer Tracts in Advanced Robotics 7 (2004), Springer-Verlag Berlin Heidelberg, pp. 95--111.
• 3: {GO04} Geraerts R., Overmars M. H.: Clearance based path optimization for motion planning. In International Conference on Robotics and Automation (ICRA) (2004), IEEE Press, San Diego, CA.
• 4: {Hel94} Helbing D.: A mathematical model for the behavior of individuals in a social field. Journal of Mathematical Sociology 19, 3 (1994), 189--219.
• 5: {HM95} Helbing D., Molnár P.: Social force model for pedestrian dynamics. Physical Review 51 (1995), 4282--4286.
• 6: {KL94} Kavraki L., Latombe J.-C.: Randomized preprocessing of configuration space for fast path planning. In International Conference on Robotics and Automation (ICRA) (1994), IEEE Press, San Diego, CA, pp. 2138--2139.
• 7: {KO04} Kamphuis A., Overmars M. H.: Motion planning for coherent groups of entities. In IEEE Int. Conf. on Robotics and Automation (2004), IEEE Press, San Diego, CA.
• 8: {KvLO96} Kavraki L., Švestka P., Latombe J.-C., Overmars M.: Probabilistic roadmaps for path planning in high-dimensional configuration spaces. IEEE Transactions on Robotics and Automation 12 (1996), 556--580.
• 9: {LC03} Li T.-Y., Chou H.-C.: Motion planning for a crowd of robots. In International Conference on Robotics and Automation (ICRA) (2003), IEEE Press, San Diego, CA.
• 10: Stephane Leroy , Jean-Paul Laumond , Thierry Siméon, Multiple Path Coordination for Mobile Robots: A Geometric Algorithm, Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, p.1118-1123, July 31-August 06, 1999
• 11: Soraia Raupp Musse , Daniel Thalmann, Hierarchical Model for Real Time Simulation of Virtual Human Crowds, IEEE Transactions on Visualization and Computer Graphics, v.7 n.2, p.152-164, April 2001 [doi>10.1109/2945.928167]
• 12: {Pot99a} Pottinger D.: Coordinated unit movement. Game Developer (January 1999), 42--51.
• 13: {Pot99b} Pottinger D.: Implementing coordinated movement. Game Developer (February 1999), 48--58.
• 14: Craig W. Reynolds, Flocks, herds and schools: A distributed behavioral model, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.25-34, July 1987
• 15: {Rey99} Reynolds C.: Steering behaviors for autonomous characters. In Game Developers Conference (1999).
• 16: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 17: John H. Reif , Hongyan Wang, Social potential fields: a distributed behavioral control for autonomous robots, Proceedings of the workshop on Algorithmic foundations of robotics, p.331-345, May 1995, San Francisco, California, United States
• 18: {SL02} Sanchez G., Latombe J.: Using a prm planner to compare centralized and decoupled planning for multi-robot systems. In Proc. IEEE Int. Conf. on Robotics and Automation (2002), pp. 2112--2119.
• 19: Branislav Ulicny , Daniel Thalmann, Crowd simulation for interactive virtual environments and VR training systems, Proceedings of the Eurographic workshop on Computer animation and simulation, p.163-170, September 02-03, 2001, Manchester, UK
• 20: {vO98} Švestka P., Overmars M.: Coordinated path planning for multiple robots. Robotics and Autonomous Systems 23 (1998), 125--152.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.9 Robotics

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems

  K. Computing Milieux
  K.8 PERSONAL COMPUTING
      K.8.0 General