Period/Dynamic Planning Problem: Formal Representation and Complexity Analysis

Transportation planning and path planning are hot research topics which can be evidenced by their frequent and repeated presence in the benchmark test in International Planning Competition. However, most of the benchmark test examples only consider the static planning problems, whose state transitions are only caused by the actions of the planners. In this paper, we will discuss the dynamic version and introduce the formalization of the Period/Dynamic planning problem. Then, we will prove that the computational complexity is EXPSPACE-Complete.