Distributed decoupling of multiagent simple temporal problems

Abstract

Simple temporal networks (STNs) have become a popular tool for modelling the temporal space for a set of tasks during their execution by an agent. Formally, the problem concerning STNs can be viewed as a TCSP (Temporal Constraint Satisfaction Problem ) where an agent has a set of tasks to complete, subject to binary and unary constraints. The binary constraints couple pairs of time points (time points can represent start or end time for a task) in an affine manner while unary constraints associate with each time point an upper and lower bound for admissible values (representative of deadlines). STNs model the TCSP as a graph with the time points being the vertices and edges representing the constraint values. In real world settings, the value for each time point is either determined or merely observed by an agent. The effect of assignment of a value to a time point needs to be propagated through the graph for checking feasibility and updating the domains for the unassigned time points while execution. STN’s owe their popularity to efficient incremental algorithms for the propagation process.

The Multi-agent STN (MaSTN) is an extension to the STN machinery where each agent owns and maintains its own STN but also shares constraints with other agents. These constraints couple time points belonging to different agents which we refer as inter-agent constraints. While executing the MaSTN, agents need to communicate with each other during the propagation process. In many multi-agent settings, communication between agents may be unreliable or may have a high cost. In such settings, one reasonable strategy would be to cooperatively constrain time points participating in inter-agent constraints prior to execution at the cost of some loss in flexibility to the overall MaSTN, a process which is referred to as decoupling in literature. A decoupled MaSTN eliminates the need for communication between agents during execution and any propagation is limited to within an agent’s own STN. The challenge is to decouple the MaSTN in a distributed fashion without too much compromise of flexibility in agent schedules.

In this thesis, we propose a new distributed algorithm for decoupling the Multi-agent Simple Temporal Network (MaSTN) problem. The agents cooperatively decouple the MaSTN while simultaneously optimizing a sum of concave objectives local to each agent. Several schedule flexibility measures are applicable in this framework. We pose the MaSTN decoupling problem as a distributed convex optimization problem subject to constraints having a block angular structure; we adapt existing variants of Alternating Direction Method of Multipliers (ADMM) type methods to perform decoupling optimally. The resulting algorithm is an iterative procedure that is guaranteed to converge. Communication only takes place between agents with temporal inter-dependencies and the information exchanged between them is carried out in a privacy preserving manner. We present experimental results for the proposed method on problems of varying sizes, and demonstrate its effectiveness in terms of solving quality and computational cost. We then provide 2 extensions to our baseline algorithm and present their empirical performance. One of the algorithms aims at reducing the number of iterations for convergence while the other aims to compute decoupling quickly with bounds on the quality of the decoupling solution with respect to the optimal. We finally conclude by summarizing the contributions of this thesis and identify future directions of research.