Planning with Goal Utility Dependencies

Minh Do, J. Benton, Menkes van den Briel, Subbarao Kambhampati

Work in partial satisfaction planning (PSP) has hitherto assumed that goals are independent thus implying that they have additive utility values. In many real-world problems, we cannot make this assumption. In this paper, we motivate the need for handling various types of goal utility dependence in PSP. We provide a framework for representing them using the General Additive Independence model and investigate two different approaches to handle this problem: (1) compiling PSP with utility dependencies to Integer Programming; (2) extending forward heuristic search planning to handle PSP goal dependencies. To guide the forward planning search, we introduce a novel heuristic framework that combines cost-propagation and Integer Programming to select beneficial goals to find an informative heuristic estimate. The two implemented planners, iPUD and SPUDS, using the approaches discussed above, are compared empirically on several benchmark domains. While iPUD is more readily amendable to handle goal utility dependencies and can provide bounded optimality guarantees, SPUDS scales much better.