Print Email Facebook Twitter Maintaining Partial Path Consistency in STNs under Event-Incremental Updates Title Maintaining Partial Path Consistency in STNs under Event-Incremental Updates Author Ten Thije, O. Planken, L.R. De Weerdt, M.M. Faculty Electrical Engineering, Mathematics and Computer Science Department Software Computer Technology Date 2011-12-08 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. To reference this document use: http://resolver.tudelft.nl/uuid:e269bc49-9138-4a83-9077-e905c2881a29 Publisher University of Huddersfield ISSN 1368-5708 Source PlanSIG 2011: Proceedings of the 29th Workshop of the UK Planning and Scheduling Special Interest Group, Huddersfield, UK, 8-9 December 2011 Part of collection Institutional Repository Document type conference paper Rights (c) 2011 The Author(s) Files PDF plansig11.pdf 566.32 KB Close viewer /islandora/object/uuid:e269bc49-9138-4a83-9077-e905c2881a29/datastream/OBJ/view