François Charpillet

ICRA Conference 2023 Conference Paper

Holistic view of Inverse Optimal Control by introducing projections on singularity curves

• Jessica Colombel
• David Daney
• François Charpillet

Inverse optimal control (IOC) is a framework used in many fields, especially in robotics and human motion analysis. In this context, various methods of resolution have been proposed in the literature. This article presents Projected Inverse Optimal Control (PIOC), an approach that offers a simple and comprehensive view of IOC methods. Especially, we explain how uncertainties can be properly addressed in our view. Thus, this article highlights how classical methods can be understood as projections of trajectories in the solution space of the underlying Direct Optimal Control (DOC) problem. This perspective allows for an examination of projections other than the classical methods, which can be fruitful for researchers in the field. As an example, we propose a projection that allows us to choose the underlying cost functions of an IOC problem from a set. The IOC's sub-problems are also addressed, such as modelling observed trajectories, noise measurement and the reliability of solutions obtained by IOC. Our proposal is supported by a simple and canonical example throughout the document.

ICRA Conference 2022 Conference Paper

On the Reliability of Inverse Optimal Control

• Jessica Colombel
• David Daney
• François Charpillet

Inverse Optimal Control (IOC) is a popular method for human motion analysis. In the context of these methods it is necessary to pay attention to the reliability of the results. This paper proposes an approach based on the evaluation of Karush-Kuhn-Tucker conditions relying on a complete analysis with Singular Value Decomposition and provides a detailed analysis of reliability. With respect to a ground truth, our simulations illustrate how the proposed method analyzes the reliability of the resolution. After introducing a clear methodology, the properties of the matrices are studied with different noise levels and different experimental models and conditions. We show how to implement the method, step by step, by explaining the numerical difficulties encountered during the resolution and thus how to make the results of the IOC problem reliable.

IROS Conference 2016 Conference Paper

Localizing an intermittent and moving sound source using a mobile robot

• Quan V. Nguyen
• Francis Colas
• Emmanuel Vincent 0001
• François Charpillet

This paper addresses the problem of localizing and tracking one intermittent, moving sound source using a microphone array on a mobile robot. Robot motion provides a solution for estimating the distance to the source and avoiding front-back ambiguity. We propose a mixture Kalman filter (MKF) framework in order to fuse the robot motion information and the measurements taken at different poses of the robot. Experiments and statistical results demonstrate the ability of the proposed method to track one intermittent sound source in a reverberant environment where false measurements of the source angle of arrival (AoA) and the source activity often occur compared to a method that does not consider tracking source activity into account.

JAIR Journal 2016 Journal Article

Optimally Solving Dec-POMDPs as Continuous-State MDPs

• Jilles Steeve Dibangoye
• Christopher Amato
• Olivier Buffet
• François Charpillet

Decentralized partially observable Markov decision processes (Dec-POMDPs) provide a general model for decision-making under uncertainty in decentralized settings, but are difficult to solve optimally (NEXP-Complete). As a new way of solving these problems, we introduce the idea of transforming a Dec-POMDP into a continuous-state deterministic MDP with a piecewise-linear and convex value function. This approach makes use of the fact that planning can be accomplished in a centralized offline manner, while execution can still be decentralized. This new Dec-POMDP formulation, which we call an occupancy MDP, allows powerful POMDP and continuous-state MDP methods to be used for the first time. To provide scalability, we refine this approach by combining heuristic search and compact representations that exploit the structure present in multi-agent domains, without losing the ability to converge to an optimal solution. In particular, we introduce a feature-based heuristic search value iteration (FB-HSVI) algorithm that relies on feature-based compact representations, point-based updates and efficient action selection. A theoretical analysis demonstrates that FB-HSVI terminates in finite time with an optimal solution. We include an extensive empirical analysis using well-known benchmarks, thereby demonstrating that our approach provides significant scalability improvements compared to the state of the art.

ICRA Conference 2016 Conference Paper

Probabilistic sensor data processing for robot localization on load-sensing floors

• Maxime Rio
• Francis Colas
• Mihai Andries
• François Charpillet

Load-sensing floors are capable of tracking objects without suffering from occlusions nor posing the same privacy issues as cameras. They have been mostly used to analyze human gait as a way of continuous diagnosis but could also be placed alongside robots to help monitoring in specialized institutions, such as elderly care facilities. However, large-scale deployments necessitate cheap sensors which do not necessarily offer the same precision. With more noisy sensors, lighter robots might be difficult to track and precisely localize. In this article, we investigate various models in order to estimate the position of a robot. We experiment with several robots of different weights and compare the models' estimates against ground truth measurements provided by a motion capture system. We show that with standard-sized tiles of 60 cm, we can track even the lighter robots with less than 4 cm of error.

