Visibility-based pursuit-evasion with limited field of view

被引:0
|
作者
Gerkey, BP [1 ]
Thrun, S [1 ]
Gordon, G [1 ]
机构
[1] Stanford Univ, Artificial Intelligence Lab, Stanford, CA 94305 USA
来源
PROCEEDING OF THE NINETEENTH NATIONAL CONFERENCE ON ARTIFICIAL INTELLIGENCE AND THE SIXTEENTH CONFERENCE ON INNOVATIVE APPLICATIONS OF ARTIFICIAL INTELLIGENCE | 2004年
关键词
D O I
暂无
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
We study a form of the pursuit-evasion problem, in which one or more searchers must move through a given environment so as to guarantee detection of any and all evaders, which can move arbitrarily fast. Our goal is to develop techniques for coordinating teams of robots to execute this task in application domains such as clearing a building, for reasons of security or safety. To this end, we introduce a new class of searcher, the phi-searcher, which can be readily instantiated as a physical mobile robot. We present a detailed analysis of the pursuit-evasion problem using phi-searchers. We show that computing the minimum number of phi-searchers required to search a given environment is NP-hard, and present the first complete search algorithm for a single phi-searcher. We show how this algorithm can be extended to handle
引用
收藏
页码:20 / 27
页数:8
相关论文
共 50 条
  • [21] A Sampling-Based Algorithm for Multi-Robot Visibility-Based Pursuit-Evasion
    Stiffler, Nicholas M.
    O'Kane, Jason M.
    2014 IEEE/RSJ INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS 2014), 2014, : 1782 - 1789
  • [22] A mixed Nash equilibrium solution for visibility-based pursuit-evasion game with multiple obstacles
    Bu, Shaoming
    Liang, Li
    Wang, Youqing
    SCIENCE CHINA-INFORMATION SCIENCES, 2024, 67 (09)
  • [23] A visibility-based pursuit-evasion game between two nonholonomic robots in environments with obstacles
    Eliezer Lozano
    Israel Becerra
    Ubaldo Ruiz
    Luis Bravo
    Rafael Murrieta-Cid
    Autonomous Robots, 2022, 46 : 349 - 371
  • [24] Capture bounds for visibility-based pursuit evasion
    Klein, Kyle
    Suri, Subhash
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2015, 48 (03): : 205 - 220
  • [25] Capture Bounds for Visibility-Based Pursuit Evasion
    Klein, Kyle
    Suri, Subhash
    PROCEEDINGS OF THE TWENTY-NINETH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SOCG'13), 2013, : 329 - 338
  • [26] Approximate Methods for Visibility-Based Pursuit Evasion
    Antonio, Emmanuel
    Becerra, Israel
    Murrieta-Cid, Rafael
    IEEE TRANSACTIONS ON ROBOTICS, 2024, 40 : 4768 - 4786
  • [27] A mixed Nash equilibrium solution for visibility-based pursuit-evasion game with multiple obstacles
    Shaoming BU
    Li LIANG
    Youqing WANG
    ScienceChina(InformationSciences), 2024, 67 (09) : 330 - 332
  • [28] A visibility-based pursuit-evasion game between two nonholonomic robots in environments with obstacles
    Lozano, Eliezer
    Becerra, Israel
    Ruiz, Ubaldo
    Bravo, Luis
    Murrieta-Cid, Rafael
    AUTONOMOUS ROBOTS, 2022, 46 (02) : 349 - 371
  • [29] Rapid Recovery from Robot Failures in Multi-Robot Visibility-Based Pursuit-Evasion
    Olsen, Trevor
    Stiffler, Nicholas M.
    O'Kane, Jason M.
    2021 IEEE/RSJ INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS), 2021, : 9734 - 9741
  • [30] Randomized pursuit-evasion with local visibility
    Isler, V
    Kannan, S
    Khanna, S
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2006, 20 (01) : 26 - 41