Real-time path planning using a simulation-based Markov decision process

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

7 Citations (Scopus)

Abstract

This paper introduces a novel path planning technique called MCRT which is aimed at non-deterministic, partially known, real-time domains populated with dynamically moving obstacles, such as might be found in a real-time strategy (RTS) game. The technique combines an efficient form of Monte-Carlo tree search with the randomized exploration capabilities of rapidly exploring random tree (RRT) planning. The main innovation of MCRT is in incrementally building an RRT structure with a collision-sensitive reward function, and then re-using it to efficiently solve multiple, sequential goals. We have implemented the technique in MCRT-planner, a program which solves non-deterministic path planning problems in imperfect information RTS games, and evaluated it in comparison to four other state of the art techniques. Planners embedding each technique were applied to a typical RTS game and evaluated using the game score and the planning cost. The empirical evidence demonstrates the success of MCRT-planner.

Original languageEnglish
Title of host publicationRes. and Dev. in Intelligent Syst. XXVIII: Incorporating Applications and Innovations in Intel. Sys. XIX - AI 2011, 31st SGAI Int. Conf. on Innovative Techniques and Applications of Artificial Intel.
Pages35-48
Number of pages14
DOIs
Publication statusPublished - 2011
Event31st SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence - Cambridge, United Kingdom
Duration: 13 Dec 201115 Dec 2011

Conference

Conference31st SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence
Abbreviated titleAI 2011
CountryUnited Kingdom
CityCambridge
Period13/12/1115/12/11

    Fingerprint

Cite this

Naveed, M., Crampton, A., Kitchin, D., & McCluskey, L. (2011). Real-time path planning using a simulation-based Markov decision process. In Res. and Dev. in Intelligent Syst. XXVIII: Incorporating Applications and Innovations in Intel. Sys. XIX - AI 2011, 31st SGAI Int. Conf. on Innovative Techniques and Applications of Artificial Intel. (pp. 35-48) https://doi.org/10.1007/978-1-4471-2318-7-3