Mixed Discrete-Continuous Heuristic Generative Planning Based on Flow Tubes

Enrique Fernández-González, Erez Karpas, Brian Charles WilliamsIJCAI 2015

Introduction

Robotic missions require reasoning across two distinct domains: discrete logic (e.g., "pick up the sample") and continuous dynamics (e.g., "accelerate to 2 m/s"). Historically, planners have struggled to bridge this gap effectively. Hybrid Model Predictive Control (MPC) systems are mathematically expressive but rely on time discretization, leading to a "state explosion" that makes long-duration missions computationally prohibitive. Conversely, AI temporal planners are fast but often oversimplify dynamics, resulting in brittle plans that cannot adapt to real-world delays.

Scotty is a hybrid generative planner designed to find the middle ground: a system as fast as AI search but as expressive as control-theoretic models. It achieves this by bridging high-level task planning with low-level trajectory optimization without the need for time discretization.

Methodology: Planning with Flow Tubes

The core innovation of Scotty is the use of flow tubes to represent continuous movement. Instead of calculating a single, rigid path, a flow tube is a mathematical abstraction that encapsulates all possible trajectories a robot can take given bounded control variables, such as a velocity range $[v_{min}, v_{max}]$.

Figure 2: Flow tube representation showing the reachability of continuous states over time without discretization.

Scotty combines two key ideas: Heuristic Forward Search (using Enforced Hill Climbing) to explore discrete actions, and Linear Programming (LP) to ensure continuous consistency. Unlike previous planners, Scotty’s LP formulation treats both time and control variables as continuous decision variables. By using linear inequalities to define the reachability of a flow tube, the planner can treat a multi-hour segment as one continuous unit rather than thousands of tiny time steps, effectively eliminating the scalability issues associated with discretization.

Experimental Evaluation

The authors evaluated Scotty using several simulated robotic domains designed to stress-test hybrid reasoning:

  • 2D and 3D AUV (Autonomous Underwater Vehicle) Missions: Navigating to regions to collect data within specific time windows.
  • Firefighting Scenarios: Coordinating multiple robots to reach and extinguish fires.
  • Scaling Benchmarks: A specific AUV sampling scenario where the target depth is varied to test how the planner scales with increasing mission horizons.

Key Results and Insights

The most significant finding is that by avoiding fixed time steps, planning time becomes largely independent of the mission's physical distance. In AUV benchmarks, Scotty was consistently 100x to 800x faster than Kongming, a state-of-the-art discretization-based planner.

Figure 5: Planning time comparison between Scotty and Kongming, demonstrating Scotty's flat scaling versus Kongming's exponential growth as sampling depth increases.

Beyond speed, Scotty provides increased robustness through flexibility. Because it produces a Qualitative State Plan (QSP)—a network of constraints rather than a rigid schedule—the robot can compensate for delays by simply increasing its velocity within the known bounds of the flow tube. This allows for successful mission execution in dynamic environments where fixed-speed plans would fail.

Limitations and Future Work

Currently, Scotty is limited to activities with linear continuous effects. It cannot natively handle non-linear dynamics, such as complex aerodynamics, without approximating them as linear segments. Additionally, the current implementation struggles with coupled variables that create quadratic constraints (e.g., speed affecting non-linear battery drain). Future work will explore "lifting" plans into partial-order structures to better handle parallel tasks and further increase plan flexibility.

Summary updated

BibTeX
@inproceedings{fernandezgonzalez2015mixed,
  author = {Enrique Fernández-González and Erez Karpas and Brian Charles Williams},
  title = {{Mixed Discrete-Continuous Heuristic Generative Planning Based on Flow Tubes}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure