Journal of Korea Game Society (한국게임학회 논문지)

Korea Game Society (한국게임학회)
권호 표지
DOI QR코드

DOI QR Code

Reducing Search Space of A* Algorithm Using Obstacle Information

장애물 정보를 이용한 A* 알고리즘의 탐색 공간의 감소

  • Received : 2015.07.10
  • Accepted : 2015.08.10
  • Published : 2015.08.20
Download PDF
⟨ Previous Next ⟩

Abstract

The A* algorithm is a well-known pathfinding algorithm. However, if the information about obstacles is not exploited, the algorithm may collide with obstacles or lead into swamp areas unnecessarily. In this paper, we propose new heuristic functions using the information of obstacles to avoid them or swamp areas. It takes time to process the information of obstacles before starting pathfinding, but it may not cause any problems most of cases because it is not processed in real time. We showed that the proposed methods could reduce the search space effectively through experiments. Furthermore, we showed that heuristic functions using obstacle information could reduce the search space effectively without processing obstacle information at all.

A* 알고리즘은 잘 알려진 길찾기 알고리즘이다. 그러나 장애물 정보를 이용하지 않을 경우에는 장애물을 만날 때 까지 탐색을 진행하여 장애물과 충돌하거나 늪(swamp)에 들어갈 수 있다. 본 논문에서는 장애물을 회피하고 늪에 들어가지 않도록 장애물 정보를 사용하고, 장애물 정보를 이용한 휴리스틱 함수도 제안한다. 장애물 정보를 사전에 처리하는데 시간이 걸리지만 실시간에 처리하는 것이 아니기 때문에 대부분의 경우에 문제가 되지 않는다. 실험을 통하여 제안한 방법들이 검색 공간을 효과적으로 줄일 수 있음을 보여주었다. 더불어 장애물 정보를 이용한 휴리스틱 함수는 사전에 장애물 정보를 처리할 필요 없이 효과적으로 검색 공간을 줄일 수 있다는 것을 보여주었다.

Keywords

References

  1. Bryan Stout, "The Basics of A* for Path Planning", Game Programming Gems, pp.254-263, Charles River Media, 2000.
  2. P. Hart, N. Nilsson, and B. Raphael, "A formal basis for the heuristic determination of minimum cost paths", IEEE Trans. Syst. Sci. Cybernet, 4(2): pp. 100-107, 1968. https://doi.org/10.1109/TSSC.1968.300136
  3. Nils J. Nilsson, Artificial intelligence: A New Synthesis, Morgan Kafmann, 1998.
  4. R. Korf, "Depth-first Iterative Deepening: An Optimal Admissible Tree Search", Artificial Intelligence, 27: pp. 97-109, 1985. https://doi.org/10.1016/0004-3702(85)90084-0
  5. Robert Kirk and DeLisle, "Beyond A*: IDA* and Fringe Search", Game Programming Gems 7, pp. 289-294, 2008.
  6. Nir Pochter, Aviv Zohar, Jeffrey S. Rosenschein, Ariel Felnner, "Search Space Reduction Using Swamp Hierarchies", Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence, pp. 155-160, 2010.
  7. Ron Penton, Data Structures for Game Programmers, Premier Press Game Development, pp. 715-767, 2002.
  8. Sung Hyun Cho, "A Pathfinding Algorithm Using Path Information", Korea Game Society, Vol. 13, No. 1, pp. 31-40, 2013.
  9. Dan Higgins, "Fast A* implementation", AI game Programming Wisdom, pp. 223-238, 2003.
  10. Steve Ravin, "A* Speed Optimizations", Game programming Gems, pp. 363-381, Charles River Media, 2000.
  11. Daniel Harabor and Alban Grastein, "Online Graph Pruning for Pathfinding on Grid Maps", Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, pp. 1114-1119, 2011.