Thierry Vidal

AAMAS Conference 2026 Conference Paper

Centralized and Distributed approaches for restoring the Weak Controllability of Multi-Agent Interdependent STNUs

• Ajdin SUMIC
• Thierry Vidal
• Gauthier Picard
• Frédéric Maris
• Roberto Posenato
• Carlo Combi

This paper models the negative cycles that cause uncontrollability in Multi-Agent Interdependent Simple Temporal Networks with Uncertainty (MISTNU) as linear constraints, enabling (1) a fast centralized linear-programming repair and (2) a novel distributed constraint-reasoningapproachthattreatsthosecyclesasinter-agent DCOP constraints, preserving privacy, with a performance comparison between distributed solvers and a centralized baseline.

I&C Journal 2026 Journal Article

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

• Ajdin SUMIC
• Thierry Vidal
• Andrea Micheli
• Alessandro Cimatti

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.

TIME Conference 2024 Conference Paper

A More Efficient and Informed Algorithm to Check Weak Controllability of Simple Temporal Networks with Uncertainty

• Aïdin Sumic
• Thierry Vidal

Simple Temporal Networks with Uncertainty (STNU) are a well-known constraint-based model expressing sets of activities (e. g. , a schedule or a plan) related by temporal constraints, each having possible durations in the form of convex intervals. Uncertainty comes from some of these durations being contingent, i. e. , the agent executing the plan cannot decide the actual duration at execution time. To check that execution will satisfy all the constraints, three levels of controllability exist: the Strong and Dynamic Controllability (SC/DC) has proven both useful in practice and provable in polynomial time, while Weak Controllability (WC) is co-NP-complete and has been left aside. Moreover, controllability checking algorithms are propagation strategies, which have the usual drawback, in case of failure, to prove unable to locate the contingents that explain the source of non-controllability. This paper has three contributions: (1) it substantiates the usefulness of WC in multi-agent systems (MAS) where another agent controls a contingent, and agents agree just before execution on the durations; (2) it provides a new WC-checking algorithm whose performance in practice depends on the network structure and is faster in loosely connected ones; (3) it provides the failing cycles in the network that explain non-WC.

TIME Conference 2024 Conference Paper

Introducing Interdependent Simple Temporal Networks with Uncertainty for Multi-Agent Temporal Planning

• Aïdin Sumic
• Thierry Vidal
• Andrea Micheli
• Alessandro Cimatti

Simple Temporal Networks with Uncertainty are a powerful and widely used formalism for representing and reasoning over convex temporal constraints in the presence of uncertainty called contingent constraints. Since their introduction, they have been used in planning and scheduling applications to model situations where the scheduling agent does not control some activity durations or event timings. What needs to be checked is then the controllability of the network, i. e. , that there is a valid execution strategy whatever the values of the contingents. This paper considers a new type of multi-agent extension, 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 will propose a semantically enriched version of STNUs that will be composed into a global Multi-agent Interdependent STNUs model. Then, controllability issues will be revisited, and we will focus on the repair problem, i. e. , how to regain failed controllability by shrinking some of the shared contract durations, here in a centralized manner.

ECAI Conference 2016 Conference Paper

Solving Dynamic Controllability Problem of Multi-Agent Plans with Uncertainty Using Mixed Integer Linear Programming

• Guillaume Casanova
• Cédric Pralet
• Charles Lesire
• Thierry Vidal

Executing multi-agent missions requires managing the uncertainty about uncontrollable events. When communications are intermittent, it additionally requires for each agent to act only based on its local view of the problem, that is independently of events which are controlled or observed by the other agents. In this paper, we propose a new framework for dealing with such contexts, with a focus on mission plans involving temporal constraints. This framework, called Multi-agent Simple Temporal Network with Uncertainty (MaSTNU), is a combination between Multi-agent Simple Temporal Network (MaSTN) and Simple Temporal Network with Uncertainty (STNU). We define the dynamic controllability property for MaSTNU, and a method for computing offline valid execution strategies which are then dispatched between agents. This method is based on a mixed-integer linear programming formulation and can also be used to optimize criteria such as the temporal flexibility of multi-agent plans.

ECAI Conference 2008 Conference Paper

Automated Web Services Composition Using Extended Representation of Planning Domain

• Mohamad El Falou
• Maroua Bouzid
• Abdel-Illah Mouaddib
• Thierry Vidal

ECAI Conference 2008 Conference Paper

Characterizing and checking self-healability

• Marie-Odile Cordier
• Yannick Pencolé
• Louise Travé-Massuyès
• Thierry Vidal

IJCAI Conference 2007 Conference Paper

• Julien Bidot
• Thierry Vidal
• Philippe Laborie
• J. Christopher Beck

There are many systems and techniques that address stochastic scheduling problems, based on distinct and sometimes opposite approaches, especially in terms of how scheduling and schedule execution are combined, and if and when knowledge about the uncertainties are taken into account. In many real-life problems, it appears that all these approaches are needed and should be combined, which to our knowledge has never been done. Hence it it first desirable to define a thorough classification of the techniques and systems, exhibiting relevant features: in this paper, we propose a tree-dimension typology that distinguishes between proactive, progressive, and revision techniques. Then a theoretical representation model integrating those three distinct approaches is defined. This model serves as a general template within which parameters can be tuned to implement a system that will fit specific application needs: we briefly introduce in this paper our first experimental prototypes which validate our model.

