A Monte-Carlo path planner for dynamic and partially observable environments

Munir Naveed, Diane Kitchin, Andrew Crampton, Lukáš Chrpa, Peter Gregory

Research output: Chapter in Book/Report/Conference proceedingConference contribution

5 Citations (Scopus)

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.

Original languageEnglish
Title of host publication2012 IEEE Conference on Computational Intelligence and Games, CIG 2012
Pages211-218
Number of pages8
DOIs
Publication statusPublished - 2012
EventIEEE International Conference on Computational Intelligence and Games - Granada, Spain
Duration: 11 Sep 201214 Sep 2012

Conference

ConferenceIEEE International Conference on Computational Intelligence and Games
Abbreviated titleCIG 2012
CountrySpain
CityGranada
Period11/09/1214/09/12

Fingerprint Dive into the research topics of 'A Monte-Carlo path planner for dynamic and partially observable environments'. Together they form a unique fingerprint.

  • Cite this

    Naveed, M., Kitchin, D., Crampton, A., Chrpa, L., & Gregory, P. (2012). A Monte-Carlo path planner for dynamic and partially observable environments. In 2012 IEEE Conference on Computational Intelligence and Games, CIG 2012 (pp. 211-218). [6374158] https://doi.org/10.1109/CIG.2012.6374158