Automated Planning for Pathfinding in Real-Time Strategy Games

Doctoral thesis English OPEN
Naveed, Munir Hussain
  • Subject: T1

This thesis is focused on the design of a new path planning algorithm to solve path planning problems in dynamic, partially observable and real-time environments such as Real-Time Strategy (RTS) games. The emphasis is put on fast action selection motivating the use of Monte-Carlo planning techniques. Three main contributions are presented in this thesis. The first contribution is a Monte-Carlo planning technique, called MCRT, that performs selective action sampling and limits how many times a particular state-action pair is explored to balance the trade-off between exploration of new actions and exploitation of the current best action. The thesis also presents two variations of MCT as the second contribution. The first variation of MCRT randomly selects an action as a sample at each state seen during the look-ahead search. The second variation, called MCRT-CAS, performs the selective action sampling using corridors. The third contribution is the design of four real-time path planners that exploit MCRT and its variations to solve path planning problems in real-time. Three of these planners are empirically evaluated using four standard pathfinding benchmarks (and over 1000 instances). Performance of these three planners is compared against two recent rival algorithms (Real-time D*-Lite (RTD) and Local Search Space-Learning Real-Time A* (LSS-LRTA)). These rival algorithms are based on real-time heuristic search. The results show that a variation of MOCART, called MOCART-CAS, performs action selection significantly faster than the rival planners. The fourth planner, called the MG-MOCART planner, is evaluated using a typical Real-Time Strategy game. The MG-MOCART planner can solve the path planning problems with multiple goals. This planner is compared against four rivals: Upper Con�dence bounds applied to Trees (UCT), LSS-LRTA, Real-Time Dynamic Programming (RTDP) and a rapidly-exploring random tree (RRT) planner. The performance is measured using score and planning cost. The results show that the MG-MOCART planner performs better than its rival techniques with respect to score and planning cost.
  • References (23)
    23 references, page 1 of 3

    [1] N. M. Amato and Y. Wu. A Randomized Roadmap Method for Path and Manipulation Planning. In In IEEE International Conference on Robotics and Automation, pages 113{120, 1996.

    [2] P. Auer, N. Cesa-Bianchi, and P. Fischer. Finite-time Analysis of the Multiarmed Bandit Problem. Machine Learning, 47(2-3):235{256, May 2002.

    [3] R. Balla and A. Fern. UCT for Tactical Assault Planning in Real-Time Strategy Games. In Proceedings of the 21st International Joint Conference on Arti cial Intelligence, pages 40{45, 2009.

    [4] J. Barraquand, L. Kavraki, J.-C. Latombe, T.-Y. Li, R. Motwani, and P. Raghavan. A random sampling scheme for path planning. INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH, 16:759{774, 1996.

    [5] A. Barto, S. Bradtke, and S. Singh. Learning to act using Real-Time Dynamic Programming. Arti cial Intelligence, 72:81{138, 1995.

    [6] R. Bellman. The Theory of Dynamic Programming. Bulletin of The American Mathematical Society, 60(6):503 { 516, 1954.

    [7] D. Bertsekas. Distributed Dynamic Programming. IEEE Transactions on Automatic Control, 27(3):610{616, 1982.

    [8] R. Bjarnason, A. Fern, and P. Tadepalli. Lower Bounding Klondike Solitaire with Monte-Carlo Planning. In Proceedings of the 19th International Conference on Automated Planning & Scheduling, 2009.

    [9] Y. Bjornsson, V. Bulitko, and N. Sturtevant. TBA*: Time-Bounded A*. In Proceedings of the 21st International Joint Conference on Arti cal Intelligence, pages 431{436, San Francisco, CA, USA, 2009. Morgan Kaufmann Publishers Inc.

    [10] Y. Bjornsson, M. Enzenberger, R. Holte, and J. Schae er. Fringe Search: Beating A* at Path nding on Game Maps. In Proceedings of the IEEE Symposium on Computational Intelligence and Games. 2005.

  • Similar Research Results (1)
  • Metrics
    views in OpenAIRE
    views in local repository
    downloads in local repository

    The information is available from the following content providers:

    From Number Of Views Number Of Downloads
    University of Huddersfield Repository - IRUS-UK 0 87
Share - Bookmark