18th International Symposium on Dynamic Games and Applications

Grenoble, France, July 9 — 12, 2018

18th International Symposium on Dynamic Games and Applications

Grenoble, France, July 9 — 12, 2018

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

Pursuit-Evasion Games

Jul 12, 2018 02:00 PM – 03:40 PM

Location: room H.103

Chaired by Meir Pachter

4 Presentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    02:00 PM - 02:30 PM

    Optimal Strategies and Task Allocation in Multi-Pursuer Single-Evader Problems

    • Venkata Ramana Makkapati, presenter, Georgia Institute of Technology
    • Panagiotis Tsiotras, Georgia Institute of Technology

    Pursuit-evasion problems involving multiple pursuers and single evader are analyzed. The pursuers are all assumed to be identical and follow either a constant bearing or a pure pursuit strategy. Initially, assuming that the evader knows the positions of all the pursuers and their strategy, the time-optimal evading strategies are examined in both cases using tools from optimal control theory. It is shown that the optimal evading strategies depend only on those pursuers that capture the evader at the time of capture, calling them influential pursuers which can be one or more. However, the optimal strategies are intractable and obtaining the information of the influential pursuers at the initial time is elusive. Subsequently, assuming the evader can follow any strategy, a dynamic task allocation algorithm is proposed for the pursuers that follow a constant bearing strategy. The algorithm is based on the well-known Apollonius circles and allows the pursuers to allocate their resources in an intelligent manner while guaranteeing the capture of the evader in minimum possible time. The algorithm is then extended to the case of pure pursuit by considering the Apollonius circle's counterpart.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    02:30 PM - 03:00 PM

    Linear Differential Game Capture Zones in the Case of Imperfect State Information

    • Stéphane Le Ménec, presenter, EADS / MBDA

    A coplanar two player pursuit evasion differential game is considered using a linearised kinematic model with first order acceleration dynamics and bounded controls for both players. Thanks to small angle assumptions, the original system is linearised and scalarized by using the guidance and control concept of zero-effort miss distance as a new scalar state variable. In the new model framework, the pursuer and the evader respectively minimizes and maximizes the perpendicular terminal miss distance at prescribed terminal time.
    Differential game capture zones and robust capture zones are constructed in the scalarized system. Robust capture zones are capture zones when the pursuer strategies are restricted to certain classes of pursuit strategies, i.e. to specific feedback control laws. Saturating and non-saturating linear strategies are considered in the case of computing robust capture zones, meaning while the differential game analysis leads to bang-bang strategies. First objective is to compare the bang-bang capture zones that are the maximum capture zones respect to the robust capture zones that are smaller but that consider more realistic pursuit strategies.
    The capture zone comparison has been performed using interval computation tools. Interval arithmetic is based upon the very simple idea of enclosing real numbers in intervals and real vectors in boxes. Contractors are interval analysis operators that allow to contract boxes respects to constraints. When the constraints are Ordinary Differential Equation constraints, ODE contractors allow to perform guaranteed integration, i.e. to simulate uncertain systems (with measurement errors, with control uncertainties) modelled by Ordinary Differential Equations and interval state vectors. Differential game capture zones and robust capture zones are simply tubes of trajectories computed thanks to ODE contractors that consider various player strategies (there exists and for all quantifiers on controls in the case of differential games).
    Therefore, interval analysis allows to take into account imperfect state measurements in a robust sense in a way to compute differential game capture zones and robust capture zones that are now also robust to measurement errors. Comparisons between noisy linear differential game capture zones and noisy robust capture zones will be presented. Last but not least, interval arithmetic which is not limited to linear systems is also used ta tackle non-linear systems of higher order dimensions.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    03:00 PM - 03:30 PM

    Robustness of capture zones with respect to Gromov-Hausdorff distance in Lion and Man game

    • Olga Yufereva, presenter, Ural Federal University

    We consider the two-person pursuit-evasion game, called Lion and Man game, i.e. we suppose that players have the same top speed and capture zone should be chosen beforehand. The key goal is describing pursuer's winning strategies in compact metric spaces that are close to the given one in the sense of Gromov-Hausdorff distance. In particular, this way allows us to approximate a metric space by finite graphs and draw some conclusions about it as a limit space. Moreover, it means that some errors in awareness of opponent's movement and some errors in control are permissible.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    03:30 PM - 04:00 PM

    Wolfpack Pursuit

    • Meir Pachter, presenter, Air Force Institute of Technology

    Meir Pachter



    We consider pursuit-evasion differential games in the Euclidean plane where an evader
    is engaged by multiple pursuers and point capture is required. All the players have
    simple motion a la Isaacs but at least one of the pursuers is faster than the evader.
    We first revisit Isaacs’ “Two Cutters and a Fugitive Ship” pursuit-evasion differential game in the Euclidean plane where two pursuers, say cutters, chase a fugitive ship. All move with simple motion, the speeds of the cutters each being greater than that of the fugitive ship, the evader. Coincidence with either one, or both pursuers, is capture, and time of capture is the payoff/cost.
    It is shown that group/swarm pursuit is fundamentally shaped by two critical pursuers
    and sometimes by just one critical pursuer, and this irrespective of the size N of the
    pursuit pack. Thus, the pursuit devolves into pure pursuit by one of the players or
    into a pincer movement maneuver by two players who engage the evader, a menage a trois.
    The critical pursuers are identified, state feedback optimal strategies are synthesized
    and the Value of the game is derived.

    Key Words: Many-on-One Pursuit; Pursuit-Evasion; Swarm Pursuit; Group Pursuit.