We consider an operations problem for an unmanned combat vehicle (UCV) in a military. The problem is to schedule a patrol path for the UCV on a set of key terrains with the objective of minimizing total threats being generated by a possible infiltration of the enemy in a forward area. In this study, threats on each key terrain are increased in nonlinear way by interval of patrols and the key terrains can be patrolled multiple times with a given mission time (2-hour) for the UCV. In order to get the objective, we make a sequence of patrolling key terrains to minimize the total threats. For making the sequence, we develop four heuristic algorithms which are composed of two-step procedure. For evaluation of the performance of the proposed heuristic, computational experiments are performed on randomly generated data sets, and results show that the algorithm gives a good solution for the problem in a short time.
본 논문에서는 무인전투차량 (UCV : Unmanned combat vehicles)이 임무시간내 (120분)에서 내에서, 정해진 확인점 (Checkpoint)을 순찰하여 적의 위협도를 최소화 시키는 순찰경로를 계획하는 문제를 다루고 있습니다. 세계 각국은 현재 미래 전투 환경에서 ‘전쟁주역’으로 활용될 군사용 로봇을 개발하기 위하여 무인체계와 관련된 각종 기술을 개발하고 있다. 따라서 우리 군 역시 점차 병력의 감소가 불가피한 상황에서 기존의 유인전투체계를 대신할 수 있고, 전투원의 생존성 보장차원에서도 유리한 무인전투체계의 필요성이 제기되고 있다. 이러한 필요성에 의하여 국방과학연구소에서는 우리군에 도입할 무인전투차량을 개발 중에 있는데, 본 논문은 이러한 무인전투차량이 확인점의 중요도 (weight)를 고려해서 적의 침투위협을 최소화 시키는알고리즘 개발을 목표로 하였다.
이러한 문제는 현재까지 많은 연구가 이루어 지지 않았으며, 지금까지의 연구는 확인점의 중요도를 고려하지 않은 상태에서 순찰경로를 계획했다. 하지만 본 논문에서는 확인점의 중요도를 고려하여 작전시간 (8시간, p.m. 22:00~a.m. 06:00)내 임무시간 단위 (2시간)로 2대의 UCV가 교대임무를 수행하게 가정사항이 주어졌다. 이는 UCV의 정비/충전 시간을 고려하며, 실제 전장에서 전장상황이 변하는 것을 임무시 간 단위로 반영하여 UCV의 임무가 교대될 시 반영하기 위함이다.
문제를 해결하기 위해 본 논문에서는 6개의 알고리듬을 제시하였다. 3개의 알고리듬은 기존에 연구된 알고리듬을 본 논문의 목적에 맞게 수정하여 적용하였고, 나머지 3개의 알고리듬은 본 논문에서 처음으로 제시한 알고리듬이다. 제시한 알고리듬 들은 단순한 개념을 바탕으로 짧은 시간에 좋은 결과값을 주었다. 이중 NEH의 insertion idea를 활용한 알고리듬이 가장 좋은 결과값을 주었다.
본 논문에서 제시한 알고리듬은 장차 병력이 부족한 군에서 UCV의 전장/주둔지 경계시 충분히 활용 될 수 있으며, 경찰이나 경호업체의 순찰경로 계획시에도 활용 될 수 있다.