ICRA Conference 2015 Conference Paper

High resolution pressure sensing using sub-pixel shifts on low resolution load-sensing tiles

• Mihai Andries
• François Charpillet
• Olivier Simonin 0001

In ambient intelligence, pressure sensing can be used for detecting and recognizing objects based on their load profile. This paper presents a pressure scanning technique that improves weight-based object recognition, by adding information about the surface of the object in contact with the floor. The new high-resolution pressure scanning technique employs sub-pixel shifting to assemble a series of low-resolution scans into an aggregated high-resolution scan. The proposed scanning device is composed of 4 load-sensing tiles, on which the scanned object slides in regular movements. The result is a regular grid image of the object's contact surface, containing the weight of each section of the grid, as well as the corresponding centers of mass. A formal proof-of-concept is provided, together with experimental results obtained both on a noiseless simulated platform, and on a noisy physical platform.

IROS Conference 2015 Conference Paper

Multi-robot taboo-list exploration of unknown structured environments

• Mihai Andries
• François Charpillet

This paper presents a new taboo-list approach for multi-robot exploration of unknown structured environments, in which agents are implicitly guided in their navigation on a globally shared map. Agents have a local view of their environment, inside which they navigate in a asynchronous manner. When the exploration is complete, agents gather at a rendezvous point. The novelty consists in using a distributed exploration algorithm which is not guided by frontiers to perform this task. Using the Brick&Mortar Improved ant-algorithm as a base, we add robot-perspective vision, variable vision range, and an optimization which prevents agents from going to the rendezvous point before exploration is complete. The algorithm was evaluated in simulation on a set of standard maps.

IROS Conference 2015 Conference Paper

Pose estimation for a partially observable human body from RGB-D cameras

• Abdallah Dib
• François Charpillet

Human pose estimation in realistic world conditions raises multiple challenges such as foreground extraction, background update and occlusion by scene objects. Most of existing approaches were demonstrated in controlled environments.

EUMAS Conference 2014 Conference Paper

Comparison of Task-Allocation Algorithms in Frontier-Based Multi-robot Exploration

• Jan Faigl
• Olivier Simonin 0001
• François Charpillet

Abstract In this paper, we address the problem of efficient allocation of the navigational goals in the multi-robot exploration of unknown environment. Goal candidate locations are repeatedly determined during the exploration. Then, the assignment of the candidates to the robots is solved as the task-allocation problem. A more frequent decision-making may improve performance of the exploration, but in a practical deployment of the exploration strategies, the frequency depends on the computational complexity of the task-allocation algorithm and available computational resources. Therefore, we propose an evaluation framework to study exploration strategies independently on the available computational resources and we report a comparison of the selected task-allocation algorithms deployed in multi-robot exploration.

ICRA Conference 2014 Conference Paper

Decentralized near-to-near approach for vehicle platooning based on memorization and heuristic search

• Jano Yazbeck
• Alexis Scheuer
• François Charpillet

This paper deals with vehicle platooning, where a convoy aims at following closely and safely its leader's path without collision nor lateral deviation. In this paper, we propose a platooning algorithm based on a near-to-near decentralized approach. Each vehicle estimates and memorizes on-line the path of its predecessor as a set of points. After choosing a suitable position to aim for, the follower estimates on-line the predecessor's path curvature around the selected target. Then, based on a heuristic search, it computes an angular velocity using the estimated curvature. The optimization criteria used in this work allows the robot to follow its predecessor's path without oscillation while reducing the lateral and angular errors.

IROS Conference 2013 Conference Paper

Multi-robot exploration of unknown environments with identification of exploration completion and post-exploration rendezvous using ant algorithms

• Mihai Andries
• François Charpillet

