The incompleteness of planning with volatile external information

In many real-world planning environments, someof the information about the world is both external (the planner
must request it from external information sources) and volatile
(it changes before the planning process completes). In such en-
vironments, a planner faces two challenges: how to generate
plans despite changes in the external information during plan-
ning, and how to guarantee that a plan returned by the plan-
ner will remain valid for some period of time after the plan-
ning ends. Previous works on planning with volatile informa-
tion have addressed the first challenge, but not the second one.
This paper provides a general model for planning with
volatile external information in which the planner offers a guar-
antee of how long the solution will remain valid after it is re-
turned, and an incompleteness theorem showing that there is no
planner that can succeed in solving all solvable planning prob-
lems in which there is volatile external information.