Rolling Horizon Path Planning of an Autonomous System of UAVs for Persistent Cooperative Service: MILP Formulation and Efficient Heuristics

Byung Duk Song, Jonghoe Kim, James R. Morrison

Research output: Contribution to journalArticlepeer-review

30 Scopus citations

Abstract

A networked system consisting of unmanned aerial vehicles (UAVs), automated logistic service stations (LSSs), customer interface software, system orchestration algorithms and UAV control software can be exploited to provide persistent service to its customers. With efficient algorithms for UAV task planning, the UAVs can autonomously serve the customers in real time. Nearly uninterrupted customer service may be accomplished via the cooperative hand-off of customer tasks from weary UAVs to ones that have recently been replenished at an LSS. With the goal of enabling the autonomy of the task planning tasks, we develop a mixed integer linear programming (MILP) formulation for the problem of providing simultaneous. UAV escort service to multiple customers across a field of operations with multiple sharable LSSs. This MILP model provides a formal representation of our problem and enables use in a rolling horizon planner via allowance of arbitrary UAV initial locations and consumable reservoir status (e.g., battery level). As such, it enables automation of the orchestration of system activities. To address computational complexity, we develop efficient heuristics to rapidly derive near optimal solutions. A receding horizon task assignment (RHTA) heuristic and sequential task assignment heuristic (STAH) are developed. STAH exploits properties observed in optimal solutions obtained for small problems via CPLEX. Numerical studies suggest that RHTA and STAH are 45 and 2100 times faster than solving the MILP via CPLEX, respectively. Both heuristics perform well relative to the optimal solution obtained via CPLEX. An example demonstrating the use of the approach for rolling horizon planning is provided.

Original languageEnglish
Pages (from-to)241-258
Number of pages18
JournalJournal of Intelligent and Robotic Systems: Theory and Applications
Volume84
Issue number1-4
DOIs
StatePublished - Dec 1 2016

Keywords

  • Cooperative UAV service
  • Heuristic
  • Mixed integer linear programming
  • Persistent UAV service
  • UAV task planning

Fingerprint

Dive into the research topics of 'Rolling Horizon Path Planning of an Autonomous System of UAVs for Persistent Cooperative Service: MILP Formulation and Efficient Heuristics'. Together they form a unique fingerprint.

Cite this