Development of Spatio-Temporal Multi-Task Assignment Approaches for Perimeter Defense Problem

Abstract

Rapidly evolving technologies in the autonomous operation of Uninhabited Aerial Vehicles (UAVs) and associated developments in low-cost sensors have created significant interest among researchers in using them for various civil and military applications. With the autonomy and presence of various sensing equipment, onboard UAVs lead to problems in the privacy, safety, and security of many safety-critical infrastructures. A critical infrastructure that needs to be protected is approximated by the convex region and called territory. A team of UAVs that protects the territory is called the defenders and UAVs which try to enter the territory are called the intruders. A team of defenders operates inside and, on the perimeter, and protects the territory from intruders by capturing intruders on the perimeter is referred as the Perimeter Defense Problem (PDP). The velocity of intruders is used to predict the arrival location on the perimeter and arrival time. In this way, each intruder generates a spatio-temporal task for the defenders to reach tha= t specific location at a specific time to neutralize that intruder. So, PDP is formulated as the spatio-temporal multi-task assignment (STMTA) problem. In the STMTA problem, some minimum number of defenders (robots) are required to execute the given spatio-temporal tasks; without this minimum number of defenders, STMTA problem is ill-posed. The proposed Dynamic REsource Allocation with Multi-task assignment (DREAM) algorithm solves the bottleneck issue of iterative computation for the required number of robots and provides the two-step solution to compute the required minimum number of robots and their optimal assignments to execute given spatio-temporal tasks. Next, the trajectory generation algorithm has been developed to compute the trajectory of each defender. Furthermore, it is proved that all the computed trajectories of homogeneous agents, operating in the convex region, are collision-free.

For highly maneuvering intruders, the errors in the prediction of tasks deteriorate the performance of DREAM. In the P-DREAM approach, a dedicated defender is assigned to each prioritized intruder by enforcing the prioritized intruder as a first task. A prioritized intruder must be delegated to the reserve defender before it becomes infeasible for the reserve defender. The static design for PDP computes the minimum number of reserve stations, their optimal location, priority region, monitoring region, and the minimum number of defenders required for monitoring. The quantification of priority and monitoring region will be helpful in practical implementations. For protecting a large territory, more defenders are required, also each defender has a limited sensing range to detect and track intruders. To address these issues of partial observability and scalability the decentralized spatio-temporal multi-task assignment approach is proposed. A modified consensus-based bundle algorithm has been proposed to solve the STMTA problem. Finally, the thesis demonstrates the working of the DREAM approach for heterogeneous pick-up and just-in-time delivery (PJITD) problems. Just-in-time tasks have been used to improve operational efficacy for static (priorly known) tasks. The non-iterative solution of modified DREAM overcomes the bottleneck problem of the iterative (and hence offline) solution and provides a real-time implementable solution. The cost function is modified to include the traveling time, operating time, and heterogeneous skills required to execute the tasks. The working of modified DREAM is illustrated using high-fidelity ROS2-GAZEBO simulations and lab-scale hardware experiments.