ReTrASE: integrating paradigms for approximate probabilistic planning
Andrey Kolobov, Daniel S. Weld · 2009
Humans are often able to solve extremely large probabilistic planning problems reasonably well by exploiting problem structure, heuristics, and various approximations. Each of these aspects seems indispensable for achieving high scalability and has been studied in detail by the automated planning community. However, most existing solvers use only a proper subset of them. In an initial attempt to bridge this gap we introduce RETRASE, a novel MDP solver that derives approximate policies by extracting problem structure and learning its parameters under heuristic guidance. RETRASE uses classical planning to discover basis functions for value-function approximation and applies expected-utility analysis to this compact space. Experiments demonstrate that RE-TRASE outperforms winners from the past three probabilistic-planning competitions on many hard problems. We outline several extensions of RE-TRASE and new directions for unifying paradigms in probabilistic planning prompted by RETRASE’s success. 1