Over All, PDDL Semantics is Simultaneously Simple and Hard to Get Right

PDDL 2.1 is the community standard for specifications of temporal planning problems, involving actions that have a duration and can overlap in time. Recent work has shown that some modelling features, such as intermediate and conditional effects, can be expressed in PDDL 2.1 by means of specific encodings. At the core of these encodings is a construction that requires two events to happen simultaneously. However, in practice, almost none of the state-space heuristic search planners known in the literature are capable of finding plans exhibiting this required simultaneity, suggesting that the search approach they use is actually incomplete with regards to the official PDDL 2.1 semantics. In this paper, we explore this issue both theoretically and experimentally. On the theoretical side, we define two different notions of required simultaneity, and we isolate which features of the semantics of PDDL 2.1 allow for such behaviors and how to possibly change the semantics to forbid each of them. In particular, we prove that the crucial detail is how the over-all conditions interact with the mutex relation. From these observations we isolate the reason why most search-based planners cannot find plans with required simultaneity, and provide an updated search strategy that recovers semantic completeness at the cost of a larger branching factor which, however, can be suitably pruned thanks to an application of our results. On the experimental side, we compare the proposed search strategies, showing that our pruning criterion allows us to recover semantic completeness without significant overhead.