Using Constraint Programming for Disjunctive Scheduling in Temporal AI Planning

TY - CHAP

T1 - Using Constraint Programming for Disjunctive Scheduling in Temporal AI Planning

AU - Green, Adam

AU - Beck, J. Christopher

AU - Coles, Amanda

PY - 2024/9/2

Y1 - 2024/9/2

N2 - We present a novel scheduling model that leverages Constraint Programming (CP) to enhance problem solving performance in Temporal Planning. Building on the established strategy of decomposing causal and temporal reasoning, our approach abstracts two common fact structures present in many Temporal Planning problems – Semaphores and Envelopes – and performs temporal reasoning in a CP-based scheduler. At each search node in a heuristic search for a temporal plan, we construct and solve a Constraint Satisfaction Problem (CSP) and integrate feedback from the CP-based scheduler to guide the causal planning search towards a solution. Through experimental analysis, we validate the impact of these advances, demonstrating a significant reduction in both the number of states searched and in search time alongside an increase in problem-solving coverage.

AB - We present a novel scheduling model that leverages Constraint Programming (CP) to enhance problem solving performance in Temporal Planning. Building on the established strategy of decomposing causal and temporal reasoning, our approach abstracts two common fact structures present in many Temporal Planning problems – Semaphores and Envelopes – and performs temporal reasoning in a CP-based scheduler. At each search node in a heuristic search for a temporal plan, we construct and solve a Constraint Satisfaction Problem (CSP) and integrate feedback from the CP-based scheduler to guide the causal planning search towards a solution. Through experimental analysis, we validate the impact of these advances, demonstrating a significant reduction in both the number of states searched and in search time alongside an increase in problem-solving coverage.

M3 - Conference paper

BT - Proceedings of the Thirtieth Conference on Principles and Practice of Constraint Programming CP 2024

PB - Springer Berlin Heidelberg

CY - Lecture Notes in Computer Science

ER -