Interactive navigation of multiple agents in crowded environments

ABSTRACT

We present a novel approach for interactive navigation and planning of multiple agents in crowded scenes with moving obstacles. Our formulation uses a precomputed roadmap that provides macroscopic, global connectivity for wayfinding and combines it with fast and localized navigation for each agent. At runtime, each agent senses the environment independently and computes a collision-free path based on an extended "Velocity Obstacles" concept. Furthermore, our algorithm ensures that each agent exhibits no oscillatory behaviors. We have tested the performance of our algorithm in several challenging scenarios with a high density of virtual agents. In practice, the algorithm performance scales almost linearly with the number of agents and can run at interactive rates on multi-core processors.

REFERENCES

• 1: Abe, Y., and Matsuo, Y. 2001. Collision avoidance method for multiple autonomous mobile agents by implicit cooperation. In Proc. IEEE Int. Conf. on Robotics and Automation, 1207--1212.
• 2: Ashida, K., Lee, S. J., Allbeck, J., Sun, H., Badler, N., and Metaxas, D. 2001. Pedestrians: Creating agent behaviors through statistical analysis of observation data. Proc. Computer Animation.
• 3: O. Burchan Bayazit , Jyh-Ming Lien , Nancy M. Amato, Better group behaviors in complex environments using global roadmaps, Proceedings of the eighth international conference on Artificial life, p.362-370, December 09-13, 2002
• 4: Cordeiro, O. C., Braun, A., Silveria, C. B., Musse, S. R., and Cavalheiro, G. G. 2005. Concurrency on social forces simulation model. First International Workshop on Crowd Simulation.
• 5: Ferguson, D., Kalra, N., and Stentz, A. 2006. Replanning with RRTs. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (May).
• 6: Feurtey, F. 2000. Simulating the Collision Avoidance Behavior of Pedestrians. Master's thesis, University of Tokyo.
• 7: Fiorini, P., and Shiller, Z. 1998. Motion planning in dynamic environments using velocity obstacles. Int. Journal of Robotics Research 17, 7, 760--772.
• 8: John Funge , Xiaoyuan Tu , Demetri Terzopoulos, Cognitive modeling: knowledge, reasoning and planning for intelligent characters, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.29-38, July 1999 [doi>10.1145/311535.311538]
• 9: Garaerts, R., and Overmars, M. H. 2007. The corridor map method: Real-time high-quality path planning. In ICRA, 1023--1028.
• 10: Gayle, R., Sud, A., Lin, M., and Manocha, D. 2007. Reactive deformation roadmaps: Motion planning of multiple robots in dynamic environments. In Proc IEEE International Conference on Intelligent Robots and Systems.
• 11: Helbing, D., Buzna, L., and Werner, T. 2003. Self-organized pedestrian crowd dynamics and design solutions. Traffic Forum 12.
• 12: Hsu, D., Kindel, R., J.-C.Latombe, and Rock, S. 2002. Randomized kinodynamic motion planning with moving obstacles. International Journal of Robotics Research.
• 13: Jaillet, L., and Simeon, T. 2004. A PRM-based motion planning for dynamically changing environments. Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).
• 14: Kallmann, M., and Mataric, M. 2004. Motion planning using dynamic roadmaps. Proceedings of the IEEE Conference on Robotics and Automation (ICRA) (April).
• 15: A. Kamphuis , M. H. Overmars, Finding paths for coherent groups using clearance, Proceedings of the 2004 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 27-29, 2004, Grenoble, France [doi>10.1145/1028523.1028526]
• 16: O Khatib, Real-time obstacle avoidance for manipulators and mobile robots, International Journal of Robotics Research, v.5 n.1, p.90-98, Spring, 1986 [doi>10.1177/027836498600500106]
• 17: Kluge, B., and Prassler, E. 2007. Reflective navigation: Individual behaviors and group behaviors. In Proc. IEEE Int. Conf. on Robotics and Automation, 4172--4177.
• 18: Koenig, S., and Likhachev, M. 2002. Improved fast replanning for robot navigation in unknown terrain. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (May).
• 19: Lamarche, F., and Donikian, S. 2004. Crowd of virtual humans: a new approach for real time navigation in complex and structured environments. Computer Graphics Forum 23, 3, 509--518.
• 20: Jean-Claude Latombe, Robot Motion Planning, Kluwer Academic Publishers, Norwell, MA, 1991
• 21: Manfred Lau , James J. Kuffner, Precomputed search trees: planning for interactive goal-driven animation, Proceedings of the 2006 ACM SIGGRAPH/Eurographics symposium on Computer animation, September 02-04, 2006, Vienna, Austria
• 22: LaValle, S., and Kuffner, J. 2001. Randomized kinodynamic planning. International Journal of Robotics Research.
• 23: Steven M. LaValle, Planning Algorithms, Cambridge University Press, New York, NY, 2006
• 24: Leven, P., and Hutchinson, S. 2000. Toward real-time path planning in changing environments. Proceedings of the fourth International Workshop on the Algorithmic Foundations of Robotics (WAFR).
• 25: Li, Y., and Gupta, K. 2007. Motion planning of multiple agents in virtual environments on parallel architectures. In ICRA, 1009--1014.
• 26: Celine Loscos , David Marchal , Alexandre Meyer, Intuitive Crowd Behaviour in Dense Urban Environments using Local Laws, Proceedings of the Theory and Practice of Computer Graphics 2003, p.122, June 03-05, 2003
• 27: MASSIVE, 2006. http://www.massivesoftware.com.
• 28: Musse, S. R., and Thalmann, D. 1997. A model of human crowd behavior: Group inter-relationship and collision detection analysis. Computer Animation and Simulation, 39--51.
• 29: Mark H. Overmars, Point location in fat subdivisions, Information Processing Letters, v.44 n.5, p.261-265, Dec. 21, 1992 [doi>10.1016/0020-0190(92)90211-D ]
• 30: Pelechano, N., O'Brien, K., Silverman, B., and Badler, N. 2005. Crowd simulation incorporating agent psychological models, roles and communication. First International Workshop on Crowd Simulation.
• 31: N. Pelechano , J. M. Allbeck , N. I. Badler, Controlling individual agents in high-density crowd simulation, Proceedings of the 2007 ACM SIGGRAPH/Eurographics symposium on Computer animation, August 02-04, 2007, San Diego, California
• 32: Pettre, J., Laumond, J.-P., and Thalmann, D. 2005. A navigation graph for real-time crowd animation on multilayered and uneven terrain. First International Workshop on Crowd Simulation.
• 33: Petty, S., and Fraichard, T. 2005. Safe motion planning in dynamic environments. In Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, 3726--3731.
• 34: Quinlan, S., and Khatib, O. 1993. Elastic bands: Connecting path planning and control. Proc. of IEEE Conf. on Robotics and Automation.
• 35: Craig W. Reynolds, Flocks, herds and schools: A distributed behavioral model, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.25-34, August 1987
• 36: Reynolds, C. 1999. Steering behaviors for autonomous characters. In Proc. Game Developers Conference, 763--782.
• 37: Craig Reynolds, Big fast crowds on PS3, Proceedings of the 2006 ACM SIGGRAPH symposium on Videogames, p.113-121, July 30-31, 2006, Boston, Massachusetts [doi>10.1145/1183316.1183333]
• 38: Schreckkenberg, M., and Sharma, S. D. 2001. Pedestrian and Evacuation Dynamics. Springer.
• 39: Wei Shao , Demetri Terzopoulos, Autonomous pedestrians, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073371]
• 40: Shiller, Z., Large, F., and Sekhavat, S. 2001. Motion planning in dynamic environments: obstacles moving along arbitrary trajectories. In Proc. IEEE Int. Conf. on Robotics and Automation, 3716--3721.
• 41: 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
• 42: Stentz, A. 1995. The focussed D* algorithm for real-time replanning. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI).
• 43: Still, G. 2000. Crowd Dynamics. PhD thesis, University of Warwik, UK. Ph.D. Thesis.
• 44: Sung, M., Gleicher, M., and Chenney, S. 2004. Scalable behaviors for crowd simulation. Computer Graphics Forum 23, 3 (Sept), 519--528.
• 45: Mankyu Sung , Lucas Kovar , Michael Gleicher, Fast and accurate goal-directed motion synthesis for crowds, Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, July 29-31, 2005, Los Angeles, California [doi>10.1145/1073368.1073410]
• 46: Thalmann, D., O'Sullivan, C., Ciechomski, P., and Dobbyn, S. 2006. Populating Virtual Environments with Crowds. Eurographics 2006 Tutorial Notes.
• 47: Tolman, E. C. 1948. Cognitive maps in rats and men. The Psychological Review 55, 4, 189--208.
• 48: Adrien Treuille , Seth Cooper , Zoran Popović, Continuum crowds, ACM SIGGRAPH 2006 Papers, July 30-August 03, 2006, Boston, Massachusetts
• 49: Xiaoyuan Tu , Demetri Terzopoulos, Artificial fishes: physics, locomotion, perception, behavior, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.43-50, July 1994 [doi>10.1145/192161.192170]
• 50: van den Berg, J., Lin, M., and Manocha, D. 2008. Reciprocal velocity obstacles for real-time multi-agent navigation. In Proc. IEEE Int. Conf. on Robotics and Automation.
• 51: Warren, C. W. 1990. Multiple path coordination using artificial potential fields. Proc. of IEEE Conf. on Robotics and Automation, 500--505.
• 52: Yang, Y., and Brock, O. 2006. Elastic roadmaps: Globally task-consistent motion for autonomous mobile manipulation. Proceedings of Robotics: Science and Systems (August).
• 53: Zucker, M., Kuffner, J., and Branicky, M. 2007. Multipartite rrts for rapid replanning in dynamic environments. Proc. IEEE Int. Conf. on Robotics and Automation.