This paper presents a new ant algorithm for the navigation of several robots, whose objective is to autonomously explore an unknown environment. When the coverage is completed, all robots move to a previously defined meeting point. The approach that we propose in this paper for solving this problem, considers that the robots build, while moving, a common and shared representation of the environment. In this representation, the environment is viewed as a graph (typically a set of connected cells in a regular grid), each grid cell having a local memory able to store a limited amount of data. A robot can write numbers on the cell on which it is lying. It can also read the values of the cells in its neighborhood, and perform some simple operations, such as computing the minimum of a set of values. Each robot is capable, contrary to most ant-based approaches, to determine, in a distributed way, when the environment coverage has completed. Few ant algorithms can do that. Brick&Mortar is one of them and this is why it retains a central place in our proposition. The novelty of our approach is that, due to an emerging property of the underlying algorithm, agents will finish their exploration at a predefined evacuation point. In addition, several improvements of the original Brick&Mortar algorithm are proposed in this paper, such as the possibility to use better local strategies at the robot level (using, for example, LRTA*). The paper also presents a set of benchmarks against the best existing ant algorithms on several widespread graph topologies.

IJCAI Conference 2013 Conference Paper

Optimally Solving Dec-POMDPs as Continuous-State MDPs

• Jilles Steeve Dibangoye
• Christopher Amato
• Olivier Buffet
• François Charpillet

Optimally solving decentralized partially observable Markov decision processes (Dec-POMDPs) is a hard combinatorial problem. Current algorithms search through the space of full histories for each agent. Because of the doubly exponential growth in the number of policies in this space as the planning horizon increases, these methods quickly become intractable. However, in real world problems, computing policies over the full history space is often unnecessary. True histories experienced by the agents often lie near a structured, low-dimensional manifold embedded into the history space. We show that by transforming a Dec-POMDP into a continuous-state MDP, we are able to find and exploit these low-dimensional representations. Using this novel transformation, we can then apply powerful techniques for solving POMDPs and continuous-state MDPs. By combining a general search algorithm and dimension reduction based on feature selection, we introduce a novel approach to optimally solve problems with significantly longer planning horizons than previous methods.

EWRL Workshop 2011 Conference Paper

Active Learning of MDP Models

• Mauricio Araya-López
• Olivier Buffet
• Vincent Thomas
• François Charpillet

Abstract We consider the active learning problem of inferring the transition model of a Markov Decision Process by acting and observing transitions. This is particularly useful when no reward function is a priori defined. Our proposal is to cast the active learning task as a utility maximization problem using Bayesian reinforcement learning with belief-dependent rewards. After presenting three possible performance criteria, we derive from them the belief-dependent rewards to be used in the decision-making process. As computing the optimal Bayesian value function is intractable for large horizons, we use a simple algorithm to approximately solve this optimization problem. Despite the sub-optimality of this technique, we show experimentally that our proposal is efficient in a number of domains.

IROS Conference 2011 Conference Paper

Improving near-to-near lateral control of platoons without communication

• Jano Yazbeck
• Alexis Scheuer
• Olivier Simonin 0001
• François Charpillet

This paper considers the platooning problem: we aim to steer a train of vehicles along an unknown path generated by the first vehicle, which is human driven. Among existing approaches, we study a decentralised local approach to avoid robustness issues due to communication failure which are common to centralised approaches. However, decentralised control rises up the problem of lateral deviation which is accumulated along the platoon.

UAI Conference 2010 Conference Paper

Distribution over Beliefs for Memory Bounded Dec-POMDP Planning

• Gabriel Corona
• François Charpillet

We propose a new point-based method for approximate planning in Dec-POMDP which outperforms the state-of-the-art approaches in terms of solution quality. It uses a heuristic estimation of the prior probability of beliefs to choose a bounded number of policy trees: this choice is formulated as a combinatorial optimisation problem minimising the error induced by pruning.

ICAART Conference 2009 Conference Paper

Intelligent Tiles - Putting Situated Multi-Agents Models in Real World

• Nicolas Pépin
• Olivier Simonin 0001
• François Charpillet

In this paper we propose to pave indoor floors with ``communicating'' tiles in order to extend perception and communication of mobile agents and more generally to implement environment-based multi-agent models. Each tile supports a real-time process which ensures communication with its neighbours and any agent laid on it. We details algorithms required for tiles to interact with mobile agents and to carry out distributed processes. Then we apply our approach to a behavior-based model, by splitting the model into the tiles and a simple agent. We show this new version is equivalent to the original one and so discuss its advantages.

ICRA Conference 2009 Conference Paper

Safe longitudinal platoons of vehicles without communication

• Alexis Scheuer
• Olivier Simonin 0001
• François Charpillet

