The flight duration of automated robotic vehicle such as Unmanned Aerial Vehicle (UAV) is limited by their battery or fuel capacity. As a consequence, the duration of missions that can be pursued by UAVs without supporting logistics is restricted. However, a system of UAVs that is supported by automated logistics structures, such as fuel service stations and orchestration algorithms, may pursue missions of conceivably indefinite dura-tion. This may be accomplished by handing off the mission tasks to fully fueled replacement UAVs when the current fleet grows weary. The drained UAVs then seek replenishment from nearby logistics support facilities. To support the vision of a persistent fleet of UAVs pursuing missions across a field of operations, we investigate three scheduling and vehicle routing problems (VRP) for automatic robotics.
In the first chapter, optimal scheduling of heterogeneous UAVs to provide persistent tracking service is investigated. With the specific path and time information of customer (service requester) and location information of multiple sharable replenishment stations, optimal scheduling of UAVs is derived by mixed integer linear programming (MILP). Commercial optimization software CPLEX was applied to demonstrate proposed MILP and derive optimal solution. To handle computational issue of the MILP, improved MILP and genetic algorithm was developed. Various numerical experiments are conducted and demonstrate the efficiency and effectiveness of proposed two approaches.
In the second chapter, the model of previous chapter is extended in term of real time scheduling perspective for long term persistent operation. There are several challenges for long term persistent operation: 1) arrival of new service request 2) unexpected loss of resource during the service 3) deviation from the original plan. To address these issues, we extend an existing MILP formulation to allow for arbitrary UAV initial locations and fuel levels. Based on the insight from the problem formulation, efficient and effective heuristic called Sequential Task Assignment Heuristic (STAH) is developed and demonstrated with numerical examples including real time operation.
In the third chapter, proposed persistent service is generalized for logistics service perspective. Bi-capacitated vehicle routing problem for heterogeneous automated robotic vehicles is introduced. Tasks are defined as Time-Space Trajectory Task (TSTT) or Stationary Service Task (SST). Each task has demand, required service time, own priority and time window. Each vehicle is restricted by fuel and loadable product capacity. Mathematical formulation with persistent and real time capability was proposed and verified via numerical examples. As a solution approach, branch and bound algorithm was developed with pruning rules, dominance properties, lower bound and upper bound algorithm. As an upper bound algorithm, sequential task assignment heuristic in chapter 2 was generalized. Proposed branch and bound algorithm can derive optimal solution much faster than CPLEX. Also, Generalized STAH can derive qualified solution in reasonably short time.
In the last chapter, we will compare the performance between developed algorithms, i.e., branch and bound (B&B) algorithm, genetic algorithm (GA), sequential task assignment heuristic (STAH) and generalized sequential task assignment heuristic (GSTAH). Due to the computational limitation of CPLEX, the optimality gap of each algorithm can be checked only for small size problems in each chapter. Therefore, we will use branch and bound algorithm to check the performance of each algorithm because branch and bound algorithm shows stronger computational power than CPLEX while deriving optimal solution as discussed. Also the example results and characteristic of developed algorithms were analyzed.
무인항공기와 같은 자동 로봇 차량의 운행 시간은 배터리 혹은 연료 용량에 의해 제한이 된다. 따라서, 무인항공기에 의해 수행가능한 임무 기간은 연료 충전 등의 보조 체계 없이는 제한이 된다. 그러나, 연료 서비스 스테이션등의 자동 지원 체계가 갖추어진 무인항공기의 시스템과 그것들을 아우르는 알고리즘일 활용한다면 오랜기간의 미션을 수행할 수 있다. 연료 수행으로 인하여 연료를 소모한 무인항공기는 새로운 무인항공기와 임무교대를 한다. 연료가 소모된 무인항공기는 근처의 지원 시설로 이동하여 연료를 충전한다. 이러한 지속 가능한 무인항공기 서비스를 지원하기 위하여 본 논문에서는 세 종류의 자동화 로봇을 위한 스케쥴링 문제 및 차량경로문제를 다룬다.
제 2장에서는 여러 개의 충전 기지가 존재하는 상황에서 복수의 무인항공기를 활용하여 이동하는 객체에 대한 감시 및 추적 서비스가 고려되었다. 이동하는 객체의 감시 및 추적 서비스는 이미 알려져 있는 것으로 가정되었으며, 무인항공기들은 최초에 충전 기지에 위치한다. 이러한 상황에서 수리적 모델을 통해 무인항공기의 운행 일정을 효율적으로 도출해 내었다. 제시된 수리적 모델의 복잡성을 해결하기 위하여 적은 수의 결정 변수를 지닌 새로운 수리적 모델 및 유전 알고리즘이 개발되었다.
제 3장에서는 2장에서 제시된 모델의 현실 적용을 위한 한계점이 해결되었다. 서비스의 운행 중 새로운 서비스의 요청, 예상 못했던 무인항공기의 손실, 급격한 연료 소모 등으로 인하여 새로운 운행 일정을 도출해야 할 상황이 발생 가능한데, 기존의 모델은 무인항공기가 최초에 충전 기지에 연료가 없는 상태로 존재한다는 가정사항이 존재하여 새로운 운행 일정 도출에 제약이 있었다. 따라서, 무인항공기들의 현재 위치 및 연료 상황, 남은 연료량에 반영된 충전 시간 등이 고려된 수리적 모델이 제시되었다. 지속적이고 신뢰성 있는 서비스의 제공을 위해 빠른 시간에 효율적인 운행 일정을 도출할 수 있는 순차적 임무 할당 알고리즘이 개발되었다.
제 4장에서는 위에서 제안된 수리적 모형이 일반화 된다. 즉, 복수의 차량들은 어느 기지에서나 충전 및 적재가 가능하다. 고객들은 이동 경로 혹은 고정된 위치 정보, 요구 수요, 서비스 시간, 우선수위 및 서비스 시작 시간에 대한 제약을 지니고 있으며, 차량들은 최초 위치, 연료 상황, 적재된 물품의 용량으로 정의된다. 이러한 상황에서 총 운행 거리의 합을 최소화시키며 수행된 임무들의 총 우선순위의 합을 최대화 시키기 위한 수리적 모델이 개발되었다. 개발된 모델의 최적해를 찾기 위하여 분기한정법이 개발되었다. 개발된 분기한정법은 상업적 소프트 웨어인 CPLEX보다 짧은 시간에 최적해를 찾을 수 있었다. 또한 더욱 짧은 시간에 효율적인 해를 찾기 위하여 3장에서 개발된 순차적 임무 할당 알고리즘이 4장에 맞게 일반화 되었다. 일반화된 순차적 임무 할당 알고리즘은 합리적인 해를 빠를 시간에 도출함으로써 실시간 서비스 운영을 위한 로봇 스케쥴링 도출에 적합한 알고리즘임이 증명되었다.
제 5장에서는 본 연구를 통하여 개발된 알고리즘의 성능 비교가 실행되었다. CPLEX, 분기한정법, 유전 알고리즘, 순차적 임무 할당 알고리즘, 일반화된 순차적 임무 할당 알고리즘이 2개의 예제를 통하여 성능 비교 및 원인 분석이 제공되었다.
본 연구에서 제시된 수리적 모형 및 해법 알고리즘들은 이동 경로를 포함한 복잡한 물류, 운송, 추적, 감시 임무 등을 수행하는데 있어서 효율적인 자동화 로봇의 운행 스케쥴을 합리적인 시간 안에 도출할 수 있다. 따라서, 자동화 로봇들을 통한 군사적, 물류 및 운송 임무들의 지속적이며 실시간적 운영에 크게 이바지 할 것으로 사료된다.
