[논문]다수의 위협과 복수의 목적지가 존재하는 임무에서 복수 무인기의 생존율 극대화를 위한 최적 경로 계획 및 분석

정성식; 장대성; 박현진; 성태현; 안재명

doi:10.5139/jksas.2015.43.6.488

다수의 위협과 복수의 목적지가 존재하는 임무에서 복수 무인기의 생존율 극대화를 위한 최적 경로 계획 및 분석
Optimal path planning and analysis for the maximization of multi UAVs survivability for missions involving multiple threats and locations 원문보기

한국항공우주학회지 = Journal of the Korean Society for Aeronautical & Space Sciences, v.43 no.6, 2015년, pp.488 - 496

정성식 (Korea Advanced Institute of Science and Technology) , 장대성 (Korea Advanced Institute of Science and Technology) , 박현진 (Korea Advanced Institute of Science and Technology) , 성태현 (Korea Advanced Institute of Science and Technology) , 안재명 (Korea Advanced Institute of Science and Technology)

초록
AI-Helper

본 연구에서는 각각 다른 목적지에서 다수의 임무를 수행해야하는 복수 무인항공기(Unmanned Aerial Vehicle, UAVs)의 경로를 결정할 때, 무인항공기의 생존가능성을 고려하여 경로를 결정하는 프레임워크를 제안하였다. 본 라우팅 문제는 무인항공기 안전과 임무 완료시간 간의 trade-off 를 나타내는 비용 매트릭스를 이용한 차량경로문제(Vehicle Routing Problem, VRP)로 정의할 수 있다. 특정위치에서 무인항공기의 위험 레벨은 감지될 확률과 격추될 확률을 고려하여 모델링 하였고, 위협 레벨과 비행거리를 고려한 두 지역간의 최소비용경로는 육각형격자(Hexagonal cells)에서 Dijkstra 알고리듬을 사용하여 결정하였다. 또한, 지속적으로 다수의 적을 감시 정찰하는 임무를 수행하는 복수 무인항공기의 최적경로를 결정하는 case study를 수행하였으며, 그 결과를 논의하였다.

Abstract ▼ AI-Helper

This paper proposes a framework to determine the routes of multiple unmanned aerial vehicles (UAVs) to conduct multiple tasks in different locations considering the survivability of the vehicles. The routing problem can be formulated as the vehicle routing problem (VRP) with different cost matrices representing the trade-off between the safety of the UAVs and the mission completion time. The threat level for a UAV at a certain location was modeled considering the detection probability and the shoot-down probability. The minimal-cost path connecting two locations considering the threat level and the flight distance was obtained using the Dijkstra algorithm in hexagonal cells. A case study for determining the optimal routes for a persistent multi-UAVs surveillance and reconnaissance missions given multiple enemy bases was conducted and its results were discussed.

주제어

AI 본문요약
AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

