We consider a problem of finding reconnaissance routes of unmanned combat vehicles (UCVs). The terrain reflecting a battlefield is divided by the grid and each grid is given the traverse time of the UCV and risk level, which is determined by the locations of the enemies. For a problem with an objective of minimizing total travel time while considering risk level caused by enemy’s possible attacks. We develop an optimal solution approach and a two-phase heuristic algorithm, both based on dynamic programming. In the heuristic algorithm, we generate feasible paths first, and then we optimize the paths using a solution method for multi-choice knapsack problems. For evaluation of the performance of the proposed algorithms, computational experiments are performed on a number of data sets, and results show that the proposed algorithms gives a solution within an acceptable time for real military operations.
본 논문은 무인 전투차량의 정찰 경로 문제를 다루고 있다. 미래 전장에서 사람을 대신하여 위험지역에서 여러 군사 임무를 수행하게 될 무인 전투차량은 적에 의해 파괴되거나 발견될 위험요소와 임무를 수행할 수 있는 능력, 작전지역 내에서 이동 가능한 시간 등 여러 요소를 고려하여야 한다. 본 연구에서는 동적 계획법을 이용하여 2단계로 이루어진 최적 및 경험적 해법을 제시하였다. 1단계에서는 출발지 및 반드시 거쳐야 하는 적의 위치를 순서대로 두 개씩 묶어 각각의 구역을 나눈 뒤에 각 구역별로 적으로부터 발견될 확률을 고려하여 이동 가능한 경로를 모두 생성하였다. 2단계에서는 1단계에서 생성된 이동 가능한 경로들을 가지고 다중배낭문제 해법을 이용하여 적에게 발견될 일정한 확률 이하의 경로 중에서 정찰 시간을 최소로 하는 경로를 찾는 것이다. 경험적 해법을 이용한 방법은 주어진 작전구역의 전 범위를 대상으로 이동 가능한 경로를 찾는 최적의 해법과는 다르게, 경로를 생성하는 범위를 출발지와 도착지를 대각선으로 하는 직사각형으로 제한하였다. 그리하여 $30\times30$ 이상의 그리드 맵에서는 최적의 방법으로 1시간 이상 소용되는 계산시간을 10분 이내로 줄임으로써 정찰경로를 빠르게 계산하여 작전부대의 작전 준비시간을 최대한 보장해 주었다.
