International audience

. Characteristics of the relation that links two or more variables of a constraint satisfaction problem can often be exploited to: reduce the computational burden of constraint propagation; avoid the instantiation of some auxiliary variables during the search for a solution; retain some flexibility in the ‘solution’, i.e. provide some specification for a set of solutions, rather than a unique solution to the problem under consideration; and provide a simpler explanationof the failure when it is proven that a given set of constraints conflict, i.e. cannot be simultaneously satisfied. The ability to test whether a subset of the constraints is consistent is important to determine which contraints conflict. This paper studies the particular cases of ordering, abstraction, and aggregation constraints. The consistency problem with both strict and non-strict inequalities is shown to be polynomial for totally ordered sets, but NP-hard in the case of partially ordered sets. The consistency problem for abstraction and aggregation relations is also shown to be NP-hard, and a particular polynomial case is proposed, with possible applications in design and configuration.

The goal of the GOFER project is to control the operation of many mobile robots in an indoor environment in order to automate a variety of tasks. This project raises many research issues: man-robot and robot-robot communication systems and protocols, implementation of non-conflicting sensor systems, task-adapted strategy in the use of sensors, sensor fusion, contingency-tolerant motion control, multi-robot motion planning, multi-robot task planning and scheduling. The purpose of the paper is to focus on the integration of software dealing with various aspects of the overall problem. The paper presents a general simulation tool designed to package such software, and to evaluate and compare methods that solve some of the specific problems mentioned above in an unpredictable environment.>

Task planning and scheduling techniques developed as part of a project whose goal is to control the operations of many robots in the same environment are presented. Centralized approaches allow task allocation to be improved. However, they are not appropriate for coordinating the actions of multiple mobile robots in a dynamic environment where unforeseeable events occur. Consequently, the author advocates a mixed strategy, allowing robots to make and execute individual plans as well as to connect with a central task planner and scheduler when appropriate. The author first presents individual planning techniques. Then he describes a framework allowing robots to exchange information with a central system able to optimize task allocation.>