Surveillance Evasive Path Planning for Autonomous Vehicles
Creators: name: Kim, Jaehyeok
Publisher: name: Purdue University Graduate School
Year: 2024
Subjects: classificationCode: 400103
subject: Aircraft performance and flight control systems
classificationCode: 400199
subject: Aerospace engineering not elsewhere classified

description: The use of autonomous vehicles, such as Unmanned Aerial Systems (UASs), Unmanned Ground Vehicles (UGVs), and Unmanned Surface Vessels (USVs), has globally increased in various applications. Their rising popularity and high accessibility have also increased the use of UASs in criminal or hazardous actions.It is beneficial to rapidly compute possible surveillance system evasive paths to evaluate the effectiveness of a given sensor deployment scheme. To find these evasive trajectories, we assume full knowledge of the current and future state of the surveillance system. This assumption allows the defender to identify worst-case trajectories to counteract. The surveillance system path planning presented in this work can be leveraged for game theoretic sensor deployment.A sensor deployment scheme determines the overall surveillance efficiency. Through redeployment after each assessment, it aims to approach an equilibrium that maximizes defense capabilities. Therefore, a method of evaluation that models mobile, directional sensors is demanded.In response to this demand, this thesis explores the design of a computationally efficient path-planning algorithm for the space-time domain. The Space-Time Parallel RRT* (STP-RRT*) algorithm obtains multiple goal candidates, drawn from a uniform distribution over the time horizon. A set of parallel RRT* trees is simultaneously populated by each goal candidate. By leveraging a connect heuristic from RRT-Connect, parallel goal trees converge to an RRT* tree populated from a start point. This simultaneous tree growth structure returns a computation complexity of O(N log(N)), where N is the number of random samples.Due to its low complexity, the STP-RRT* algorithm is suitable to be used as an evaluation metric that computes the cost of the infiltration path of a malicious autonomous system to assess the performance of the deployment layout. The feedback assessment can be used for the surveillance system redeployment to strengthen the vulnerability.To identify potential and existing bottlenecks in the algorithm, a computation complexity analysis is conducted, and complexity reduction techniques are employed. Given that surveillance system characteristics are known, 1-dimensional and 2-dimensional environments are generated where positions and surveillance patterns of stationary and dynamic obstacles are randomly selected. In each randomized environment, the STP-RRT*, RRT*, and ST-RRT* are evaluated by comparing success rate, computation time, tree size, and normalized cost through 100-trial Monte Carlo simulations. Under the provided conditions, the proposed STP-RRT* algorithm outperforms two other algorithms with an improved mean success rate and reduced mean computation time by 10.02% and 12.88%, respectively, while maintaining a similar cost level, showing its potential application in surveillance-evasive path-planning problems for surveillance deployment evaluation. Finally, we integrate our algorithm with Nav2, an open-source navigation stack for various robotics applications, including UAV, UGV, and USV. We demonstrate its effectiveness via software-in-the-loop (SiTL) experiments utilizing open-source autopilot software.