This paper addresses the visibility-based pursuit-evasion problem where a team of pursuer robots operating in a two-dimensional polygonal space seek to establish visibility of an arbitrarily fast evader. This is a computationally challenging task for which the best known complete algorithm takes time doubly exponential in the number of robots. However, recent advances that utilize sampling-based methods have shown progress in generating feasible solutions. An aspect of this problem that has yet to be explored concerns how to ensure that the robots can recover from catastrophic failures which leave one or more robots unexpectedly incapable of continuing to contribute to the pursuit of the evader. To address this issue, we propose an algorithm that can rapidly recover from catastrophic failures. When such failures occur, a replanning occurs, leveraging both the information retained from the previous iteration and the partial progress of the search completed before the failure to generate a new motion strategy for the reduced team of pursuers. We describe an implementation of this algorithm and provide quantitative results that show that the proposed method is able to recover from robot failures more rapidly than a baseline approach that plans from scratch.
more »
« less
A Visibility Roadmap Sampling Approach for a Multi-Robot Visibility-Based Pursuit-Evasion Problem
Given a two-dimensional polygonal space, the multi-robot visibility-based pursuit-evasion problem tasks several pursuer robots with the goal of establishing visibility with an arbitrarily fast evader. The best known complete algorithm for this problem takes time doubly exponential in the number of robots. However, sampling-based techniques have shown promise in generating feasible solutions in these scenarios. One of the primary drawbacks to employing existing sampling-based methods is that existing algorithms have long execution times and high failure rates for complex environments. This paper addresses that limitation by proposing a new algorithm that takes an environment as its input and returns a joint motion strategy which ensures that the evader is captured by one of the pursuers. Starting with a single pursuer, we sequentially construct Sample-Generated Pursuit-Evasion Graphs to create such a joint motion strategy. This sequential graph structure ensures that our algorithm will always terminate with a solution, regardless of the complexity of the environment. We describe an implementation of this algorithm and present quantitative results that show significant improvement in comparison to the existing algorithm.
more »
« less
- NSF-PAR ID:
- 10249089
- Date Published:
- Journal Name:
- IEEE International Conference on Robotics and Automation
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
We study the problem of pursuit-evasion for a single pursuer and an evader in polygonal environments where the players have visibility constraints. The pursuer is tasked with catching the evader as quickly as possible while the evader tries to avoid being captured. We formalize this problem as a zero-sum game where the players have private observations and conflicting objectives.One of the challenging aspects of this game is due to limited visibility. When a player, for example, the pursuer does not see the evader, it needs to reason about all possible locations of the evader. This causes an exponential increase in the size of the state space as compared to the arena size. To overcome the challenges associated with large state spaces, we introduce a new learning-based method that compresses the game state and uses it to plan actions for the players. The results indicate that our method outperforms the existing reinforcement learning methods, and performs competitively against the current state-of-the-art randomized strategy in complex environments.more » « less
-
This paper studies a multi-robot visibility-based pursuit-evasion problem in which a group of pursuer robots are tasked with detecting an evader within a two dimensional polygonal environment. The primary contribution is a novel formulation of the pursuit-evasion problem that modifies the pursuers' objective by requiring that the evader still be detected, even in spite of the failure of any single pursuer robot. This novel constraint, whereby two pursuers are required to detect an evader, has the benefit of providing redundancy to the search, should any member of the team become unresponsive, suffer temporary sensor disruption/failure, or otherwise become incapacitated. Existing methods, even those that are designed to respond to failures, rely on the pursuers to replan and update their search pattern to handle such occurrences. In contrast, the proposed formulation produces plans that are inherently tolerant of some level of disturbance. Building upon this new formulation, we introduce an augmented data structure for encoding the problem state and a novel sampling technique to ensure that the generated plans are robust to failures of any single pursuer robot. An implementation and simulation results illustrating the effectiveness of this approach are described.more » « less
-
In this paper, pursuit-evasion scenarios in a stochastic flow field involving one pursuer and one evader are analyzed. Using a forward reachability set-based approach and the associated level set equations, nominal solutions of the players are generated. The dynamical system is linearized along the nominal solution to formulate a chance-constrained, linear-quadratic stochastic dynamic game. Assuming an affine disturbance feedback structure, the proposed game is solved using the standard Gauss-Seidel iterative scheme. Numerical simulations demonstrate the proposed approach for realistic flow fields.more » « less
-
Time-optimal evading strategies for pursuit-evasion problems involving two pursuers and one evader are analyzed. It is assumed that both pursuers are identical and possess higher speed capabilities when compared to the evader. The problems are categorized into two scenarios, which are based on the evader's information provided to the pursuers. In the rst scenario, the pursuers have information of the evader's position and velocity at each instant of time and follow a constant bearing strategy. In the second scenario, the pursuers have only positional information of the evader and follow a pure pursuit strategy.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
