The Parti-game Algorithm for Variable Resolution Reinforcement Learning in Multidimensional State-spaces

December 1995

The Parti-game Algorithm for Variable Resolution Reinforcement Learning in Multidimensional State-spaces

Authors:

Andrew Moore and C. G. Atkeson

Abstract:

Parti-game is a new algorithm for learning feasible trajectories to goal regions in high dimensional continuous state-spaces. In high dimensions it is essential that neither planning nor exploration occurs uniformly over a state-space. Parti-game maintains a decision-tree partitioning of state-space and applies techniques from game-theory and computational geometry to efficiently and adaptively concentrate high resolution only on critical areas. The current version of the algorithm is designed to find feasible paths or trajectories to goal regions in high dimensional spaces. Future versions will be designed to find a solution that optimizes a real-valued criterion. Many simulated problems have been rested, ranging from two-dimensional to nine-dimensional state-spaces, including mazes, path planning, non-linear dynamics, and planar snake robots in restricted spaces. In all cases, a good solution is found in less than ten trials and a few minutes.
@article{Moore-1995-14049,
author = {Andrew Moore And C. G. Atkeson},
title = {The Parti-game Algorithm for Variable Resolution Reinforcement Learning in Multidimensional State-spaces},
journal = {Proceedings of Machine Learning},
year = {1995},
month = {December},
volume = {21},
pages = {199 - 233},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.