Optimal Human-UAV Collaborative Search Path Planning for an Immobile Target with Edge Detection Probabilities

Abstract

Unmanned Aerial Vehicles (UAVs) are mobile faster remotely controllable for search and rescue (SAR) missions This thesis investigates a SAR mission by SAR teams and a fleet of UAVs to search over arcs of positive probability to identify an immobile target (e g an injured hiker) with minimum expected time To deal with the range anxiety we assume each SAR team serves as a mobile battery-swapping station similar to the Ground Vehicle (GV) role in the 2-Echelon UAV & GV Routing Problem (2E-GU-RP) In particular while a SAR team searches along hiking routes on foot a UAV can be launched and retrieved at some nodes A retrieved UAV will become fully charged right after its rendezvous with teams Both teams and UAVs have two moving modes: a slower searching mode and a faster passing mode The searching mode searches the target along arcs but a UAV on the passing mode might fly between nonadjacent nodes Two integer programming formulations carried model and non-carried model are proposed on a time-space network which can only deal with smaller networks A local search based heuristic algorithm (LS) is designed to calculate solutions of good qualities in a short time Our computational experiments’ numerical results indicate that our heuristic with the 2-opt and cross-exchange LS mechanisms can get a nearly optimal solution in a short time

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