Abstract:
This paper proposes a structure for utility functions that are useful when modeling and solving important classes of practical planning applications--problems that are not adequately characterized by an additive utility function, but still have some additive structure. The structure is Xu(t)*mod(t,...) where is a function of how and when a single task is completed and rood(t,...) captures the effects of dependencies between tasks. This structure makes it relatively easy to represent many important problems and allows decision theoretic techniques to be used to merge the available evidence when making variable and value order decisions during heuristic search.