As the capability of unmanned aerial vehicles (UAVs) increases, there is increased interest in exploiting UAVs for continuous and long-term missions. However, due to UAV fuel restrictions, it is not possible to con-duct long-term missions with a few UAVs. Rather, a system that includes multiple UAVs and automated re-charging stations is required to provide automatic and persistent service. We are concerned with a particular class of missions in which the system should provide an uninterrupted UAV presence to predefined target are-as. Such missions are common in local surveillance and monitoring tasks. In order to construct a system providing persistent presence, one key question is to determine the number of resources required - we call this a system design. Further, the assignment of resources to tasks – we call resource allocation. We are also inter-ested in a generalization of the problem in which each target region requires a different service level.
In the first chapter, we consider system design and resource allocation for the task of providing persistent UAV presence to multiple target areas with a single recharging station. The objective is to design the system which provides persistent presence that satisfies the required presence time ratio (service level) for each target. A decision-free Petri net model is developed that exploits the periodic nature of the problem and enables one to determine the number of resource required for fixed UAV routes. Combining the Petri net results with a search over feasible routes for the UAVs, a non-linear program with integer decision variables is developed to formalize the problem. A distance based heuristic and hybrid GA are developed to search for solutions and resolve the computational complexity of the problem. As the result, the number of resources and mission paths are derived.
In the second chapter, the perspective is expanded to allow for two types of service stations: refueling sta-tions and central maintenance stations. UAVs can travel further using the refueling stations. A decision-free Petri net model for persistency is developed for cyclic paths including multiple immobile targets and stations. From the Petri net model, we derive a closed-form function for the minimum number of resources in the per-sistent system. A mathematical model that has the objective function derived from the Petri net is developed. To resolve the computational issue, a genetic algorithm (GA) is used to solve the problem. As the result, the minimum number of resources required and the mission path are derived.
In the third chapter, resource allocation in a system where there are uncertain targets is conducted. Analyz-ing the number of resources required for uncertain targets is necessary to construct a new PUP system or pre-pare for a new target. We calculate 1) the expected number of resources for a single target uniformly distribut-ed in a disk centered at the station and 2) the expected number of resources required when the target’s location is assumed distributed in an arbitrary disk of given radius. We also analyze the properties of the system with uncertain targets and conduct a numerical study. Through the study, it is compared to the result from previous chapters. It is observed that the number of resources required increases inversely as the service area is widened to maximum capacity.
무인항공기 (UAV) 의 능력이 증가함에 따라, 무인기가 계속적이고 장기적인 임무를 수행할 수 있도록 하는 연구에 관심이 모아지고 있다. 그러나 그 연료 제약으로 인해, 소수의 무인기로는 장기적인 임무를 수행하기에 어려움이 있다. 그리하여 다수의 무인기와 자동화된 충전 스테이션으로 구성된 시스템이 지속적이고 자동화된 임무를 임무를 가능하게 한다. 우리는 미리 정의된 임무 지역들에 무인기가 상주하는 형식의 임무들을 다루려 한다. 그러한 임무들은 지역 순찰이나 관제 시스템에서 흔히 다루어 진다. 상주하는 시스템을 구축하기 위해서 중요한 요소 중에 하나는 바로 필요한 자원의 양을 결정하는 것이다. 우리는 이것을 시스템 설계라 부른다. 또한 그러한 자원들을 각 임무에 배치하는 문제를 자원 할당 문제라 부르기로 한다. 특히 이러한 문제를 일반화 시켜 각 임무 지역들이 다른 수준의 체류 율을 가지도록 하였다.
우리는 첫 번째 챕터에서, 다수의 임무 지역과 하나의 충전 스테이션이 존재하는 시스템에 대하여 무인항공기 상주 시스템을 운용하는데 있어 고려 되야 할 시스템 설계와 자원 할당 문제를 다루었다. 이 문제의 목적은 각 임무지역들의 최소로 요구되는 체류 율을 만족시키는 상주 시스템을 설계하는 것이다. 고정된 경로에 대해 주기성을 가지는 문제의 특성 상, 무 결정 페트리 넷을 개발하여 필요한 자원의 수를 결정하였다. 이러한 페트리 넷에 가능한 경로 탐색을 결합하여, 정수 변수를 가지는 비선형 문제를 수식으로 표현하였다. 문제의 복잡성을 해결하여 해를 탐색하기 위해, 거리 기반 휴리스틱과 하이브리드 유전 알고리즘을 개발하였다. 이를 이용하여 시스템에 필요한 자원의 수와 그 자원으로 수행 가능한 임무 경로를 결정하였다.
두 번째 챕터에서는, 시스템 내에서 중심, 재보급 스테이션의 두 가지 종류가 존재하도록 문제를 확장하였다. 재보급 스테이션의 존재로 인해 무인기는 더욱 멀리 비행이 가능하게 된다. 이러한 스테이션들과 다수의 고정된 목표들을 포함하는 주기적 경로를 위해 무 결정 페트리 넷을 개발하였다. 이러한 모델에 의해 우리는 무인기 상주 시스템에 요구되는 최소한의 자원을 결정하는 수식을 도출하였다. 이러한 수식을 목적 식으로 삼는 수리적 모델을 개발하였으며, 이 모델의 문제 복잡성을 해결하기 위해 유전 알고리즘을 개발하였다. 이로 인해 시스템을 위한 최소한의 필요 자원과 그 임무 경로를 결정하였다.
세 번째 챕터에서는 불분명한 목표물이 존재하는 시스템에 대한 자원 할당 문제를 다루었다. 이러한 불분명한 목표물을 위해 필요한 자원의 수를 분석하는 것은, 새로운 무인기 상주 시스템 구축이나 새롭게 편입되는 목표물을 위해 필수적이다. 우리는 1) 스테이션을 중심으로 하는 원반 형태인 영역에 균일하게 분포되어 있는 단일 목표물에 대한 필요 자원의 기대치, 2) 목표물의 위치가 주어진 반경을 가지는 원반 형태의 영역에 존재할 때 단일 목표물에 대한 필요 자원의 기대치를 계산하였다. 그리고 우리는 불분명한 목표물이 존재하는 시스템의 특성에 대해 분석하였으며 수치적 연구를 수행하였다. 이러한 연구를 통해 전 챕터에서의 결과와 비교하였다. 우리는 여기서 시스템의 서비스 지역을 비행 능력의 최대치로 넓히면 필요한 자원의 수가 기하급수적으로 증가하게 됨을 관찰하였다.