Efficient Temporal Piecewise-Linear Numeric Planning with Lazy Consistency Checking
Josef Bajada, Maria Fox and Derek Long
Abstract: Temporal planning often involves numeric effects that are directly proportional to their actionÕs duration. These include continuous effects, where a numeric variable is subjected to a rate of change while the action is being executed, and discrete duration-dependent effects, where the variable is updated instantaneously but the magnitude of such change is computed from the actionÕs duration. When these effects are linear, stateÐofÐtheÐart temporal planners often make use of Linear Programming to ensure that these numeric updates are consistent with the chosen start times and durations of the planÕs actions. This is typically done for each evaluated state as part of the search process. This exhaustive approach is not scalable to solve real-world problems that require long plans, because the linear programÕs size becomes larger and slower to solve. In this work we propose techniques that minimise this overhead by computing these checks more selectively and formulating linear programs that have a smaller footprint. The effectiveness of these techniques is demonstrated on domains that use a mix of discrete and continuous effects, which is typical of real-world planning problems. The resultant planner also outperforms most state-of-the-art temporal-numeric and hybrid planners, in terms of both coverage and scalability.
*This password protected talk video will only be available after it was presented at the conference.
