Ankit Anand
ABSTRACT
Abstractions are a useful tool for computing policies in large domains modeled as a Markov Decision Process. Prior work in this field is mostly focused on developing different notions for state abstractions. In this paper, we develop a novel framework for abstractions, which unifies prior work and directly exploits symmetry at the state-action pair level, thereby uncovering a much larger number of symmetries in a given domain. We describe the application of abstractions computed through this framework in UCT, a popular MCTS technique for online planning.
- A. Anand, A. Grover, Mausam, and P. Singla. A Novel Abstraction Framework for Online Planning. Technical report, Indian Institute of Technology, Delhi, 2015.Google Scholar
- R. Givan, T. Dean, and M. Greig. Equivalence notions and model minimization in Markov decision processes. Artificial Intelligence, 147(1--2):163--223, 2003. Google ScholarDigital Library
- J. Hostetler, A. Fern, and T. Dietterich. State Aggregation in Monte Carlo Tree Search. In AAAI, 2014.Google Scholar
- N. Jiang, S. Singh, and R. Lewis. Improving UCT Planning via Approximate Homomorphisms. In AAMAS, pages 1289--1296, 2014. Google ScholarDigital Library
- L. Kocsis and C. Szepesvári. Bandit based monte-carlo planning. In Machine Learning: ECML 2006, pages 282--293. Springer, 2006. Google ScholarDigital Library
- B. Ravindran and A. Barto. Approximate homomorphisms: A framework for nonexact minimization in Markov decision processes. In Proc. 5th Int. Conf. Knowledge-Based Computer Systems, 2004.Google Scholar
Index Terms
- A Novel Abstraction Framework for Online Planning: Extended Abstract
Recommendations
Improving UCT planning via approximate homomorphisms
AAMAS '14: Proceedings of the 2014 international conference on Autonomous agents and multi-agent systemsIn this paper we show how abstractions can help UCT's performance. Ideal abstractions are homomorphisms because they preserve optimal policies, but they rarely exist, and are computationally hard to find even when they do. We show how a combination of (...
Planning with abstraction based on partial predicate mappings
AbstractPlanning with abstraction is an act of finding an abstract plan that can be instantiated into a concrete plan for a given planning problem. It is very important for an abstract planning system to satisfy a property, calledDownward-Solution ...
Comments