This thesis addresses a formulation and develops novel approaches to solve a nonholonomic path planning problem for a group of heterogeneous unmanned aerial vehicles (UAVs) with capabilities of executing tasks remotely in a two-dimensional environment. The purpose of the path planning problem is to find an appropriate tour for each vehicle with minimum costs such that all the tasks in the mission are visited by one of the vehicles. In general, each vehicle has different motion constraints and is located at different points when starting the mission. A sum of two terms, the normalized sum of the total tour cost and the largest cost tour among the vehicles, is used as the objective function to be minimized. In particular, the proposed algorithms are structured to obtain high performance with considering the motion constraints of the vehicles when the tasks are closely located. The problem is formulated as a Mixed-Integer Linear Programming (MILP) based on the sampling-based roadmap, and three different approaches are proposed: a) the main ingredient of a branch-and-cut algorithm to compute the optimal solution; b) the transformation method which changes the given problem instance into the form of asymmetric traveling salesman problem to use the Lin-Kernighan-Helsgaun heuristic; c) the memetic algorithm to obtain the the near-optimal solution. After obtaining solutions from the above approaches, the path refinement process is applied to locally optimize the obtained solution. Comparative numerical experiments show the validity and efficiency of the proposed methods compared with the previous methods.
In addition, the transformation method is utilized in an observation task scheduling of a heterogeneous satellite constellation orbiting in the low-Earth-orbit area. The purpose of the problem is to find a scheduling output that maximizes the sum of profits while following all of the constraints originating from the complex mission environment. The scheduling problem is modeled as an instance of asymmetric traveling salesman problem (ATSP), and then solved using the Lin-Kernighan-Helsgaun algorithm available for the ATSP. Numerical experiments are designed to show the characteristics, efficiency, and scalability of scheduling results which has an improvement of up to 20% in the sum of profits and the number of assignments over the first-in/first-out strategy-based greedy algorithm.
본 학위 논문에서는 2차원 환경에서 원격 임무 수행하는 이종 무인 비행체 군집에 대한 논홀로노믹 경로 계획에 대한 문제 정의 및 여러 효과적인 접근법에 대하여 다룬다. 본 논문에서 다루는 경로 계획 문제의 목적은 무인체 군집이 주어진 모든 임무 지역을 주어진 조건 하에서 최소의 비용으로 순회하는 것이다. 일반적으로 각 비행체는 모델에 따라 서로 다른 동적 구속 조건을 가지며, 임무 시작 시점에 임의의 상태에 놓임을 가정할 수 있다. 목적 함수는 각각 군집 전체의 비용에 대한 항과 각 무인체의 비용 중 최대 비용에 대한 항 두 가지로 이루어져 있으며, 이를 통해 전체적인 임무 비용 및 각 무인체 간의 비용 차이를 최소화할 수 있다. 특히, 논문에서 제안하는 기법들은 임무 지역이 비행체의 동적 구속 조건에 비해 밀집되어 위치하는 경우에 기존의 기법들에 비하여 상당한 효율을 얻을 수 있도록 고안되었다. 경로 계획 문제는 샘플링 로드맵 기반의 혼합 선형 정수 계획법으로 구성하며, 크게 다음의 세 가지 기법을 통해 문제를 접근한다: a) 문제의 최적 해를 구하기 위한 branch-and-cut 알고리듬의 주요 부분을 제안한다; b) 문제의 인스턴스를 비대칭 외판원 문제 꼴로 변환하는 기법을 제시하여 Lin-Kernighan-Helsgaun 휴리스틱을 적용할 수 있도록 한다; c) 준 최적해를 구하기 위한 모방 알고리듬을 제시한다. 마지막으로는 위의 기법들을 통해 얻은 해를 지역적으로 최적화하는 경로 정제 기법을 제안한다. 다수의 수치 시뮬레이션 결과 및 분석을 통하여 제안한 기법이 기존의 기법에 비하여 해의 성능 및 계산 시간 측면에서 뛰어남을 보인다.
이에 덧붙여, 본 논문에서 제시하는 두 번째 기법과 유사한 기법을 통해 이종 저궤도 인공위성군의 관측 임무 스케줄링 문제를 풀 수 있음을 보인다. 문제의 목적은 각 위성이 복잡한 임무 환경에서 기인하는 모든 구속 조건을 따르면서 최대의 이익을 얻을 수 있는 임무 스케줄을 얻는 것이다. 스케줄링 결과는 문제 인스턴스를 비대칭 외판원 문제 꼴로 변환된 후 Lin-Kernighan-Helsgaun 휴리스틱을 통해 얻을 수 있으며, 단순한 선입선출 전략 기반의 욕심쟁이 알고리듬에 비해 최대 20% 정도의 효율 향상을 얻음을 보인다.
