TY - JOUR
T1 - Efficient Temporal Piecewise-Linear Numeric Planning With Lazy Consistency Checking
AU - Bajada, Josef
AU - Fox, Maria
AU - Long, Derek
N1 - Funding Information:
This work was supported in part by the U.K. Engineering and Physical Sciences Research Council (EPSRC) as a part of a project entitled The Autonomic Power System under Grant EP/I031650/1
Publisher Copyright:
© 2020 IEEE.
PY - 2022/8/1
Y1 - 2022/8/1
N2 - 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 a part of the search process. This exhaustive approach is not scalable to solve real-world problems that require long plans, because the size of the linear program becomes larger and slower to solve. In this article, we propose techniques that minimize 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.
AB - 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 a part of the search process. This exhaustive approach is not scalable to solve real-world problems that require long plans, because the size of the linear program becomes larger and slower to solve. In this article, we propose techniques that minimize 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.
KW - Continuous effects
KW - numeric planning
KW - planning domain definition language (PDDL)
KW - scheduling
KW - temporal planning
UR - http://www.scopus.com/inward/record.url?scp=85135346583&partnerID=8YFLogxK
U2 - 10.1109/TAI.2022.3146797
DO - 10.1109/TAI.2022.3146797
M3 - Article
AN - SCOPUS:85135346583
SN - 2691-4581
VL - 3
SP - 506
EP - 517
JO - IEEE Transactions on Artificial Intelligence
JF - IEEE Transactions on Artificial Intelligence
IS - 4
ER -