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

DOI10.1016/J.TCS.2013.12.001zbMATH Open1282.91054arXiv1108.1561OpenAlexW1994248032MaRDI QIDQ393889FDOQ393889

Authors: Shaunak D. Bopardikar, Subhash Suri 

Publication date: 24 January 2014

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A game of cops and robbers
• Title not available (Why is that?)
• A framework for pursuit evasion games in
• The role of information in the cop-robber game
• Capture pursuit games on unbounded domains
• Title not available (Why is that?)
• On k-Hulls and Related Problems
• Title not available (Why is that?)
• “Lion and Man”: Upper and Lower Bounds
• Solution of David Gale's lion and man problem

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)