טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentNir Drucker
SubjectCyclic Routing of Unmanned Aerial Vehicles
DepartmentDepartment of Industrial Engineering and Management
Supervisors Professor Penn Michal
Full Professor Strichman Ofer
Full Thesis textFull thesis text - English Version


Abstract

Many defense and civilian-related tasks targeted by Unmanned Aerial Vehicles (UAVs) are concerned with monitoring of a predefined set of ground targets under various timing constraints. In particular we are concerned with tasks in which each target is associated with a relative deadline, which means that there is an upper bound on the time between two consecutive scans of that target. Such constraints may be related to the nature of the target and the speed in which the client needs to react to a particular scenario. One may imagine a situation in which a military monitors enemy gatherings, attempting to detect various changes when they occur. Civilian applications may include monitoring of facilities and monitoring of forests for fire. In each such application the relative deadline is calculated according to the relative value of shortening the time to react versus the cost of additional UAVs.


The tasks discussed above are (seemingly endless) routines that can be solved with a cyclic plan. Only rarely it is necessary to deviate from such a plan. This stands in stark contrast to the common practice today of manually guiding the UAVs from the ground. Loading preplanned flight routes are supported by modern UAV systems, but no one as far as we know used this capability for planning optimal cyclic routes of fleets of UAVs. Automation of UAVs in various levels is an urgent need since the market, both the defense and civilian-related, is growing rapidly given the major progress in their capabilities and proven success in the last decade.


In this work we formally define the CR-UAV problem and prove a lower-bound on the number of required UAVs. This bound is useful for saving computation time, as it is easy to compute and avoids costly search that is bound to fail. We study several venues for solving this (NP-hard) problem. Specifically, we propose a model based on disjunctive MILP. We explain how they can be solved not only with MILP tools, but also with SMT (Satisfiability Modulo Theory) solvers. We present a DFS-based search algorithm that explores bounded cyclic paths; We show a DFS-based algorithm that explores a discretized version of the (otherwise continuous) state-space.  Finally, we present the results of our extensive empirical evaluation of these methods.