This thesis studies an autonomous mission planning algorithm that enables unmanned aerial vehicles (UAVs) to autonomously re-plan missions without human direct intervention under various dynamic mission environment changes, such as the creation of new missions, cancellation or change of existing missions. In this study, the mission re-planning problem is developed based on the Team Orienteering Problem (TOP), one of the variants of the Vehicle Routing Problem with Profits (VRPP). Existing deep reinforcement learning (DRL) based methods have largely focused on learning heuristics for Vehicle Routing Problem (VRP) and its variants that intrinsically have vehicles departing from a given depot and returning to that depot. While this setting is necessary to plan routing missions in advance, it needs to be expanded to cope with mission re-planning scenarios where vehicles are located away from the depot at the start. Additionally, many real-life re-planning situations are subject to a fuel constraint on each vehicle, which is likely to have variable remaining fuel. Therefore, this thesis investigates a Multiple-Start TOP (MSTOP), in which vehicles begin at multiple random locations, travel to maximize the total prizes, and arrive at the given depot, while satisfying fuel constraints. To solve MSTOP, this thesis proposes a methodology consisting of self-attention mechanism on each partial tour, and encoder-decoder attention mechanism between partial tour and remaining nodes. The proposed DRL-based method produces a suboptimal solution comparable to the existing meta-heuristic techniques, even for more complex problems. Furthermore, several case studies are presented to demonstrate the performance of the proposed model and solution procedure.
본 학위논문은 무인기가 임무수행 중 임무 지역에 대한 불확실한 정보로 인하여 발생하는 새로운 임무의 생성, 기존 임무의 취소 또는 변경 등과 같은 여러 동적 임무 환경 변화에 대하여 사람의 직접적인 개입 없이 무인기가 자율적으로 임무을 재계획할 수 있는 자율 임무 계획 알고리즘을 연구한다. 본 연구에서는 이러한 무인기 임무 재계획 문제를 이익에 기반한 차량 경로 결정 문제 (Vehicle Routing Problem, VRP)의 변형 중 하나인 Team Orienteering Problem (TOP)를 근간으로 설계한다. 하나 이상의 무인기가 임무 지역에서 활동할 때, 임무 환경의 동적 변화에 대한 신속하고 정확한 임무 재계획이 필요하다. 기존 방법의 경우, 빠르지만 준최적성을 갖는 다양한 Meta-heuristic 기법이 존재한다. 그러나, 무인기 개수 또는 임무점 개수가 증가하는 복잡한 시나리오에서는 현존하는 Meta-heuristic 기법의 성능은 현저히 떨어진다. 이를 극복하기 위해 최근 들어 각광을 받고 있는 심층 강화학습 기반의 새로운 방법론을 제시하고자 한다. 본 연구에서 제안한 심층 강화학습 기반의 방법은 문제의 복잡도가 증가할수록 기존 Meta-heuristic 기법 대비 신속하면서도 최적해와 가까운 준최적해를 도출한다. 이를 토대로 여러 임무 동적 변화 시나리오에 대해 심층 강화학습 기반 방법론의 성능을 기존 기법 및 MILP를 활용한 최적해 및 준최적해와 비교하여 그 성능을 검증한다.
