Randomized Visibility-based Pursuit-Evasion Applet

Jump to the applet.

What is the problem?

In the visibility based pursuit-evasion game, one or more pursuers try to locate (see) an evader. The evader's initial position and strategy is unknown. Further, the evader is much more powerful than the pursuers: It knows the pursuers' locations at all times and can be much more faster than them.

Guibas, Latombe, LaValle, Lin, and Motwani [2,3] studied this game and presented an algorithmic characterization of polygons where a single pursuer can locate the evader using a deterministic strategy. A demonstration of this result can be found here.

Recently, we showed that, in fact, a single pursuer can locate the evader in any simply-connected polygon with probability arbitrarily close to one [1]. This requires a randomized strategy.

The randomized strategy

Here is an applet [4] that demonstrates the randomized strategy. The user-interface and the triangulation code is based on the Art Gallery Applet of Thierry Dagnino. You may also want to check out his nice Art Gallery Page to learn about polygon triangulation.

The triangulation of a polygon is a partitioning of the polygon into disjoint triangles such that the vertices of the triangles are chosen from the vertices of the polygon. Here is an example:

The dual of a triangulation is a graph which has a vertex for each triangle. There is an edge between two vertices if the corresponding triangles share a side. The dual of a triangulation of any simply-connected polygon is always a tree. Here is the dual of the above triangulation.
The randomized strategy for finding the evader is as follows: It is divided into rounds. At the beginning of each round the pursuer is located at a leaf triangle, say t. We root the triangulation tree at t. The pursuer randomly picks one of the children of t and goes there. Each child is chosen with probability proportional to the number of leaves of the subtree rooted at this child. Afterwards, the pursuer recursively repeats this guessing strategy until he arrives at a leaf. At this time, the round ends.
The pursuer repeats these rounds until he locates the evader.

Please see the paper for a formal description and analysis of this strategy. You are now ready to play the game!

How to use the applet

First you need to draw a polygon. Here are Thierry Dagnino's instructions:

 

Enter your points , maximum 100. You will not be allowed to enter a point that will cause intersection in the polygon. (Remember that we are working with simple polygons.)

Close the polygon by clicking on the first point you entered.

The triangulation will appear and the vertices will be colored. A white circle surrounds vertices representing guards.

You can toggle the display by clicking on the buttons below the applet.

The undo button will remove the last point you entered.

The reset button will delete the polygon allowing you to enter a new one.

The coloring and guards are not relevant to the game but I left them untouched -- in case you want to play with them. Once you close the polygon, the game starts..

We will play an abstract version of the game. We will not worry about the actual positions of the players. What matters is which triangles the players are located in. The players will move from one triangle to another until the pursuer and the evader are located in the same triangle. For the visibility-based pursuit evasion game, if the pursuer and the evader are in the same triangle, clearly the pursuer can see the evader and win the game.

The pursuer's triangle is the blue one. Initially, only the pursuer's location (triangle) is shown. The gray triangles adjacent to the blue triangle are possible next moves of the pursuer. Next, you can choose your (the evader's) initial triangle by clicking on it. You are the green player. Your goal is to avoid capture, i.e. being located in the same triangle..Good Luck!!

Oh, by the way, the pursuer does not see you until he is located in your triangle..But you'll have to trust me for that!
Also, if a triangle is too thin, it gets quite difficult to click in it!!

If you read this, your browser does not have java support. Click here to go to the netscape web site.

BLUE: The pursuer GREEN: The evader (you)
LIGHT GRAY:Pursuer's possible next moves
Reset:Erases the polygon Replay:Restarts the game on the same polygon

Thanks for stopping by! I hope you enjoyed it. Please feel free to contact me if you have any comments. If you'd like to play with the source code, please see [4] below.
References
  1. Locating and Capturing an Evader in a Polygonal Environment, Volkan Isler, Sampath Kannan, and Sanjeev Khanna. University of Pennsylvania, Technical Report MS-CIS-03-33. (To appear in WAFR'04).
  2. Finding an Unpredictable Target in a Workspace with Obstacles, Steven M. LaValle, David Lin, Leonidas J. Guibas, Jean-Claude Latombe, and Rajeev Motwani. In Proc. 1997 IEEE International Conference on Robotics and Automation.
  3. Visibility-based pursuit-evasion in a polygonal environment. L. J. Guibas, J.-C. Latombe, S. M. LaValle, D. Lin, and R. Motwani. International Journal of Computational Geometry and Applications, 9(5):471--494, 1999.
  4. You can download the source code peapplet.tar.gz (~7.5K, unix) or peapplet.zip (~10K, win2k) -- sorry it's a quick and dirty one!
  5. The Art Gallery Applet, Thierry Dagnino.

 

Back to RSN

Volkan Isler