Maintaining Partial Path Consistency in STNs under Event-Incremental Updates

Conference paper (2011)
Department
Software Computer Technology (EEMCS) (TU Delft)
Copyright: © 2011 The Author(s)
More Info
expand_more

Published Date

08-12-2011

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Source:

PlanSIG 2011: Proceedings of the 29th Workshop of the UK Planning and Scheduling Special Interest Group, Huddersfield, UK, 8-9 December 2011

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Software Computer Technology

Abstract

Efficient management of temporal constraints is important for temporal planning. During plan development, many solvers employ a heuristic-driven backtracking approach, over the course of which they maintain a so-called Simple Temporal Network (STN) of events and constraints. This paper presents the Vertex-IPPC algorithm, which efficiently enforces partial path consistency when an STN is extended with an event and all its associated constraints. This algorithm uses some new results on directed path consistency on subgraphs. We prove that the worst-case time complexity of our algorithm is competitive with extant approaches. Our algorithm integrates well with a recently discovered vertex-incremental triangulation method, which, to the best of our knowledge, we are the first to have implemented. While experiments show that the new algorithm is outperformed on realistic networks, it is competitive on chordal graphs.

Files

Plansig11.pdf
(pdf | 0.553 Mb)
Unknown license