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}]$.
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.
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