Introduction
Traditional AI planning often relies on discrete state transitions, treating the world as a sequence of static snapshots. However, real-world applications—from naval strategy to autonomous robotics—operate in dynamic, continuous environments where variables like velocity, fuel, and position change nonlinearly over time. This paper presents SHOP2$_{PDDL+}$, an extension of the Hierarchical Task Network (HTN) planner designed to reason about such complex continuous effects by integrating PDDL+ formalisms.
The Challenge of Continuous Dynamics
Most existing planners struggle with nonlinear continuous effects, such as a vehicle's position under constant acceleration (a function of time squared). While some can handle linear changes, high-fidelity simulations require the ability to project these changes into the future to predict when specific event thresholds will be met. HTN planners, though efficient due to their use of domain knowledge, historically lacked the internal machinery to handle these exogenous processes and continuous fluents.
Methodology: SHOP2$_{PDDL+}$
The authors introduce two primary innovations to bridge this gap: the "Wait" action and a specialized state projection algorithm.
The "Wait" Action
By introducing an explicit "wait" action, the planner can model the passage of time as a first-class operation. This allows the system to synchronize discrete agent actions with ongoing continuous processes, such as waiting for a ship to reach a certain coordinate before initiating a maneuver.
State Projection Algorithm
To determine the state of the world after a "wait" interval, the planner employs the ProjectState algorithm. This algorithm builds a fluent update table of algebraic functions and identifies "eligible events" by finding the roots of threshold functions. Given the potential nonlinearity of these functions, numerical methods like bisection and golden section search are utilized to pinpoint the exact moment an event is triggered.
Evaluation and Results
The SHOP2$_{PDDL+}$ planner was evaluated across several domains, including a US Navy strategy simulator (TAO Sandbox) and a "Stunt Car" domain specifically designed to test nonlinear reasoning.
Performance and Robustness
In the Rover Domain benchmark, SHOP2$_{PDDL+}$ demonstrated superior robustness, solving all test cases where state-of-the-art linear planners like COLIN failed on more challenging problems. Despite the computational overhead of nonlinear root-finding, the HTN's ability to prune the search space using domain knowledge kept planning times efficient.
In the TAO Sandbox, the planner generated complex plans for 12 moving vessels in approximately one second, proving its viability for real-time simulation environments. The planner also successfully navigated the Stunt Car domain, correctly calculating the precise braking and acceleration needed to hit a specific velocity window—a task impossible for linear-only planners.
Discussion and Future Work
While SHOP2$_{PDDL+}$ successfully handles nonlinear dynamics, the authors note a significant computational cost compared to purely discrete planning. Future research will focus on optimizing the state projection algorithm through dynamic programming and caching. Additionally, improving heuristics for determining optimal "wait" times and integrating real-time execution monitoring remain key areas for development to enhance the agent's responsiveness to unexpected environmental changes.
Summary updated