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.

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.

The human driver is no longer the only one concerned with the complexity of the driving scenarios. Autonomous vehicles (AV) are similarly becoming involved in the process. Nowadays, the development of AV in urban places raises essential safety concerns for vulnerable road users (VRUs) such as pedestrians. Therefore, to make the roads safer, it is critical to classify and predict the pedestrians’ future behavior. In this paper, we present a framework based on multiple variations of the Transformer models able to predict the pedestrian street-crossing decision-making based on the dynamics of its initiated trajectory. We showed that using solely bounding boxes as input features can outperform the previous state-of-the-art results by reaching a prediction accuracy of 91% and an F1-score of 0.83 on the PIE dataset. In addition, we introduced a large-size simulated dataset (CP2A) using CARLA for action prediction. Our model has similarly reached high accuracy (91%) and F1-score (0.91) on this dataset. Interestingly, we showed that pre-training our Transformer model on the CP2A dataset and then fine-tuning it on the PIE dataset is beneficial for the action prediction task. Finally, our model’s results are successfully supported by the “human attention to bounding boxes” experiment which we created to test humans’ ability for pedestrian action prediction without the need for environmental context. The code for the dataset and the models is available at: https://github.com/ linaashaji/Action_Anticipation

Domestic robots and agents are widely sold to the grand public, leading us to ethical issues related to the data harvested by such machines. While users show a general acceptance of these robots, concerns remain when it comes to information security and privacy. Current research indicates that there’s a privacy-security trade-off for better use, but the anthropomorphic and social abilities of a robot are also known to modulate its acceptance and use. To explore and deepen what literature already brought on the subject we examined how users perceived their robot (Replika, Roomba©, Amazon Echo©, Google Home©, or Cozmo©/Vector©) through an online questionnaire exploring acceptance, perceived privacy and security, anthropomorphism, disclosure, perceived intimacy, and loneliness. The results supported the literature regarding the potential manipulative effects of robot’s anthropomorphism for acceptance but also information disclosure, perceived intimacy, security, and privacy.

Early detection of frailty signs is important for the senior population that prefers to keep living in their homes instead of moving to a nursing home. Sleep quality is a good predictor for frailty monitoring. Thus we are interested in tracking sleep parameters like sleep wake patterns to predict and detect potential sleep disturbances of the monitored senior residents. We use an unsupervised inference method based on actigraphy data generated by ambient motion sensors scattered around the senior's apartment. This enables our monitoring solution to be flexible and robust to the different types of housings it can equip while still attaining accuracy of 0.94 for sleep period estimates.

In this paper, we propose a new local descriptor for action recognition in depth images. Our proposed descriptor jointly encodes the shape and motion cues using surface normals in 4D space of depth, time, spatial coordinates and higher-order partial derivatives of depth values along spatial coordinates. In a traditional Bag-of-words (BoW) approach, local descriptors extracted from a depth sequence are encoded to form a global representation of the sequence. In our approach, local descriptors are encoded using Sparse Coding (SC) and Fisher Vector (FV), which have been recently proven effective for action recognition. Action recognition is then simply performed using a linear SVM classifier. Our proposed action descriptor is evaluated on two public benchmark datasets, MSRAction3D and MSRGesture3D. The experimental result shows the effectiveness of the proposed method on both the datasets.

In this paper, we propose a new local descriptor for action recognition in depth images. The proposed descriptor relies on surface normals in 4D space of depth, time, spatial coordinates and higher-order partial derivatives of depth values along spatial coordinates. In order to classify actions, we follow the traditional Bag-of-words (BoW) approach, and propose two encoding methods termed Multi-Scale Fisher Vector (MSFV) and Temporal Sparse Coding based Fisher Vector Coding (TSCFVC) to form global representations of depth sequences. The high-dimensional action descriptors resulted from the two encoding methods are fed to a linear SVM for efficient action classification. Our proposed methods are evaluated on two public benchmark datasets, MSRAction3D and MSRGesture3D. The experimental result shows the effectiveness of the proposed methods on both the datasets.

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.

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.

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.