각 정점에는 위치정보와 2장에서 정의한 확률 모델에 따른 그 지점에서의 탐지확률(P(D))과 격추확률(P(N|D)) 정보가 들어있으며, 이 정보를 간선의 가중치에 반영하여 목적지까지 무인항공기의 생존확률을 최대화하는 경로를 구성하고자 한다.
또한 고장확률을 고려하는 것이 최적 경로를 결정하는데 어떠한 영향을 미치는지 알아보기 위하여, 전체 무인항공기의 생존확률을 최대화 하는 목적을 가지고 동일한 조건하에서 고장확률을 고려할 경우와 고려하지 않을 경우의 결과를 비교해 보았다.
일반적으로 VRP문제는 NP-hard 문제로서 문제의 크기가 커질수록 계산량이 지수적으로 증가하게 되며, 해를 제공하지 못하는 경우도 생긴다. 무인항공기의 임무의 경우 비행거리와 시간의 제약으로 인해 문제의 크기의 크지 않을 것이라 판단하여, 본 논문에서는 모든 경우의 수에 대해 분석하는 방법으로 최적 경로를 탐색하였다.
일반적인 VRP에서의 비용은 주로 이동거리나 소요시간을 환산하여 계산한다. 본 논문에서는 각 경로의 무인항공기 생존확률을 비용으로 환산하여, 전체 목적지를 방문하고 돌아올 때까지의 생존확률을 최대화하는 경로를 찾고자 한다.
본 논문에서는 거리에 따른 레이더의 탐지 성능을 분석하기 위하여, 레이더 종합적인 성능을 나타내는 Signal to Noise Ratio(SNR) 공식(1)과, SNR에 따른 레이더 탐지 확률 공식(3)을 이용하여 거리에 따른 탐지 확률을 분석하였다.
본 논문에서는 다수의 위협이 존재하는 상황에서 복수의 목적지를 방문해야하는 임무를 수행하는 무인항공기의 생존가능성을 최대화 하는 최적 경로 결정 방법을 제안하였다. 레이더의 성능, 적군 무기의 종류, 규모 등을 고려하여 다수의 위협에 대해 위험도를 평가하고 수치적 값을 얻기 위하여 각각의 확률모델을 설계 하였다.
본 논문에서는 복수의 무인항공기가 다수의 위협이 존재하는 지역에서 복수의 목적지를 모두 방문해야하는 임무를 가지고 있을 때, 무인항공기의 격추확률과 고장확률을 모델링하고 이를 바탕으로 무인항공기의 생존성을 최대화하는 경로 최적화 기법을 제안하였다. 또한 이때의 임무 성공 가능성 분석을 수행하였다.
본 연구에서 다루고자 하는 문제는 다수의 위협이 존재하는 상황에서 복수의 목적지를 방문하고 돌아오기까지 복수무인항공기의 생존가능성을 최대화하는 최적 이동경로를 구성하는 문제이다. 3장에서는 앞서 수행한 위험도 확률모델을 바탕으로, 각 지점사이의 생존확률을 최대화 하는 최적경로 결정방법을 제안하고, 차량경로문제로 접근하여 복수의 목적지를 방문하는 최적 경로를 결정하는 프레임워크를 제안한다.

가설 설정

본 논문에서는 다수의 위협이 존재하는 경우를 고려하기 때문에, 다수의 레이더가 존재할 경우의 탐지확률 모델링을 수행해야한다. 각 레이더의 거리에 따른 탐지확률은 Fig. 2와 같은 확률 분포를 가지며, 각각의 레이더에 의해 탐지되는 사건은 상호 독립이라 가정한다. 즉, k개의 레이더가 존재하는 지역에서 무인항공기가 단위시간동안 (x,y,z)위치에 존재할 때 탐지될 확률은 식(5)와 같이 표현할 수 있다.
각 목적지의 불확실성은 시간에 따라 선형적으로 증가한다고 가정하였으며, 각각 일정 기준 이상이 될 때 그 지역을 방문해야 하는 임무가 발생한다고 가정하였다. 목적지를 방문하라는 임무가 발생하였지만, UAV가 모두 추락하여 더 이상 임무를 수행하지 못하게 될 경우 임무가 실패하였다고 정의하였다.
각 셀의 중심은 그래프 이론의 정점이며 무인 항공기는 매 시간 하나의 셀 안에 위치한다. 각 정점사이의 거리는 단위시간동안 무인항공기의 이동거리와 같으며, 단위 시간이 경과 시에 인접 셀로 반드시 이동해야 한다고 가정하였다. 또한 각 정점을 이은 선분은 이동 경로 및 간선을 뜻한다.
따라서 다수의 위협이 존재하는 지역에서 무인항공기가 격추될 확률은 탐지확률과 탐지되었을 때 적군에 의해 격추될 확률로 구분해서 분석할 수 있다. 또한 탐지가 되지 않았을 경우는 격추될 확률이 없다고 가정하였다. 이는 다음과 같이 표현할 수 있다.
본 문제에서는 실제 레이더 성능을 고려하여 각 파라미터를 P(FA) = 10-6, a = 5.119 X 105, σ=1로 가정하였다.
여기서 P_b는 단위 시간 당 고장확률을 의미하며, UNMANNED AIRCRAFT SYSTEMS ROADMAP[13]에서 공개된 값을 참고하여 비행시간 당 고장확률을 가정 하였다.

제안 방법

