Utility of pathmax in partial order heuristic search

Dasgupta, Pallab ; Chakrabarti, P. P. ; DeSarkar, S. C. (1995) Utility of pathmax in partial order heuristic search Information Processing Letters, 55 (6). pp. 317-322. ISSN 0020-0190

Full text not available from this repository.

Official URL: http://linkinghub.elsevier.com/retrieve/pii/002001...

Related URL: http://dx.doi.org/10.1016/0020-0190(95)00086-R


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).

Item Type:Article
Source:Copyright of this article belongs to Elsevier Science.
Keywords:Artificial Intelligence; Heuristic Search; Multiobjective Optimization
ID Code:5969
Deposited On:19 Oct 2010 10:02
Last Modified:20 May 2011 09:43

Repository Staff Only: item control page