We propose a novel innovation marking method for Neuro-Evolution of Augmenting Topologies in Embodied Evolutionary Robotics. This method does not rely on a centralized clock, which makes it well suited for the decentralized nature of EE where no central evolutionary process governs the adaptation of a team of robots exchanging messages locally.

We consider the task of audio source localization using a microphone array on a mobile robot. Active localization algorithms have been proposed in the literature that can estimate the 3D position of a source by fusing the measurements taken for different poses of the robot. The robot movements are typically fixed, however, or they obey heuristic strategies, such as turning the head and moving towards the source, which may be suboptimal. In this paper, we propose to control the robot movements so as to locate the source as quickly as possible. We represent the belief about the source position by a discrete grid and we introduce a dynamic programming algorithm to find the optimal robot motion minimizing the entropy of the grid. We report initial results in a real environment.

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.

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.

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. In this paper, we propose a framework to improve the performance of existing tracking methods to cope with these problems. To this end, a robust and scalable framework is provided composed of three main stages. In the first one, a probabilistic occupancy grid updated with a Hidden Markov Model used to maintain an up-to-date background and to extract moving persons. The second stage uses component labelling to identify and track persons in the scene. The last stage uses an hierarchical particle filter to estimate the body pose for each moving person. Occlusions are handled by querying the occupancy grid to identify hidden body parts so that they can be discarded from the pose estimation process. We provide a parallel implementation that runs on CPU and GPU at 4 frames per second. We also validate the approach on our own dataset that consists of synchronized motion capture with a single RGB-D camera data of a person performing actions in challenging situations with severe occlusions generated by scene objects. We make this dataset available online.

In this paper, we study the impact of selection methods in the context of on-line on-board distributed evolutionary algorithms. We propose a variant of the mEDEA algorithm in which we add a selection operator, and we apply it in a taskdriven scenario. We evaluate four selection methods that induce different intensity of selection pressure in a multi-robot navigation with obstacle avoidance task and a collective foraging task. Experiments show that a small intensity of selection pressure is sufficient to rapidly obtain good performances on the tasks at hand. We introduce different measures to compare the selection methods, and show that the higher the selection pressure, the better the performances obtained, especially for the more challenging food foraging task.

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.

This article addresses the problem of computing a Voronoi diagram in a distributed fashion without any synchronization heuristic. To our knowledge, no previous work asynchronously solves this problem. We investigate a simple case of a synchronism and tackle this challenge in a decentralized fashion on a grid of communicating cells with a von Neumann neighborhood. We describe algorithms for extracting single site, area and pseudo line Voronoi diagrams. These algorithms are implemented and executed on maps in which we consider different kinds of sites defined as simple polygonal shapes to extract roadmaps.

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.

This work is related to the development of a marker less system allowing the tracking of elderly people at home. Microsoft Kinect is a low cost 3D camera adapted to the tracking of human movements. We propose a method for making the fusion of the information provided by several Kinects. The observed space is tesselated into cells forming a 3D occupancy grid. We calculate a probability of occupation for each cell of the grid. From this probability we distinguish whether the cells are occupied or not by a static object (wall) or a mobile object (chair, human being). This categorization is realized in real-time using a simple three states HMM. The proposed method for discriminating between mobile and static objects in a room is the main contribution of this paper. The use of HMMs allows to deal with an aliasing problem since mobile objects result in the same observation as static objects. The approach is evaluated in simulation and in a real environment showing an efficient real-time discrimination between cells occupied by mobile objects and cells occupied by static objects.

