Automated planning is a field of Artificial Intelligence interested in finding a set of actions that drives the evolution of the environment from an initial state to a desired goal state. Much of the work of the community has been on so-called domain-independent planning where a solver is expected to produce a plan from an abstract problem, specified in a common description language. This has led the community to produce a number of highly-efficient solvers that can be expected to work on a large variety of domains without any fine-tuning. Where most of the work has focused on sequential plans over purely symbolic states, we instead propose a constraint-based planner whose focus is on more expressive variants, namely numeric and temporal planning, essential in many practical applications. We extend an existing CP encoding of temporal planning with support for optimization and numeric states and leverage an existing lazy clause generation CP solver to find and optimize plans. Where the most successful automated planners rely on some form of forward-search, we show that constraint-programming can be just as effective in finding satisfiable solutions while substantially improving the quality of the produced plans.

The Multi-Agent Path Finding with Task Assignment (MAPF-TA) problem combines task allocation and collision-free path finding for multiple agents within a graph. It can be solved by an extension of the well-known Conflict-Based Search (CBS) algorithm called CBS-TA, which has been demonstrated to be optimal in terms of the sum of costs of all agents. While coordination between agents in MAPF-TA is limited to no-collision constraints, real-world scenarios may require cooperation between agents. For instance, in an exploration mission involving a system of multiple robots, one robot might need to enter a hazardous area only if another agent is able to monitor this area from a support location. Given a hazardous location and its corresponding support location, this coordination requirement can be modeled by a support constraint. In this paper, we propose an extension of the CBS-TA algorithm to handle these support conflicts. In addition, we improve the algorithm’s performance by introducing an alternative cost matrix for task assignment, which takes into account support coordination while maintaining the optimality of the CBS-TA algorithm. We compare the proposed approach to a greedy algorithm in which the task assignment and path finding problems are decoupled, and using two different assignment matrices: the original matrix of CBS-TA and our support-aware matrix. Experiments are carried out using standard MAPF benchmark instances, showing that the proposed cost matrix improves search time and increases the number of instances solved within a given timeout.

This work presents a novel approach for the online supervision of robotic systems assembled from multiple complex components with skillset-based architectures, using Petri nets (PN). Predictive runtime verification is performed, which warns the system user about actions that would lead to the violation of safety specifications, using online model-checking tools on the system PNs.

Performing a complex autonomous mission with a multi-robot system requires to integrate several deliberative approaches to perform task allocation, optimization, and execution control. Implementing such a deliberative architecture is a complex task: it requires the developer to master the decision algorithms themselves (e.g., automated planning models), to have a good knowledge of the involved robotic platforms, and to think about how these elements will be assembled as a system architecture. We propose a framework to help designing such deliberative architectures. The framework relies on the concept of a hierarchical structure of actors, each actor managing goals with specific planning or optimization approaches, and delegating sub-goals to other actors.

In this paper, we study the effects of impaired communications on the performances of auction-based task allocation in a dynamic surveillance scenario. We propose a novel connectivity term to include in the bid valuation formula, that aims at improving communications in the multi-robot team. We evaluate our method as well as another state-of-the-art method using robot inter-distance to maintain communication, on randomly generated scenarios and on a real-world scenario. We demonstrate that including our connectivity term in the bid valuation formula improves the performances of the auction scheme.

We propose a decentralized approach that simultaneously allocates and decomposes high level tasks among various robots. The approach exploits HTN structures and algorithms, that are used within an auction-based allocation scheme, and aims at dealing with complex tasks with causal or temporal relations. The paper formalizes the approach, and depicts how HTN planning processes are used to estimate bids and distribute tasks. Results on a statistical series of coverage problems are presented and their performance is assessed through a comparison with a state of the art algorithm.

In this paper, we propose a formal language to specify robot skills, i.e. the elementary behaviours or functions provided by the robot platform in order to perform an autonomous mission. The advantage of the language we propose is that it integrates a wide range of elements that allows to define and provide automatic translation both to operational models, used online to control the skill execution, and descriptive models, allowing to reason about the expected skill execution, and then apply automated planning or model-checking taking skill models into account.

