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

4 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

Motion planning
Experiments

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
Naveed, Munir ; Kitchin, Diane ; Crampton, Andrew ; Chrpa, Lukáš ; Gregory, Peter. / A Monte-Carlo path planner for dynamic and partially observable environments. 2012 IEEE Conference on Computational Intelligence and Games, CIG 2012. 2012. pp. 211-218
@inproceedings{9debd07d62be4bf49b0976a288eb3dee,
title = "A Monte-Carlo path planner for dynamic and partially observable environments",
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.",
author = "Munir Naveed and Diane Kitchin and Andrew Crampton and Luk{\'a}š Chrpa and Peter Gregory",
year = "2012",
doi = "10.1109/CIG.2012.6374158",
language = "English",
isbn = "9781467311922",
pages = "211--218",
booktitle = "2012 IEEE Conference on Computational Intelligence and Games, CIG 2012",

}

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., 6374158, pp. 211-218, IEEE International Conference on Computational Intelligence and Games, Granada, Spain, 11/09/12. https://doi.org/10.1109/CIG.2012.6374158

A Monte-Carlo path planner for dynamic and partially observable environments. / Naveed, Munir; Kitchin, Diane; Crampton, Andrew; Chrpa, Lukáš; Gregory, Peter.

2012 IEEE Conference on Computational Intelligence and Games, CIG 2012. 2012. p. 211-218 6374158.

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

TY - GEN

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

AU - Naveed, Munir

AU - Kitchin, Diane

AU - Crampton, Andrew

AU - Chrpa, Lukáš

AU - Gregory, Peter

PY - 2012

Y1 - 2012

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84871961426&partnerID=8YFLogxK

U2 - 10.1109/CIG.2012.6374158

DO - 10.1109/CIG.2012.6374158

M3 - Conference contribution

SN - 9781467311922

SP - 211

EP - 218

BT - 2012 IEEE Conference on Computational Intelligence and Games, CIG 2012

ER -

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