As a task assigned to an UAV becomes more complicated, the efficiency of operating these systems was encountered to the certain limitation using only a single UAV. On the other hand, managing the multiple UAVs system rises as an alternative way. To prevent from failing under the complicated missions, multiple UAVs system has been researched for risked missions such as the salvage works or the military operations owing to their high achievement ratio. In addition, this system is more resilient and adaptable to many kinds of missions than single UAV system, and it is also scalable and flexible to perform tasks and to achieve goals. Therefore, future systems of UAVs will be carried out by a large number of heterogeneous groups of both manned and unmanned sub-systems, which interact one another in systematic, hierarchical, and highly organic manners, so that a mission can be carried out with minimal collateral loss while maximizing the outcome.
This thesis aims to develop the architecture and algorithms for the multi-UAV systems, an indispensible component of future network-centric warfare systems or civil operations such as rescues or transportations. This thesis also pursue such a goal by researching on the component technologies for efficient operation of multiple UAVs, namely mission planning and assignment, information fusion and inference, dynamic mission allocation, path planning, and collision avoidance. The research outcomes on these component technologies will be then integrated, implemented, and validated in a series of simulations. Moreover, the final goal of this thesis is to propose the hierarchical architecture of the swarm intelligence system.
To achieve the objectives of this research, a hierarchical swarm intelligence system is presented. The overall system architecture is based on the objects. Four objects in this system will be presented: UAVs statuses, environments, missions and tasks, and communications and data sharing. In addition, each agent has a formal hierarchy which can be expressed as four layers: decision making layer, task assignment layer, path planning layer, and collision avoidance layer.
In addition, three specific techniques are introduced in this thesis. One in the task assignment algorithm is based on the negotiation process, which is applied for one task-to-one UAV matching process. The main difference between other algorithms is that the proposed procedure is progressed with the path planning algorithm in real time. Although these presented algorithms are uncomplicated because those algorithms start from the fundamental concept of the negotiation process, it can find the reasonable path efficiently owing to the fast convergence for the result. Therefore, this algorithm can show the powerful procedure and fast computation time though this method can be classified by the direct approach, and it also generate the admissible solution for complex cases such as urban environments.
Another technique for path planning layer is an efficient path planning algorithm for collision avoidance of obstacles in a given environment. This presented algorithm can be a method to find the shortest path in complex surroundings and can be applied from totally known environments to totally unknown environments. It is an axiom that the shortest path between two points in two or three-dimensional space is the line which connects two points. The main idea of this presented algorithm starts on this axiom, and it is a major difference from the other path planning algorithms. To find the shortest path efficiently and correctly, a fundamental concepts of A* algorithm is used.
The other method is a low-level trajectory planning algorithm considering the collision avoidance between UAVs, and partially known obstacles or threats. The proposed algorithm is based on the fundamental concepts of two algorithms: receding horizon control and potential-field planning. The receding horizon control has been being actively studied since a decade ago, and the potential field-based approach for the path planning or the collision avoidance guidance is also widely applied for mission planning.
This thesis also contains the result from a simulation of hierarchical swarm intelligence system by using the overall proposed algorithms. This simulation is the result from integration among the task assignment, path planning, and collision avoidance in three-dimensional space. The outcomes from the simulation show that it is adequate to apply to the swarming of UAVs as squads and it is well interlocked between different layers. The results also show that it is simple but powerful to apply in real time because of the hierarchical system.
미래의 전투체계는 다수의 유인 또는 무인 시스템이 체계적, 계층적, 유기적으로 통합되어, 정확하고 다양한 정보에 기반하여 최소의 부수적인 손실로 최대한의 성과를 거둘 수 있는 방향으로 개발될 것이다. 이를 위해서는 서로 다른 다수의 시스템의 통합과 운용기술의 개발이 요구된다.
복수의 무인기를 사용하여 임무를 수행하기 위해서는 기존의 운용기법보다 훨씬 정교하고 계속 변화하는 상황에 유연하게 대처할 수 있을 운용기법이 요구된다. 여기에는 사전에 주어진 임무를 분석하고 계획하는 임무 계획 기술, 각각의 무인기에 임무를 분담시키는 임무 할당기술, 각 무인기의 실제 임무수행을 위한 경로생성 기술 및 충돌 회피 기술이 포함된다. 임무 수행 중에는 기존에 인식된 장애물에 추가하여 주변 항공기 및 새로 인식된 장애물이나 위협요소들을 고려하여 안전하고 협응적으로 대처할 수 있는 기술도 요구된다.
이 논문에서는 다수의 무인항공기를 효율적으로 운용할 수 있는 제반 소요 기술들을 제안함과 동시에, 시스템을 효율적으로 운용할 수 있는 계층적인 시스템을 제안하였다. 계층화된 복수 무인항공기의 군집지능 시스템의 데이터 구조는 네 개의 객체(object)로 구성되며, 각각 무인항공기의 상태(status), 임무를 수행하는 환경(environment), 임무와 이를 구성하는 작업(task), 그리고 각 무인기들 간의 통신(communication) 및 정보 공유(data sharing)를 나타낸다. 또한, 각 무인기의 시스템은 크게 의사 판단(decision making), 임무할당(task assignment), 경로계획(path planning), 그리고 충돌회피(collision avoidance)의 층(layer)으로 구성된다. 객체 지향적인 데이터 구조와 계층화된 무인기 시스템의 연동을 통해 서로 다른 우선순위를 가지는 층들 사이에 필요한 데이터 및 명령들을 효율적으로 관리할 수 있게 하였다.
이와 함께, 각 층에 필요한 기술들을 제안하여 모의실험을 통해 각 기술들의 성능을 분석하였다. 먼저, 임무할당을 위해 협상(negotiation) 기반의 임무 할당 기술을 제안하였다. 이 기술은 한 개의 임무에 단수의 무인기가 전임하는 방식으로써, 실시간에서 무인기의 수와 임무의 수가 다를 경우에도 준최적(sub-optimal)의 해를 보여준다.
경로 생성 기술로서, 선(line) 기반의 경로 생성법을 제안하였다. 제안한 알고리듬은 유클리디안(Euclidean) 공간에서의 기본적인 공리(axiom)와 A* 알고리듬의 기본 개념을 응용한 것으로, 임무 환경에 주어진 장애물을 회피하여 최단 거리를 찾아낸다. 이 알고리듬은 최소한의 데이터를 이용하여 빠른 시간 내에 최적의 해를 보이는 장점을 지니며, 모두 알려진 환경이나 부분적으로 알려진 환경, 전혀 알지 못하는 환경에서도 실시간으로 적용할 수 있다.
가장 최하층에 위치하는 충돌회피 궤적 생성법은 임무를 수행하면서 각 무인기들 간의 충돌이나 알려지지 않은 장애물들을 회피하는 알고리듬으로, 모델 추정 기법(model predictive control)과 포텐셜 필드 기법(potential field method)의 기본 개념을 이용하였다.
비록 제안한 알고리듬과 시스템의 구조는 복잡하지 않지만, 실시간으로 효율적인 결과를 보임을 모의실험을 통해서 확인하였다. 특히 모의 실험 결과는 분대(squads)로 구성된 복수 무인기의 군집 지능 시스템에 적용이 가능하며, 계층화된 구조로 인하여 실시간에도 충분히 적용할 수 있을 정도의 낮은 연산 시간을 보인다. 또한, 부록에 수록된 무인자율주행차량의 충돌회피 기술은 최하층에 위치한 충돌 회피법을 이용한 것으로, 실험 결과는 무인기에도 적용이 가능함을 보여준다.
마지막으로, 본 연구를 통해서, 복수 단위의 무인기에 대한 유기적인 운용 기술을 개발하고, 유인기와 무인기와의 통합 운용 기법 개발에도 응용할 수 있을 것으로 기대된다. 뿐만 아니라 유인기의 충돌 회피 기술 및 운항안정성을 향상시킬 수 있을 것으로 기대할 수 있으며, 무인항공기 분야뿐 아니라 무인 전투 차량이나 무인 잠수정과 같은 무인 시스템에도 용이하게 적용할 수 있을 것으로 기대한다.