1장에서 언급한 두 지점사이의 생존확률을 최대화하는 최적 경로로 결정하였다. 각 지점사이의 최적 경로를 바탕으로 VRP를 풀었으며, 다음과 같은 세 가지 경우에 대하여 최적화 문제의 목적을 정의하고 최적 경로 탐색을 수행하였다.
으로 나누어 분석하였다. 각각의 사건은 N(적의 공격으로 격추된 사건), D(적의 레이더에 의해 탐지되는 사건), B(고장으로 인해 추락한 사건)으로 표현하고, 위험도를 다음과 같이 확률 모델을 적용하여 수학적으로 모델링 하였다.
곱을 합으로 표현하기 위하여 양변을 log변환하였으며, 최소화 문제로 만들기 위해 양변에 음수를 취하여 최적화 문제의 목적을 다음과 같은 형태로 변환하였다.
본 연구에서는 그래프로 표현하기 위해 활동 영역을 셀 (cell)로 분할하였다. 균일한 크기로 평면을 분할할 수 있는 기하학적 도형인 3각형, 4각형, 6각형의 셀 중, 자유도가 큰 정6각형 형태의 셀(Fig. 5)을 사용하였다. 여기서 자유도가 크다는 의미는 현재의 셀에서 이동 가능한 이웃한 셀의 개수가 많다는 것을 의미한다.
따라서 격추 확률은 탐지 확률과 탐지되었을 때 격추될 확률로 나누어 고려할 수 있다. 또한 격추될 확률만 고려할 경우 위험지역을 피하기 위해 비효율적으로 긴 비행경로를 선택할 수 있기 때문에, 비행시간에 따른 무인항공기의 고장 확률을 고려하였다.
본 논문에서는 복수의 무인항공기가 다수의 위협이 존재하는 지역에서 복수의 목적지를 모두 방문해야하는 임무를 가지고 있을 때, 무인항공기의 격추확률과 고장확률을 모델링하고 이를 바탕으로 무인항공기의 생존성을 최대화하는 경로 최적화 기법을 제안하였다. 또한 이때의 임무 성공 가능성 분석을 수행하였다.
본 논문에서는 다수의 위협이 존재하는 상황에서 복수의 목적지를 방문해야하는 임무를 수행하는 무인항공기의 생존가능성을 최대화 하는 최적 경로 결정 방법을 제안하였다. 레이더의 성능, 적군 무기의 종류, 규모 등을 고려하여 다수의 위협에 대해 위험도를 평가하고 수치적 값을 얻기 위하여 각각의 확률모델을 설계 하였다. 주로 시간이나 거리의 최소화 문제로만 접근했던 기존 차량경로문제(VRP)들과 달리 각 간선에 생존확률을 가중치로 두어 그 확률을 최대화 하는 경로를 최적경로를 결정하였다.
이때의 각 간선은 그 경로의 무인항공기 생존확률을 가중치로 갖고, 이를 바탕으로 VRP를 수행하여 전체 경로를 결정한다. 모든 목적지를 방문하고 돌아올 때까지 생존확률을 최대화 하는 것이 목적이며, 모든 목적지를 방문하되 각각의 지점은 한번씩 만 방문되어야 하고, 각 무인항공기의 최대 비행시간을 제약조건으로 고려하였다.
최단경로를 찾는 알고리듬은 이 경로를 구성하는 간선들의 가중치 합을 최소로 하는 경로를 찾는 것으로서, 모든 간선에 대해 음의 가중치를 허용하지 않는 Dijkstra 알고리듬과 음의 가중치를 허용하는 Bellman-Ford 알고리듬 등이 있다[14]. 본 논문에서는 항상 최단 경로 탐색을 보장하는 Dijkstra 알고리듬을 사용하여 출발점과 도착점사이의 최단경로를 결정하였다.
최적 경로를 결정할 때, 목적함수와 제약조건에 따라 다양한 결과가 나올 수 있다. 본 연구에서는 2대의 무인기가 동시에 임무를 수행할 수 있는 경우를 고려하였으며, 각 지점사이의 경로는 3.1장에서 언급한 두 지점사이의 생존확률을 최대화하는 최적 경로로 결정하였다. 각 지점사이의 최적 경로를 바탕으로 VRP를 풀었으며, 다음과 같은 세 가지 경우에 대하여 최적화 문제의 목적을 정의하고 최적 경로 탐색을 수행하였다.
각 지점사이의 최적 경로를 최단경로기법을 적용하여 구하기 위해선 무인항공기의 활동영역을 그래프 G = (V,E)로 표현해야한다. 본 연구에서는 그래프로 표현하기 위해 활동 영역을 셀 (cell)로 분할하였다. 균일한 크기로 평면을 분할할 수 있는 기하학적 도형인 3각형, 4각형, 6각형의 셀 중, 자유도가 큰 정6각형 형태의 셀(Fig.
으로 나누어 분석하였다. 각각의 사건은 N(적의 공격으로 격추된 사건), D(적의 레이더에 의해 탐지되는 사건), B(고장으로 인해 추락한 사건)으로 표현하고, 위험도를 다음과 같이 확률 모델을 적용하여 수학적으로 모델링 하였다.
조건부 확률인 P(N|D)는 적의 레이더에 탐지되었을 경우 격추될 확률을 의미하며, 적군의 위치와 규모, 무기 종류에 따라 그 범위와 격추확률 등이 달라질 것이다. 이를 표현하기 위해 bell shaped function을 적용하여 확률 분포를 다음과 같이 모델링하였다.
레이더의 성능, 적군 무기의 종류, 규모 등을 고려하여 다수의 위협에 대해 위험도를 평가하고 수치적 값을 얻기 위하여 각각의 확률모델을 설계 하였다. 주로 시간이나 거리의 최소화 문제로만 접근했던 기존 차량경로문제(VRP)들과 달리 각 간선에 생존확률을 가중치로 두어 그 확률을 최대화 하는 경로를 최적경로를 결정하였다. 각 정점들 사이의 최대 생존확률 경로를 다익스트라(Dijkstra)알고리듬을 이용하여 구한 후 VRP를 수행하여 전체 최적 경로를 결정하였다.

이론/모형

주로 시간이나 거리의 최소화 문제로만 접근했던 기존 차량경로문제(VRP)들과 달리 각 간선에 생존확률을 가중치로 두어 그 확률을 최대화 하는 경로를 최적경로를 결정하였다. 각 정점들 사이의 최대 생존확률 경로를 다익스트라(Dijkstra)알고리듬을 이용하여 구한 후 VRP를 수행하여 전체 최적 경로를 결정하였다.

성능/효과

48% 증가하는 것을 볼 수 있다. 또한 얻어진 경로에 대하여 고장확률을 고려하여 무인항공기의 생존 가능성을 분석해보면 76.36%로 생존확률이 더 낮아지는 것을 확인할 수 있다.
본 연구로 얻어진 결과를 통해 위험도를 최소화 하는 경로를 결정할 수 있으며, 생존확률 최대화, 총 이동거리 최소화, 임무수행시간 최소화의 각 목적함수에 따라 그 경로와 결과 값들이 어떻게 결정되는지 확인할 수 있다. 또한 지속적으로 임무를 수행할 때, 그 임무의 성공가능성을 확인할 수 있다.
위의 최적 경로의 결과와 동일조건하에서 고장확률을 고려하여 얻어진 경로의 결과를 비교해 보면 이동거리는 약 35.65%, 임무완료시간은 약 12.48% 증가하는 것을 볼 수 있다.
81km, 임무 완료시간은 13540s이다. 전체 이동 경로를 최소화하는 경우(Fig. 10)의 무인기 생존확률은 77.62%, 총 이동거리는 592.58km, 임무 완료시간은 14090s이며, 임무 완료 시간을 최소화하는 경로(Fig. 11)의 경우 각각 76.54%, 920.47km, 12980s의 결과를 얻을 수 있다.

후속연구

2는 가정한 조건하에서 SNR에 따른 탐지확률과, 거리에 따른 탐지확률 그래프이다. 본 논문에서는 다수의 위협이 존재하는 경우를 고려하기 때문에, 다수의 레이더가 존재할 경우의 탐지확률 모델링을 수행해야한다. 각 레이더의 거리에 따른 탐지확률은 Fig.
미국, 이스라엘 등의 선진국을 중심으로 세계 각국에서 무인항공기 개발이 활발히 이루어지고 있으며 구글, 아마존 등의 다국적 기업도 무인항공기를 활용한 서비스 사업에 뛰어드는 등 항공우주산업 분야에서 가장 빠른 성장세를 기록하고 있다. 향후 민간 무인항공기 시장이 활성화된다면 그 발전 속도는 더욱 더 빨라질 것이다.

질의응답

핵심어	질문	논문에서 추출한 답변
	무인항공기 운용에서 중요한 경로 계획이란 무엇인가?	무인항공기 운용에서 중요한 요소 중 하나는 경로 계획(path planning)이다. 경로 계획이란 현재 위치로부터 목적지에 도달하는 과정에서 걸리는 시간이나 거리, 소모 연료 등을 고려하여 효과적인 이동 경로를 사전에 계획하는 것이다. 일반적인 경로 계획 문제에서는 주로 경로의 길이나 이동에 걸리는 시간을 비용으로 고려하여 최소화 하는 문제, 즉 최단 거리 경로나 최소 시간 경로를 찾는다.
	무인항공기가 유인 항공기에 비해 가지는 장점은 무엇인가?	무인항공기(Unmanned Aerial Vehicle, UAV)는 조종사가 탑승하지 않고 지정된 임무를 수행 할 수 있도록 제작된 비행체로서 사람이 탑승하지 않기 때문에 인명 손실에 대한 위험 없이 위험요소가 존재하거나 오염된 지역에서의 작전수행이 가능하다. 또한 유인항공기에 비해 상대적으로 조작 방법이 손쉽고 기체 소형화를 통해 레이더 피탐성 감소가 가능하다는 장점을 가지고 있다[1]. 이러한 장점으로 인해 무인항공기는 감시정찰, 공격, 전자정보전 등 군사적 용도에서부터 기상 관측, 방송촬영, 물류 배송 등의 민간 활용 분야까지 폭넓은 분야에서 활용되고 있다.
	무인항공기는 무엇인가?	무인항공기(Unmanned Aerial Vehicle, UAV)는 조종사가 탑승하지 않고 지정된 임무를 수행 할 수 있도록 제작된 비행체로서 사람이 탑승하지 않기 때문에 인명 손실에 대한 위험 없이 위험요소가 존재하거나 오염된 지역에서의 작전수행이 가능하다. 또한 유인항공기에 비해 상대적으로 조작 방법이 손쉽고 기체 소형화를 통해 레이더 피탐성 감소가 가능하다는 장점을 가지고 있다[1].

참고문헌 (15)

Mylander, W. C., Wagner, D. H., "Naval Operations Analysis," Naval Institute Press, Annapolis, Maryland, 1999.
Dogan, A., "Probabilistic Approach in Path Planning for UAVs," In IEEE international symposium on intelligent control, Houston, October 2003, pp.608-613.
Yoon, S. J., Ahn, J. J., Nam, G. W., "A Study on the UAV Guidance and Control Minimizing Radar Exposure," Proceedings of the 2004 KSAS Spring Conference, 2004, pp.318-321
Novy, M. C., Jacques, D. T., Pachter, M., "Air Vehicle Optimal Trajectories Between Two Radars," Proceedings of the American Control Conference, Anchorage, AK, 2002.
Bortoff, S. A., "Path Planning for UAVs," Proceedings of the American Control Conference, 2000.
Kant, G., "Algorithms for Drawing Planar Graph," Ph. D. Thesis, Utrecht University, 1993.
Lee, H. T., Meyn, L. A., and Kim, S. "Probabilistic safety assessment of unmanned aerial system operations." Journal of Guidance, Control, and Dynamics, Vol.36, No.2, 2013, pp. 610-617.

상세보기
Kim, K. T., Park, S. H., Cho, S. J., Jeon, G. W., "An Optimal Path Planning for Survival Rate Maximization of Submarine," Journal of the Military Operations Research Society of Korea, Vol.36, No.3, 2010, pp.135-145
Jun, M. S., D'Andrea, R., "Path Planning for Unmanned Aerial Vehicles in Uncertain and Adversarial Environments," Cooperative Control: Models, Applications and Algorithms Cooperative Systems Vol.1, 2003, pp. 95-110.
Woo, K. S., Park, J. H., Huh, U. Y., "Dynamic Path Planning for Mobile Robots Using Fuzzy Potential Field Method," The Transactions of The Korean Institute of Electrical Engineers, Vol.61, No.2, 2012, pp.291-297.

원문보기 상세보기
Skolnik, M. I., "Radar handbook." NewYork, McGrawHill, 1990.
DiFranoco, J. V., Rubin, W. L., "Radar Detection," Englewood Cliffs, Prentice-Hall, 1968.
"Unmanned aircraft systems roadmap 2005-2030." Defense Technical Information Center, 2005.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., and Stein, C. "Introduction to algorithms." Cambridge, MIT press, 2001.
Moon, G. J., Park, S. M., "Analysis and Reconstruction of Vehicle Speeds to Design an Efficient Time Dependent VRP Heuristic," Journal of the Society of Korea Industrial and Systems Engineering, Vol.35, No.1, 2012, pp.140-147.

저자의 다른 논문 :

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format