In this paper we propose a new experimental device for defining and studying self-organized systems, especially those including physical or chemical interactions such as those encountered in collective natural phenomena. We want to be able to reproduce with real robots several paradigms such as stigmergy. In these phenomena the environment stores, diffuses, evaporates chemical substances (pheromones) that drive the behavior of each entity. The proposed device is a smart surface which relies on a graphical environment on top of which robots can move but also read/write information thanks colorimetric sensors and infrared emitters. The surface itself is able to perform some computation, implementing e.g. diffusion/evaporation mechanisms. More generally, the proposed robotic system allows to re-examine theoretical/simulated models in the perspective of defining self-organized robots. We consider in this paper the foraging problem as a case study. In particular we re-examine the expression of the model proposed by Drogoul&Ferber to implement pheromone-based exploration and transport with robots. We then analyze self-organized behaviors, as emergence of chains of robots, and their robustness.

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.

The difficulties encountered in sequential decision-making problems under uncertainty are often linked to the large size of the state space. Exploiting the structure of the problem, for example by employing a factored representation, is usually an efficient approach but, in the case of partially observable Markov decision processes, the fact that some state variables may be visible has not been sufficiently appreciated. In this article, we present a complementary analysis and discussion about MOMDPs, a formalism that exploits the fact that the state space may be factored in one visible part and one hidden part. Starting from a POMDP description, we dig into the structure of the belief update, value function, and the consequences in value iteration, specifically how classical algorithms can be adapted to this factorization, and demonstrate the resulting benefits through an empirical evaluation.

We present a markerless human motion capture system that estimates the 3D positions of the body joints over time. The system uses a dynamic bayesian network and a factored particle filtering algorithm. In this paper we evaluate the impact of using different observation functions for the bayesian state estimation: chamfer distance, a pixel intersection and finally a pseudo-observation of the subject direction calculated from the previous output of the system. We also compare two methods for the factored generation of the particles. The first one uses a deterministic interval exploration strategy whereas the second one is based on an adaptive diffusion. The capacity of the system to recover after occlusion by obstacles was tested on simulated movements in a virtual scene.

Partially Observable Markov Decision Processes (POMDPs) model sequential decision-making problems under uncertainty and partial observability. Unfortunately, some problems cannot be modeled with state-dependent reward functions, e.g., problems whose objective explicitly implies reducing the uncertainty on the state. To that end, we introduce rho-POMDPs, an extension of POMDPs where the reward function rho depends on the belief state. We show that, under the common assumption that rho is convex, the value function is also convex, what makes it possible to (1) approximate rho arbitrarily well with a piecewise linear and convex (PWLC) function, and (2) use state-of-the-art exact or approximate solving algorithms with limited changes.

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.

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.

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.

This paper deals with the multi-agent patrolling problem in unknown environment using two collective approaches exploiting environmental dynamics. After specifying criteria of performances, we define a first algorithm based only on the evaporation of a pheromone dropped by reactive agents (EVAP). Then we present the model CLInG [10] proposed in 2003 which introduces the diffusion of the idleness of areas to visit. We systematically compare by simulations the performances of these two models on growing- complexity environments. The analysis is supplemented by a comparison with the theoretical optimum performances, allowing to identify topologies for which methods are the most adapted.

This paper presents a multi-sensor fusion strategy for a novel road-matching method designed to support real-time navigational features within advanced driving-assistance systems. Managing multi- hypotheses is a useful strategy for the road-matching problem. The multi-sensor fusion and multi-modal estimation are realized using Dynamical Bayesian Network. Experimental results, using data from Anti- lock Braking System (ABS) sensors, a differential Global Positioning System (GPS) receiver and an accurate digital roadmap, illustrate the performances of this approach, especially in ambiguous situations.

We propose a formulation of a general-sum bimatrix game as a bipartite directed graph with the objective of establishing a correspondence between the set of the relevant structures of the graph (in particular elementary cycles) and the set of the Nash equilibria of the game. We show that finding the set of elementary cycles of the graph permits the computation of the set of equilibria. For games whose graphs have a sparse adjacency matrix, this serves as a good heuristic for computing the set of equilibria. The heuristic also allows the discarding of sections of the support space that do not yield any equilibrium, thus serving as a useful preprocessing step for algorithms that compute the equilibria through support enumeration

