On the Nature of Modal Truth in Plans

Abstract

Chapman's paper, "Planning for Conjunctive Goals", has been widely acknowledged as a major step towards understanding the nature of nonlinear planning, and it has been one of the bases of later work by others -- but it is not free of problems. This paper discusses the following problems with modal truth and the modal truth criterion.<P>1. It is NP-hard to tell, given a plan P and a ground atom p, whether P is possibly true in P's final situation. This is true despite the fact that modal truth criterion can be computed in a polynomial time.<P>2. The reason for this discrepancy is that the "possible truth" version of the modal truth criterion is incorrect. It tells whether - p is not necessarily true --- but this is different from telling whether p is possibly true. Possible truth is not the dual of necessary truth, as Chapman had thought it was.<P>3. Instead, possible truth is the dual of another problem, which is co-NP-hard: the problem of determining whether p is true over all executable completions of a plan.<P>Despite the above problems, the "necessary truth" version of the modal truth criterion (and hence the TWEAK planner) are still correct.