Symbolic Generalization for On-line Planning
Zhengzhu Feng
Eric A. Hansen
Shlomo Zilberstein
Abstract
Symbolic representations have been used successfully
in off-line planning algorithms for Markov decision processes.
We show that they can also improve the performance of on-line
planners. In addition to reducing computation
time, symbolic generalization can reduce
the amount of costly real-world interactions
required for convergence. We introduce
Symbolic Real-Time Dynamic Programming (or sRTDP),
an extension of RTDP. After
each step of on-line interaction with an
environment, sRTDP uses symbolic model-checking
techniques to generalizes its experience
by updating a group of states rather
than a single state. We examine two heuristic
approaches to dynamic grouping of states
and show that they accelerate the planning
process significantly in terms of both CPU
time and the number of steps of interaction
with the environment.
Download
[pdf]