We study the problem of consistency checking for constraint networks over combined qualitative formalisms. We propose a framework which encompasses loose integrations and a form of spatio-temporal reasoning. In particular, we identify sufficient conditions ensuring the polynomiality of consistency checking, and we use them to find tractable subclasses.

Relying on the recently introduced multi-algebras, we present a general approach for reasoning about temporal sequences of qualitative information that is generally more efficient than existing techniques. Applying our approach to the specific case of sequences of topological information about constant-size regions, we show that the resulting formalism has a complete procedure for deciding consistency, and we identify its three maximal tractable subclasses containing all basic relations.

International audience

Due to the considerable increase of freely available data, the discovery of relevant information from textual content is a critical challenge. The work presented here takes part in ongoing researches to develop a global knowledge gathering system. It aims at building knowledge sheets summarizing all the pieces of information we know about events extracted from text. For this sake, we define a global process bringing together different methods and components from multiple domains of research.

Dealing with spatial knowledge requires the consistency of spatial information. This consistency is usually enforced by constraint satisfaction techniques including constraint propagation through arc and path consistency. While theses techniques often assume that spatial information are static, this is in general not the case in the real world. Our goal is to propose an approach to maintain the consistency of spatial knowledge in a dynamic environment. To our best knowledge no work in spatial reasoning has addressed this issue. In this paper we use a spatial ontology called Space Ontology to describe both objects and spatial relations namely topological and distance relations between these objects. Based on a dynamic path consistency algorithm, our proposed method maintains the consistency of spatial information after adding new instances of topological relations described by Space Ontology of a given environment. In order to evaluate the performance of our dynamic path consistency method, we conducted several tests on instantiations of Space Ontology in addition to randomly generated spatial constraint problems. The results of these tests demonstrate the efficiency of our method to deal with large size problems in a dynamic environment.

A* is the algorithm of finding the shortest path between two nodes in a graph. When the searching problem is constituted of a set of linked graphs, A* searches solution like if it is face of one graph formed by linked graphs. While researchers have developed solutions to reduce the execution time of A* in multiple cases by multiples techniques, we develop a new algorithm: DEC-A* which is a decentralized version of A* composing a solution through a collection of graph. A* uses a distance-plus-cost heuristic function to determine the order in which the search visits nodes in the tree. Our algorithm DEC-A* extends the evaluation of the distance-plus-cost heuristic to be the sum of two functions : local distance, which evaluates the cost to reach the nearest neighbor node s to the goal, and global distance which evaluates the cost from s to the goal through other graphs. DEC-A* reduces the time of finding the shortest path and reduces the complexity, while ensuring the privacy of graphs.

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.

In the last decade, there has been significant progress on Robotics. This development has widened the intervention fields of robots, particularly the assistance and interaction with humans. Improving the quality of this interaction requires robots to be endowed with representation and/or reasoning system for spatial knowledge. Our goal is to develop a planner allowing us to use human robot interaction to solve space sharing problems. This work is original, in that the representation of the same space for humans (symbolic, fuzzy) and robots (numeric) is not the same. Our objective is to combine human and robots representations of space in order to develop a mixed reasoning. We propose here an ontology called \textit{Space Ontology} as a spatial knowledge representation and reasoning system. In this paper, we focus on this ontology, and show how this type of knowledge can be profitably used for task planning. Our objective is to incorporate this ontology into a planner by extending the planning language PDDL.

Social networks and fast blogging services are interesting information sources. Anyone can contribute and submit information that matters to him/her. Among these many digital information sources, some appeared on the Internet as public means to be aware and to follow disasters and their evolutions. However, automatic raw information processing is more or less complex, error producer, relevant and reliable. This paper introduces a formal event modelisation extended with semantic properties to represent these information. We explain how to combine this extended model with reasoning methods on structured knowledge in order to discover unobvious relations hidden in information. Finally, we present a prototype based on this model and we discuss results returned by our experiments.

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.

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.

