Optimal Planning with Global Numerical State Constraints

Automating the operations of infrastructure networks such as energy grids and oil pipelines requires a range of planning and optimisation technologies. However, current planners face significant challenges in responding to this need. Notably, they are unable to model and reason about the global numerical state constraints necessary to capture flows and similar physical phenomena occurring in these networks. A single discrete control action can affect the flow throughout the network in a way that may depend on the entire network topology. Determining whether preconditions, goals and invariant conditions are satisfied requires solving a system of numerical constraints after each action application. This paper extends domain-independent optimal planning to this kind of reasoning. We present extensions of the formalism, relaxed plans, and heuristics, as well as new search variants and experimental results on two problem domains.

Authors

• Franc Ivankovic
• Patrik Haslum
• Sylvie Thiébaux
• Vikas Shivashankar
• Dana S. Nau

Keywords

• Planning
• Hybrid systems
• Numerical state constraints