DocumentCode :
3649361
Title :
A Monte-Carlo path planner for dynamic and partially observable environments
Author :
Munir Naveed;Diane Kitchin;Andrew Crampton;Lukáš Chrpa;Peter Gregory
Author_Institution :
Department of Software Engineering, Fatima Jinnah Women University, Pakistan
fYear :
2012
Firstpage :
211
Lastpage :
218
Abstract :
In this paper, we present a Monte-Carlo policy rollout technique (called MOCART-CGA) for path planning in dynamic and partially observable real-time environments such as Real-time Strategy games. The emphasis is put on fast action selection motivating the use of Monte-Carlo techniques in MOCART-CGA. Exploration of the space is guided by using corridors which direct simulations in the neighbourhood of the best found moves. MOCART-CGA limits how many times a particular state-action pair is explored to balance exploration of the neighbourhood of the state and exploitation of promising actions. MOCART-CGA is evaluated using four standard pathfinding benchmark maps, and over 1000 instances. The empirical results show that MOCART-CGA outperforms existing techniques, in terms of search time, in dynamic and partially observable environments. Experiments have also been performed in static (and partially observable) environments where MOCART-CGA still requires less time to search than its competitors, but typically finds lower quality plans.
Keywords :
"Planning","Games","Real-time systems","Monte Carlo methods","Path planning","Heuristic algorithms","Topology"
Publisher :
ieee
Conference_Titel :
Computational Intelligence and Games (CIG), 2012 IEEE Conference on
Print_ISBN :
978-1-4673-1193-9
Type :
conf
DOI :
10.1109/CIG.2012.6374158
Filename :
6374158
Link To Document :
بازگشت