Computational Complexity of Planning with Discrete Time and Continuous State Variables

Traditionally, most planning research in AI was concentrated on systems whose state can be characterized by discrete-valued fluents. In many practical applications, however, we want to control systems (like robots) whose state can only be described if we used continuous variables (like coordinates). Planning for such systems corresponds, crudely speaking, to Level 2 of the planing language PDDL2.1. In this paper, we analyze the computational complexity of such planning problems