UTILITY OF PATHMAX IN PARTIAL ORDER HEURISTIC-SEARCH

The idea of using the pathmax property suggested by Mere [7] to correc t admissible non-monotonic heuristics has been well studied within the framework of total order search. It has been shown by Dechter and Pea rl [3] that pathmax may reduce the set of nodes expanded by algorithms such as A [8] in pathological problem instances only, that is, in pr oblem instances where every solution path contains at least one fully informed non-goal node. This result severely restricts the use of path max especially in tree search. In case of graphs, it may reduce the nu mber of node re-expansions in non-pathological cases as well, though t he set of nodes that are expanded remain the same. In this paper we sh ow that in the framework of partial order search, where costs are vect or valued, an appropriate extension of pathmax is useful in non-pathol ogical problem instances as well (including tree search).