Delete-Free Planning with Object Creation is Undecidable

Abstract

In planning with object creation, actions might introduce new objects as part of their effect. While this makes the formalism more expressive, it also renders the plan existence problem undecidable. A natural next step is to ask whether simpler fragments and relaxations are still undecidable when powered with object creation. Probably the most popular fragment is delete-free planning, where actions can only add but never delete atoms. In this work, we show that delete-free planning with object creation is still undecidable. We do so by reducing the problem of deciding whether a given atom is reached by the chase procedure to the plan existence problem. Our result implies that heuristics based on the delete relaxation may not be immediately useful for the object creation setting. We then highlight which restrictions we can apply to make delete-free planning with object creation practical.