Pursuit and evasion with uncertain bearing measurements

Josh Vander Hook, Volkan Isler

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations


We study pursuit-evasion games in which a deterministic pursuer tries to capture an evader by moving onto the evader's position. We investigate how sensing capability of the pursuer affects the game outcome. In particular, we consider a pursuer which can sense only the bearing to an evader. Furthermore, there is noise in the measurements such that an adversary may adjust each bearing measured by an angle up to α away from the true value. We consider two classical pursuit evasion games under this bearing uncertainty model. The first game is played on the open plane. The pursuer tries to maintain the distance to an evader with equal speed. If the pursuer has full knowledge of the evader's location the pursuer can maintain the separation between the players by moving toward the evader. However, when an adversarial sensing model is introduced, we show that for any pursuer strategy, the evader can increase the distance to the pursuer indefinitely. The rate at which the distance increases is linear in time. In the second game, both players are inside a bounded circular area. This version is known as the Lion-and- Man game, and has been well studied when no sensing limitations are imposed. In particular, the pursuer (Lion) is known to have an O(r log r) strategy to capture the evader, where r is the radius of the circle. In contrast, when sensing uncertainty is introduced, we show that for any α > 0, there exist circular environments in which the man can evade capture indefinitely.

Original languageEnglish (US)
Title of host publication26th Canadian Conference on Computational Geometry, CCCG 2014
PublisherCanadian Conference on Computational Geometry
Number of pages9
StatePublished - Jan 1 2014
Event26th Canadian Conference on Computational Geometry, CCCG 2014 - Halifax, Canada
Duration: Aug 11 2014Aug 13 2014


Other26th Canadian Conference on Computational Geometry, CCCG 2014


Dive into the research topics of 'Pursuit and evasion with uncertain bearing measurements'. Together they form a unique fingerprint.

Cite this