Pursuit - Evasion Game in Crowd

Matrix: Escaping from Mr.Smiths


2007 Fall COMP 790-058
Professor: Dinesh Manocha
Students: Joohwi Lee & Sang Woo Lee
Course Homepage Initial Proposal


0. Content


Introduction    Previous Works    Methods    Results    Conclusion    References   


1. Introduction

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.

Such scenario is known as pursuit-evasion games and appears in various context such as guiding a missle to an aircraft, rescueing people in hazardous area, surveillance, and so forth. Because of its various applicability, there have been many researches. However, their approach is so different and there is no principal way. Thus, we classify their approaches, investigate some of them, and then implement and compare selected ones.

To see the result of global and local path planning, our comparison will be conducted in crowded environment where many chances of collision are expected. In addition to this, in crowded environment pursuer and evader's vision is restricted and their movement is obstructed by lots of other agents. We expect that we can know which strategy would be the best in crowded environment by this experiment. For crowd simulation, we use Jur's Reciprocal Velocity Obstacles[1] and apply simple visibility contraint rule.



2. Previous Works

  • Probabilistic Approach

    Vidal et al[2] implements a pursuit-evasion task on a physical team of aerial and ground vehicles. In this paper, map building and pursuit-evasion games are combined into a single probablistic approach. Each agent estimates their joint positions in a known environment and tracks the positions of autonomously moving objects. The state estimators of different robots cooperate to increase the accuracy and reliability of the estimation process. This cooperation between the robots enables them to track temporarily occluded objects and to recover faster their position after they have lost track of it. They evaluate various pursuit policies relating expected capture times to the speed and intelligence of the evaders and the sensing capabilities of the pursuers.

  • Roadmap Based Approach

    Roadmap-based approach[3] assumes that a pursuer and an evader use the same roadmap to plan their trajectories. Therefore, both players have globally conflicting objectives. It consists of two parts, one is to obtain solutions to pursuit-evasion games and another is to handle robots with local planner. Its pursuit-evasion algorithm is based on the dynamic programming by using time aware controllers to build roadmaps. Collision avoidance algorithm is applied to handle unpredictability which occurs when the robots are independent within reaction zones. For this, they build a collision-probability map and compute optimal collision avoding trajectories using standard MDP algorithms. This approach guarantees sound and complete solution, but its running times increase with the dimension of the configuration space. Also, [5] implements flocking behavior using roadmap and applies it to cover all the area.

  • Game Theoretic Approach

    To model the adversal nature of the game, pursuit-evasion game are usually studied in a game theoretic framework[4]. The conditions under which the pursuer can capture the evader are obtained by studying a Hamilton-Jacobi-Issacs equation which brings together the system equations of the pursuer and the evader. This approach has the advantage of yielding a closed-form solution of the game. Unfortunately, as the environments get complicated, solving Hamilton-Jacobi-Issacs equations become intractable.

  • Evolutionary Approach

    Biological obeservation inspired robot communities to examine various social characteristics of insects and animals. Pursuit and evasion is also one of them that can be seen in every animal society. Since usually pursuer and evader are different species, they evolve against one another in an ongoing way and often give rise to co-evolution between species. From this point of view, [6] made a vast survey on pursuit-evasion behavior and simulated this scenario using the Genetic algorithm. At first they formulated two dimensional physical dynamics that explained the motion of animals. And then, they encoded the controller specifications as bit-strings as an artifical neurons. As a result, they found out that the most successful individuals would have very simple neural architecture similar to Braitenberg's Vehicles, which has a symmetric sensors connected to the motors by 'crossed' or 'uncrossed'.



3. Methods

Our simulations are based on Jur's RVO code framework, 09/28/2007 version. RVO has a very good advantage; it runs in real-time. Therefore, we are able to change and feedback result in real-time. We hope new version of RVO to have improvements such as global roadmap, more natural movements, human behavior, and etc. Also, we think about integrating Russ's RDR to RVO, as a global roadmap.

At present, we implemented two simple algorithms. The first is a randomized approach. In this algorithm both pursuer and evader determine their next position randomly. So they wander whole map and do not have specific strategy. In contrast to this, in another algorithm (Amato's covering algorithm in [5]), we build up hard-coded voronoi roadmap and every pursuer explorers whole map based on flocking behavior using roadmap. We assume several rules to simplify complex environment and focus on our goal.

Our assumptions are

  1. Smith can only detect by their vision (considering their direction)
  2. Smith knows Neo's position with some time intervals after detection.
  3. We use simple static obstacles to focus on crowd simulation situation.
  4. We use very simple evasion algorithm for Neo.
  5. Neo does not escape from crowd region. He is wondering in crowd.



4. Results

We found out these facts:

  1. As we expected, in crowded environment, it is difficult to detect with vision because of crowds. In currently established pursuit-evasion algorithm, pursuers have almost infinite sight. However, in crowd environment, we can hardly detect the evader. It is also same for the evader so that crowded environment distinguishes the problem from previous works.
  2. Even in crowded situation, it is about five to ten times faster when we use covering algorithm with roadmap than when the randomized search strategy is used. We started Smiths from other sides, and just covering makes quite good result. This could be due to simple static obstacle placement, but maybe we can use some classic strategies of covering with limited sensor.

What we will implement:

  1. Mixing some theory of covering, and pursuit-evasion game theory
  2. Improve Neo's evasion algorithm
  3. Make Smiths cooperative each other
  4. Simulate with complex static obstacles environment

Figure 1. Agents (Black) finding Neo (Red) Figure 2. Neo caught by an Agent
Figure 3. Finding Neo in low density crowd  



5. Conclusion



6. References

  1. Jur van den Berg, Ming Lin, Dinesh Manocha, "Reciprocal Velocity Obstacles for Real-Time Multi-Agent Collision Avoidance". Technical Report, Department of Computer Science, UNC
  2. R. Vidal, O. Shakernia, H. J. Kim, D. Shim, and S. Sastry, "Probabilistic pursuit-evasion games: Theory, implementation and experimental evaluation, " IEEE Transactions on Robotics and Automation, Oct 2002.
  3. T. Basar and G. J. Olsder, Dynamic Noncooperative Game Theory. SIAM, 1998
  4. Volkan Isler, Dengfeng Sun, Shankar Sastry, "Roadmap Based Pursuit-Evasion and Collision Avoidance". Proceedings of Robotics: Science and Systems, June 2005
  5. Bayazit O. B., Lien J. - M., Amato N. M.: The Eurographics Association 2005. Roadmap-based flocking for complex environments. In Pacific Conference on Computer Graphics and Applications (2002), pp. 104--115.
  6. D. Cliff and G. F. Miller. "Co-evolution of pursuit and evasion II: Simulation methods and results". Technical Report CSRP377, COGS, University of Sussex, 1995.

2007 Fall COMP790-058 Course Homepage