On the Concerted Design and Scheduling of Multiple Resources for Persistent UAV Operations

作     者：Kim, Jonghoe Morrison, James R. 

作者机构：Korea Adv Inst Sci & Technol Dept Ind & Syst Engn Taejon 305701 South Korea 

出 版 物：《JOURNAL OF INTELLIGENT & ROBOTIC SYSTEMS》 (智能和机器人系统杂志)

年 卷 期：2014年第74卷第1-2期

页      面：479-498页

核心收录：

学科分类：08[工学] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：KAIST HRHRP [N10120008] National Research Foundation of Korea (NRF) Basic Science Research Program 

主　　题：Persistent UAV service Concerted design and scheduling Replenishment stations Branch and bound algorithms UAV scheduling for persistence 

摘      要：A fleet of unmanned aerial vehicles (UAVs) supported by logistics infrastructure, such as automated service stations, may be capable of long-term persistent operations. Typically, two key stages in the deployment of such a system are resource selection and scheduling. Here, we endeavor to conduct both of these phases in concert for persistent UAV operations. We develop a mixed integer linear program (MILP) to formally describe this joint design and scheduling problem. The MILP allows UAVs to replenish their energy resources, and then return to service, using any of a number of candidate service station locations distributed throughout the field. The UAVs provide service to known determin-istic customer space-time trajectories. There may be many of these customer missions occurring simultaneously in the time horizon. A customer mission may be served by several UAVs, each of which prosecutes a different segment of the customer mission. Multiple tasks may be conducted by each UAV between visits to the service stations. The MILP jointly determines the number and locations of resources (design) and their schedules to provide service to the customers. We address the computational complexity of the MILP formulation via two methods. We develop a branch and bound algorithm that guarantees an optimal solution and is faster than solving the MILP directly via CPLEX. This method exploits numerous properties of the problem to reduce the search space. We also develop a modified receding horizon task assignment heuristic that includes the design problem (RHTA(d)). This method may not find an optimal solution, but can find feasible solutions to problems for which the other methods fail. Numerical experiments are conducted to assess the performance of the RHTA(d) and branch and bound methods relative to the MILP solved via CPLEX. For the experiments conducted, the branch and bound algorithm and RHTA(d) are about 500 and 25,000 times faster than the MILP solved via CPLEX, respectively