OBDD-Based Planning with Real-Valued Variables in Non-Deterministic Environments

Abstract

Planning for highly dynamic and uncertain real-world domains is difficult using current planning tools. These domains may be characterized by non-deterministic actions and the need to represent large real-valued state spaces. Classical planning considers only deterministic domains and sidesteps the issue of non-determinism. Real-valued variables are handled by requiring domains to either represent real variables as relative booleans (e.g. using on-table or on-block in the classical blocks world), or to explicitly enumerate each possible value for a real variable (e.g. using at11, at12, at21, at22 for block position in a 2x2 blocks world). The former approach is a lossy transformation where positioning information is lost while the latter is subject to state explosion for large domains. We are developing a planner that can efficiently handle