This paper deals with the platooning problem that can be defined as the automatic following of a manned driven vehicle by a convoy of automatic ones. Different approaches have been proposed so far. Some require the localisation of each vehicle and a communication infrastructure, others called near-to-near approach only needs vehicle on-board sensors. However, to our knowledge, they do not provide any proof of non collision. We propose a novel near-to-near longitudinal platooning building a collision-free platooning whatever the number of vehicles. The model is derived from the study of the most dangerous interaction between two vehicles, i. e. considering the maximum acceptable acceleration when the previous vehicles brakes at maximum capacity. Collision avoidance of this model is proved. Finally, we show that this model can be combined to existing ones, keeping this collision-free property while allowing more various behaviors.

ICRA Conference 2008 Conference Paper

Obstacle detection and localization method based on 3D model: Distance validation with ladar

• Cindy Cappelle
• Maan E. El Najjar
• François Charpillet
• Denis Pomorski

This paper presents a method for the detection and the geo-localization of obstacle in outdoor environment. The proposed approach exploits a geographical 3D model managed by a 3D Geographical Information System (3D-GIS) and a video camera. An image processing module is developed to match synchronized real image and virtual image. The real image is provided by an on-board camera and gives the real view of the scene seen by the vehicle whereas the virtual image is provided by the 3D-GIS. A centimetric LRK GPS provides an estimation of the geo-position of the vehicle, which is used to localized the vehicle in the geographical 3D model. Obstacle(s) are then detected and tracked by comparison between the real image that contain the obstacle(s) and the virtual image where obstacle(s) are absent. The developed method permits also to compute the distance between the camera and obstacle(s), as well as the geo-position of these detected obstacles. In order to validate the computed distance, a 2D ladar (laser range scanner) is used. A necessary condition to complete the comparison is to calibrate the camera and the ladar together. Experimental results with real data are presented in the final section.

ECAI Conference 2008 Conference Paper

Theoretical Study of Ant-based Algorithms for Multi-Agent Patrolling

• Arnaud Glad
• Olivier Simonin 0001
• Olivier Buffet
• François Charpillet

This paper addresses the multi-agent patrolling problem, which consists for a set of autonomous agents to visit all the places of an unknown environment as regularly as possible. The proposed approach is based on the ant paradigm. Each agent can only mark and move according to its local perception of the environment. We study EVAW, a pheromone-based variant of the EVAP [3] and VAW [12]. The main novelty of the paper is the proof of some emergent spatial properties of the proposed algorithm. In particular we show that obtained cycles are necessarily of same length, which ensures an efficient spatial distribution of the agents. We also report some experimental results and discuss open questions concerning the proposed algorithm.

ICAPS Conference 2007 Conference Paper

Mixed Integer Linear Programming for Exact Finite-Horizon Planning in Decentralized Pomdps

• Raghav Aras
• Alain Dutech
• François Charpillet

We consider the problem of finding an n-agent joint-policy for the optimal finite-horizon control of a decentralized Pomdp (Dec-Pomdp). This is a problem of very high complexity (NEXP-hard in n ≥ 2). In this paper, we propose a new mathematical programming approach for the problem. Our approach is based on two ideas: First, we represent each agent's policy in the sequence-form and not in the tree-form, thereby obtaining a very compact representation of the set of joint-policies. Second, using this compact representation, we solve this problem as an instance of combinatorial optimization for which we formulate a mixed integer linear program (MILP). The optimal solution of the MILP directly yields an optimal joint-policy for the Dec-Pomdp. Computational experience shows that formulating and solving the MILP requires significantly less time to solve benchmark Dec-Pomdp problems than existing algorithms. For example, the multi-agent tiger problem for horizon 4 is solved in 72 secs with the MILP whereas existing algorithms require several hours to solve it.

JAAMAS Journal 2007 Journal Article

Shaping multi-agent systems with gradient reinforcement learning

• Olivier Buffet
• Alain Dutech
• François Charpillet

Abstract An original reinforcement learning (RL) methodology is proposed for the design of multi-agent systems. In the realistic setting of situated agents with local perception, the task of automatically building a coordinated system is of crucial importance. To that end, we design simple reactive agents in a decentralized way as independent learners. But to cope with the difficulties inherent to RL used in that framework, we have developed an incremental learning algorithm where agents face a sequence of progressively more complex tasks. We illustrate this general framework by computer experiments where agents have to coordinate to reach a global goal.

TAAS Journal 2006 Journal Article

A reactive agent-based problem-solving model

• Franck Gechter
• Vincent Chevrier
• François Charpillet

