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

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

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

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

Motion planning
Planning
Innovation
Costs

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
Naveed, Munir ; Crampton, Andrew ; Kitchin, Diane ; McCluskey, Lee. / Real-time path planning using a simulation-based Markov decision process. 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.. 2011. pp. 35-48
@inproceedings{f9cfb31d57ba4f5a98e080243985e955,
title = "Real-time path planning using a simulation-based Markov decision process",
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.",
author = "Munir Naveed and Andrew Crampton and Diane Kitchin and Lee McCluskey",
year = "2011",
doi = "10.1007/978-1-4471-2318-7-3",
language = "English",
isbn = "9781447123170",
pages = "35--48",
booktitle = "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.",

}

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, 31st SGAI International Conference on Innovative Techniques and Applications of Artificial Intelligence, Cambridge, United Kingdom, 13/12/11. https://doi.org/10.1007/978-1-4471-2318-7-3

Real-time path planning using a simulation-based Markov decision process. / Naveed, Munir; Crampton, Andrew; Kitchin, Diane; McCluskey, Lee.

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.. 2011. p. 35-48.

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

TY - GEN

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

AU - Naveed, Munir

AU - Crampton, Andrew

AU - Kitchin, Diane

AU - McCluskey, Lee

PY - 2011

Y1 - 2011

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

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

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

U2 - 10.1007/978-1-4471-2318-7-3

DO - 10.1007/978-1-4471-2318-7-3

M3 - Conference contribution

SN - 9781447123170

SP - 35

EP - 48

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

ER -

Naveed M, Crampton A, Kitchin D, McCluskey L. 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.. 2011. p. 35-48 https://doi.org/10.1007/978-1-4471-2318-7-3