  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.