TIME Conference 2004 Invited Paper

The Many Ways of Facing Temporal Uncertainty in Planning and Scheduling

• Thierry Vidal

Generating off line a plan of activities before executing it on line is no longer realistic when one expects disturbances from an uncertain environment. Focusing on temporal plans and uncertain temporal constraints, we show that there are three main ways of tackling the issue: the reactive way, the proactive way and the progressive way, which are illustrated through existing models and systems. In realistic applications, one usually needs all of them, requiring a unified model. Such a model are introduced together with the first results of a modular system developed in the ILOG programming environment.

ICAPS Conference 2000 Conference Paper

A Unified Dynamic Approach for Dealing with Temporal Uncertainty and Conditional Planning

• Thierry Vidal

a decision-making processunderuncertainty, andconsi In temporal planning, TemporalConstraint Networks allow to check the temporal consistency of a plan, but es it has to be extended to deal with tasks which effecth tive duration is uncertain and will only be observed dy during execution. The Contingent TCNmodels it: in is whichDynamicontrollability has to be dmcked, i. e.: as during execution, will the system be able to consisfa tently release tasks accordingto the observeddurations kn of already completed tasks? This behaviour is a rere active one suggesting the plan is conditional in some gi sense. A Timed Game Automaton model has been on specifically designed to check the Dynamicontrollability. This paper furthermorediscusses the use of such ce a modelwith respect to conditional and reactive planco ning, and its strength with respect to execution superth vision needs, and suggests improvingefficiency by parsa titioning the plan into subparts~ introducing so-called pe waypointswith fixed time of occurrence. Last we show an that the expressive power of automata might allow Wa to address moreelaborate reactive planning features, such as preprocessed subplans, information gathering, or synchronizationconstraints. co Ti of Background and overview in

IJCAI Conference 1999 Conference Paper

Highly reactive decision making: a game with Time

• Silvia Coradeschi
• Thierry Vidal

Real-time monitoring calls for decision making capabilities in reaction to observed events. Associative models provide efficiency by matching the observed situation to a recorded pattern equipped with an accurate decision. We rely on a decision tree accounting for the context and temporal chronicles expressing dynamic patterns. In highly reactive domains, i. e. when actions get as frequent as observations, the decision must anticipate the complete recognition of a pattern, comparing possible evolutions. This paper focuses on the on-line decision process, a game against Nature in the general case: a timed game automaton gathers the possible next steps with associated goodness values, and uses an opportunistic algorithm to compute a temporally expressive decision, maximizing its utility, i. e. the chances of "winning".

TIME Conference 1998 Conference Paper

Accounting for Temporal Evolutions in Highly Reactive Decision-Making

• Silvia Coradeschi
• Thierry Vidal

Applications such as aircraft combat simulation require both dynamic supervision and real-time decision-making: actions and observations interact in a reactive way, and durations between two events must be accounted for. We start from a decision-tree model, which owns strong context handling capabilities, but provides only static decision-making. We improve it by matching possible temporal chronicles, accounting for dynamic evolutions, to the context. A decision in this framework is activated upon complete recognition of such a chronicle, whereas our highly reactive application domain requires anticipated decisions, comparing possible evolutions to take the best decision in real-time. We choose to dynamically compute a timed game automaton synthesizing the predicted possible next steps, and propose an algorithm that computes the best decision from this simple controller model.

TIME Conference 1997 Conference Paper

Contingent Durations in Temporal CSPs: From Consistency to Controllabilities

• Thierry Vidal
• Hélène Fargier

Temporal Constraint Networks (TCSP) allow to express minimal and maximal durations between time-points. Though being used in many research areas, this model disregards the contingent nature of some constraints, whose effective duration cannot be decided by the system but is provided by the external world. We propose an extension of TCSP in which the classical network consistency property must be redefined in terms of controllability: intuitively, we would like to say that a network is controllable if it is consistent in any situation (i. e. any assignment of the whole set of contingent intervals) that may arise in the external world. Three levels of controllability must be distinguished, namely the Strong, the Weak and the Dynamic ones. This preliminary report mainly stresses the representation and concept issues, discussing their relevance in dynamic application domains, and partially tackles the reasoning issues (complexity, algorithms and tractable subclasses).

ECAI Conference 1996 Conference Paper

Dealing with Uncertain Durations In Temporal Constraint Networks dedicated to Planning

• Thierry Vidal
• Malik Ghallab

ICRA Conference 1996 Conference Paper

Incremental mission allocation to a large team of robots

• Thierry Vidal
• Malik Ghallab
• Rachid Alami 0001

In the MARTHA project, a large number of robots in a harbour are given the global task of transporting containers from one area to another. The global decision-making process of allocating robots to those predefined tasks can be viewed as a scheduling and resource allocation problem, which is addressed here in a centralised way. Imprecision of temporal constraints makes it meaningless to search for a strict optimal schedule. The authors' approach interleaves task allocation and execution, scheduling in a sliding short-term horizon, as the execution process runs, and providing near-optimal solutions. For large applications the complexity of temporal management is a crucial issue. The authors present a graph decomposition technique, leading to nearly-constant time temporal propagation, without any loss of information.