We consider a problem minimizing the total duration of accomplishing missions performed by heterogeneous vehicles. The problem respects constraints related to vehicles' capabilities and energy capacities. The goal is to determine the best routes of each vehicle deployed by choosing which waypoints to pass and which observations to perform. Each vehicle has a particular distance matrix and a limited energy. In order to provide high quality solutions within reasonable computational time, two decomposition-based approximate methods were implemented: (i) the Multiphase heuristic, and (ii) the Two-Phase iterative heuristic. The performance of the methods is evaluated against the Branch-and-Cut algorithm using generated instances.

Fault-tolerant architectures are mandatory to ensure the robustness of autonomous robots performing missions in complex and uncertain environments. The first step of a fault-tolerant mechanism is the detection of a faulty behavior of the system. It is then important to provide tools to help robot developers specify relevant observers. It is moreover crucial to guarantee a correct implementation of the observers, i.e. that the observers do not miss data and do not trigger unsuitable recovery actions in case of false detection. In this paper, we propose a specification language for observers that uses Past-Time LTL to express complex formulas on data produced by software components, and timed constraints on the evaluations of these formulas. We moreover provide an implementation of this specification that guarantees a real-time evaluation of the observers. We briefly describe the observers we have specified for a patrolling mission, and we evaluate the performance of our approach compared to state of the art on a benchmark in which we detect errors on a laser range sensor.

Field multi-robot missions face numerous unavoidable disturbances, such as delays in executing tasks and intermittent communications. Coping with such disturbances requires to endow the robots with high-level decision skills. We present a distributed decision architecture based first on a hybrid planner that can manage decentralized repairs with partial communication, and secondly on a distributed execution algorithm that efficiently propagates delays. This architecture has been successfully experimented on the field for the achievement of surveillance missions involving eight (8) real autonomous aerial and ground robots.

In the context of tree-search stochastic planning algorithms where a generative model is available, we consider on-line planning algorithms building trees in order to recommend an action. We investigate the question of avoiding re-planning in subsequent decision steps by directly using sub-trees as action recommender. Firstly, we propose a method for open loop control via a new algorithm taking the decision of re-planning or not at each time step based on an analysis of the statistics of the sub-tree. Secondly, we show that the probability of selecting a suboptimal action at any depth of the tree can be upper bounded and converges towards zero. Moreover, this upper bound decays in a logarithmic way between subsequent depths. This leads to a distinction between node-wise optimality and state-wise optimality. Finally, we empirically demonstrate that our method achieves a compromise between loss of performance and computational gain.

Acting systems aim at refining high-level actions into executable commands, while managing access to resources, possible failures, or any other unpredictable situation. Improving the trust on autonomous robots also requires to have a formal model of acting, and the capability to perform some analysis on this model. In this paper, we present ASPiC, an acting system based on the modeling of robot's skills using a specific control-flow Petri net model. The skills can then be combined using well-defined operators to build a complete plan that refines a high-level action. Some properties are guaranteed by construction, while others can be verified on the resulting plan model. ASPiC is finally applied to an area protection mission by an autonomous surface vehicle.

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.

Providing guarantees on the system behavior is mandatory in order to let the robots enter our every-day life. Among these guarantees, proving the fulfillment of real-time constraints on the software is a key issue, as their violation could result into unexpected and unsafe behaviors. In this paper, we present a methodology to guarantee real-time constraints on component-based software architectures of robots. This methodology relies on the MAUVE language to model the component architecture, and on a set of analysis tools that first estimate the worst case execution time of elementary functions from actual component traces, and then check the real-time constraints of each component. We illustrate this process on the architecture developed for the autonomous navigation of a partially known area by a mobile robot.

