Premium
AN EVALUATION OF THE TEMPORAL COHERENCE HEURISTIC IN PARTIAL‐ORDER PLANNING
Author(s) -
Yang Qiang,
Murray Cheryl
Publication year - 1994
Publication title -
computational intelligence
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.353
H-Index - 52
eISSN - 1467-8640
pISSN - 0824-7935
DOI - 10.1111/j.1467-8640.1994.tb00165.x
Subject(s) - heuristic , completeness (order theory) , coherence (philosophical gambling strategy) , computer science , planner , set (abstract data type) , constraint (computer aided design) , domain (mathematical analysis) , mathematical optimization , artificial intelligence , mathematics , statistics , mathematical analysis , geometry , programming language
This paper presents an evaluation of a heuristic for partial‐order planning, known as temporal coherence. The temporal coherence heuristic was proposed by Drummond and Currie as a method to improve the efficiency of partial‐order planning without losing the ability to find a solution (i.e., completeness). It works by using a set of domain constraints to prune away plans that do not “make sense,” or are temporally incoherent. Our analysis shows that, while intuitively appealing, temporal coherence can only be applied to a very specific implementation of a partial‐order planner and still maintain completeness. Furthermore, the heuristic does not always improve planning efficiency; in some cases, its application can actually degrade the efficiency of planning dramatically. To understand when the heuristic will work well, we conducted complexity analysis and empirical tests. Our results show that temporal coherence works well when strong domain constraints exist that significantly reduce the search space, when the number of subgoals is small, when the plan size is not too large, and when it is inexpensive to check each domain constraint.