The Effective Pathfinding Algorithm for Gaming Maps Using Systemized Iterative Deepening A

다국어 초록 (Multilingual Abstract)

A<SUP>*</SUP> algorithm is the de facto standard used for a pathfinding search. IDA* is a space-efficient version of A<SUP>*</SUP>, but it suffers from CPU cycles in the search space (the price for using no storage), repeatedly visiting nodes from left to- right traversal of the search tree. To overcome these concerns, recently fringe search algorithm is launched. At some extent, fringe search algorithm performs iterations same as A<SUP>*</SUP> and IDA<SUP>*</SUP>, but still the fringe search algorithm has some drawbacks, visiting nodes that are irrelevant for the current iteration. In this paper, Systemized Iterative Deepening A<SUP>*</SUP> (SIDA<SUP>*</SUP>) introduced to eliminate in-efficiencies such as, search space, visiting irrelevant nodes. It also detects dead ends and reachs the destination node faster than the existing pathfinding algorithms. We considered on-track strategy for accidental obstacles, in addition we include curvature information to avoid off road in static curves. Finally our experiment results performed on grid based pathfinding application between SIDA<SUP>*</SUP> and A<SUP>*</SUP>. We executed on two different platforms with and without obstacles (walls), in both different platforms SIDA<SUP>*</SUP> achieve 15-35% (i.e., time, length, weight, operation) faster than A<SUP>*</SUP> search algorithm. Evaluation results of proposed framework, On-track strategy shows effective for avoiding obstacles on static curves.

참고문헌 (Reference)

1 고정운, "임의의 공간상에서 A-Star 알고리즘을 사용한 AGV 통합 환경 시스템" 한국정보기술학회 11 (11): 227-235, 2013

2 안진호, "우선순위 큐를 이용한 A* 기반 최단경로 탐색 기법" 한국정보기술학회 8 (8): 1-7, 2010

3 C. Hernandez, "Tree Adaptive A*" 123-130, 2011

4 D. Loiacono, "The WCCI 2008 simulated car racing competition" 119-126, 2008

5 Bagchi, Mahanti, "Search algorithms under different kinds of heuristics - a comparative study" 30 (30): 1-21, 1983

6 Martelli, A., "On the complexity of admissible search algorithms" 8 : 1-13, 1977

7 J. Quadflieg, "Learning the track and planning ahead in a car racing controller"

8 Pearl, "Intelligent Search Strategies for Computer Problem Solving" Addison &Wesley 1984

9 Koenig, Sven, "Incremental heuristic search in AI"

10 Koenig, Sven, "Incremental heuristic search in AI" 25 (25): 99-112, 2004

11 Ghosh, S., "ITS:An efficient limited-memory heuristic tree search algorithm" 1353-1358, 1994

12 Wikipedia, "IDA*"

13 Y. C. Hui, "Game AI: artificial intelligence for 3D path finding" 2 : 2004

14 Wikipedia, "Fringe serach"

15 Björnsson, Yngvi, "Fringe Search: Beating A* at Pathfinding on Game Maps" 2005

16 Reinefeld, A., "Enhanced iterative-deepening search" 16 : 701-710, 1994

17 Russell, S. J., "Efficient memorybounded search methods" Wiley 1-5, 1992

18 Korf, "Depth-first Iterative-Deepening: An Optimal Admissible Tree Search" 27 : 97-109, 1985

19 N. Hansen, "Completely derandomized self adaption in ecolution strategied" 9 : 159-195, 2001

20 Martin V. Butz, "COBOSTAR (On track Strategy )" 2009

21 B. G. Weber, "Building human-level ai for realtime strategy games" AAAI Press 2011

22 F. Safadi, "Artificial intelligence design for real-time strategy games" 2011

23 Suyanto, "Artificial Intelligence: Searching -Reasoning - Planning - Learning (Edisi Revisi)"

24 S. Ontanon, "A survey of real-time strategy game AI research and competition in StarCraft" 293-311, 2013

25 Mohamad EL Falou, "A Decentralized Multiagent Pathfinding Algorithm" 2012