Heuristic search with a general order relation

Abstract

Algorithms are developed and analyzed for the solution of a class of problems that can be represented by locally finite graphs in which preferences among solution paths may be described by a transitive binary relation. The basic algorithmic structure of the popular heuristic search algorithm A* and its relatives is generalized using concepts from decision theory to allow for problems not effectively formulated in terms of the standard scalar criterion for directing search. The major motivation for this generalization is the importance of multiobjective problems in which it is often the case that development of a total order over the set of solution paths is neither necessary nor desirable. Relevant background on heuristic search theory and decision theory is presented. A general algorithm for heuristic search using transitive binary relations, referred to as GOZ* for generally ordered Z*, is presented and its formal properties are investigated. Similar to its precursors, A* and Z*, this generalization is found to be complete and admissible under the appropriately adjusted definitions. Other relevant characteristics of the algorithm that are considered include termination, comparison of heuristics, monotonicity, and consistency. Specializations of this general algorithm to the cases of additive multiobjective problems and a linear additive parametric generalization of those problems are presented with the help of several illustrative examples. Implementation issues, computational questions, and extensions related to preferences and search of AND/OR graphs are discussed in the context of future research directions. Pseudo-code for several of the generalized search algorithms is presented in an appendix.