Pharmaceutic studies require to analyze thousands of ECGs in order to evaluate the side effects of a new drug. In this paper we present a new approach to automatic ECG segmentation based on hierarchic continuous density hidden Markov models. We applied a wavelet transform to the signals in order to highlight the discontinuities in the modeled ECGs. A training base of standard 12-lead ECGs segmented by cardiologists was used to evaluate the performance of our method. We used a Bayesian HMM clustering algorithm to partition the training base, and we improved the method by using a multi-model approach. We present a statistical analysis of the results where we compare different automatic methods to the segmentation of the cardiologist

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.

Telemedicine is a mean of facilitating the distribution of human resources and professional competences. It can speed up diagnosis and therapeutic care delivery and allow peripheral healthcare providers to receive continuous assistance from specialized centers. The need of specialized human resources becomes critical with the aging of the population. The treatment of renal failure is an example where telemedicine can help to increase care quality. Over the last decades Bayesian networks has become a popular representation for encoding uncertain expert knowledge. Dynamic Bayesian networks are an extension of Bayesian networks for modeling dynamic processes. We developed a dynamic Bayesian network adapted to the monitoring of the dry weight of patients suffering from chronic renal failure treated by hemodialysis. An experimentation conducted at dialysis units indicated that the system is reliable and gets the approbation of its users

In this paper we present a new approach for marker less human motion capture from conventional camera feeds. The aim of our study is to recover 3D positions of key points of the body that can serve for gait analysis. Our approach is based on foreground segmentation, an articulated body model and particle filters. In order to be generic and simple no restrictive dynamic modelling was used. A new modified particle filtering algorithm was introduced. It is used efficiently to search the model configuration space. This new algorithm which we call interval particle filtering reorganizes the configurations search space in an optimal deterministic way and proved to be efficient in tracking natural human movement. Results for human motion capture from a single camera are presented and compared to results obtained from a marker based system. The system proved to be able to track motion successfully even in partial occlusions

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.

In this paper, we describe how certain aspects of the biological phenomena of stigmergy can be imported into multiagent reinforcement learning (MARL), with the purpose of better enabling coordination of agent actions and speeding up learning. In particular, we detail how these stigmergic aspects can be used to define an inter-agent communication framework.

In this paper, we consider the problem of adapting the model of a diagnosis-helping module, which interacts with human experts. The approach consists of enforcing strong semantics in the model, so that this interaction may be as intuitive as possible. When learning the model, the problem consists in respecting these semantics while learning with few data. We addressed this problem through a semisupervised gradient descent algorithm applied to partially observable Markov models with fuzzy observations. This method optimizes several criteria at once, guiding the search to a compromise between the expert's directives and objective evaluations. This method has been successfully applied to a tele-medicine application where the system monitors dialyzed patients and alerts nephrologists.

Localization and target-tracking are both difficult yet essential and wide spread tasks in mobile robotics. Localization can be defined as determining the position of an object within a reference coordinate system, tracking consists of constructing a trajectory given a collection of spatially and temporally coherent localizations. We propose A swarm approach to address these issues using an interaction paradigm inspired from physics. The combination of different interactions such as attraction, repulsion, consumption and evaporation results in a self-organized process that builds patterns interpreted as solutions of the problem. After a description of the proposed model, This work analyses the properties and the performance of our device through experiments in simulation and with real robots. In particular, a comparison with the standard Kalman filtering method demonstrates the relevancy of our approach. Moreover, it improves upon traditional ones int terms of robustness, adaptability, and data fusion capabilities.

We present a new algorithm for cooperative reinforcement learning in multiagent systems. We consider autonomous and independently learning agents, and we seek to obtain an optimal solution for the team as a whole while keeping the learning as much decentralized as possible. Coordination between agents occurs through communication, namely the mutual notification algorithm. We define the learning problem as a decentralized process using the MDP formalism. We then give an optimality criterion and prove the convergence of the algorithm for deterministic environments. We introduce variable and hierarchical communication strategies which considerably reduce the number of communications. Finally we study the convergence properties and communication overhead on a small example.

