COMP790-058 Robot Motion Planning
Matrix: Escaping from Mr. Smiths

Joohwi Lee / Sang Woo Lee

Proposal PPT

download Progress Report


In this project, we try to integrate global and local path planning. By combining those, we can put interesting constraints and reality in simulation. One example is agents chasing a target based on their own local information. In real world, agents are usually have limited vision so that they should decide their path with their eyes. Moreover agents chasing the target in crowded environment should avoid dynamic obstacles in clever ways. In addition, we hope to see both methods working together and to compare them.


  1. Crowd of pedestrian are heading to each end of road.
  2. Small numbers of Anderson are trying to find Neo based on their vision and communicate each other.
  3. Neo is trying to escape from Anderson and heading for specific target.

Prior Works

Reciporcal Velocity Object

Second order voronoi diagram

Continuum Crowd

Cognitive Modeling


  1. Simulate crowd of pedestrian agents based on Avneesh's work
  2. Anderson and Neo use local information to chase and escape
    1. While detecting, Andersons should cover as most place as possible (exploring)
    2. Andersons find the chasing path to Neo using D* or any other dynamic path planning algorithm (path finding)
  3. Integrating 1) and 2)


  1. J. V. D. Berg, M. C. Lin, D. Manocha. Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation, To appear ICRA 2008
  2. A. Sud, E. Andersen, S. Curtis, M. C. Lin, D. Manocha. Real-time Path Planning for Virtual Agents in Dynamic Environments, IEEE Virtual Reality, 2007
  3. Treuille, A. Cooper, S. Popovi?, Z. Continuum Crowds. ACM Transactions on Graphics 25(3) (SIGGRAPH 2006)
  4. J. Funge, X. Yu, D. Terzopoulos, Cognitive Modeling
  5. J. Pettre, H. Grillon and D. Thalmann, Crowds of Moving Objects: Navigation Planning and Simulation. ICRA, Rome, 14-17 April 2007