Ph.D.(Engg) : Multi-Agent Pursuit-Evasion and Coverage Strategies

Autonomous agents are increasingly being used to solve many tasks, deemed complex by humans, with ease and effectiveness. Two such applications are in defense scenarios and in coverage. This thesis, therefore, is devoted towards 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. In the first part, pursuit-evasion is considered between an evader and one or more pursuers, all the agents being non-holonomic 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 for the WCSP strategy. In 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 modeled 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, 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 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 shape of the structure. A variety of enclosing volumes are 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 helps in ascertaining the quality of coverage.

Speaker : Suryadeep Nath   

Research Supervisor: Debasish Ghose