An Optimal Joint UAV and Ground Vehicle Path Planning Problem for Area Coverage with Energy Consideration

Abstract

The Unmanned Aerial Vehicles (UAVs) may be the only means by which to conduct coverage missions that search monitor or take photos from the air space over target ground areas that are too difficult to reach by ground manpower Suppose we divided the air space into several virtual cells that cover all the target ground areas Then a scan mission on a target ground area can be done by a UAV flying over (i e covering) its corresponding virtual cell in air space for a specific period of time In this research we plan to route UAVs to cover all necessary virtual cells Since UAVs have limited battery power they can be carried by some mobile Ground Vehicles (GVs) and then be launched from and retrieved by GVs on some nodes in the ground road networks This thesis investigates how to calculate optimal routes for both GVs and UAVs so that all the target ground areas can be scanned by UAVs within a minimum total time subject to the battery limitation of the UAVs To model the combined operations by the UAVs and GVs we use the coverage path planning (CPP) and two-echelon routing problems as our approaches We propose two mathematical models based on integer programming techniques over a time-space network We consider one GV with one UAV case ( ) and one GV with multiple UAVs case ( ) To the best of our knowledge might arguably be the first mathematical programming model that can deal with routings for both GV and multiple UAVs at the same time Our proposed model can calculate the detailed movement for both UAVs and GV yet it is very time-consuming To calculate good routings in shorter time we also designed a greedy algorithm for the one GV with one UAV case where a depth-first search mechanism is exploited to find a feasible UAV route in the time-pace network that covers all target areas within the time limit T The computational experiments indicate our greedy algorithm calculates a good solution faster than the proposed integer programming model

Date of Award	2019
Original language	English
Supervisor	I-Lin Wang (Supervisor)