컴퓨터 게임 등에서 가상객체를 이용해 다양한 환경을 체험하는 것과 유사하게 국방 분야에서도 War-game simulator를 활용한다. 실제 군인과 컴퓨터가 생성한 가상군(Computer Generated Force: CGF)이 전장상황을 3차원의 가상환경 속에서 교육훈련을 실시하고 있다. 하지만 시뮬레이션 모델 구현 기술 중 하나인 길 찾기 알고리즘의 현 수준은 단순히 최단시간 경로만을 고려하기 때문에 군의 특수한 전장상황에서 최적의 경로를 선정하기에는 제한되는 면이 있다. 본 논문의 초점은 주어진 정보를 바탕으로 목적지까지 무조건 짧은 경로나 최단시간 경로만을 찾는 것이 아니라, 여러 가지 다양한 임무조건(METT+TC)에 부합하는 경로를 찾음과 동시에 마감시간이라는 제약요소를 잘 활용하여 가능한 비용이 최소가 되는 경로를 선택하는 것이다. 최단시간만을 선택하는 알고리즘과 METT+TC 요소들 중 하나인 마감시간(Deadline, $d_t$) 내의 최소비용을 선택하는 알고리즘을 대상으로, 가능한 모든 경로에 대한 이동시 소요되는 시간(t)과 가용부대의 전투력(Troops ability, a) 요소의 변화에 따른 이동시 소요되는 총비용(c(t))의 비교를 통해 그 효용성을 검증하였다. 실험결과에 의하면 마감시간을 고려할 경우, 제안 알고리즘이 최대 62.5% 가량의 비용 절감 효과가 있음을 확인하였다.
컴퓨터 게임 등에서 가상객체를 이용해 다양한 환경을 체험하는 것과 유사하게 국방 분야에서도 War-game simulator를 활용한다. 실제 군인과 컴퓨터가 생성한 가상군(Computer Generated Force: CGF)이 전장상황을 3차원의 가상환경 속에서 교육훈련을 실시하고 있다. 하지만 시뮬레이션 모델 구현 기술 중 하나인 길 찾기 알고리즘의 현 수준은 단순히 최단시간 경로만을 고려하기 때문에 군의 특수한 전장상황에서 최적의 경로를 선정하기에는 제한되는 면이 있다. 본 논문의 초점은 주어진 정보를 바탕으로 목적지까지 무조건 짧은 경로나 최단시간 경로만을 찾는 것이 아니라, 여러 가지 다양한 임무조건(METT+TC)에 부합하는 경로를 찾음과 동시에 마감시간이라는 제약요소를 잘 활용하여 가능한 비용이 최소가 되는 경로를 선택하는 것이다. 최단시간만을 선택하는 알고리즘과 METT+TC 요소들 중 하나인 마감시간(Deadline, $d_t$) 내의 최소비용을 선택하는 알고리즘을 대상으로, 가능한 모든 경로에 대한 이동시 소요되는 시간(t)과 가용부대의 전투력(Troops ability, a) 요소의 변화에 따른 이동시 소요되는 총비용(c(t))의 비교를 통해 그 효용성을 검증하였다. 실험결과에 의하면 마감시간을 고려할 경우, 제안 알고리즘이 최대 62.5% 가량의 비용 절감 효과가 있음을 확인하였다.
At the computer games, we can experience a variety of environments using a virtual object. It is similar to that be trained in War-game simulator of the defense. Actual soldiers and a computer-generated virtual group(Computer Generated Force: CGF) in 3-D virtual battlefield environment are training....
At the computer games, we can experience a variety of environments using a virtual object. It is similar to that be trained in War-game simulator of the defense. Actual soldiers and a computer-generated virtual group(Computer Generated Force: CGF) in 3-D virtual battlefield environment are training. However, path finding algorithm, one of the techniques of simulation models, to the current level only considers the shortest time path. So, this current level at the special situation of the army in the battlefield for selecting the optimal path is limited. The focus of this paper is to select the least-cost path using the deadline with several different mission conditions(METT+TC). For the only shortest time path algorithm and the least-cost path algorithm using dealine,($d_t$, one of METT+TC elements), Its usefulness is verifying the change of the move spent time(t) for all possible paths and the fighting power of the combat troops(Troops ability, a) through a comparison of the total cost of moves(c(t)). According to the results, when considering the deadline, the proposed algorithm saves about 62.5% of the maximum cost.
At the computer games, we can experience a variety of environments using a virtual object. It is similar to that be trained in War-game simulator of the defense. Actual soldiers and a computer-generated virtual group(Computer Generated Force: CGF) in 3-D virtual battlefield environment are training. However, path finding algorithm, one of the techniques of simulation models, to the current level only considers the shortest time path. So, this current level at the special situation of the army in the battlefield for selecting the optimal path is limited. The focus of this paper is to select the least-cost path using the deadline with several different mission conditions(METT+TC). For the only shortest time path algorithm and the least-cost path algorithm using dealine,($d_t$, one of METT+TC elements), Its usefulness is verifying the change of the move spent time(t) for all possible paths and the fighting power of the combat troops(Troops ability, a) through a comparison of the total cost of moves(c(t)). According to the results, when considering the deadline, the proposed algorithm saves about 62.5% of the maximum cost.
* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.
문제 정의
군의 특수성을 반영한 길 찾기 알고리즘 (Path finding)을 사용하여 최단시간 경로가 아닌 마감시간(%) 내에 최소의 비용(c(D)으로 최적의 경로를 탐색하는 알고리즘을 필요로 한다. 문제 해결의 열쇠는알고리즘에서 사용될 영향요소, 즉 METT+TC 요소들에 대한 정보를 지수화하여 이들의 영향을 평가하는 것이라 하겠다. METT+TC 요소 중에서 대표적인 파라미터들(Time, Troops 등)에 대한 상관관계를 수학적 분석과 시뮬레이션을 통해 기존 알고리즘과 제안 알고리즘의 총소요비용(c(t))을 비교하여 가상군과 같은 특수한 환경에서 제안 알고리즘의 타당성과 우수성을 증명하였다.
여기서 본 논문의 초점은 주어진 정보를 바탕으로목적지까지 무조건 짧은 경로나 최단시간 경로만을 찾는 것이 아니라, 여러가지 다양한 임무조건에 부합하는 경로를 찾음과 동시어】, 마감시간이라는 제약요소를반영하여 가능한 한 최소 비용이 소요되는 경로를 선택하는 것이다. 길 찾기 알고리즘 가운데 가장 많이 활용되는 A* 알고리즘처럼 다양한 영향요소에 따른 경로구간 간 비용을 산줄하고 가중치를 알고리즘에 적용/수행함으로써 이를 구현할 수 있다.
이를 통해, 기존 알고리즘의 가중치 요소로 특정 거리 이동시소요되는 시간만을 고려했을 때와 이동시 소요되는 비용(혹은 기타 METT+TC 요소)을 고려했을 때 산출되는 경로가 차이가 나타남을 알 수 있다. 이처럼 경로 이동시 영향을 줄 수 있는 요소들을 최대한 가중치 요소로 반영하면서 마감시간(Dealine) 내 목적지에 도달 가능한 경로를 찾고자 한다.
가설 설정
평가하는 것이다. 이를 우】해, 우선 객관적으로지수화가 가능한 요소들(Time, Troops 등)을 바탕으로시간에 따른 다양한 비용함수를 가정하고 실험을 통해증명한다.
제안 방법
더불어 다음의 세 가지 간단한 함수 관계 비교를 통해 기존 알고리즘과 제안 알고리즘의 성능을 비교 및판단한다.
(3)의 경우는 항공기나 배와 같은 이동수단을 활용하여 많은 비용이 소요되지만 단시간에 이동가능한 경로로 비용 대비 시간의 가치가 현저히 작으므로 비용 산출 시 시간이 무시될 수 있는 경우이다. 이외에도 많은 경우의 수가 있겠지만 본 논문에서는 위의경우를 대상으로 최적 경로 산출간 마감시간을 적용하여 비교/분석하였다.
편의를 위해 일정량의 마감시간(%) 변화를 함께 도시하였다.
대상 데이터
시간。) 중 METT+TC 요소들 중 하나인 마감시간(&)을 초과하지 않는 경로에 대한 총 소요비용을 대상으로 최소비용경로를 선택한다. 가용부대(Troops)의좁은 의미의 전투력伝)은 최초 출발지에서의 전투력 수준과 목적지에서의 전투력 수준의 차로 정의할 수 있으며, 최초 전투력 발생 시점에서 소요되는 비용을 전투력 (a)로 표시하였다.
평가 및 분석 대상들은 기존의 Dijkstra's, A* 등 일반적인 알고리즘과 본 논문에서 제안하는 알고리즘으로써, 즉 최단시간만을 선택하는 알고리즘과 METI'+TC 요소들 중 하나인 마감시간(Deadline, dt) 내의 최소비용을 선택하는 알고리즘을 그 대상들로 한다. 이들에대해, 가능한 모든 경로에 대한 이동시 소요되는 시간 (t) 과 이동시 소요되는 가용부대의 전투력 (Troops ability, a) 요소의 변화에 따른 이동시 소요되는 종비용 (c(t))의 비교를 통해 증명한다.
성능/효과
문제 해결의 열쇠는알고리즘에서 사용될 영향요소, 즉 METT+TC 요소들에 대한 정보를 지수화하여 이들의 영향을 평가하는 것이라 하겠다. METT+TC 요소 중에서 대표적인 파라미터들(Time, Troops 등)에 대한 상관관계를 수학적 분석과 시뮬레이션을 통해 기존 알고리즘과 제안 알고리즘의 총소요비용(c(t))을 비교하여 가상군과 같은 특수한 환경에서 제안 알고리즘의 타당성과 우수성을 증명하였다.
5가 된다. 결론적으로, 마감시간을 고려할 경우 제안알고리즘이 최대 62.5% 가량(마감시간 澜일 때, 기존 1.25, 제안0.2)의 비용 절감 효과를 나타냈다.
산출하게 된다. 따라서 비교하는 두 알고리즘 중 위의 세 가지 함수 관계를 만족하면서, 가장 효과적으로 최소한의 총소요비용(c(t))을 산출하는 알고리즘의 성능이 가상군과 같은 특수한 환경에서 더 우수한알고리즘으로 판단할 수 있다.
따라서, 그림 H에서 그림 13 모두에서 기존의 알고리즘보다 동일 혹은 적은 총소요비용(c(t))이 나타나 가상군과 같은 특수한 환경에서 제안 알고리즘의 타당성과 우수함을 확인하였다.
왜냐하면, 현재의 METT+TC요소 즉, 가상군객체의 임무의 특성(정찰, 진지점령, 특작부대 소탕 등) 과 적 상황, 지형 및 기상과 가용부대의 기동 및 전투능력, 임무완수 마감시간(Deadline), 민간요소 등 기타 영향요소들이 가중치함수에 반영되어 있지 않기 때문이며, 가상군 객체에 이를 반영한 길 찾기 알고리즘 수행이 상용화된 일반 차량용 내비게이션의 실시간 정체구간 반영과 유사하게, 보다 실제적이고 정확한 시뮬레이션 환경을 제공할 것이다. 또한, 관련연구를 통해 확인된 알고리즘 중 어떠한 알고리즘도 METT+TC요소를가중치 요소로 반영하거나 마감시간 고려의 필요성이언급된 알고리즘은 식별되지 않았다.
이러한소요시간이나 소요비용을 가중치로 산출하여 예상비용을 판단 후 죄적 경로를 도줄하게 되는 것이다. 이를 통해, 기존 알고리즘의 가중치 요소로 특정 거리 이동시소요되는 시간만을 고려했을 때와 이동시 소요되는 비용(혹은 기타 METT+TC 요소)을 고려했을 때 산출되는 경로가 차이가 나타남을 알 수 있다. 이처럼 경로 이동시 영향을 줄 수 있는 요소들을 최대한 가중치 요소로 반영하면서 마감시간(Dealine) 내 목적지에 도달 가능한 경로를 찾고자 한다.
후속연구
연구와 시뮬레이션을 지속할 것이다. 끝으로 본논문을 위시로 많은 연구를 통해 VnR과 같은 최신의가상 현실 기술이 군사 훈련 분야에도 효과적으로 접목되어, 국가 예산의 인적 물적 비용 절감에 일조할 수 있도록 지속적인 관심과 발전을 위해 노력하여야겠다.
가상군을 구성하는 각 객체들은 다양한 전장 환경(장애물, 적과의 조우, 포탄 낙하 등에서 지휘 결심의 바탕이 되는 정보인 METT+TC 요소 (Mission, Enemy, Terrain and Weather, Troops and Time available, Civil affairs) 를고려해야 한다. 이 때, 실시간으로 변화하는 전장상황과시간적 제약요소를 전반적으로 반영한 실시간성을 만족시키면서 최적의 경로를 선정할 때, 보다 실제와 유사한 시뮬레이션 훈련 결과를 얻을 수 있을 것이다.
향후 가상군(Comixiter Generated Froces) 환경의 영향요소들(인접 지형과 적 병력 배치, 위장과 같이 미처발견하지 못한 경우의 위험도 등)을 추가적으로 식별하여 임무와 상황에 따른 최적의 길 찾기 알고리즘 적용방안 연구와 시뮬레이션을 지속할 것이다. 끝으로 본논문을 위시로 많은 연구를 통해 VnR과 같은 최신의가상 현실 기술이 군사 훈련 분야에도 효과적으로 접목되어, 국가 예산의 인적 물적 비용 절감에 일조할 수 있도록 지속적인 관심과 발전을 위해 노력하여야겠다.
참고문헌 (11)
TTA. "ICT Standardization Roadmap 2010", Virtual and Real Worlds(VnR) pp. 60-72. 2010.
Nilsson, N. "Principles of Artificial Intelligence", Morgan Kaufman Publishers Inc., Los Altos. pp. 53-130. 1980.
Dijkstra, E. W. "A note on two problems in connection with graphs". Numerische Mathematik pp. 269-271. 1959.
Hart, P. "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Transactions on SSC, Vol. 4. pp. 100-107. 1968.
Stentz, A. "Optimal and efficient path planning for partially known environments". In Proceedings of the International Conference on Robotics and Automation, pp. 3310-3317. 1994.
Baek J.S. and Lee C.J. "A Study on the Autonomous Navigation Algorithm of the Unmanned Ground Combat Vehicle in Partially Unknown Environment", Defense Science & Technology Vol. 1-2, pp. 58-67. 2008.
Stentz, A. "The Focused D* Algorithm for Real-Time Planning", Proceedings of the International Joint Conference on Artificial Intelligence, pp. 1652-1659. 1995.
Koenig, S. and Likhachev, M. "Lifelong Planning A*", Technical Report GIT-COGSCI-2002/2, Georgia Institute of Technology. pp. 93-146. 2001.
Koenig, S. and Likhachev, M. "D* Lite", Proceedings of the National Conference on Artificial Intelligence, pp. 476-483. 2002.
Mackay, D., "Path Planning with D* Lite", Technical Memorandum, Defense R&D Canada Suffield TM 2005-242. pp. 9-18. 2005.
B. Stout, "Smart Moves: Intelligent Path finding". Game Developer Magazine, July, pp. 28-35. 1997.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.