Unlike mono-agent systems, multi-agent planing addresses the problem of resolving conflicts between individual and group interests. In this paper, we are using a Decentralized Vector Valued Markov Decision Process (2V-DEC-MDP) in order to solve this problem. It uses an utility function which is returning a vector representing both individual and group interest. The individual interest of an agent, computed off-line, is based on its optimal policy. The group interest is computed on-line by the agents using their own local observations. In order to take into account both criteria in a decision process and to find a good trade-off between the group interest and the agent's one, we developed a regret-based algorithm based on the Tchebychev Norm.

This paper presents a new approach to multi-agent planning under temporal constraints and uncertainty of admissible operations. A planning problem in AI is usually specified as follows: given a description of the current state of some system, a set of actions that can be performed on the system and a description of a goal set of states for the system, find a sequence of actions that can be performed to transform the system into one of the goal states. The problem described in this paper is to find a way to reach a set of goals satisfying all specified constraints. By constraints, we mean temporal constraints and other constraints in the form of costs, number of agents, etc. Temporal constraints concern both qualitative and quantitative aspects of the system. We consider a set of agents, a set of goals and a description of the environment. The objective is, for one or more agents, to execute a set of tasks to satisfy all goals while respecting all the constraints. A planning procedure over AND-OR graphs is used to generate plans. The proposed multi-agent planning method is based on a centralized scheme in which all the coordination is done at a central location and the agents have no autonomy at the planning level. A specific feature of the task statement in this paper is that we aim at solving tasks of planning and scheduling, the complexity of which is conditioned by temporal and other constraints.

The paper describes a new approach to generating partially ordered plans with durative actions. Both cost and duration of any task is defined through probability distribution. We propose a planner that generates a plan represented in the form of a partially ordered set of tasks. Each task has a set of temporal constraints, a set of probabilities and a set of constant costs. The planning system generates admissible plans satisfying temporal constraints and allows to select the plan of lowest expected cost.

This paper defines a coordination process allowing hierarchical agents equipped with multiple methods to treat efficiently arriving tasks. The aim is to find an optimal (i.e. maximizing the utility of the result) combination of methods within the time window specified by the task. Agents are resource-limited and operate under time constraints. Agents (with their chosen methods) are used in sequential levels to progressively improve the quality of a task response

Specification and efficient handling of temporal knowledge is an important issue in design and implementation of contemporary information systems, such as databases, knowledge-based systems or decision support systems. This paper re-explores TUS, the time unit system being an algebraic tool for constructing simple yet powerful temporal specifications. In particular, an extended version of TUS, to be called XTUS is introduced and its basic operations and properties are shown

In this paper, we address the problem of the on-line transportation scheduling. Previous approaches use an off-line scheduling algorithm that accounts for new transportation tasks only when trucks are at a destination. To increase the performance of the system, we need to introduce the ability to account for the new transportation tasks immediately and to delegate it to a truck while this latter is moving toward a destination. For this purpose, the system needs to address two issues: (1) to determine the current location of the truck and its proximity to the departure and arrival of the new transportation task, and (2) to respect the temporal constraints. To this purpose, we use a space-time approach allowing us to deal with the first issue using a spatial reasoning, then address the second issue using a temporal reasoning. This approach is a first step towards a design of temporally situated multi-agent system that allows us to take location and the time of agents existing at this location to determine the suitable actions.

The paper is devoted to presentation of temporal causal networks (TCN) for representing and dealing with causal dependencies propagation over time. A temporal causal network is a causal network incorporating explicit representation of intervals of time during which its symptoms/nodes are valid, not valid, and unknown. The temporal knowledge is represented with use of the so called characteristic functions formalism, which allows for classical binary valued logic specification and can be easily extended towards multivalued or fuzzy logic. The presented approach makes use of specific time constraints propagation algorithm for determining causality propagation over the network in time. This is done by evaluating the characteristic functions used as means for representing time constraints for network nodes. The main application includes simulation, monitoring and elements of diagnostic reasoning for dynamic systems with explicit time representation.

Reasoning about time in presence of incomplete information is central in a wide range of artificial intelligence applications. For this purpose, time must be accounted for while reasoning about assumptions. To deal with the hypothetical dimension of inference, De Kleer's assumption-based truth maintenance approach proved valuable in many situations. However, it cannot handle temporally-qualified assertions. This paper contributes to fill the gap. It addresses the problem of performing assumption-based truth maintenance in a window-based temporal logic.>