Pursuit-Evasion with Fixed Beams

被引:0
|
作者
Stiffler, Nicholas M. [1 ]
O'Kane, Jason M. [1 ]
机构
[1] Univ South Carolina, Dept Comp Sci & Engn, 301 Main St, Columbia, SC 29208 USA
来源
2016 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION (ICRA) | 2016年
关键词
POLYGONAL REGION; VISIBILITY; ALGORITHM; STRATEGIES; PRIMALITY;
D O I
暂无
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We introduce a complete algorithm for solving a pursuit-evasion problem in a simply connected two-dimensional environment, for the case of a single pursuer equipped with fixed beam sensors. The input for our algorithm is an environment and a collection of sensor directions, in which each is capable of line-of-sight detection in a fixed direction. The output is a pursuer motion strategy that ensures the detection of an evader that moves with unbounded speed, or a statement that no such strategy exists. The intuition of the algorithm is to decompose the environment into a collection of convex conservative regions, within which the evader cannot sneak between any pair of adjacent sensors. This decomposition induces a graph we call the pursuit-evasion graph (PEG), such that any correct solution strategy can be expressed as a path through the PEG. For an instance defined by m beams and an environment with n vertices, the algorithm runs in time O(2(m)n(2)). We implemented the algorithm in simulation and present some computed examples illustrating the algorithm's correctness.
引用
收藏
页码:4251 / 4258
页数:8
相关论文
共 50 条
  • [42] Search and pursuit-evasion in mobile robotics A survey
    Chung, Timothy H.
    Hollinger, Geoffrey A.
    Isler, Volkan
    AUTONOMOUS ROBOTS, 2011, 31 (04) : 299 - 316
  • [43] Adaptive Sampling for Tracking in Pursuit-Evasion Games
    Tolic, Domagoj
    Fierro, Rafael
    2011 IEEE INTERNATIONAL SYMPOSIUM ON INTELLIGENT CONTROL (ISIC), 2011, : 179 - 184
  • [44] On the Value of Information in a Differential Pursuit-Evasion Game
    Becerra, Israel
    Macias, Vladimir
    Murrieta-Cid, Rafael
    2015 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION (ICRA), 2015, : 4768 - 4774
  • [45] CONTROL SEQUENCING IN A GAME OF IDENTITY PURSUIT-EVASION
    Wenk, Carl J.
    SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 2015, 53 (04) : 1815 - 1841
  • [46] Distribution of Miss Distance for Pursuit-Evasion Problem
    Shengwen Xiang
    Hongqi Fan
    Qiang Fu
    IEEE/CAA Journal of Automatica Sinica, 2020, 7 (04) : 1161 - 1168
  • [47] Scalable and practical pursuit-evasion with networked robots
    Vieira, Marcos A. M.
    Govindan, Ramesh
    Sukhatme, Gaurav S.
    INTELLIGENT SERVICE ROBOTICS, 2009, 2 (04) : 247 - 263
  • [48] Pursuit-evasion bibliography. Version 2
    Rodin, E.Y.
    Computers & mathematics with applications, 1989, 18 (1-3): : 245 - 320
  • [49] A practical pursuit-evasion algorithm: Detection and tracking
    AlDahak, Amna
    Elnagar, Ashraf
    PROCEEDINGS OF THE 2007 IEEE INTERNATIONAL CONFERENCE ON ROBOTICS AND AUTOMATION, VOLS 1-10, 2007, : 343 - 348
  • [50] DIFFERENTIAL GAMES AND OPTIMAL PURSUIT-EVASION STRATEGIES
    HO, YC
    BRYSON, AE
    BARON, S
    IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1965, AC10 (04) : 385 - &