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.

International audience

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.

The ability to automatically answer a request that requires the composition of a set of web services has received much interest in the last decade, as it supports B2B applications. It aims at selecting and inter-connecting services provided by differ

The establishment of a self-healing agent has received much interest in multiple domains such as : Web services, production supply chain, transport systems, etc. This agent has a set of actions. Its role is to respond to user request with a plan of composed actions, to on-line diagnose the status of the plan execution and to automatically repair the plan when a fault is detected during the plan's execution. To this end, three main areas are studied and modeled for the establishment of such an agent : composition, diagnosis and repair.

The ability to automatically answer a request that requires the composition of a set of web services has received much interest in the last decade, as it supports B2B applications. Planning techniques are used widely in the literature to describe the web services composition problem but they don't scale up well. This weakness is due to the search space explosion caused by the large ranges of data exchanged among services. In addition, it is more interesting to use a decentralised planner because the nature of the problem is distributed. In this paper, we consider a set of web service agents where each agent has a set of services organised in a graph. To respond to a request, agents propose their best local partial plans which are partial paths in the graph. They then coordinate their partial plans to provide the global plan for the submitted request using an algorithm based on a distributed heuristic function. This function ensures the optimality and the completeness of the algorithm. Indeed, it is based not only on the agent capabilities to respond to a request, but also taking into account the plans proposed by other agents. The complexity of the algorithm is polynomial. The experiments show the ability of our approach to find the optimal solutions for automated web services composition taking into account the dependencies betwen the agents.

An important number of planning approaches have been proposed to tackle the problem of Web services composition which aims at selecting and inter-connecting services provided by different partners in response to client request. This process is beyond the human ability to analyse and generate the composition manually. Planning techniques are used widely in the literature to automatically compose web services but they don't scale up well. This weakness is due to the search space explosion caused by using the state-space or the plan-space planning techniques without take into account the distribution nature of web services domain. In a previous work, we proposed a decentralised multi-agent approach to solve the problem by associating a planning agent to each web services. Agent organises its services in a graph and respond to requests by its best partial plan extracted basing on a local heuristic. This approach is complete if the agents are independant. In this paper, we extend our previous approach by introducing a global heuristic to ensure the completeness and the optimality of the decentralised approach even if agents are dependent. The complexity of the new distributed algorithm is polynomial. This global heuristic of evaluating the best local plan avoids the wells by considering the intermediate local plans offered by other agents. To respond to a request, agents propose their best local plans basing on a distributed heuristic function. They then coordinate their partial plans by merging them to provide a global one for the submitted request.

Automated composition of Web services has received much interest in the last decade, as it supports B2B applications. It aims at selecting and inter-connecting services provided by different partners in response to client requests. Planning techniques are used widely in the literature to describe Web services composition problem. However, since Web services proliferate day after day, classical planners are no longer well suited to compose Web services in a reasonable time. This weakness is due to the explosion of the search space caused by the large number of services and the broad range of data exchanged among services. In this paper, we propose a decentralised multi-agent approach to solve the Web services composition problem at runtime. Our model consists of a set of Web service agents where each agent has a set of services organised in a graph. Responding to a request, agents propose partial plans which are partial paths in the graph, then they coordinate their partial plans to provide the best global plan for the submitted request. The analysis of the complexity and results of the implementation show the ability of our approach to scale up when compared to the of state-of-the-art techniques for automated web service composition.

Real-life complex systems are often required to offer high reliability and quality of service and must be provided with self-management abilities, even in faulty situations. They are expected to be self-aware of their current state and survive autonomously the occurrence of faults, still managing to provide the desired functionality. In other words, such systems must be self-healing [2]. Designing self-healing systems requires to be able to evaluate the joint degree of self-awareness and reactiveness. In the artificial intelligence community, these two properties are better known as diagnosability [3, 1], i.e. the capability of a system to exhibit different observables for different anticipated faulty situations, and repairability, i.e. the ability of a system and its repair actions to cope with any unexpected situation. Checking separately diagnosability and repairability leads to a conservative assessement of self-healability. In this paper, we show that neither standard diagnosability nor repairability of every anticipated fault are necessary to achieve self-healability. Our main contribution consists of defining self-healability as a joint property bridging diagnosability and repairability, which requires a new definition of diagnosability that allows diagnosable subsets of faults to overlap, as opposed to the standard definitions which rely on a partition.

WS are distributed software components that can be exposed and invoked over the Internet using standard protocols. They communicate with their clients and with other WS by sending XML based messages over the Internet. AI planning techniques can help solving the composition of WS problem. In fact, services can be modelled as actions and the business process as planning to connect the WS. The main contribution of this paper is the extension of the model of actions to handle the creation or elimination of objects as effects of actions. This contribution allows us to answer to new and more expressive requests, called implicit requests, in which goals may contain objects that have been generated by the plan.

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.

In flexible manufacturing cells, scheduling has to take into account multiple cells in charge of distinct manufacturing orders sharing common flexible machines, and frequent disturbances must be accounted for efficiently. That suggests a multiagent model distributing decisions between manufacturing order agents and machine agents. The solving process is achieved by alternating infinite capacity scheduling processes performed by the former and several finite capacity scheduling processes performed by the latter. The resulting chronological greedy search is shown to be robust to sudden changes and is able to tackle overconstrained problems. To make the heuristics more effective, we add negotiation processes between manufacturing order agents through forward checking techniques inspired by the constraint-based scheduling community.

Temporal Constraint Networks (TCN) allow one to express minimal and maximal durations between time-points. Although 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 TCN based on the definition of the Simple Temporal Problem under Uncertainty (STPU) 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 iff 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 paper provides a full characterization of those properties and their usefulness in practice, and proposes algorithms for checking them. Complexity issues and tractable equivalence classes are only partially tackled, since it is still the topic of on-going work. All the same, hardness is discussed and argued, giving evidence for the general intractability of Dynamic controllability, which is the most commonly required property in domains such as planning or scheduling.

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.