Minimum-Cost Path Finding Algorithm in Real-Time For Computer Generated Force

실시간성을 고려한 가상군 최소비용 길 찾기 알고리즘

  • Received : 2010.12.03
  • Accepted : 2011.01.07
  • Published : 2011.01.25

Abstract

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.

컴퓨터 게임 등에서 가상객체를 이용해 다양한 환경을 체험하는 것과 유사하게 국방 분야에서도 War-game simulator를 활용한다. 실제 군인과 컴퓨터가 생성한 가상군(Computer Generated Force: CGF)이 전장상황을 3차원의 가상환경 속에서 교육훈련을 실시하고 있다. 하지만 시뮬레이션 모델 구현 기술 중 하나인 길 찾기 알고리즘의 현 수준은 단순히 최단시간 경로만을 고려하기 때문에 군의 특수한 전장상황에서 최적의 경로를 선정하기에는 제한되는 면이 있다. 본 논문의 초점은 주어진 정보를 바탕으로 목적지까지 무조건 짧은 경로나 최단시간 경로만을 찾는 것이 아니라, 여러 가지 다양한 임무조건(METT+TC)에 부합하는 경로를 찾음과 동시에 마감시간이라는 제약요소를 잘 활용하여 가능한 비용이 최소가 되는 경로를 선택하는 것이다. 최단시간만을 선택하는 알고리즘과 METT+TC 요소들 중 하나인 마감시간(Deadline, $d_t$) 내의 최소비용을 선택하는 알고리즘을 대상으로, 가능한 모든 경로에 대한 이동시 소요되는 시간(t)과 가용부대의 전투력(Troops ability, a) 요소의 변화에 따른 이동시 소요되는 총비용(c(t))의 비교를 통해 그 효용성을 검증하였다. 실험결과에 의하면 마감시간을 고려할 경우, 제안 알고리즘이 최대 62.5% 가량의 비용 절감 효과가 있음을 확인하였다.

Keywords

References

  1. TTA. "ICT Standardization Roadmap 2010", Virtual and Real Worlds(VnR) pp. 60-72. 2010.
  2. Nilsson, N. "Principles of Artificial Intelligence", Morgan Kaufman Publishers Inc., Los Altos. pp. 53-130. 1980.
  3. Dijkstra, E. W. "A note on two problems in connection with graphs". Numerische Mathematik pp. 269-271. 1959.
  4. Hart, P. "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", IEEE Transactions on SSC, Vol. 4. pp. 100-107. 1968.
  5. 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.
  6. 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.
  7. Stentz, A. "The Focused D* Algorithm for Real-Time Planning", Proceedings of the International Joint Conference on Artificial Intelligence, pp. 1652-1659. 1995.
  8. Koenig, S. and Likhachev, M. "Lifelong Planning A*", Technical Report GIT-COGSCI-2002/2, Georgia Institute of Technology. pp. 93-146. 2001.
  9. Koenig, S. and Likhachev, M. "D* Lite", Proceedings of the National Conference on Artificial Intelligence, pp. 476-483. 2002.
  10. Mackay, D., "Path Planning with D* Lite", Technical Memorandum, Defense R&D Canada Suffield TM 2005-242. pp. 9-18. 2005.
  11. B. Stout, "Smart Moves: Intelligent Path finding". Game Developer Magazine, July, pp. 28-35. 1997.