Project Ideas

Multi-Robot Pursuit & Evasion

Imagine the following scenarios:

1. A team of autonomous robot security guards are protecting a building. These robots, mounted with cameras, must follow and monitor intruders.
2. Multiple police patrol cars are chasing a speeder.

In both scenarios, the pursuers must find the best motions to "capture" the target, while the target wants to find the best way to evade the pursuers. In the class, we will look at pursuit and tracking strategies for a simplified scenario: a single robot pursues a single target. In this project, you will explore tracking strategies for multiple robots against a single target.

For simplicity, assume that the problem is modeled in a 2-D polygonal environment (see the figure above). The first step in your project (as part of your proposal) is to define the problem precisely. For this, you need to consider at least the following issues:

• Is the target initially visible to at least one of the robots?
• Is the target always visible to at least one of the robots?
• What does it mean by "capturing"? Does it mean that the robots and the target are in exactly the same location? Or does it mean that the target is within the robots' sensor range?
• What is a reasonable model for the robots' sensor range?
• How fast can the robots move? How fast can the target move? What role would their relative speed play in the problem?

To design a tracking strategy, here are some additional issues that you want to think about. Is your motion strategy centralized or distributed? Do the robots know the entire environment in advance? If your strategy is distributed, what information do the robots communicate to one another?

Listed below are some papers, which will help you get started. You should read them and additional relevant ones cited in these papers. They are not complete solutions to your problem and sometimes not a solution to your problem at all, but they should be a useful starting point for thinking about the problem.

References

1. R. Murrieta, B. Tovar, S. Hutchinson. A sampling based motion planning approach to maintain visibility of unpredictable moving targets. Autonomous Robots 19(3):285-300, 2005.
2. H.H. Gonzalez-Banos, C.Y. Lee, and J.C. Latombe. Real-Time combinatorial tracking of a target moving unpredictably among obstacles. Proc. IEEE Int. Conf. on Robotics and Automation, 2002.
3. B. Jung and G. S. Sukhatme. Tracking targets using multiple robots: The effect of environment occlusion. Autonomous Robots, 13(3):191-205, 2002.
4. Z. Liu, M.H. Ang Jr., and W. K. G. Seah. A searching and tracking framework for multi-robot observation of multiple moving targets. J. Advanced Computational Intelligence and Intelligent Informatics, 8(1):14-22, 2004.