A pursuit-evasion problem on a grid

被引:13
|
作者
Neufeld, SW
机构
[1] Winnipeg, Man. R3C 1Y3
关键词
algorithms; pursuit-evasion; robotics;
D O I
10.1016/0020-0190(96)00025-7
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We consider a two-player (searcher & fugitive) pursuit-evasion game played on an n x m grid, n less than or equal to m. Both players move continously and simultaneously along the edges of the grid; the fugitive has unit maximum speed and the searcher has maximum speed v (a constant). If the searcher is on row i (column j), then only the edges and vertices on row i (column j) are visible to the searcher. The fugitive, on the other hand, has full knowledge. The searcher wins if she can locate the fugitive. R. Dawes (1992) investigated the problem of the minimum speed v(0) by which the searcher can force a win and he showed v(0) less than or equal to n + 1. In this paper we prove an upper bound on v(0) which is essentially 2n/3.
引用
收藏
页码:5 / 9
页数:5
相关论文
共 50 条
  • [31] The pursuit-evasion problem in a discrete version of the hamstrung car game
    Ruziboyev, M. B.
    PMM JOURNAL OF APPLIED MATHEMATICS AND MECHANICS, 2008, 72 (06): : 669 - 672
  • [32] MULTI-ROBOT CONTROL SYSTEM FOR PURSUIT-EVASION PROBLEM
    Hladek, Daniel
    Vascak, Jan
    Sincak, Peter
    JOURNAL OF ELECTRICAL ENGINEERING-ELEKTROTECHNICKY CASOPIS, 2009, 60 (03): : 143 - 148
  • [33] Parameterized pursuit-evasion games
    Scott, Allan
    Stege, Ulrike
    THEORETICAL COMPUTER SCIENCE, 2010, 411 (43) : 3845 - 3858
  • [34] Randomized pursuit-evasion in graphs
    Adler, M
    Räcke, H
    Sivadasan, N
    Sohler, C
    Vöcking, B
    COMBINATORICS PROBABILITY & COMPUTING, 2003, 12 (03): : 225 - 244
  • [35] Numerical control optimization methods in one pursuit-evasion problem
    Utemov, A. E.
    JOURNAL OF COMPUTER AND SYSTEMS SCIENCES INTERNATIONAL, 2006, 45 (03) : 395 - 412
  • [36] Multiagent Pursuit-Evasion Problem with the Pursuers Moving at Uncertain Speeds
    Yan, Fuhan
    Jiang, Jiuchuan
    Di, Kai
    Jiang, Yichuan
    Hao, Zhifeng
    JOURNAL OF INTELLIGENT & ROBOTIC SYSTEMS, 2019, 95 (01) : 119 - 135
  • [37] Multiagent Pursuit-Evasion Problem with the Pursuers Moving at Uncertain Speeds
    Fuhan Yan
    Jiuchuan Jiang
    Kai Di
    Yichuan Jiang
    Zhifeng Hao
    Journal of Intelligent & Robotic Systems, 2019, 95 : 119 - 135
  • [38] ON A CLASS OF PURSUIT-EVASION PROBLEMS
    JACOB, JP
    POLAK, E
    IEEE TRANSACTIONS ON AUTOMATIC CONTROL, 1967, AC12 (06) : 752 - &
  • [39] A Method for Solving the Optimal Strategy of a Class of Pursuit-evasion Problem
    He, Guohui
    Liu, Daijun
    Zhang, Yifei
    Fu, Yaowei
    Jiang, Kaichen
    Wu, Yuhu
    2022 41ST CHINESE CONTROL CONFERENCE (CCC), 2022, : 6933 - 6938
  • [40] Numerical control optimization methods in one pursuit-evasion problem
    A. E. Utemov
    Journal of Computer and Systems Sciences International, 2006, 45 : 395 - 412