TTree: Tree-based state generalization with temporally abstract actions

August 2002

TTree: Tree-based state generalization with temporally abstract actions

Authors:

William Uther and Manuela Veloso

Abstract:

In this paper we describe the Trajectory Tree, or TTree, algorithm. TTree uses a small set of supplied policies to help solve a Semi-Markov Decision Problem (SMDP). The algorithm uses a learned tree based discretization of the state space as an abstract state description and both user supplied and auto-generated policies as temporally abstract actions. It uses a generative model of the world to sample the transition function for the abstract SMDP defined by those state and temporal abstractions, and then finds a policy for that abstract SMDP. This policy for the abstract SMDP can then be mapped back to a policy for the base SMDP, solving the supplied problem. In this paper we present the TTree algorithm and give empirical comparisons to other SMDP algorithms showing its effectiveness.
@conference{Uther-2002-8524,
author = {William Uther And Manuela Veloso},
title = {TTree: Tree-based state generalization with temporally abstract actions},
booktitle = {Proceedings of International Symposium on Abstraction, Reformulation, and Approximation (SARA '02)},
year = {2002},
month = {August},
pages = {308 - 315},
}
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.