Multi-Agent Pursuit-Evasion and Coverage Strategies

Abstract

Autonomous agents are increasingly being used to solve many tasks deemed complex by humans with ease and effectiveness. Two such related applications are in defence scenarios and in coverage. Inspired by these applications, this thesis is devoted towards the study of motion planning strategies for autonomous agents in the context of pursuit-evasion problems as well as different coverage problems. The thesis comprises two parts. The first part studies some pursuit-evasion problems among multiple agents, with the focus being on evasive strategies against the non-cooperative pursuers. The second part focuses on coverage problems in which a group of agents pursue a target structure cooperatively and attempt to create static or dynamic coverage around it.

In the first part, pursuit-evasion is considered between an evader and one or more pursuers, all the agents being non-holonomic and having turn radius constraints. A partial information setting is considered wherein the agents (evader and pursuer) know about each others' speed and position but not about their turning capability. The objective in these problems, where the pursuer is of higher speed but less agile, is to obtain an evasive strategy. A two-phase evasive strategy is proposed as an effective solution against the pursuers. It is a proximity-based strategy. In the first phase, when the pursuer is beyond a critical distance from the evader, the latter assumes the worst that the pursuer is holonomic and solves for the best response strategy. This phase is called the Worst Case Scenario Planning (WCSP). When the evader is within the critical range from the pursuer, the former attempts sharp maneuvers to sidestep the pursuer and extend time of capture. This phase is called the Proximity Based Maneuver (PBM). Dynamic programming is used to solve the WCSP strategy. In the case of multiple pursuers, the concept of dominance regions is used to obtain the WCSP strategy. Additionally, the pursuit-evasion problem is extended to a reach-avoid problem where the evader has the dual objective of avoiding the pursuer and reaching a target. This thesis considers the problem of reaching a moving but non-maneuvering target by a turn radius constrained evader in the shortest time. The evader is modelled as a Dubins vehicle, and the reaching strategy is deduced by studying the time-to-go properties for different strategies and chronologically checking simple conditions at crossover points. The proposed two-phase evasive strategy is used for avoiding the pursuer. The reaching strategy and the avoiding strategy are linearly combined to obtain the net reach-avoid strategy. Extensive simulation results are provided to corroborate the effectiveness of both the evasive and the reach-avoid strategies.

In the second part of the thesis, static and dynamic coverage problems are discussed. Inspiration from flocking principles with substantial modifications is used to design a static coverage strategy. This ensures that the covering agents are spread uniformly around the structure while avoiding collision among themselves and with obstacles in the environment. Coverage is addressed for convex and non-convex shapes in 2D and 3D. For dynamic coverage, the concept of Lissajous curves is used to achieve coverage. Dynamic coverage is split into two chapters: coverage of planar regions and coverage of 3D structures. For planar regions, the boundary of the region is approximated using the Fourier series and radial Lissajous curves are generated within the boundary as reference coverage paths. The optimal field-of-view size is analytically determined along with the upper-bound on the time taken for complete coverage. Various extensions of the strategy, such as preferential coverage and simultaneous coverage, are also discussed. For 3D structures, an enclosing volume is considered, and Lissajous curves are generated on the surface of the enclosing volume. Conditions for complete coverage, as well as collision-free coverage in case of multiple agents, are determined analytically. Artificial potential fields are used to obtain coverage by conforming to the shape of the structure. A variety of enclosing volumes is discussed, along with diverse applications such as patch coverage, waypoint coverage, and coverage of moving structures. Performance metrics are proposed for both static and dynamic coverage problems that help in ascertaining the quality of coverage.