Introduction
In automated planning, temporal scheduling involves coordinating actions over time. While standard PDDL 2.1 supports linear continuous changes, real-world physics often involves non-linear dynamics, such as a tank draining faster when full or a vehicle accelerating. Traditional planners often struggle with these complexities, either failing to represent them or relying on computationally expensive time discretization. This paper introduces uNICOrn, a temporal planner designed to handle non-linear continuous changes by approximating them as linear segments within a Linear Programming (LP) framework. By utilizing "semantic attachments" and an iterative convergence algorithm, uNICOrn bridges the gap between efficient linear solvers and complex physical models.
Methodology: Iterative Linear Approximation
The core innovation of uNICOrn lies in its use of Iterative Linear Approximation combined with Semantic Attachment. Instead of embedding complex differential equations directly into the planning language, the system allows the planner to call external C++ functions (semantic attachments) to calculate non-linear values at specific time points.
The planner explores the state space using Breadth-First Search (BFS). For each state, it constructs an LP to verify temporal feasibility. Since LPs require linear constraints, uNICOrn approximates non-linear curves as straight lines between action boundaries.
As shown in Figure 2, the algorithm starts with an initial duration guess and calculates the actual value via the semantic attachment. If the discrepancy between the linear approximation and the true value exceeds a user-defined margin of error ($e_m$), the algorithm adjusts the line's gradient and adds temporal constraints to "sandwich" the function. This process repeats until the approximation converges within the specified tolerance. A critical requirement is that the functions must be monotonic, ensuring reliable convergence.
Evaluation and Results
The authors evaluated uNICOrn across two primary domains: the Tanks Domain, based on Torricelli’s Law where drainage rates are non-linearly related to water height, and the Car Domain, where linear acceleration results in quadratic distance changes. uNICOrn demonstrated significant improvements in scalability and performance compared to discretization-based planners like UPMurphi.
As illustrated in Figure 4, uNICOrn successfully solved problems involving up to 7 tanks (and up to 10 in extended tests), whereas UPMurphi failed to scale beyond 3 tanks due to memory or time limits. For a 3-tank instance, uNICOrn achieved a solution in 0.67 seconds, nearly 50 times faster than UPMurphi's 31.44 seconds. Furthermore, uNICOrn proved robust to precision requirements; tightening the error tolerance from 1.0 to 0.0001 had a minimal impact on computation time, highlighting the efficiency of the iterative refinement process.
Conclusion and Future Work
uNICOrn offers a scalable approach to temporal planning with non-linear dynamics by leveraging monotonicity and iterative linearization. However, the current reliance on monotonic functions limits its application to systems with oscillating behaviors. Future work aims to incorporate advanced search heuristics to navigate larger state spaces more effectively and to extend the linearization technique to handle non-monotonic piecewise functions.
Summary updated