Computing All-Pairs Shortest Paths by Leveraging Low Treewidth (extended abstract)

Incrementally Solving STNs by Enforcing Partial Path Consistency

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...

P³C: A New Algorithm for the Simple Temporal Problem

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...

Optimal Temporal Decoupling in Multiagent Systems

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...

Maintaining Partial Path Consistency in STNs under Event-Incremental Updates

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...