"uuid","repository link","title","author","contributor","publication year","abstract","subject topic","language","publication type","publisher","isbn","issn","patent","patent status","bibliographic note","access restriction","embargo date","faculty","department","research group","programme","project","coordinates"
"uuid:e269bc49-9138-4a83-9077-e905c2881a29","http://resolver.tudelft.nl/uuid:e269bc49-9138-4a83-9077-e905c2881a29","Maintaining Partial Path Consistency in STNs under Event-Incremental Updates","Ten Thije, O.; Planken, L.R.; De Weerdt, M.M.","","2011","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.","","en","conference paper","University of Huddersfield","","","","","","","","Electrical Engineering, Mathematics and Computer Science","Software Computer Technology","","","",""
"uuid:43311872-65c0-484f-ad26-7ad712e624a2","http://resolver.tudelft.nl/uuid:43311872-65c0-484f-ad26-7ad712e624a2","Computing All-Pairs Shortest Paths by Leveraging Low Treewidth (extended abstract)","Planken, L.R.; De Weerdt, M.M.; Van der Krogt, R.","","2011","","","en","conference paper","","","","","","","","","Electrical Engineering, Mathematics and Computer Science","Software Computer Technology","","","",""
"uuid:3ca1a60e-8de4-4207-93aa-27e1442ecc18","http://resolver.tudelft.nl/uuid:3ca1a60e-8de4-4207-93aa-27e1442ecc18","Incrementally Solving STNs by Enforcing Partial Path Consistency","Planken, L.R.; De Weerdt, M.M.; Yorke-Smith, N.","","2010","Efficient management and propagation of temporal constraints is important for temporal planning as well as for scheduling. During plan development, new events and temporal constraints are added and existing constraints may be tightened; the consistency of the whole temporal network is frequently checked; and results of constraint propagation guide further search. Recent work shows that enforcing partial path consistency provides an efficient means of propagating temporal information for the popular Simple Temporal Network (STN). We show that partial path consistency can be enforced incrementally, thus exploiting the similarities of the constraint network between subsequent edge tightenings. We prove that the worst-case time complexity of our algorithm can be bounded both by the number of edges in the chordal graph (which is better than the previous bound of the number of vertices squared), and by the degree of the chordal graph times the number of vertices incident on updated edges. We show that for many sparse graphs, the latter bound is better than that of the previously best-known approaches. In addition, our algorithm requires space only linear in the number of edges of the chordal graph, whereas earlier work uses space quadratic in the number of vertices. Finally, empirical results show that when incrementally solving sparse STNs, stemming from problems such as Hierarchical Task Network planning, our approach outperforms extant algorithms.","","en","conference paper","Association for the Advancement of Artificial Intelligence (AAAI)","","","","","","Campus only","","Electrical Engineering, Mathematics and Computer Science","Software Computer Technology","","","",""
"uuid:9b751b3e-7067-4df5-8b2a-2fe05e0c87b0","http://resolver.tudelft.nl/uuid:9b751b3e-7067-4df5-8b2a-2fe05e0c87b0","Optimal Temporal Decoupling in Multiagent Systems","Planken, L.R.; De Weerdt, M.M.; Witteveen, C.","","2010","When agents need to interact in order to solve some (possibly common) problem, resolving potential conflicts beforehand is often preferred to coordination during execution. Agents may lose some flexibility, but their course of action will be more predictable and often also more efficient, obtaining a socially optimal outcome instead of a local optimum. One way to resolve conflicts beforehand is to give extra constraints to each of the agents such that when they all meet these constraints, the resulting execution is conflictfree. A set of constraints that meets this requirement is called a decoupling of the original problem; if it also maximizes the social welfare (i.e. the sum of the valuations of all the agents), it is called optimal. Representing interesting multiagent problems as a constraint problem, we show that finding an optimal decoupling is at least as hard as finding a solution for the constraint problem. We therefore focus on a constraint problem that is efficiently solvable, but still very relevant and interesting in the context of multiple agents executing their actions, i.e. the Simple Temporal Problem (STP). Two more technical results, then, are that we resolve the open question whether finding an optimal decoupling of the STP is NP-hard (it is), and if all agents have linear valuation functions, this decoupling problem can be solved efficiently.","optimal decoupling; temporal decoupling problem","en","conference paper","International Foundation for Autonomous Agents and Multiagent Systems (IFAAMAS)","","","","","","","","Electrical Engineering, Mathematics and Computer Science","Software Computer Technology","","","",""
"uuid:34400dad-c8a1-4fe7-9ed9-98a4f7273710","http://resolver.tudelft.nl/uuid:34400dad-c8a1-4fe7-9ed9-98a4f7273710","P³C: A New Algorithm for the Simple Temporal Problem","Planken, L.; De Weerdt, M.M.; Van der Krogt, R.P.J.","","2008","The Simple Temporal Problem (STP) is a sub-problem of almost any planning or scheduling problem involving time constraints. An existing efficient method to solve the STP, called ?STP, is based on partial path consistency and starts from a chordal constraint graph. In this paper, we analyse this algorithm and show that there exist instances for which its time complexity is quadratic in the number of triangles in the constraint graph. We propose a new algorithm, P³C, whose worst-case time complexity is linear in the number of triangles. We show both formally and experimentally that P³C outperforms ?STP significantly.","","en","conference paper","Association for the Advancement of Artificial Intelligence (AAAI)","","","","","","Campus only","","Electrical Engineering, Mathematics and Computer Science","Software Computer Technology","","","",""