본 논문은 다수의 목표물과 다수의 임무가 존재하는 상황에서의 다수 무인항공기의 임무할당 문제를 다룬다. 다수 무인항공기의 임무할당 문제는 순회 세일즈맨 문제, 차량 라우팅 문제와 같은 조합최적화 문제의 일종으로 NP-hard의 계산 복잡도를 가지고 있다. 이런 성격의 문제는 문제의 크기가 커질수록 계산시간이 급격히 증가하는 특징을 지니기 때문에 문제를 효율적으로 풀기 위해서 근사화 방법 또는 발견적인 방법을 사용한다. 본 연구에서는 임무할당 문제를 혼합정수 선형계획 문제로 정식화하고, 혼합정수 선형계획법과 유전 알고리듬으로 해를 구하였다. 다수의 목표물, 다수의 임무, 장애물이 존재하는 환경에 대한 수치 시뮬레이션을 수행하여 각 방법의 최적성과 효율성에 대해 검토하였다.
본 논문은 다수의 목표물과 다수의 임무가 존재하는 상황에서의 다수 무인항공기의 임무할당 문제를 다룬다. 다수 무인항공기의 임무할당 문제는 순회 세일즈맨 문제, 차량 라우팅 문제와 같은 조합최적화 문제의 일종으로 NP-hard의 계산 복잡도를 가지고 있다. 이런 성격의 문제는 문제의 크기가 커질수록 계산시간이 급격히 증가하는 특징을 지니기 때문에 문제를 효율적으로 풀기 위해서 근사화 방법 또는 발견적인 방법을 사용한다. 본 연구에서는 임무할당 문제를 혼합정수 선형계획 문제로 정식화하고, 혼합정수 선형계획법과 유전 알고리듬으로 해를 구하였다. 다수의 목표물, 다수의 임무, 장애물이 존재하는 환경에 대한 수치 시뮬레이션을 수행하여 각 방법의 최적성과 효율성에 대해 검토하였다.
This paper deals with a task assignment problem of multiple UAVs performing multiple tasks on multiple targets. The task assignment problem of multiple UAVs is a kind of combinatorial optimization problems such as traveling salesman problem or vehicle routing problem, and it has NP-hard computationa...
This paper deals with a task assignment problem of multiple UAVs performing multiple tasks on multiple targets. The task assignment problem of multiple UAVs is a kind of combinatorial optimization problems such as traveling salesman problem or vehicle routing problem, and it has NP-hard computational complexity. Therefore, computation time increases as the size of considered problem increases. To solve the problem efficiently, approximation methods or heuristic methods are widely used. In this study, the problem is formulated as a mixed integer linear program, and is solved by a mixed integer linear programming and a genetic algorithm, respectively. Numerical simulations for the environment of the multiple targets, multiple tasks, and obstacles were performed to analyze the optimality and efficiency of each method.
This paper deals with a task assignment problem of multiple UAVs performing multiple tasks on multiple targets. The task assignment problem of multiple UAVs is a kind of combinatorial optimization problems such as traveling salesman problem or vehicle routing problem, and it has NP-hard computational complexity. Therefore, computation time increases as the size of considered problem increases. To solve the problem efficiently, approximation methods or heuristic methods are widely used. In this study, the problem is formulated as a mixed integer linear program, and is solved by a mixed integer linear programming and a genetic algorithm, respectively. Numerical simulations for the environment of the multiple targets, multiple tasks, and obstacles were performed to analyze the optimality and efficiency of each method.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
본 논문에서는 다수의 목표물, 다수의 임무, 그리고 장애물이 존재하는 상황에서의 다수 무인항공기의 집중형 임무할당 문제를 혼합정수 선형 계획법과 유전 알고리듬을 사용하여 풀고 두 기법의 효율성과 최적성을 분석하였다. 본 논문의 구성은 다음과 같다.
다수의 목표물, 다수의 임무가 존재하는 상황에서의 다수 무인항공기 임무할당 문제는 조합최적화 문제의 한 종류로 이러한 문제를 효과적으로 풀기 위해서는 계산의 복잡도 측면을 고려해야 한다. 본 논문에서는 혼합정수 선형계획법과 유전 알고리듬을 이용하여 계산 복잡도 측면을 고려한 시나리오에 대해 임무할당 문제를 구성하고 해를 구하였다.
일반적으로 다수 무인항공기의 비행시간에 관련된 성능지수는 가장 오래 비행한 무인항공기의 비행시간을 줄이거나 개별 무인항공기의 비행시간의 합을 줄이도록 선택할 수 있다[11]. 본 연구에서는 개별 무인항공기의 비행시간을 줄이면서 무인항공기 그룹의 비행시간을 줄일 수 있도록 개별 무인항공기의 임무 수행시간의 총 합을 예측해야 할 비용으로 설정하였다.
염색체의 표현방법으로는 이진수 표현, 그레이 (Gray) 표현방법에서부터 k-진수 표현, 실수 또는 정수 표현, 다차원 표현 등에 이르기까지 다양한 표현법이 존재한다. 본 연구에서는 무인항공기의 임무할당을 표현하기 위해 자연수의 배열로 염색체를 표현하였다. 즉, Fig.
가설 설정
4. 무인항공기의 최대 임무수행 횟수는 제한이 없다고 가정한다.
5. 무인항공기 사이의 충돌은 없다고 가정한다.
무인항공기의 속도는 일정하다고 가정하여, 총 이동거리를 속도로 나누어 임무 수행시간을 계산하였다. 비용예측 시에는 임무할당 결과를 알 수 없기 때문에 노드와 노드사이의 비용을 선형 조합하여 전체 할당된 비용을 예측하였다.
임무수행 지역에는 3대의 동종의 무인항공기와 6개의 목표물이 존재하고, 무인항공기는 25m/s의 일정한 속도로 비행하며, 최소 회전반경은 100m로 가정하였다.
제안 방법
Ⅰ절에서는 연구배경과 동향, 연구내용을 서술하였고, Ⅱ절에서는 다수 무인항공기의 임무할당 문제를 정리하였다. Ⅲ절에서는 혼합정수 선형계획법과 유전 알고리듬을 이용해서 본 연구에서 고려한 문제를 구성하였다. Ⅳ절에서는 수치 시뮬레이션을 통해 두 방법을 비교 분석하고, Ⅴ절에서 결론을 지었다.
실제 다수 무인항공기의 임무할당은 임무를 수행하기 전에 중앙 컴퓨터에서 집중적으로 모든 무인항공기에게 임무를 할당하는 오프라인 방식과 비행 중에 무인항공기가 개별적으로 임무를 할당하는 온라인 방식으로 나눌 수 있고, 이 무인항공기의 임무할당 방식에 따라 정확한 해를 구하는 것과 효율적으로 해를 구하는 것에 대한 비중에 차이가 생기게 된다. 그래서 본 연구를 통해 효율성과 최적성 측면에서 혼합정수 선형계획법과 유전 알고리듬을 비교, 분석하고 임무할당 문제의 조건에 따른 각각의 방법의 특징과 한계를 조명하였고, 온라인과 오프라인 시스템에 적용 가능한 임무할당 기법에 대한 단서를 제시 하였다.
다수 무인항공기에 다수의 임무를 할당하는 경우, 무인항공기에 할당된 임무의 순서를 조정하는 것과 무인항공기 간의 임무를 교환하는 것이 이루어져야한다. 그래서 위와 같이 행으로 각각의 무인항공기를 나타내고 열로 목표물과 임무의 순서를 나타내는 염색체 표현법을 고려하였고, 염색체가 생성될 때 제한 조건(임무의 순서)을 만족하도록 염색체 내부 배열이 조정되도록 하였다.
돌연변이 연산은 Fig. 6과 같이 일정한 확률로 임무할당 순서를 변화시키거나 개별 무인항공기의 할당 결과를 교환하는 방식으로 구현하였다. 특히 개별 무인항공기 간의 임무를 교환하는 확률을 높여 교차연산의 단점을 보완하였다.
무인항공기의 경로생성은 구성한 가시성 그래프를 바탕으로 충돌에서 자유로운 노드를 경로점으로 설정하여 경로를 생성하였다.
경로점 통과 임무는 무인항공기가 주어진 지역을 한번만 통과해도 되는 임무임에 반해, WASM 임무는 하나의 목표물에 복합적인 임무를 수행해야 하므로 임무 수행순서와 같은 타이밍 제한조건을 가진다. 본 연구에서는 WASM 임무로서 목표물을 분류하고 공격하는 {Classification and Attack}, 공격 결과를 검증 하는 {Target Damage Assessment}로 임무를 분류하였다.
본 연구에서는 계산시간을 줄이기 위해서 비용을 예측하고 예측된 비용을 임무할당에 적용함으로써 임무할당 문제를 경로계획과 분리하였다.
문제의 특성상 임무할당은 무인항공기의 수, 목표물의 수, 임무의 수에 따라 고려해야 할 사항이 달라진다. 본 연구에서는 다수의 무인항공기의 임무할당 시나리오로 경로점 통과 임무와 일정지역을 탐색하고 위험시설을 공격한 후 이를 검증하는 WASM(Wide Area Search Munitions) 임무[6]를 고려하였다. 경로점 통과 임무는 무인항공기가 주어진 지역을 한번만 통과해도 되는 임무임에 반해, WASM 임무는 하나의 목표물에 복합적인 임무를 수행해야 하므로 임무 수행순서와 같은 타이밍 제한조건을 가진다.
무인항공기의 속도는 일정하다고 가정하여, 총 이동거리를 속도로 나누어 임무 수행시간을 계산하였다. 비용예측 시에는 임무할당 결과를 알 수 없기 때문에 노드와 노드사이의 비용을 선형 조합하여 전체 할당된 비용을 예측하였다. 노드와 노드 사이의 거리 d 는 Euclidean distance와 무인항공기의 최소 회전반경을 통해 근사화하였다.
장애물이 존재하는 경우에는 장애물 회피를 고려하여 노드와 노드사이의 비용을 예측해야 한다. 비용을 예측하기에 앞서 장애물과의 충돌에서 안전한 범위를 설정한 후에 가시성 그래프(Visibility Graph)를 Fig. 3과 같이 구성하였고, 목표물과 목표물 사이의 최소거리를 데이크스트라(Dijkstra) 알고리듬으로 계산하였다[13].
임무할당 문제에서 고려할 수 있는 비용(성능지수)으로는 에너지 소모량, 연료 소모량, 비행시간 등이 될 수 있다. 비용함수는 문제의 성격에 따라 다르게 설정될 수 있는데, 본 문제에서는 임무를 적절히 분배하여 무인항공기의 비행시간을 줄이는 것이 제한된 무인항공기의 비행시간을 최대한 활용하는 하나의 방법이라 간주하였다. 일반적으로 다수 무인항공기의 비행시간에 관련된 성능지수는 가장 오래 비행한 무인항공기의 비행시간을 줄이거나 개별 무인항공기의 비행시간의 합을 줄이도록 선택할 수 있다[11].
유전 알고리듬의 해집단 염색체 개수는 30개로 설정하였고, 모든 염색체가 동일한 적합도를 가진 상태에서 100번의 발생과정 동안 변화가 없으면 알고리듬을 종료하도록 하였다. 시뮬레이션은 2.
치환은 자식해의 품질을 기존 염색체 집단의 품질과 비교하여 가장 낮은 적합도를 가지는 염색체와 치환되도록 하였다. 치환이 일어날 때 우수한 품질의 해는 보존되므로 엘리티즘(Elitism) 은 따로 두지 않았다.
6과 같이 일정한 확률로 임무할당 순서를 변화시키거나 개별 무인항공기의 할당 결과를 교환하는 방식으로 구현하였다. 특히 개별 무인항공기 간의 임무를 교환하는 확률을 높여 교차연산의 단점을 보완하였다.
혼합정수 선형계획법을 통한 문제의 구성은 제한된 조건의 임무할당 문제[6]에 대해 본 문제에 적합하도록 수정, 보완하여 식을 구성하였다. 식을 구성하는 파라미터들은 Table 1에 정리하였다.
데이터처리
유전 알고리듬의 해집단 염색체 개수는 30개로 설정하였고, 모든 염색체가 동일한 적합도를 가진 상태에서 100번의 발생과정 동안 변화가 없으면 알고리듬을 종료하도록 하였다. 시뮬레이션은 2.6GHz dual core CPU, 2GB RAM의 컴퓨터에서 MATLAB 프로그램으로 수행하였다.
이론/모형
본 논문에서는 할당된 임무에 대한 경로생성을 위해 2차원 Dubins 모델을 고려하였다. Dubins 모델의 운동방정식은 다음과 같다.
본 연구에서는 경로점 통과 임무와 WASM 임무를 고려하여 시나리오를 구성하였으며, 혼합정수 선형계획법(MILP)과 유전 알고리듬(GA)을 이용하여 해를 구하였다.
선택 연산의 방법으로는 품질비례 룰렛휠 선택을 사용하였다. 품질비례 룰렛휠 선택 방법은 각각의 염색체가 적합도에 비례하는 룰렛휠 상의 공간을 가지고 있고, 랜덤 함수를 이용하여 룰렛 상의 염색체를 선택하는 방법이다.
혼합정수 선형계획법은 선형계획법과 정수계획법을 혼합한 방법으로 주어진 제한조건 내에서 성능지수를 최대 또는 최소로 하는 실수 및 정수 조건의 해를 구하는 방법이다. 이 방법은 정수인 조건의 해를 포함하기 때문에 계산의 복잡도가 증가하게 되는데, 이를 효과적으로 풀기 위해 분기한정법(Branch and Bound)을 사용한다[3,4].
성능/효과
1. 하나의 목표물에 수행되어야 할 임무가 다수인 경우, 임무가 순서대로 수행되어야 한다.
3. 임무가 할당되지 않거나, 할당된 임무를 모두 수행한 무인항공기는 종료 지점에서 임무를 종료한다.
질의응답
핵심어
질문
논문에서 추출한 답변
다수 무인항공기의 임무할당 문제는 어떤 방법을 사용한 연구가 수행되었는가?
다수 무인항공기의 임무할당 문제는 계산복잡도 관점에서 문제를 이해할 수 있다. 이에 대한 연구로 크게 혼합정수 선형계획법(MILP, Mixed Integer Linear Programming) 또는 메타-휴리스틱(Meta-heuristic) 방법 등을 사용해 왔다. 혼합 정수 선형계획법으로는 다수의 목표물과 단일 임무, 장애물이 존재하는 상황에 대한 임무할당[5], 타이밍 제한조건이 존재하는 경우의 임무할당[6,7] 등의 연구가 수행되었고, 메타 휴리스틱 방법으로는 개체 군집 최적화 알고리듬[8], 트리 서치 알고리듬[9], 유전 알고리듬(GA, Genetic Algorithm)[10-12] 둥의 방법을 사용한 연구가 수행되었다.
혼합 정수 선형계획법으로는 어떤 연구가 수행되었는가?
이에 대한 연구로 크게 혼합정수 선형계획법(MILP, Mixed Integer Linear Programming) 또는 메타-휴리스틱(Meta-heuristic) 방법 등을 사용해 왔다. 혼합 정수 선형계획법으로는 다수의 목표물과 단일 임무, 장애물이 존재하는 상황에 대한 임무할당[5], 타이밍 제한조건이 존재하는 경우의 임무할당[6,7] 등의 연구가 수행되었고, 메타 휴리스틱 방법으로는 개체 군집 최적화 알고리듬[8], 트리 서치 알고리듬[9], 유전 알고리듬(GA, Genetic Algorithm)[10-12] 둥의 방법을 사용한 연구가 수행되었다.
다수의 무인항공기를 이용하는 것의 장점은 무엇인가?
SEAD (Suppression of Enemy Air Defence)와 같은 군사적 임무수행에 다수의 무인항공기를 활용하려는 연구가 하나의 예이다. 다수의 무인항공기를 이용하면 단일 무인항공기에 비해 복잡한 임무를 효과적으로 수행할 수 있는 장점이 있다[1,2].
참고문헌 (14)
R. M. Murray, “Recent Research inCooperative Control of Multivehicle Systems”,Journal of Dynamic Systems, Measurement, andControl, Vol. 129, No. 5, 2007, pp. 571-583.
C. H. Papadimitriou, and K. Steiglitz,Combinatorial Optimization: Algorithms andComplexity, Prentice-Hall, Englewood Cliffs, NJ,1982.
T. H. Cormen, C. E. Leiserson, R. L.Rivest, and C. Stein, Introduction to Algorithms,2nd Ed., MIT Press, Cambridge, MA, 2001.
A. Richards, J. Bellingham, M. Tillerson,and J. P. How, “Coordination and Control ofMultiple UAVs”, AIAA Guidance, Navigation, andControl Conference, Monterey, CA, Aug. 2002.
C. Schumacher, P. Chandler, M. Pachter,and L. Pachter, “Constrained Optimization forUAV Task Assignment”, AIAA Guidance,Navigation, and Control Conference, Providence,RI, Aug. 2004.
M. Alighanbari, Y. Kuwata, and J. P. How, "Coordination and Control of Multiple UAVs with Timing Constraints and Loitering”, American Control Conference, Denver, CO, June 2003.
A. Salman, I. Ahmad, and S. Al-Madani “,Particle Swarm Optimization for TaskAssignment Problem”, Microprocessors andMicrosystems, Vol. 26, No. 8, 2002, pp. 363-371.
S. J. Rasmussen, and T. Shima, “Tree Search Algorithm for Assigning Cooperating UAVs to Multiple Tasks”, International Journal of Robust Nonlinear Control, Vol. 18, No. 2, 2007, pp. 135-153.
T. Shima, S. J. Rasmussen, A. G. Sparks,and K. M. Passino, “Multiple TaskAssignments for Cooperating UninhabitedAerial Vehicles using Genetic Algorithms”,Computers & Operation Research, Vol. 33, No.11, 2006, pp. 3252-3269.
Y. Eun, and H. Bang, “Cooperative TaskAssignment/Path Planning of MultipleUnmanned Aerial Vehicles Using GeneticAlgorithms”, Journal of Aircraft, Vol. 46, No. 1,2009, pp. 338-343.
H. Alt, and E. Welzl. "Visibility Graphs and Obstacle-Avoiding Shortest Paths”, Mathematical Methods of Operations Research, Vol. 32, No. 3-4, 1988, pp. 145-164.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.