ReTrASE: Integrating Paradigms for Approximate Probabilistic Planning

Abstract

The Web Service Composition (WSC) problem with respect to behavioral descriptions deals with the automatic synthesis of a coordinator web service, c, that controls a set of web services to reach a goal state. Despite its importance, however, solving the WSC problem for a general case (when c has only partial observations) remains to be doubly exponential in the number of variables in web service descriptions, rendering any attempts to compute an exact solution for modest size impractical. Toward this challenge, in this paper, we propose two novel (signature preserving and subsuming) approximation-based approaches using abstraction and refinement. We empirically validate that our proposals can solve realistic problems efficientlyHyunyoung Kil, Wonhong Nam, Dongwon LeePast approaches for solving MDPs have several weaknesses: 1) Decision-theoretic computation over the state space can yield optimal results but scales poorly. 2) Value-function approximation typically requires human-specified basis functions and has not been shown successful on nominal (discrete) domains such as those in the ICAPS planning competitions. 3) Replanning by applying a classical planner to a determinized domain model can generate approximate policies for very large problems but has trouble handling probabilistic subtlety. This paper presents ReTrASE, a novel MDP solver, which combines decision theory, function approximation and classical planning in a new way. ReTrASE uses classical planning to create basis functions for value-function approximation and applies expected-utility analysis to this compact space. Our algorithm is memory-efficient and fast (due to its compact, approximate representation), returns high-quality solutions (due to the decision-theoretic framework) and does not require additional knowledge from domain engineers (since we apply classical planning to automatically construct the basis functions). Experiments demonstrate that ReTrASE outperforms winners from the past three probabilistic-planning competitions on many hard problems.Andrey Kolobov, Mausam, Daniel S. Weld