Making heterogeneous agents cooperate is still an open problem. We have studied the interaction between a human agent and an information service agent. Our approach is to introduce a mediator agent to formalize the requests of the users, according to their profile and then to give the relevant answers. The mediator must find the best mediation strategy (a sequence of interactions) with a Markov decision process (MDP). The states are built on an attribute based referential and the capacity of the source to answer the request under formalization. The actions allow to ask questions to the user or to probe the information source. The rewards reflect the satisfaction of the user, the length of the mediation and the quantity of results. Our prototype uses reinforcement learning (Q-learning) for an on-line adaptation without requiring an a priori model. We describe our experiments on a flight information service with a simulated behaviour.

Solving multiagent reinforcement learning problems is a key issue. Indeed, the complexity of deriving multiagent plans, especially when one uses an explicit model of the problem, is dramatically increasing with the number of agents. This papers introduces a general iterative heuristic: at each step one chooses a sub-group of agents and update their policies to optimize the task given the rest of agents have fixed plans. We analyse this process in a general purpose and show how it can be applied to Markov decision processes, partially observable Markov decision processes and decentralized partially observable Markov decision processes.

Presents a vision-based localisation system for a mobile robot that uses a representative set of images obtained during an initial exploration of the environment. This set of images makes it possible to represent the environment as a partially Markov decision process. The originality of this approach is the resulting data fusion process that uses both image matching and the decisions made by the robot in order to estimate the set of plausible positions of the robot and the associated probabilities. Image matching or recognition is achieved using principal components analysis.

Markov decision processes have been successfully used in robotics for indoor robot navigation problems. They allow the computation of optimal sequences of actions in order to achieve a given goal, accounting for actuator uncertainties. However, MDPs are unsatisfactory at avoiding unknown obstacles. On the other hand, reactive navigators are particularly adapted to that, and don't need any prior knowledge about the environment, but they are unable to plan the set of actions that will permit the realization of a given mission. We present a new state aggregation technique for Markov decision processes, such that part of the work usually dedicated to the planner is achieved by a reactive navigator. Thus some characteristics of our environments, such as the width of corridors, have not been considered, which allows to cluster states together, significantly reducing the state space. As a consequence, policies are computed faster and are shown to be at least as efficient as optimal ones.

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).

Second order hidden Markov models have been used for a long time in pattern recognition, especially in speech recognition. Their main advantages over other methods (neural networks etc.) are their capabilities of modeling noisy temporal signals of variable length. In a previous work, we proposed a new method based on second order hidden Markov models to learn and recognize places in an indoor environment by a mobile robot, and showed that this approach is well suited for learning and recognizing places. In this paper, we propose major modifications to increase the global rate of place recognition. Results of experiments on a real robot with distinctive places are given.

Scheduling techniques have been intensively studied by several research communities and have been applied to a wide range of applications in computer and manufacturing environments. Most of the scheduling problems are NP-hard. Therefore, heuristics and approximation algorithms must be used for large problems. Obviously these methods are of interest when they provide near optimal solutions and when computational complexity can be controlled. For this purpose, we have developed a method based on the Hopfield neural network model. This approach permits us to solve in an iterative way a scheduling problem, finding a solution through the minimization of an energy function. An interesting property of this approach is its capacity to trade-off the quality for computation time. Indeed, the convergence speed of the minimization process can be tuned by adapting several parameters that influence the quality of the results. By tuning these parameters, we can build a library of a set of run-time executions (contracts) of the Hopfield minimization process with different characteristics (quality, efficiency). We present two applications exploiting the advantage of having available anytime contract algorithms. The first application illustrates how to build a solution of a one machine scheduling problem within a delay that follows a stochastic distribution. The second application deals with unrelated parallel machine scheduling of non preemptive tasks.