Nowadays dangerous, repetitive or precision requiring jobs are done by robots like flying drones, industrial assembly arms or medical assistants. In all these cases, human beings can interact with the machines, therefore it is essential to guarantee that every part of the robot's software and hardware will produce a safe behavior: both the overall behavior and the local behaviors of such embedded systems have to be carefully analyzed. The complexity of embedded systems software architectures increase with more and more tasks involved; state-machines are applied to implement more functional capabilities of the tasks; and the task models used in the analyses gain in complexity. The analysis techniques have to be adapted in order to face such new complexities. This paper focuses on the real-time analysis of state-machine-based software architectures. We propose a method to analyze the temporal behavior of a component-based architecture in which the components are described by state-machines. The method computes an accurate worst-case response time by taking into account the state-machines of the components. Finally, we validate our approach with a real real-time robotic case study.

This paper tackles high-level decision-making techniques for robotic missions, which involve both active sensing and symbolic goal reaching, under uncertain probabilistic environments and strong time constraints. Our case study is a POMDP model of an online multi-target detection and recognition mission by an autonomous UAV. The POMDP model of the multi-target detection and recognition problem is generated online from a list of areas of interest, which are automatically extracted at the beginning of the flight from a coarse-grained high altitude observation of the scene. The POMDP observation model relies on a statistical abstraction of an image processing algorithm's output used to detect targets. As the POMDP problem cannot be known and thus optimized before the beginning of the flight, our main contribution is an "optimize-while-execute" algorithmic framework: it drives a POMDP sub-planner to optimize and execute the POMDP policy in parallel under action duration constraints. We present new results from real outdoor flights and SAIL simulations, which highlight both the benefits of using POMDPs in multi-target detection and recognition missions, and of our "optimize-while-execute" paradigm.

This paper presents HiDDeN, a high-level distributed architecture for multi-robot cooperation. HiDDeN aims at controlling a team of heterogeneous robots in environments with uncertain communications. It relies on a mission plan defined as an instantiated HTN, i.e. a hierarchical decomposition of robots' tasks. This hierarchical structure also benefits to plan repair operations in case of failure detections. This repair is made as local as possible, in order to avoid unnecessary communications between robots.

Robotic missions require to implement various functionalities in order to link reactive functions at actuators and sensors level to deliberative functions like vision, supervision and planning at decisional level. All these functionalities must be versatile and generic enough to interact differently according to the missions while minimizing recoding effort. Moreover, deliberative functions like automated planning consume lots of memory and CPU time and usually complete in time incompatible with robotic missions' durations. Thus, we present a new generic and anytime planning concept for modular robotic architectures, which manages multiple planning requests at a time, solved in background, while allowing for reactive execution of planned actions at the same time. Different planners based on various formalisms and data structures can be plugged to the planning component without changing its behavior nor its code, facilitating reusability and validation of the component. We highlight the versatility of our concept on different use cases; then we demonstrate the efficiency of our approach in terms of mission duration and success, compared with traditional plan-then-execute approaches; we finally present a search and rescue mission by an autonomous rotorcraft solved with our paradigm, that cannot be tackled by traditional approaches.

Optimization of ground traffic is a major issue of air traffic management: optimal ground circulation could decrease flight delays and consequently decrease costs and increase passenger wellness. This paper proposes a planning algorithm for ground traffic based on contract reservation. This algorithm is iterative: it plans aircraft itinerary one after the other. A first version is described using the classical A* algorithm. Then the model is extended to deal with time and speed uncertainty to ensure the feasibility of the planned trajectories while avoiding conflicts between aircrafts. Its efficiency is evaluated on Toulouse-Blagnac airport, regarding quality of the solution and computation times.

Autonomous robots are complex systems that require the interaction/cooperation of numerous heterogeneous software components. Nowadays, robots are critical systems and must meet safety properties including in particular temporal and real-time constraints. We present a methodology for modeling and analyzing a robotic system using the BIP component framework integrated with an existing framework and architecture, the LAAS Architecture for Autonomous System, based on Geno