Planning with goal utility dependencies
Bùi Quang Minh, J. Benton, Menkes van den Briel, Subbarao Kambhampati · 2007
Work in partial satisfaction planning (PSP) has hither to assumed that goals are independent. This implies that that individual goals have additive utility values. In many real-world problems we cannot make this assumption and thus goal utility is not additive. In this paper, we motivate the need for representing and handling goal utility dependencies in PSP and we provide a framework for representing them using the General Additive Independence (GAI) model (Bacchus & Grove 1995). We then present an algorithm based on forward heuristic planning to solve this problem using heuristics derived from the planning graph. To show the effectiveness of our framework, we provide empirical results on benchmark planning domains.