Randomized pursuit-evasion in a polygonal environment

• Published in: IEEE transactions on robotics 2005-10, Vol.21 (5), p.875-884
• Main Authors: Isler, V., Kannan, S., Khanna, S.
• Format: Article
• Language: English
• Subjects: Air traffic control; Algorithms; Applied sciences; Collision avoidance; Computer science; control theory; systems; Control theory. Systems; Decisions; Doors; Dynamic noncooperative game theory; Engineering profession; Equations; Exact sciences and technology; Expenses; Game theory; Information science; Information technology; Path planning; Polygons; Pursuit algorithms; pursuit-evasion games; randomized algorithms; Robotics; Robots; Strategy; Subroutines
• ISSN: 1552-3098; 1941-0468
• DOI: 10.1109/TRO.2005.851373

This paper contains two main results. First, we revisit the well-known visibility-based pursuit-evasion problem, and show that in contrast to deterministic strategies, a single pursuer can locate an unpredictable evader in any simply connected polygonal environment, using a randomized strategy. The evader can be arbitrarily faster than the pursuer, and it may know the position of the pursuer at all times, but it does not have prior knowledge of the random decisions made by the pursuer. Second, using the randomized algorithm, together with the solution to a problem called the "lion and man problem" as subroutines, we present a strategy for two pursuers (one of which is at least as fast as the evader) to quickly capture an evader in a simply connected polygonal environment. We show how this strategy can be extended to obtain a strategy for a polygonal room with a door, two pursuers who have only line-of-sight communication, and a single pursuer (at the expense of increased capture time).