More Like this

1. Rapid Recovery from Robot Failures in Multi-Robot Visibility-Based Pursuit-Evasion

   https://doi.org/10.1109/IROS51168.2021.9636141  

   Olsen, Trevor; Stiffler, Nicholas M.; O'Kane, Jason M. (September 2021, IEEE/RSJ International Conference on Intelligent Robots and Systems)

   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
2. Learning to Play Pursuit-Evasion with Visibility Constraints

   https://doi.org/10.1109/IROS51168.2021.9635959  

   Engin, Selim; Jiang, Qingyuan; Isler, Volkan (September 2021, 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS))

   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
3. Robust-by-design plans for multi-robot pursuit-evasion

   Trevor Olsen, Nicholas Stiffler (January 2022, IEEE International Conference on Robotics and Automation)

   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
4. Usable boundary for visibility-based surveillance-evasion games

   https://doi.org/10.1007/s40687-025-00528-4  

   Esteve-Yagüe, Carlos; Tsai, Richard (June 2025, Research in the Mathematical Sciences)

   Abstract We consider a surveillance-evasion game in an environment with obstacles. In such an environment, a mobile pursuer seeks to maintain visibility with a mobile evader, who tries to hide from the pursuer in the shortest time possible. In this two-player zero-sum game setting, we study the discontinuities of the value of the game near the boundary of the target set, where the players cannot see each other (the non-visibility region). In particular, we describe the transition between the usable part of the boundary of the target (where the value vanishes) and the non-usable part (where the value is positive). We show that the value exhibits different behaviour depending on the regularity of the obstacles. Namely, we prove that the boundary profile is continuous in the case of smooth obstacles and that it exhibits a jump discontinuity when the obstacle contains corners. Moreover, we prove that, in the latter case, there is a semi-permeable barrier emanating from the interface between the usable and the non-usable part of the boundary of the target set. 

   more » « less
5. A Visibility-Based Escort Problem

   https://doi.org/10.1109/IROS55552.2023.10341574  

   Fletcher, Lance G; Perali, Priyankari; Beathard, Andrew; O'Kane, Jason M (October 2023, IEEE)

   This paper introduces and solves a visibility-based escort planning problem. This novel problem, which is closely related to the well-researched family of visibility-based pursuit-evasion problems in robotics, entails an escort agent tasked with escorting a vulnerable agent, called the VIP, in a 2-dimensional environment. The escort protects the VIP from adversaries that pose line-of-sight threats. We describe a correct and complete planning algorithm whose inputs are a simply-connected polygonal map of the environment, starting locations for the escort and the VIP, along with a goal location to which the VIP agent should be safely moved. The algorithm computes trajectories for the escort and VIP which allow the VIP to reach its goal without coming into the line-of-sight of the adversary at any time. During the execution of these trajectories, the adversary is allowed to move along any continuous path that does not enter into the line-of-sight of the escort. The algorithm proceeds by dividing the environment into a collection of conservative regions and planning the escort's movements as a sequence of these regions via breadth-first search over an information graph. The trajectory of the VIP can then be constructed by tracing the 'safe zones' swept out by the escort's trajectory. We describe an implementation of this algorithm and present computed examples of escort agent strategies in diverse environments. 

   more » « less