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 条
  • [21] NOISY SATELLITE PURSUIT-EVASION GUIDANCE
    MERZ, AW
    JOURNAL OF GUIDANCE CONTROL AND DYNAMICS, 1989, 12 (06) : 901 - 905
  • [22] PURSUIT-EVASION GUIDANCE IN A SWITCHED SYSTEM
    Turetsky, Vladimir
    Shima, Tal
    SIAM JOURNAL ON CONTROL AND OPTIMIZATION, 2018, 56 (04) : 2613 - 2633
  • [23] Pursuit-Evasion Game for Normal Distributions
    Jun, Chanyoung
    Bhattacharya, Subhrajit
    Ghrist, Robert
    2014 IEEE/RSJ INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS 2014), 2014, : 83 - 88
  • [24] Pursuit-evasion games with impulsive dynamics
    Cruck, Eva
    Quincampoix, Marc
    Saint-Pierre, Patrick
    ADVANCES IN DYNAMIC GAME THEORY: NUMERICAL METHODS, ALGORITHMS, AND APPLICATIONS TO ECOLOGY AND ECONOMICS, 2007, 9 : 223 - +
  • [25] Capture zones in a pursuit-evasion game
    Shima, T
    42ND IEEE CONFERENCE ON DECISION AND CONTROL, VOLS 1-6, PROCEEDINGS, 2003, : 5450 - 5455
  • [26] A PURSUIT-EVASION GAME IN THE ORBITAL PLANE
    Selvakumar, Jhanani
    Bakolas, Efstathios
    SPACEFLIGHT MECHANICS 2017, PTS I - IV, 2017, 160 : 1105 - 1116
  • [27] Pursuit-evasion games in the presence of obstacles
    Oyler, Dave W.
    Kabamba, Pierre T.
    Girard, Anouck R.
    AUTOMATICA, 2016, 65 : 1 - 11
  • [28] Randomized pursuit-evasion in a polygonal environment
    Isler, V
    Kannan, S
    Khanna, S
    IEEE TRANSACTIONS ON ROBOTICS, 2005, 21 (05) : 875 - 884
  • [29] Pursuit-evasion of an Evader by Multiple Pursuers
    Von Moll, Alexander
    Casbeer, David W.
    Garcia, Eloy
    Milutinovic, Dejan
    2018 INTERNATIONAL CONFERENCE ON UNMANNED AIRCRAFT SYSTEMS (ICUAS), 2018, : 133 - 142
  • [30] An Introduction to Pursuit-evasion Differential Games
    Weintraub, Isaac E.
    Pachter, Meir
    Garcia, Eloy
    2020 AMERICAN CONTROL CONFERENCE (ACC), 2020, : 1049 - 1066