For two decades, multi-agent systems have been an attractive approach for problem solving and have been applied to a wide range of applications. Despite the lack of generic methodology, the reactive approach is interesting considering the properties it provides. This article presents a problem-solving model based on a swarm approach where agents interact using physics-inspired mechanisms. The initial problem and its constraints are represented through agents' environment, the dynamics of which is part of the problem-solving process. This model is then applied to localization and target tracking. Experiments assess our approach and compare it to widely-used classical algorithms.

UAI Conference 2005 Conference Paper

MAA*: A Heuristic Search Algorithm for Solving Decentralized POMDPs

• Daniel Szer
• François Charpillet
• Shlomo Zilberstein

We present multi-agent A* (MAA*), the first complete and optimal heuristic search algorithm for solving decentralized partially-observable Markov decision problems (DEC-POMDPs) with finite horizon. The algorithm is suitable for computing optimal plans for a cooperative group of agents that operate in a stochastic environment such as multirobot coordination, network traffic control, `or distributed resource allocation. Solving such problems efiectively is a major challenge in the area of planning under uncertainty. Our solution is based on a synthesis of classical heuristic search and decentralized control theory. Experimental results show that MAA* has significant advantages. We introduce an anytime variant of MAA* and conclude with a discussion of promising extensions such as an approach to solving infinite horizon problems.

IROS Conference 2005 Conference Paper

Meta-level control under uncertainty for handling multiple consumable resources of robots

• Simon Le Gloannec
• Abdel-Illah Mouaddib
• François Charpillet

Most of works on planning under uncertainty in AI assumes rather simple action models, which do not consider multiple resources. This assumption is not reasonable for many applications such as planetary rovers or robotics which cope with much uncertainty about the duration of tasks, the energy, and the data storage. In this paper, we outline an approach to control the operation of an autonomous rover which operates under multiple resource constraints. We consider a directed acyclic graph of progressive processing tasks with multiple resources, for which an optimal policy is obtained by solving a corresponding Markov decision process (MDP). Computing an optimal policy for an MDP with multiple resources makes the search space large. We cannot calculate this optimal policy at run-time. The approach developed in this paper overcomes this difficulty by combining: decomposition of a large MDP into smaller ones, compression of the state space by exploiting characteristics of the multiple resources constraint, construction of local policies for the decomposed MDPs using state space discretization and resource compression, and recomposition of the local policies to obtain a near optimal global policy. Finally, we present first experimental results showing the feasibility and performances of our approach.

ECAI Conference 2002 Conference Paper

Adaptive Combination of Behaviors in an Agent

• Olivier Buffet
• Alain Dutech
• François Charpillet

ICRA Conference 1998 Conference Paper

Mobile Robot Localization in Dynamic Environments using Places Recognition

• Olivier Aycard
• Pierre Laroche
• François Charpillet

We present a new method to localize a mobile robot in dynamic environments. This method is based on place recognition, and a match between places recognized and the sequence of places that the mobile robot is able to see during a run from an initial place to an ending place. Our method gives a coarse idea of the robot's position and orientation. Moreover, the robot can determine the actual state of places (i. e. open doors, closed doors).

IROS Conference 1997 Conference Paper

Place learning and recognition using hidden Markov models

• Olivier Aycard
• François Charpillet
• Dominique Fohr
• Jean-François Mari

In this paper, we propose a new method based on hidden Markov models to learn and recognize places in an indoor environment by a mobile robot. Hidden Markov models have been used for a long time in pattern recognition, especially in speech recognition. Their main advantages over other methods (e. g. neural networks) are their capabilities to modelize noisy temporal signals of variable length. We show in this paper that this approach is well adapted for learning and recognition of places by a mobile robot. Results of experiments on a real robot with five distinctive places are given.

ECAI Conference 1996 Conference Paper

Hopfield Neural Network for Scheduling Non Pre-emptive Tasks

• Jean-Michel Gallone
• François Charpillet

ECAI Conference 1992 Conference Paper

A Model for Hypothetical Reasoning Applied to Speech Recognition

• Anne Bonneau
• François Charpillet
• Sylvie Coste-Marquis
• Jean Paul Haton
• Yves Laprie
• Pierre Marquis

ECAI Conference 1992 Conference Paper

A Real Time Blackboard Based Architecture

• Philippe Lalanda
• François Charpillet
• Jean Paul Haton

ECAI Conference 1988 Conference Paper

ATOME: A Blackboard Architecture with Temporal and Hypothetical Reasoning

• H. Lâasri
• B. Maître
• T. Mondot
• François Charpillet
• Jean Paul Haton