Multiple interdependent Simple Temporal Networks with Uncertainty: A semi-decentralized multi-agent model with shared control of activity durations

Simple Temporal Networks with Uncertainty are a powerful and widely used formalism for representing and reasoning over convex temporal constraints, when some of them are subject to uncertainty. Since their introduction, they have been used in planning and scheduling applications to model situations where some agent acting in the real world does not control some activity durations or event timings, which are called contingent constraints. Depending on when uncertainties are revealed, one needs now to check the Weak, Dynamic or Strong controllability of the network, i.e., that there is a valid execution strategy, whatever the values of the contingent constraints. This paper proposes for the first time a semantic characterization of the possible extensions to multi-agent settings and reviews previous approaches that tried to address such topics, in order to thoroughly introduce a new type of multi-agent collaborative model, where, as opposed to previous works, each agent manages its own separate STNU, and the control over activity durations is shared among the agents: what is called here a contract is a mutual constraint controllable for some agent and contingent for others. We introduce the cSTNU, a semantically enriched version of an STNU, a set of cSTNUs forming the global Multiple Interdependent STNUs model. Then, controllability issues are revisited, and a new problem called the Repair problem is introduced, which goal is to find how to regain failed controllability by shrinking some of the shared contract durations. In this paper, we also propose the very first SMT-based centralized algorithms that are able to solve both the Weak and Strong repair problems, supported by detailed experimentation with different SMT solvers. We finally discuss why that first approach remains limited in terms of scalability, and suggest some promising alternatives to design more effective methods, both paving the way towards a Dynamic repair solving method and distributed algorithms.