homeresources & publications › planning with goal utility dependencies


Planning with goal utility dependencies


Work in partial satisfaction planning (PSP) has hither to assumed that goals are independent thus implying that they have additive utility values. In many real-world problems, we can not make this assumption. In this paper, we motivate the need for handling various types of goal utility dependency in PSP. We provide a framework for representing them using the General Additive Independence model and investigate two different approaches to handle this problem: (i) compiling PSP with utility dependencies to Integer Programming; (ii) forward heuristic search planning. To guide the forward planning search, we introduce a novel heuristics framework of combining cost-propagation and Integer Programing encoding to select goals and extract good quality heuristic estimate. We investigate the effectiveness of different approaches by comparing them empirically on several benchmark planning domains.


Do, M. B. ; Benton, J.; van den Briel, M.; Kambhampati, S. Planning with goal utility dependencies. Twentieth International Joint Conference on Artificial Intelligence (IJCAI 2007); 2007 January 6-12; Hyderabad; India; 1872-1878.