The Parti-game Algorithm for Variable Resolution Reinforcement Learning in Multidimensional State-spaces (1995)
Tags
Markov Decision Processes, Optimization, Reinforcement Learning
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 learning does not plan uniformly over a state-space. Parti-game maintains a decision-tree partitioning of state-space and applies techniques from game-theoryand 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 tested, 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.
Full text
Download (application/pdf, 806.5 kB)
Approximate BibTeX Entry
@article{moore-partigame,
Year = {1995},
Journal = {Machine Learning},
Volume = {21},
Author = {
Andrew Moore, Chris
Atkeson
},
Title = {The Parti-game Algorithm for Variable Resolution Reinforcement Learning in Multidimensional State-spaces}
}