In this paper we present two state aggregation methods used to build stochastic plans, modelling our environment with Markov decision processes. Classical methods used to compute stochastic plans are highly intractable for problems necessitating a large number of states, such as our robotics application. The use of aggregation techniques allows to reduce the number of states and our methods give nearly optimal plans in a significantly reduced time.

Guaranteed response time is one of the most important issues encountered in designing real time systems. The AI community has developed various approaches to solve this problem, e.g. anytime algorithms, approximate processing, design to time scheduling and progressive reasoning. All these approaches rely on a trade-off between run time and quality of results. In the framework of the ESPRIT projects Nos. 5145 and 7805 REAKT (Real time Knowledge Tool), we have developed a similar approach called PROGRESS (PROGressive REasoning System). PROGRESS manages AI tasks with hard and soft deadlines, provided that competing methods are available for the tasks to be solved. A comparison was made between our model and a conventional algorithm (Earliest Deadline Algorithm) and showed the higher robustness and efficiency of PROGRESS.

Most scheduling problems are NP hard. Therefore, heuristics and approximation algorithms must be used for large problems when timing constraints have to be addressed. Obviously these methods are of interest when they provide near optimal solutions and when computational complexity can be controlled. The paper presents such a method based on Hopfield neural networks. Scheduling problems are solved in an iterative way, by finding a solution through the minimization of an energy function. An interesting property of this approach is its capacity to trade-off quality for computation time. Indeed, the convergence speed of the minimization process can be tuned by adapting several parameters that influence the quality of the results.

We present a multi agent architecture for controlling a mobile robot in an unpredictable environment. This architecture has been developed with the objective of coordinating the various competences of the robot (e.g., perception, navigation, planning). The architecture is made up of two agents: the first one specialized for cognitive tasks, the second one dedicated to control of the robot's physical devices. This two agent architecture guarantees a good robustness of the system, as the navigation modules can run independently of the cognitive ones.

International audience

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.

In previous work (J.-M. Gallone and F. Charpillet, 1996), we have studied the Hopfield artificial neural network model and its use for solving a particular scheduling problem: non preemptive tasks with release times, deadlines and computation times to be scheduled on several uniform machines. We presented an iterative approach based on Hopfield networks which enables resource bounded reasoning. We have validated our approach on a great number of randomly generated examples. Results are better than an efficient scheduling heuristics when no timing constraint exists and our system is able to adapt its behavior when timing constraints are imposed by the application. We extend this work by studying the incidence of two kinds of approximations on the processing time and on the success rate, so as to decide what sequence of activations for the contract will be likely to give the best success rate.

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.>

The problem of producing timely responses when faced with deadlines is an important issue for real-time systems. To deal with this problem different kinds of scheduling algorithms have been developed within the real-time community. Unfortunately, these approaches fail when applied to knowledge based systems, mainly because AI techniques rely on time-consuming algorithms with unpredictable, or highly variable performances. To face this problem researchers in AI have introduced deliberative techniques that enable to adapt the way a task is working in function of the available time. For this purpose approximation algorithms of two kinds have been developed: iterative refinement and multiple methods. The model we propose in this paper, belongs to iterative refinement methods. The main advantage of our approach is the capability of designing iterative refinement methods using a general rule language.>

International audience

To deal with complex problems, many kinds of reasoning and representation techniques are needed. The cooperation between different reasoning models constitutes one of the objectives of second-generation systems. The need to mix temporal and hypothetical reasoning for qualitative simulation is highlighted. A system built around an ATMS, a TCP, and a model that reasons on orders of magnitude is proposed. This system relies on an extension of HEART (see C. Joubel and O. Raiman, 1990). A new method for making histories concise has been developed.>

A new temporal representation combining the notions of intervals, dates, and durations is presented. The manipulation of this representation is based on the notion of time map managers (TMMs) allowing both kinds of constraints, symbolic or numeric. These algorithms are a generalization of AC4, an optimal algorithm for arc-consistency, and can handle n-ary constraints.>

International audience