Utility of pathmax in partial order heuristic search

Abstract

The idea of using the pathmax property suggested by Mero [7] to correct admissible non-monotonic heuristics has been well studied within the framework of total order search. It has been shown by Dechter and Pearl [3] that pathmax may reduce the set of nodes expanded by algorithms such as A* [8] in pathological problem instances only, that is, in problem instances where every solution path contains at least one fully informed non-goal node. This result severely restricts the use of pathmax especially in tree search. In case of graphs, it may reduce the number of node re-expansions in non-pathological cases as well, though the set of nodes that are expanded remain the same. In this paper we show that in the framework of partial order search, where costs are vector valued, an appropriate extension of pathmax is useful in non-pathological problem instances as well (including tree search).