k-capture in multiagent pursuit evasion, or the lion and the hyenas

DOI10.1016/J.TCS.2013.12.001MaRDI QIDQ393889zbMATH OpenOpenAlexFDO

Authors Shaunak D. Bopardikar, Subhash Suri

Publication date 24 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.1561

zbMATH Keywords

pursuit-evasion gamesdiscrete-time games\(k\)-capture problem

Mathematics Subject Classification ID

Positional games (pursuit and evasion, etc.) (91A24) Discrete-time games (91A50)

Abstract: We consider the following generalization of the classical pursuit-evasion problem, which we call k-capture. A group of n pursuers (hyenas) wish to capture an evader (lion) who is free to move in an m-dimensional Euclidean space, the pursuers and the evader can move with the same maximum speed, and at least k pursuers must simultaneously reach the evader's location to capture it. If fewer than k pursuers reach the evader, then those pursuers get destroyed by the evader. Under what conditions can the evader be k-captured? We study this problem in the discrete time, continuous space model and prove that k-capture is possible if and only there exists a time when the evader lies in the interior of the pursuers' k-Hull. When the pursuit occurs inside a compact, convex subset of the Euclidean space, we show through an easy constructive strategy that k-capture is always possible.

Recommendations

• Smarter Lions: efficient cooperative pursuit in general bounded arenas
• Simultaneous multiple capture of evaders in a simple group pursuit problem
• scientific article; zbMATH DE number 3954700
• Multiple capture of a given number of evaders in the problem of a simple pursuit
• Capture pursuit games on unbounded domains

Cites work

• scientific article; zbMATH DE number 3972833 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 16392 (Why is no real title available?)
• scientific article; zbMATH DE number 3590298 (Why is no real title available?)
• scientific article; zbMATH DE number 3245077 (Why is no real title available?)
• A framework for pursuit evasion games in
• A game of cops and robbers
• Capture pursuit games on unbounded domains
• On k-Hulls and Related Problems
• Solution of David Gale's lion and man problem
• The role of information in the cop-robber game
• “Lion and Man”: Upper and Lower Bounds

Cited in

(16)

• Problem of multiple capture of given number of evaders in recurrent differential games
• Matrix resolving functions in the linear group pursuit problem with fractional derivatives
• Smarter Lions: efficient cooperative pursuit in general bounded arenas
• A new class of pursuer strategies for the discrete-time lion and man problem
• Multiagent Pursuit Evasion, or Playing Kabaddi
• Formulation of a cooperative-confinement-escape problem of multiple cooperative defenders against an evader escaping from a circular region
• Capture of given number of evaders in Pontryagin's nonstationary example
• Evasion in a linear differential game with many pursuers
• Multiple capture of a given number of evaders in the problem of simple pursuit with phase restrictions on timescales
• Cops and robber game on infinite chessboard
• On the problem of pursuing two coordinated evaders in linear recurrent differential games
• Simultaneous multiple capture of rigidly coordinated evaders
• Police and robber game on infinite chessboard
• On a discrete game problem with non-convex control vectograms
• How many lions are needed to clear a grid?
• Multiple capture of given number of evaders in linear recurrent differential games

This page was built for publication: \(k\)-capture in multiagent pursuit evasion, or the lion and the hyenas

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q393889)