We consider a problem of finding paths between two points in a region or terrain for the movement of an unmanned combat vehicle (UCV). To represent the terrain while reflecting a battlefield situation, we use a grid generation method in which to represent the region. The terrain is divided by the grid and each grid is given the path-length costs with the traverse time of the UCV, risk level determined by the enemy position and jamming level influenced by the electronic attack of the enemy. For a problem with a multiple criterion objective of minimizing time, risk and jamming, we develop a two-phase hybrid labeling algorithm with a new label selection strategy and propose a global path planning algorithm based on the label correcting method. For the evaluating of the performance of the proposed algorithm, computational experiments are performed on a number of data sets, and results show that the proposed algorithm performs better than existing methods. We also give results of a case in which the proposed algorithm is applied to a real problem.
본 논문에서는 무인전투차량 (UCV : Unmanned combat vehicles)이 제한된 임무시간 내에서, 위험도와 통신방해도를 고려하여 주어진 목적지까지 전역경로 (Global path)를 생성하는 다기준 최단경로 문제 (MSPP-TR : Multi-criteria shortest path problem with time window and resource constraint)를 다루고 있다. 세계 각국은 현재 미래 전투 환경에서 ‘전쟁주역’으로 활용될 군사용 로봇을 개발하기 위하여 무인체계와 관련된 각종 기술을 개발하고 있다. 따라서 우리 군 역시 점차 병력의 감소가 불가피한 상황에서 기존의 유인전투체계를 대신할 수 있고, 전투원의 생존성 보장차원에서도 유리한 무인전투체계의 필요성이 제기되고 있다. 이러한 필요성에 의하여 국방과학연구소에서는 우리군에 도입할 무인전투차량을 개발 중에 있는데, 본 논문은 이러한 무인전투차량이 주어진 임무에 따라 최적의 경로를 탐색하고, 탐색한 경로를 이동할 수 있는 알고리듬 개발을 목표로 하였다.
일반적으로, 다기준 최단경로 문제는 이미 NP-hard 문제로 알려져 있으므로, 시간과 위험도, 통신요소를 고려하는 본 논문의 문제 또한 NP-hard임을 알 수 있다. 이러한 문제의 복잡성 때문에 이 분야는 기존에 많은 연구가 진행되었다. 하지만 본 논문은 실제 전장상황을 반영하기 위하여 기존의 문제들과는 달리 1차원의 선분(Edge) 이 아닌 2차원의 격자 (Grid, $100m\times100m$)에 벡터값들을 부여한 문제를 고려하였다. 그 이유는 육군에서 개발한 속도맵 (Velocity map)이 2차원의 격자값들로 구성이 되어있고, 실제 전장에서 무인전투차량의 기동하는 공간이 도로보다는 논과 밭 같은 지형이므로, 기존의 방식으로는 표현이 제한되기 때문이다. 따라서 본 논문에서는 격자상에 속도, 위험도, 통신방해도값이 존재하는 최단경로 문제를 해결하기 위해, 상대적인 최적경로 (Pareto-optimal path) 를 찾는 TPHL (Two phases hybrid labeling) 알고리듬과 세가지 요소에 가중치를 부여하여, 한 개의 목적식으로 전환시키는 단순가중치법 (Simple additive weighting method) 을 이용한 GPP (Global path planning) 알고리듬을 구현하였다. TPHL 알고리듬은 기존에 구현된 다익스트라 알고리듬 (Dijkstra’s algorithm)에 $A^{\ast}$ 알고리듬의 특징인 추정값 (Estimate value) 개념을 추가한 일종의 라벨수정방법 (Label correcting method) 이다. 그리고 GPP 알고리듬은 세 가지 요소 (시간, 위험도, 통신방해도) 중, 지휘관이 작전 상황에 맞게 특정 요소에 가중치를 고려하여 최적경로 (Optimal path)를 생성하는 라벨수정방법을 변형시킨 발견적기법 (Heuristic method) 이다. 제안된 두 가지 알고리듬은 성능 평가를 위해 실제 창원일대의 지형정보와 속도맵을 반영하여, 기존에 구현된 다른 방법들과 비교하였다. 그 결과 본 논문에서 제시한 알고리듬들이 더욱더 빠른 시간내에 최적해를 가진 경로를 생성하였다.
본 논문에서 제시한 알고리듬은 육군에서 개발중인 속도맵과 연동하여 무인전투차량에 운용할 수 있으며, 전장 상황을 반영하여 고려해야 할 요소를 알고리듬에 추가할 수 있도록 구현하여, 변화하는 전투양상에 무인전투차량이 능동적으로 대처할 수 있을 것으로 판단된다.
