Current research in semantic bird's-eye view segmentation for autonomous driving focuses solely on optimizing neural network models using a single dataset, typically nuScenes. This practice leads to the development of highly specialized models that may fail when faced with different environments or sensor setups, a problem known as domain shift. In this paper, we conduct a comprehensive cross-dataset evaluation of state-of-the-art BEV segmentation models to assess their performance across different training and testing datasets and setups, as well as different semantic categories. We investigate the influence of different sensors, such as cameras and LiDAR, on the models' ability to generalize to diverse conditions and scenarios. Additionally, we conduct multi-dataset training experiments that improve models' BEV segmentation performance compared to single-dataset training. Our work addresses the gap in evaluating BEV segmentation models under cross-dataset validation. And our findings underscore the importance of enhancing model generalizability and adaptability to ensure more robust and reliable BEV segmentation approaches for autonomous driving applications. The code for this paper available at https: // github. com/ manueldiaz96/beval/.

In autonomous driving, addressing occlusion scenarios is crucial yet challenging. Robust surrounding perception is essential for handling occlusions and aiding navigation. State-of-the-art models fuse LiDAR and Camera data to produce impressive perception results, but detecting occluded objects remains challenging. In this paper, we emphasize the crucial role of temporal cues in reinforcing resilience against occlusions in the bird’s eye view (BEV) semantic grid segmentation task. We proposed a novel architecture that enables the processing of temporal multi-step inputs, where the input at each time step comprises the spatial information encoded from fusing LiDAR and camera sensor readings. We experimented on the real-world nuScenes dataset and our results outperformed other baselines, with particularly large differences when evaluating on occluded and partially-occluded vehicles. Additionally, we applied the proposed model to downstream tasks, such as multi-step BEV prediction and trajectory forecasting of the ego-vehicle. The qualitative results obtained from these tasks underscore the adaptability and effectiveness of our proposed approach.

Semantic grids can be useful representations of the scene around an autonomous system. By having information about the layout of the space around itself, a robot can leverage this type of representation for crucial tasks such as navigation or tracking. By fusing information from multiple sensors, robustness can be increased and the computational load for the task can be lowered, achieving real time performance. Our multi-scale LiDAR-Aided Perspective Transform network uses information available in point clouds to guide the projection of image features to a top-view representation, resulting in a relative improvement in the state of the art for semantic grid generation for human (+8.67%) and movable object (+49.07%) classes in the nuScenes dataset, as well as achieving results close to the state of the art for the vehicle, drivable area and walkway classes, while performing inference at 25 FPS.

Motion prediction is a challenging task for autonomous vehicles due to uncertainty in the sensor data, the non-deterministic nature of future, and complex behavior of agents. In this paper, we tackle this problem by representing the scene as dynamic occupancy grid maps (DOGMs), associating semantic labels to the occupied cells and incorporating map information. We propose a novel framework that combines deep-learning-based spatio-temporal and probabilistic approaches to predict vehicle behaviors. Contrary to the conventional OGM prediction methods, evaluation of our work is conducted against the ground truth annotations. We experiment and validate our results on real-world NuScenes dataset and show that our model shows superior ability to predict both static and dynamic vehicles compared to OGM predictions. Furthermore, we perform an ablation study and assess the role of semantic labels and map in the architecture.

With their progressive deployment in increasingly complex environments, autonomous vehicles will more often interact with humans in shared spaces. However proactive planners, the most effective for human-aware navigation, are rarely applicable with real-world constraints because of their inherent complexity. Meanwhile classical approaches fail to navigate in cooperation with humans in complex or crowded scenarios. Therefore we propose to extend a global kinodynamic predictive collision avoidance approach with an interaction-aware behavioral prediction model for human-vehicle interactions. Thanks to a grid based Bayesian perception, our approach is versatile in modeling uncertainty and complex scenes. We deploy this solution on a robotic car and show that it can be used in real-world applications. With a qualitative and quantitative validation, we show that this interaction-aware collision avoidance solution is safe and performs well in crowded scenarios. Less computationally demanding and more versatile than proactive planners but still able to benefit from cooperation with humans, this interaction-aware approach offers a compromise between predictive and proactive planners.

Simulation, a common practice to evaluate au-tonomous vehicles, requires to specify realistic scenarios, in par-ticular critical ones, occurring rarely and potentially dangerous to reproduce on the road. Such scenarios may be either generated randomly, or specified manually. Randomly generating scenarios is easy, but their relevance might be difficult to assess. Manually specified scenarios can focus on a given feature, but their design might be difficult and time-consuming, especially to achieve satisfactory coverage. In this work, we propose an automatic approach to generate a large number of relevant critical scenarios for autonomous driving simulators. The approach is based on the generation of behavioral conformance tests from a formal model (specifying the ground truth configuration with the range of vehicle behaviors) and a test purpose (specifying the critical feature to focus on). The obtained abstract test cases cover, by construction, all possible executions exercising a given feature, and can be automatically translated into the inputs of autonomous driving simulators. We illustrate our approach by generating thousands of behavior trees for the CARLA simulator for several realistic configurations.

Prediction of dynamic environment is crucial to safe navigation of an autonomous vehicle. Urban traffic scenes are particularly challenging to forecast due to complex interactions between various dynamic agents, such as vehicles and vulnerable road users. Previous approaches have used ego-centric occupancy grid maps to represent and predict dynamic environments. However, these predictions suffer from blurriness, loss of scene structure at turns, and vanishing of agents over longer prediction horizon. In this work, we propose a novel framework to make long-term predictions by representing the traffic scene in a fixed frame, referred as allo-centric occupancy grid. This allows for the static scene to remain fixed and to represent motion of the ego-vehicle on the grid like other agents'. We study the allo-centric grid prediction with different video prediction networks and validate the approach on the real-world Nuscenes dataset. The results demonstrate that the allo-centric grid representation significantly improves scene prediction, in comparison to the conventional ego-centric grid approach.

Semantic grids are a useful representation of the environment around a robot. They can be used in autonomous vehicles to concisely represent the scene around the car, capturing vital information for downstream tasks like navigation or collision assessment. Information from different sensors can be used to generate these grids. Some methods rely only on RGB images, whereas others choose to incorporate information from other sensors, such as radar or LiDAR. In this paper, we present an architecture that fuses LiDAR and camera information to generate semantic grids. By using the 3D information from a LiDAR point cloud, the LiDAR-Aided Perspective Transform Network (LAPTNet) is able to associate features in the camera plane to the bird's eye view without having to predict any depth information about the scene. Compared to state-of-the-art camera-only methods, LAPTNet achieves an improvement of up to 8.8 points (or 38.13%) over state-of-art competing approaches for the classes proposed in the NuScenes dataset validation split.

Accurate modeling of complex dynamic environments is a fundamental requirement in robotics and automotive applications. While grid-mapping approaches used to be limited to static settings, methods for dynamic occupancy grids have recently been developed, tracking spatial occupancy at a sub-object level, in every cell. In this paper, we present a generic dynamic occupancy grid tracker, which filters cell states and infers dynamics of the scene through the interaction of a grid-based and a particle-based model. These are set to represent different parts of the scene, and optimize particle allocation only to relevant areas, their predictions being fused accordingly. New hidden variables in the filtering process permit to address previously mishandled situations, like concurrent state predictions or specific filtering sensitivity. The presented method has been implemented, optimized on a GPU and tested on real-road conditions, embedded on an experimental vehicle.

Semantic grids are a succinct and convenient approach to represent the environment for mobile robotics and autonomous driving applications. While the use of Lidar sensors is now generalized in robotics, most semantic grid prediction approaches in the literature focus only on RGB data. In this paper, we present an approach for semantic grid prediction that uses a transformer architecture to fuse Lidar sensor data with RGB images from multiple cameras. Our proposed method, TransFuseGrid, first transforms both input streams into top-view embeddings, and then fuses these embeddings at multiple scales with Transformers. Finally, a decoder transforms the fused, top-view feature map into a semantic grid of the vehicle's environment. We evaluate the performance of our approach on the nuScenes dataset for the vehicle, drivable area, lane divider and walkway segmentation tasks. The results show that Trans-FuseGrid achieves superior performance than competing RGB-only and Lidar-only methods. Additionally, the Transformer feature fusion leads to a significative improvement over naive RGB-Lidar concatenation. In particular, for the segmentation of vehicles, our model outperforms state-of-the-art RGB-only and Lidar-only methods by 24% and 53%, respectively.

The ability to detect objects, under image corruptions and different weather conditions is vital for deep learning models especially when applied to real-world applications such as autonomous driving. Traditional RGB-based detection fails under these conditions and it is thus important to design a sensor suite that is redundant to failures of the primary frame-based detection. Event-based cameras can complement frame-based cameras in low-light conditions and high dynamic range scenarios that an autonomous vehicle can encounter during navigation. Accordingly, we propose a redundant sensor fusion model of event-based and frame-based cameras that is robust to common image corruptions. The method utilizes a voxel grid representation for events as input and proposes a two-parallel feature extractor network for frames and events. Our sensor fusion approach is more robust to corruptions by over 30% compared to only frame-based detections and outperforms the only event-based detection. The model is trained and evaluated on the publicly released DSEC dataset.

Testing and validating advanced automotive software is of paramount importance to guarantee safety and quality. While real-world testing is highly demanding and simulation testing is not reliable, we propose a new augmented reality framework that takes advantage of both environments. This new testing methodology is intended to be a bridge between Vehicle-in-the-Loop and real-world testing. It enables to easily and safely place the whole vehicle and all its software, from perception to control, in realistic test conditions. This framework provides a flexible way to introduce any virtual element in the outputs of the sensors of the vehicle under test. For each modality of sensing, the framework requires a real time augmentation function that preserves real sensor data and enhances them with virtual data. The LiDAR data augmentation function is presented together with its implementation details. Relying on both qualitative and quantitative analysis of experimental results, the representability of tests scenes generated by the augmented reality framework is finally proven.

Reliably predicting future occupancy of highly dynamic urban environments is an important precursor for safe autonomous navigation. Common challenges in the prediction include forecasting the relative position of other vehicles, modelling the dynamics of vehicles subjected to different traffic conditions, and vanishing surrounding objects. To tackle these challenges, we propose a spatio-temporal prediction network pipeline that takes the past information from the environment and semantic labels separately for generating future occupancy predictions. Compared to the current SOTA, our approach predicts occupancy for a longer horizon of 3 seconds and in a relatively complex environment from the nuScenes dataset. Our experimental results demonstrate the ability of spatiotemporal networks to understand scene dynamics without the need for HD-Maps and explicit modeling dynamic objects. We publicly release our occupancy grid dataset based on nuScenes to support further research.

Autonomous vehicles need information about their surroundings to safely navigate them. For this, the task of Panoptic Segmentation is proposed as a method of fully parsing the scene by assigning each pixel a label and instance id. Given the constraints of autonomous driving, this process needs to be done in a fast manner. In this paper, we propose the first panoptic segmentation network based on the YOLOv3 real-time object detection network by adding a semantic and instance segmentation branches. YOLO-panoptic is able to do real-time inference and achieves a performance similar to the state of the art methods in some metrics.

Detection of the objects around a vehicle is important for a safe and successful navigation of an autonomous vehicle. Instance segmentation provides a fine and accurate classification of the objects such as cars, trucks, pedestrians, etc. In this study, we propose a fast and accurate approach which can detect and segment the object instances which can be adapted to new conditions without requiring the labels from the new condition. Furthermore, the performance of the instance segmentation does not degrade in detection of the objects in the original condition after it adapts to the new condition. To our knowledge, currently there are not other methods which perform unsupervised domain adaptation for the task of instance segmentation using non-synthetic datasets. We evaluate the adaptation capability of our method on two datasets. Firstly, we test its capacity of adapting to a new domain; secondly, we test its ability to adapt to new weather conditions. The results show that it can adapt to new conditions with an improved accuracy while preserving the accuracy of the original condition.

Traditionally, point cloud-based 3D object detectors are trained on annotated, non-sequential samples taken from driving sequences (e.g. the KITTI dataset). However, by doing this, the developed algorithms renounce to exploit any dynamic information from the driving sequences. It is reasonable to think that this information, which is available at test time when deploying the models in the experimental vehicles, could have significant predictive potential for the object detection task. To study the advantages that this kind of information could provide, we construct a dataset of dynamic occupancy grid maps from the raw KITTI dataset and find the correspondence to each of the KITTI 3D object detection dataset samples. By training a Lidar-based state-of-the-art 3D object detector with and without the dynamic information we get insights into the predictive value of the dynamics. Our results show that having access to the environment dynamics improves by 27% the ability of the detection algorithm to predict the orientation of smaller obstacles such as pedestrians. Furthermore, the 3D and bird's eye view bounding box predictions for pedestrians in challenging cases also see a 7% improvement. Qualitatively speaking, the dynamics help with the detection of partially occluded and far-away obstacles. We illustrate this fact with numerous qualitative prediction results.

Perception systems on autonomous vehicles have the challenge of understanding the traffic scene in different situations. The fusion of redundant information obtained from different sources has been shown considerable progress under different methodologies to achieve this objective. However, new opportunities are available to obtain better fusion results with the advance of deep-learning models and computing hardware. In this paper, we aim to recognize moving objects in traffic scenes through the fusion of semantic information with occupancy-grid estimations. Our approach considers a deep-learning model with inference times between 22 to 55 milliseconds. Moreover, we use a Bayesian occupancy framework with a Highly-parallelized design to obtain the occupancy-grid estimations. We validate our approach using experimental results with real-world data on urban scenery.

Accurate and reliable localization is crucial to autonomous vehicle navigation and driver assistance systems. This paper presents a novel approach for online vehicle localization in a digital map. Two distinct map matching algorithms are proposed: i) Iterative Closest Point (ICP) based lane level map matching is performed with visual lane tracker and grid map ii) decision-rule based approach is used to perform topological map matching. Results of both the map matching algorithms are fused together with GPS and dead reckoning using Extended Kalman Filter to estimate vehicle's pose relative to the map. The proposed approach has been validated on real life conditions on an equipped vehicle. Detailed analysis of the experimental results show improved localization using the two aforementioned map matching algorithms.

Ground plane estimation and ground point segmentation is a crucial precursor for many applications in robotics and intelligent vehicles like navigable space detection and occupancy grid generation, 3D object detection, point cloud matching for localization and registration for mapping. In this paper, we present GndNet, a novel end-to-end approach that estimates the ground plane elevation information in a grid-based representation and segments the ground points simultaneously in real-time. GndNet uses PointNet and Pillar Feature Encoding network to extract features and regresses ground height for each cell of the grid. We augment the SemanticKITTI dataset to train our network. We demonstrate qualitative and quantitative evaluation of our results for ground elevation estimation and semantic segmentation of point cloud. GndNet establishes a new state-of-the-art, achieves a run-time of 55Hz for ground plane estimation and ground point segmentation.

Risk mitigation is an important element to consider in risk evaluation. Safety features have helped to decrease the death ratio over the years. However, to date, each driver assistance system works on a single domain of operation. The problem remains in how to use perception to contextualize the scene to fully minimize the collision severity in a complex emergency scenario. Up to now, works on cost maps have consider simple contextualized object in mitigation scenarios. For instance, the use of binary allowed/forbidden zones or, a fixed weight to each type of object in the scene. Our work employs the risk of injury issued by accidentology to each class of object present in the scene. Each class of object presents an injury probability with respect to the impact speed and ethical/economical/political factors. The method generates a cost map containing a collision probability along with to the risk of injury. It dynamically contextualizes the objects, since the risk of injury depends on the characteristics of the scene. Simulation and dataset results validate that changing the referred parameters alters the context and evaluation of the scene. Then, the proposed method allows a better assessment of the surroundings by creating a dynamic navigation cost map for complex scenarios.

A crucial aspect that automotive systems need to face before being used in everyday life is the validation of their components. To this end, standard exhaustive methods are inappropriate to validate the probabilistic algorithms widely used in this field and new solutions need to be adopted. In this paper, we present an approach based on Statistical Model Checking (SMC) to validate the collision risk assessment generated by a probabilistic perception system. SMC represents an intermediate between test and exhaustive verification by relying on statistics and evaluates the probability of meeting appropriate Key Performance Indicators (KPIs) based on a large number of simulations. As a case study, a state-of-the-art algorithm is adopted to obtain the collision risk estimations. This algorithm provides an environment representation through Bayesian probabilistic occupancy grids and estimates positions in the near future of every static and dynamic part of the grid. Based on these estimations, time-to-collision probabilities are then associated with the corresponding cells. Using CARLA simulator, a large number of execution traces are then generated, considering both collisions and almost-collisions in realistic urban scenarios. Real experiments complete the analysis and show the reliability of the simulation results.

Automotive systems must undergo a strict process of validation before their release on commercial vehicles. With the increased use of probabilistic approaches in autonomous systems, standard validation methods are not applicable to this end. Furthermore, real life validation, when even possible, implies costs which can be obstructive. New methods for validation and testing are thus necessary. In this paper, we propose a generic method to evaluate complex probabilistic frameworks for autonomous driving. The method is based on Statistical Model Checking (SMC), using specifically defined Key Performance Indicators (KPIs), as temporal properties depending on a set of identified metrics. By studying the behavior of these metrics during a large number of simulations via our statistical model checker, we finally evaluate the probability for the system to meet the KPIs. We show how this method can be applied to two different subsystems of an autonomous vehicle: a perception system and a decision-making approach. An overview of these two systems is given to understand related validation challenges. Extensive validation results are then provided for the decision-making case.

As drivers approach a road intersection, they must decide whether to cross it or to come to a stop. For this purpose, drivers make a situation assessment and adapt their behaviour accordingly. When this task is performed by a computer, the available information is partial and uncertain. Any decision requires the system to use this information as well as taking into account the behaviour of other drivers to avoid collisions. Common metrics such as collision rate can remain low in an interactive environment because of other driver's actions. Consequently, evaluation metrics must depend on other driving aspects. In this paper a decision-making mechanism and metrics to evaluate such a system at road intersection crossing are presented. For the former, a Partially Observable Markov Decision Process is used to model the system with respect to uncertainties in the behaviour of other drivers. For the latter, different key performance indicators are defined to evaluate the resulting behaviour of the system with different configurations and scenarios. The approach is demonstrated within an automotive grade simulator. It has showed at times, that whilst the vehicle can cross safely the intersection, it might not satisfy other key performance indicators related to highway code.

We propose a method to estimate the semantic grid for an autonomous vehicle. The semantic grid is a 2D bird's eye view map where the grid cells contain semantic characteristics such as road, car, pedestrian, signage, etc. We obtain the semantic grid by fusing the semantic segmentation information and an occupancy grid computed by using a Bayesian filter technique. To compute the semantic information from a monocular RGB image, we integrate segmentation deep neural networks into our model. We use a deep neural network to learn the relation between the semantic information and the occupancy grid which can be trained end-to-end extending our previous work on semantic grids. Furthermore, we investigate the effect of using a conditional random field to refine the results. Finally, we test our method on two datasets and compare different architecture types for semantic segmentation. We perform the experiments on KITTI dataset and Inria-Chroma dataset.

One of the most challenging tasks in the development of path planners for intelligent vehicles is the design of the cost function that models the desired behavior of the vehicle. While this task has been traditionally accomplished by hand-tuning the model parameters, recent approaches propose to learn the model automatically from demonstrated driving data using Inverse Reinforcement Learning (IRL). To determine if the model has correctly captured the demonstrated behavior, most IRL methods require obtaining a policy by solving the forward control problem repetitively. Calculating the full policy is a costly task in continuous or large domains and thus often approximated by finding a single trajectory using traditional path-planning techniques. In this work, we propose to find such a trajectory using a conformal spatiotemporal state lattice, which offers two main advantages. First, by conforming the lattice to the environment, the search is focused only on feasible motions for the robot, saving computational power. And second, by considering time as part of the state, the trajectory is optimized with respect to the motion of the dynamic obstacles in the scene. As a consequence, the resulting trajectory can be used for the model assessment. We show how the proposed IRL framework can successfully handle highly dynamic environments by modeling the highway tactical driving task from demonstrated driving data gathered with an instrumented vehicle.

In an autonomous vehicle setting, we propose a method for the estimation of a semantic grid, i.e. a bird's eye grid centered on the car's position and aligned with its driving direction, which contains high-level semantic information about the environment and its actors. Each grid cell contains a semantic label with divers classes, as for instance {Road, Vegetation, Building, Pedestrian, Car...}. We propose a hybrid approach, which combines the advantages of two different methodologies: we use Deep Learning to perform semantic segmentation on monocular RGB images with supervised learning from labeled groundtruth data. We combine these segmentations with occupancy grids calculated from LIDAR data using a generative Bayesian particle filter. The fusion itself is carried out with a deep neural network, which learns to integrate geometric information from the LIDAR with semantic information from the RGB data. We tested our method on two datasets, namely the KITTI dataset, which is publicly available and widely used, and our own dataset obtained with our own platform, equipped with a LIDAR and various sensors. We largely outperform baselines which calculate the semantic grid either from the RGB image alone or from LIDAR output alone, showing the interest of this hybrid approach.

When approaching a road intersection, drivers consider several factors and choose amongst different likely manoeuvres. For an autonomous agent, it is fundamental to understand what other drivers are doing before deciding their own manoeuvres. These are seldom be the same as intersections differ and the situations too. Whilst, learning techniques can be used to process features of trajectories and to predict manoeuvres of others cars. The problem with such approaches is the difficult process of recording data for each intersection, not only of the subject vehicle but of the other vehicles. To address this problem, a hybrid data set was constructed. It is built in a simulated environment and completed with real data after has driven multiple times across the intersection. To analyze these data, classification technique is used to find the common range of features for each manoeuvre. Random forest classifiers are used in conjunction with our functional discretization to analyze the trajectories of cars approaching an intersection. The classifiers can determine the longitudinal manoeuvre as well as the direction. We show how our approach performs compared to other classifiers and space discretization. In addition, we demonstrate the impact and the usefulness of the mixture between simulated and real data. An improvement of 30% accuracy is obtained with the hybrid data set, and 5% using our functional discretization with respect to baseline approach.

Robust perception is the cornerstone of safe and environmentally-aware autonomous navigation systems. Autonomous robots are expected to recognise the objects in their surroundings under a wide range of challenging environmental conditions. This problem has been tackled by combining multiple sensor modalities that have complementary characteristics. This paper proposes an approach to multi-sensor-based robotic perception that leverages the rich and dense appearance information provided by camera sensors, and the range data provided by active sensors independently of how dense their measurements are. We introduce a framework we call XDvision where colour images are augmented with dense depth information obtained from sparser sensors such as lidars. We demonstrate the utility of our framework by comparing the performance of a standard CNN-based image classifier fed with image data only with the performance of a two-layer multimodal CNN trained using our augmented representation.

Whether it be to feed data for an object detection-and-tracking system or to generate proper occupancy grids, 3D point cloud extraction of the ground and data classification are critical processing tasks, on their efficiency can drastically depend the whole perception chain. Flat-ground assumption or form recognition in point clouds can either lead to systematic error, or massive calculations. This paper describes an adaptive method for ground labeling in 3D Point clouds, based on a local ground elevation estimation. The system proposes to model the ground as a Spatio-Temporal Conditional Random Field (STCRF). Spatial and temporal dependencies within the segmentation process are unified by a dynamic probabilistic framework based on the conditional random field (CRF). Ground elevation parameters are estimated in parallel in each node, using an interconnected Expectation Maximization (EM) algorithm variant. The approach, designed to target high-speed vehicle constraints and performs efficiently with highly-dense (Velodyne-64) and sparser (Ibeo-Lux) 3D point clouds, has been implemented and deployed on experimental vehicle and platforms, and are currently tested on embedded systems (Nvidia Jetson TX1, TK1). The experiments on real road data, in various situations (city, countryside, mountain roads,...), show promising results.

Occupancy Grids (OGs) are a popular framework for robotic perception. They were recently adopted for performing multi-sensor fusion and environment mapping for autonomous vehicles. However, high computational requirements strongly hinder their integration into less powerful automotive ECUs. To overcome this problem, we propose an algorithmic improvement for mapping range measurements into OGs. Experiments were conducted on a vehicle equipped with 16 LIDAR scans. Results demonstrate that a single-core ARM cortex A9 can build now in real-time OGs that map urban traffic scenarios of 100m-by-100m.

For the last 25 years, occupancy grids have been intensively used as a well-understood framework for many robotic applications, such as path planning or obstacle avoidance. They offer a unifying framework for multiple heterogeneous sensor integration using a probabilistic representation of sensor data. This integration is computed through Bayesian techniques or evidence combination approaches, both requiring high computation workload using real number representation. In critical application domains, it is challenging to fuse data coming out of several sensors in real-time using constrained embedded platforms. In this paper, we propose a revised theoretical formulation of multi-sensor fusion using only integer arithmetic. We apply this novel framework to compute occupancy grid by only using integer numbers to represent probabilities. Compared to the state-of-the-art solutions, our fusion framework enables implementation on platforms with no floating-point support. Our experiments demonstrate that fusion of real automotive data from a 4-scans LIDAR can be integrated into a microcontroller without a floating-point unit. Our approach opens the perspective for microcontroller or even for hardware block based on ASIC or FPGA to support occupancy grid applications with real-time performance.

Summary form only given. Modern cars include more and more sophisticated electronics, sensors, processing and control components. These new components are used both for controlling the main functions of the vehicle and for providing the driver with Advanced Driving Assistance Systems (ADAS). Such ADAS functionalities are increasingly based on Robotics technologies for partly automating some driving functions such as adaptive cruise control, acceleration/braking in a traffic lane, lane keeping, parking assistance, or even simple collision avoidance or mitigation actions (including braking or airbag actuation). Most of the automotive constructors are now proposing ADAS options, and the degree of autonomy of cars is progressively increasing. But the ultimate challenge addressed by many Academic and Industrial Research Laboratories and is to develop driverless cars. Impressive results have already been published and shown to a large public through the media, and many announcements concerning the future deployment of such vehicles have recently been done by several major Automotive Manufacturers and Multinational groups such as Google. This talk addresses both the socio-economic and technical issues which are behind the development of the next car generation. These future cars will include both smart ADAS and Driverless Car functionalities. An emphasis will be put on the main enabling technologies which are required for providing the vehicle with a Robust Embedded Perception system, a Situation Awareness capability including Short term Prediction and Collision Risk estimation, and a Decisional and Control System for generating safe Navigation and Maneuvering actions. All theses functionalities have to be robust in the presence of sensing errors, uncertainty and traffic hazards. It will be shown that "Bayesian Perception" and "Bayesian Decision" are two key paradigms for developing the above mentioned functionalities. Experimental results obtained on real equipped vehicles provided by Toyota and by Renault will be used to illustrate the talk.

This paper presents a novel method to perform the outlier rejection task between two different views of a camera rigidly attached to an Inertial Measurement Unit (IMU). Only two feature correspondences and gyroscopic data from IMU measurerments are used to compute the motion hypothesis. By exploiting this 2-point motion parametrization, we propose two algorithms to remove wrong data associations in the feature-matching process for case of a 6DoF motion. We show that in the case of a monocular camera mounted on a quadrotor vehicle, motion priors from IMU can be used to discard wrong estimations in the framework of a 2-point-RANSAC based approach. The proposed methods are evaluated on both synthetic and real data.

Approaching a group of humans is an important navigation task. Although many methods have been proposed to avoid interrupting groups of people engaged in a conversation, just a few works have considered the proper way of joining those groups. Research in the field of social sciences have proposed geometric models to compute the best points to join a group. In this article we propose a method to use those points as possible destinations when driving a robotic wheelchair. Those points are considered together with other possible destinations in the environment such as points of interest or typical static destinations defined by the user's habits. The intended destination is inferred using a Dynamic Bayesian Network that takes into account the contextual information of the environment and user's orders to compute the probability for each destination.

Service and assistance robots that must move in human environment must address the difficult issue of navigating in dynamic environments. As it has been shown in previous works, in such situations the robots can take advantage of the motion of persons by following them, managing to move together with humans in difficult situations. In those circumstances, the problem to be solved is how to choose a human leader to be followed. This work proposes an innovative method for leader selection, based on human experience. A learning framework is developed, where data is acquired, labeled and then used to train an AdaBoost classification algorithm, to determine if a candidate is a bad or a good leader, and also to study the contribution of features to the classification process.

Modeling and monitoring dynamic environments is a complex task but is crucial in the field of intelligent vehicle. A traditional way of addressing these issues is the modeling of moving objects, through Detection And Tracking of Moving Objects (DATMO) methods. An alternative to a classic object model framework is the occupancy grid filtering domain. Instead of segmenting the scene into objects and track them, the environment is represented as a regular grid of occupancy, in which each cell is tracked at a sub-object level. The Bayesian Occupancy Filter [1] is a generic occupancy grid framework which predicts the spread of spatial occupancy by estimating cell velocity distributions. However its velocity model, corresponding to a transition histogram per cell, leads to huge data management which in practice makes it hardly compatible to severe computational and hardware constraints, like in many embedded systems. In this paper, we present a new representation for the BOF, describing the environment through a mix of static and dynamic occupancy. This differentiation enables the use of a model adapted to the considered nature: static occupancy is described in a classic occupancy grid, while dynamic occupancy is modeled by a set of moving particles. Both static and dynamic parts are jointly generated and evaluated, their distribution over the cells being adjusted. This approach leads to a more compact model and to drastically improve the accuracy of the results, in particular in term of velocities. Experimental results show that the number of values required to model the velocities have been reduced from a typical 900 per cell (for a 30×30 neighborhood) to less than 2 per cell in average. The massive data compression allows to plan dedicated embedded devices.

In this paper, a method to perform semi-autonomous navigation on a wheelchair is presented. The wheelchair could be controlled in semi-autonomous mode estimating the user's intention by using a face pose recognition system or in manual mode. The estimator was performed within a Bayesian network approach. To switch these two modes, a speech interface was used. The user's intention was modeled as a set of typical destinations visited by the user. The algorithm was implemented to one experimental wheelchair robot. The new application of the wheelchair system with more natural and easy-to-use human machine interfaces was one of the main contributions. as user's habits and points of interest are employed to infer the user's desired destination in a map. Erroneous steering signals coming from the user-machine interface input are filtered out, improving the overall performance of the system. Human aware navigation, path planning and obstacle avoidance are performed by the robotic wheelchair while the user is just concerned with “looking where he wants to go”.

For collision avoidance systems to be accepted by human drivers, it is important to keep the rate of unnecessary interventions very low. This is challenging since the decision to intervene or not is based on incomplete and uncertain information. The contribution of this paper is a decision making strategy for collision avoidance systems which allows the system to occasionally postpone a decision in order to collect more information. The problem is formulated in the framework of statistical decision theory, and the core of the algorithm is to run a preposterior analysis to estimate the benefit of deciding with the additional information. A final decision is made by comparing this benefit with the cost of delaying the intervention. The proposed approach is evaluated in simulation at a two-way stop road intersection for stop sign violation scenarios. The results show that the ability to postpone decisions leads to a significant reduction of false alarms and does not impair the ability of the collision avoidance system to prevent accidents.

With robots technology shifting towards entering human populated environments, the need for augmented perceptual and planning robotic skills emerges that complement to human presence. In this integration, perception and adaptation to the implicit human social conventions plays a fundamental role. Toward this goal, we propose a novel framework that can model context-dependent human spatial interactions, encoded in the form of a social map. The core idea of our approach resides in modelling human personal spaces as non-linearly scaled probability functions within the robotic state space and devise the structure and shape of a social map by solving a learning problem in kernel space. The social borders are subsequently obtained as isocontours of the learned implicit function that can realistically model arbitrarily complex social interactions of varying shape and size. We present our experiments using a rich dataset of human interactions, demonstrating the feasibility and utility of the proposed approach and promoting its application to social mapping of human-populated environments.

Predicting driver behavior is a key component for Advanced Driver Assistance Systems (ADAS). In this paper, a novel approach based on Support Vector Machine and Bayesian filtering is proposed for online lane change intention prediction. The approach uses the multiclass probabilistic outputs of the Support Vector Machine as an input to the Bayesian filter, and the output of the Bayesian filter is used for the final prediction of lane changes. A lane tracker integrated in a passenger vehicle is used for real-world data collection for the purpose of training and testing. Data from different drivers on different highways were used to evaluate the robustness of the approach. The results demonstrate that the proposed approach is able to predict driver intention to change lanes on average 1.3 seconds in advance, with a maximum prediction horizon of 3.29 seconds.

Service robots have a great potential of improving human quality of life by aiding in everyday tasks. However, robots that share an environment and interact with humans still face some challenges that limits their acceptance. One of these challenges is how to move and behave among groups of people, which is a task performed seamlessly by humans and some animals. Motion planning in dynamic environments has been addressed mostly by predicting future position of humans and avoiding them. However, with the increase of the number of persons in such environments, techniques that are based only on the prediction of the movement of humans can fail, as they usually ignore the human's reaction to the presence of the robot. Instead of trying to model the complex human motion behavior, this work proposes to rely on humans to guide the robot through difficult situations, where modern approaches would fail to find a solution. This will be accomplished by a probabilistic approach for selecting a human leader, according to the robot's desired destination. In this way, the robot can take advantage of the humans' paths and behavior, effortlessly avoiding dynamic and static features together with the human leader, relieving the robot from the burden of having to generate its own path in difficult situations.

In this paper, an object class recognition method is presented. The method uses local image features and follows the part-based detection approach. It fuses intensity and depth information in a probabilistic framework. The depth of each local feature is used to weigh the probability of finding the object at a given distance. To train the system for an object class, only a database of images annotated with bounding boxes is required, thus automatizing the extension of the system to different object classes. We apply our method to the problem of detecting vehicles from a moving platform. The experiments with a data set of stereo images in an urban environment show a significant improvement in performance when using both information modalities.

In this paper we present some important improvements to a fast motion detection technique based on laser data and odometry/imu information. This technique instead of performing a complete SLAM (Simultaneous Localization and Mapping) solution, is based on transferring occupancy information between two consecutive data grids. Then we show its integration with Bayesian Occupancy Filter (BOF) and with the subsequent tracking module called Fast Clustering-Tracking Algorithm (FCTA). We especially show the improvements achieved in tracking results after this integration.

A crucial requirement for service robots is to be able to move in dynamic environments shared with humans as well as interact with them. Navigation in such environments is a challenging task, as the environment is constantly changing, future states have to be predicted and planning and execution must be carried on-line. However, even in very complex situations, humans can easily find a path that avoid both dynamic agents and static obstacles. This paper proposes a technique to take advantage of the human movement in such populated environments, using a probabilistic approach for the leader selection, according to the robot's desired destination. By choosing a leader to be followed in dynamic environments, the robot can take advantage of the paths traveled by humans or other robots, effortlessly avoiding dynamic and static features as its leader does, relieving the robot from the burden of having to generate its own path. Both the leader selection and the leader following algorithms have been tested in a real environment, with a robotic wheelchair.

Perception is a key component for any robotic system. In this paper we present a method to construct occupancy grids by fusing sensory information using Linear Opinion Pools. We used lidar sensors and a stereo-vision system mounted on a vehicle to make the experiments. To perform the validation, we compared the proposed method with the fusion method previously used in the Bayesian Occupancy Filter framework, using real data taken from highway and urban scenarios. The results show that our method is better at dealing with conflicting information coming from the sensors. We propose an implementation on parallel hardware which allows real-time execution.

The objective of this paper is to present a strategy to safely move a robot in an unknown and complex environment where people are moving and interacting. The robot, by using only its sensor data, must navigate respecting humans' comfort. To obtain good results in such a dynamic environment, a prediction on humans' movement is also crucial. To solve all the aforementioned problems we introduce a suitable cost function. Its optimization is obtained by using a new stochastic and adaptive optimization algorithm (CAO). This method is very useful in particular when the analytical expression of the optimization function is unknown but numerical values are available for any state configuration. Additionally, the proposed method can easily incorporate any dynamical and environmental constraints. To validate the performance of the proposed solution, several simulation results are provided.

This paper proposes a novel approach to risk assessment at road intersections. Unlike most approaches in the literature, it does not rely on trajectory prediction. Instead, dangerous situations are identified by comparing what drivers intend to do with what they are expected to do. Driver intentions and expectations are estimated from the joint motion of the vehicles, taking into account the layout of the intersection and the traffic rules at the intersection. The proposed approach was evaluated in simulation with two vehicles involved in typical collision scenarios. An analysis of the collision prediction horizon allows to characterize the efficiency of the approach in different situations, as well as the potential of different strategies to avoid an accident after a dangerous situation is detected.

Intersections are the most complex and hazardous areas of the road network, and 89% of accidents at intersection are caused by driver error. We focus on these accidents and propose a novel approach to risk assessment: in this work dangerous situations are identified by detecting conflicts between intention and expectation, i.e. between what drivers intend to do and what is expected of them. Our approach is formulated as a Bayesian inference problem where intention and expectation are estimated jointly for the vehicles converging to the same intersection. This work exploits the sharing of information between vehicles using V2V wireless communication links. The proposed solution was validated by field experiments using passenger vehicles. Results show the importance of taking into account interactions between vehicles when modeling intersection situations.

Occupancy grids are a very convenient tool for environment representation in robotics. This paper will detail a novel approach for computing occupancy grids from stereo vision and show its application to intelligent vehicles. In the proposed approach, occupancy is initially computed directly in the stereoscopic sensor's disparity space. The calculation formally accounts for the detection of obstacles and road pixels in disparity space, as well as partial occlusions in the scene. In the second stage, this disparity-space occupancy grid is transformed into a Cartesian space occupancy grid to be used by subsequent applications. This transformation includes spatial and temporal filtering. The proposed method is designed to easily be processed in parallel. Consequently, we chose to implement it on a graphics processing unit, which allows real-time processing for demanding applications. In this paper, we present this method, and we propose an application to the problem of perception in a road environment. Results are presented with real road data, qualitatively comparing this approach with other methods.

With the growing demand of personal assistance to mobility and mobile service robotics, robot navigation systems must be ¿aware¿ of the social conventions followed by people. They must respect proximity constraints but also respect people interacting. For example, they may not break interaction between people talking, unless the occupants want to take part in the conversation. In this case, they must be able to join the group using a socially adapted behavior. This paper proposes a risk-based navigation method including both the traditional notion of risk of collision and the notion of risk of disturbance. Results exhibit new emerging behavior showing how a robot takes into account social conventions in its navigation strategy.

Safety applications at road intersections require algorithms that can estimate the manoeuvre intention of all the drivers in the scene. In this paper, the use of contextual information extracted from a digital map of the road network is explored. We propose a Bayesian network which combines probabilistically uncertain observations on the vehicle's behaviour and information about the geometrical and topological characteristics of the road intersection in order to infer a driver's manoeuvre intention. The approach is evaluated on trajectories recorded from real traffic, including complex scenarios where the behaviour of the vehicle is inconsistent. We define an evaluation method that accounts for the impossibility to make reliable predictions in some situations, and show that the system is able to reliably combine vehicle state information and map information to infer a driver's intended manoeuvre.

Fusion of telemetric and visual data from traffic scenes helps exploit synergies between different on-board sensors, which monitor the environment around the ego-vehicle. This paper outlines our approach to sensor data fusion, detection and tracking of objects in a dynamic environment. The approach uses a Bayesian Occupancy Filter to obtain a spatio-temporal grid representation of the traffic scene. We have implemented the approach on our experimental platform on a Lexus car. The data is obtained in traffic scenes typical of urban driving, with multiple road participants. The data fusion results in a model of the dynamic environment of the ego-vehicle. The model serves for the subsequent analysis and interpretation of the traffic scene to enable collision risk estimation for improving the safety of driving.

The ArosDyn project aims to develop embedded software for robust analysis of dynamic scenes in urban traffic environments, in order to estimate and predict collision risks during car driving. The on-board telemetric sensors (lidars) and visual sensors (stereo camera) are used to monitor the environment around the car. The algorithms make use of Bayesian fusion of heterogenous sensor data. The key objective is to process sensor data for robust detection and tracking of multiple moving objects for estimating and predicting collision risks in real time, in order to help avoid potentially dangerous situations.

In many computer vision related applications it is necessary to distinguish between the background of an image and the objects that are contained in it. This is a difficult problem because of the constraints imposed by the available time and the computational cost of robust object extraction algorithms. This report describes a new method that benefits from state of the art background/foreground classification combined with the strong theoretical foundations of clustering. The pixels on the scene background are modeled as Mixtures of Gaussians and the output of the classification process are continuous values representing the likelihood that each pixel belongs to the foreground. The clustering is based on a Self Organizing Network (SON) which has a robust initialization schema and is able to find the number of objects in an image or grid. The algorithm's complexity is linear with respect to the number of pixels or cells.

The occupancy grid is a popular tool for probabilistic robotics, used for a variety of applications. Such grids are typically based on data from range sensors (e.g. laser, ultrasound), and the computation process is well known. The use of stereo-vision in this framework is less common, and typically treats the stereo sensor as a distance sensor, or fails to account for the uncertainties specific to vision. In this paper, we propose a novel approach to compute occupancy grids from stereo-vision, for the purpose of intelligent vehicles. Occupancy is initially computed directly in the stereoscopic sensor's disparity space, using the sensor's pixel-wise precision during the computation process and allowing the handling of occlusions in the observed area. It is also computationally efficient, since it uses the u-disparity approach to avoid processing a large point cloud. In a second stage, this disparity-space occupancy is transformed into a Cartesian space occupancy grid to be used by subsequent applications. In this paper, we present the method and show results obtained with real road data, comparing this approach with others.

The paper presents a navigation algorithm for dynamic probabilistic environments. The static environment is unknown; moving pedestrians are detected and tracked on-line. Pedestrians are supposed to move along typical motion patterns represented by HMMs. The planning algorithm is based on an extension of the rapidly-exploring random tree algorithm, where the likelihood of the obstacles future trajectory and the probability of collision is explicitly taken into account. The algorithm is used in a partial motion planner, and the probability of collision is updated in real-time according to the most recent estimation. Results show the performance for a car-like robot in a simulated environment among multiple dynamic obstacles.

The nine papers in this special section examine perception, planning, and navigation for intelligent vehicles.

Modeling and predicting human and vehicle motion is an active research domain. Due to the difficulty of modeling the various factors that determine motion (e.g., internal state and perception), this is often tackled by applying machine learning techniques to build a statistical model, using as input a collection of trajectories gathered through a sensor (e.g., camera and laser scanner), and then using that model to predict further motion. Unfortunately, most current techniques use offline learning algorithms, meaning that they are not able to learn new motion patterns once the learning stage has finished. In this paper, we present an approach where motion patterns can be learned incrementally and in parallel with prediction. Our work is based on a novel extension to hidden Markov models (HMMs) - called growing hidden Markov models - which gives us the ability to incrementally learn both the parameters and the structure of the model.

In many computer vision related applications it is necessary to distinguish between the background of an image and the objects that are contained in it. This is a difficult problem because of the double constraint on the available time and the computational cost of robust object extraction algorithms. This paper builds upon former work on combining the strong theoretical foundations of clustering with the speed of other approaches. It is based on a novel self organizing network (SON) which has a robust initialization schema and is able to find the number of objects in an image or grid. The main contribution of our extension is that it eliminates the use of a threshold, allowing the algorithm to work on continuous, while having a complexity that remains linear with respect to the number of pixels or cells.

The paper describes a navigation algorithm for dynamic, uncertain environment. Moving obstacles are supposed to move on typical patterns which are pre-learned and are represented by Gaussian processes. The planning algorithm is based on an extension of the rapidly-exploring random tree algorithm, where the likelihood of the obstacles trajectory and the probability of collision is explicitly taken into account. The algorithm is used in a partial motion planner, and the probability of collision is updated in real-time according to the most recent estimation. Results show the performance of the navigation algorithm for a car-like robot moving among dynamic obstacles with probabilistic trajectory prediction.

Abstract — Most of present work for autonomous navigation in dynamic environment doesn’t take into account the dynamics of the obstacles or the limits of the perception system. To face these problems we applied the Probabilistic Velocity Obstacle (PV O) approach [1] to a dynamic occupancy grid. The paper presents a method to estimate the probability of collision where uncertainty in position, shape and velocity of the obstacles, occlusions and limited sensor range contribute directly to the computation. A simple navigation algorithm is then presented in order to apply the method to collision avoidance and goal driven control. Simulation results show that the robot is able to adapt its behaviour to the level of available knowledge and navigate safely among obstacles with a constant linear velocity. Extensions to non-linear, non-constant velocities are proposed. I.

The Bayesian occupancy filter (BOF) (Coue et al., 2002) has achieved promising results in the object tracking applications. This paper presents a new development of BOF which inherits original BOF's advantages. Meanwhile, the new formulation has significantly reduced original BOF's complexities and can be run in realtime. In Bayesian occupancy filter, the environment is finely divided into 2-dimensional grids. Different from conventional occupancy gridmaps, in BOF, each grid has both static (occupancy) and dynamic (velocity) characteristics. In the new proposed BOF, the velocity of each cell is modeled as a distribution. The distribution for each cell occupancy can therefore be inferred using a filtering mechanism. A segmentation algorithm is implemented to extract the objects from BOF estimation. Thereafter, standard target tracking methods are employed to further analyze each object's motion. By using BOF as a pre-processing tool, the complexity of the data association is significantly reduced. Experiments using data from an indoor human tracking application demonstrate that our approach yields satisfactory results

Despite their popularity, occupancy grids cannot be directly applied to problems where the identity of the objects populating an environment needs to be taken into account (e.g., object tracking, scene interpretation, etc.), in this cases it is necessary to postprocess the grid in order to extract object information. This paper approaches the problem by proposing a novel algorithm inspired on image segmentation techniques. The proposed approach works without prior knowledge about the number of objects to be detected and, at the same time, is very fast. This is possible thanks to the use of a novel self organizing network (SON) coupled with a dynamic threshold. Our experimental results on both real and simulated data show that our approach is robust and able to operate at normal camera frame rate

In this paper, we propose a real-time method to detect obstacles using theoretical models of the ground plane, first in a 3D point cloud given by a stereo camera, and then in an optical flow field given by one of the stereo pair's camera. The idea of our method is to combine two partial occupancy grids from both sensor modalities with an occupancy grid framework. The two methods do not have the same range, precision and resolution. For example, the stereo method is precise for close objects but cannot see further than 7 m (with our lenses), while the optical flow method can see considerably further but has lower accuracy. Experiments that have been carried on the CyCab mobile robot and on a tractor demonstrate that we can combine the advantages of both algorithms to build local occupancy grids from incomplete data (optical flow from a monocular camera cannot give depth information without time integration)

To address perception problems we must be able to track dynamics targets of the environment. An important issue of tracking is filtering problem in which estimates of the target's state are computed while observations are progressively received. This paper presents an adaptive interacting multiple models (IMM) based filtering method. Interacting multiple models have been successfully applied to many applications as they allow, using several filters in parallel, to deal with the uncertainty on motion model, a critical component of filtering. Indeed targets can rapidly change their motion over a lapse of time. This is the case of pedestrians for which it is difficult to define an unique motion model which matches all their possible displacements. Nevertheless, the transition probability matrix (TPM) which models the interaction between different filters in an IMM is in currently defined a priori or needs an important amount of tuning to be used efficiently. In this paper, we put forward a method which automatically adapts online the TPM. The TPM adaptation using on-line data significantly improves the effectiveness of IMM filtering and so better target estimates are obtained. To validate our work we applied our method to pedestrian tracking in car parks on a real platform

Building occupancy grids (OGs) in order to model the surrounding environment of a vehicle implies to fusion occupancy information provided by the different embedded sensors in the same grid. The principal difficulty comes from the fact that each can have a different resolution, but also that the resolution of some sensors varies with the location in the field of view. In this article we present a new exact approach to this issue and we explain why the problem of switching coordinate systems is an instance of the texture mapping problem in computer graphics. Therefore we introduce a calculus architecture to build occupancy grids with a graphical processor unit (GPU). Thus we present computational time results that can allow to compute occupancy grids for 50 sensors at frame rate even for a very fine grid. To validate our method, the results with GPU are compared to results obtained through the exact approach

In this project, we took on the task of localizing an automatic vehicle and building a map of the car park in real time. This takes place within the car park of INRIA Rhone-Alpes on the CyCab vehicle with a Sick laser range scanner. Our method uses only laser scanners to retrieve the position and orientations of vehicles in the car park. With the detected vehicles as landmarks, CyCab performs a localization of itself and builds a map of the car park at the same time. Classical clustering and segmentation techniques to extract line segments from the laser scan data are applied. The key contribution of the paper is the extraction of vehicle poses from the line segments using Bayesian programming. The method of FastSLAM is used in localizing CyCab and estimating the pose of vehicles in the car park. A set of hypotheses is obtained as a result. The second contribution is a method of combining the set of hypotheses together to form a final map of the car park.

Localization with respect to a reference model is a key feature for mobile robots. Urban environment offers numerous landmarks that can be used for the localization process. This paper deals with the use of an environment model stored in a geographic information system, to drive a vision system i.e. highlights what to look for and where to look for. This task is achieved by propagating uncertainties along the image acquisition system to highlight some region of interest in the image.

Vehicle navigation in dynamic environments is an important challenge, especially when the motion of the objects populating the environment is unknown. Traditional motion planning approaches are too slow to be applied in real-time to this domain, hence, new techniques are needed. Recently, iterative planning has emerged as a promising approach. Nevertheless, existing iterative methods do not provide a way to estimate the future behavior of moving obstacles and use the resulting estimates in trajectory computation. This paper presents an iterative planning approach that addresses these two issues. It consists of two complementary methods: 1) a motion prediction method which learns typical behaviors of objects in a given environment; 2) an iterative motion planning technique based on the concept of velocity obstacles.

The recent development of a new kind of public transportation system relies on a particular double-steering kinematic structure enhancing maneuverability in cluttered environments such as downtown areas. We call bi-steerable car a vehicle showing this kind of kinematics. Endowed with autonomy capacities, the bi-steerable car ought to combine suitably and safely a set of abilities: simultaneous localisation and environment modelling, motion planning and motion execution amidst moderately dynamic obstacles. In this paper we address the integration of these four essential autonomy abilities into a single application. Specifically, we aim at reactive execution of planned motion. We address the fusion of controls issued from the control law and the obstacle avoidance module using probabilistic techniques.

Vehicle navigation in dynamic environments is an important challenge, especially when the motion of the objects populating the environment is unknown. Traditional motion planning approaches are too slow to be applied in real-time to this domain, hence, new techniques are needed. Recently, iterative planning has emerged as a promising approach. Nevertheless, existing iterative methods do not provide a way to estimate the future behaviour of moving obstacles and use the resulting estimates in trajectory computation. This paper presents an iterative planning approach that addresses these two issues. It consists of two complementary methods: 1) a motion prediction method which learns typical behaviours of objects in a given environment; 2) an iterative motion planning technique based on the concept of velocity obstacles.

The recent development of a new kind of public transportation system relies on a particular double-steering kinematic structure enhancing maneuverability in cluttered environments such as downtown areas. We call bi-steerable car a vehicle showing this kind of kinematics. We present experimental results, from map-building to trajectory tracking, aiming at validating the theoretical considerations obtained recently for the general bi-steerable system. These results are a first step towards the motion autonomy of this kind of transportation system.

This paper presents a methodology to simulate cuts in deformable objects. It proposes a simple physical model of cutting in combination with a large displacement (Green) strain tensor formulation. Explicit finite elements are used to allow real-time simulations and fast topology updates during cutting procedures. Force feedback is added to increase realism.

Computer assisted navigation and biomechanical modeling have made surgical simulation a new domain of research in the last decade. In this paper, we focus on assisting the surgeon to manage anterior cruciate ligament (ACL) reconstruction. During this operation, the ACL graft has to be placed in such a way that it is isometric during a flexion-extension and in traction when the leg is in extension. That is to say, two constraints: a geometrical one and a physical one. We present a CT-Free system that solves both these constraints in real-time and intra-operatively. The geometrical constraint is solved by Aesculap's OrthoPilot system while a deformable model is used to solve the physical one. With our combined solution, the surgeon will be able to know intra-operatively if the graft placement will lead to robust and effective reconstruction or otherwise.

Soft tissue cutting is an important task in surgery simulators. We use a separation of elements approach instead of destroying or subdividing the elements. Previously we have started a new cutting approach for 2D mass-springs models: separating the elements. It does not increment the number of elements (as in the subdivision approach) and maintains the same mass during simulations (against the destruction approach).

This paper focuses on real-time motion planning in a dynamic environment. Most of the global existing approaches cannot satisfy real-time due to heavy computation, while local methods don't guarantee reaching the goal. In this paper we present a novel global approach based on the non-linear velocity obstacle concept. We use the rich information on the velocities admissible for the robot to build a complete autonomous navigation module, composed of a local obstacle-avoidance system coupled with an incremental global motion planner. Real-time computation issues are discussed. Results obtained in simulation for dynamic environments are presented.

The kinematic constraints on a car limits the movements that it can follow, and this difficulty also makes planning a path a challenging problem. More precisely, the parallel parking problem has been widely addressed in the literature, but these approaches rely on more traditional methods using control laws, motion planners or artificial intelligence. There have been recently much interest in the robotics domain on using probabilistic approaches. In this paper, we propose an original formulation and resolution of the parking problem using Bayesian Robot Programming.

In this paper, we propose solutions to real time simulation and interaction of deformable objects in virtual reality. Firstly, we present LEM (long element method), a method created for physically based simulation of deformable objects. LEM has been conceived specially for objects filled with fluids. Using Pascal's principle and volume conservation, the method produces a static solution for global elastic deformation. Bulk variables such as pressure, density, volume and stress are used to model the deformable object. Secondly, we present a deformable buffer model that is used to solve problems arising from the difference between sampling and update rates. We look into the construction and the updating process of this buffer model. Our approach to linking the two models to get realistic force feedback is also presented. The physical and haptic model is then coupled to be part of a surgical simulator for soft tissue. We present some results from our prototype medical simulator for echography exams of the human thigh.

This paper focuses on real-time global motion planning in a dynamic environment. Most of the existing approaches suffer from heavy computation and cannot satisfy real-time constraints. In this paper we present a novel approach, based on the Non-Linear Velocity Obstacle Concept, that maps the positions of the obstacles and their known or estimated trajectories directly in the space of the velocities admissible by our robot, taking into account its kinematic and dynamics constraints. The result is a map of all the collision free velocities. We present a few improvements to this approach and introduce the notion of risk to perform local goal-oriented obstacle-avoidance. Combining it with graph-expansion techniques, we propose to extend the system to an incremental global motion planner in a dynamic environment.

This paper presents the modification to LEM - Long Element Method to simulate large deformations. We are interested us deformable objects filled with some incompressible fluid By large deformations, we mean deformations such as stretching, bending and twisting which involves the entire body, in contrast to poking or pinching which relatively covers a small region of the deformable object. We make use of Pascals's Principle and volume conservation as boundary conditions to obtain a static solution due to an externally applied pressure. We believe that the state of such an object is a result from effects of the surface tension (generally in any direction) and the pressure of the internal fluid (normal to the surface). By allowing such liberty, large deformations such as stretching, bending and twisting can be simulated without much change to the initial formulation of the physical model. This approach is particularly interesting for real time quasi-dynamic simulation of well damped soft tissue. This paper presents the modification to LEM-Long Element Method to simulate large deformations. We are interested us deformable objects filled with some incompressible fluid By large deformations, we mean deformations such as stretching, bending and twisting which involves the entire body, in contrast to poking or pinching which relatively covers a small region of the deformable object. We make use of Pascid's Principle and volume conservation as boundary conditions to obtain a static solution due to an externally applied pressure. We believe that the state of such an object is a result from effects of the surface tension (generally in any direction) and the pressure of the internal fluid (normal to the surface). By allowing such liberty, large deformations such as stretching, bending and twisting can be simulated without much change to the initial formulation of the physical model. This approach is particularly interesting for real time quasi-dynamic simulation of well damped soft tissue.

This paper presents an approach to apply the long element method (LEM), a new method for physically based simulation of deformable objects, to a general polygonal mesh. The LEM is suitable for real time simulation and virtual environment interaction. The approach implements a static solution for elastic global deformation of objects filled with fluids based on Pascal's Principle and the volume conservation. The volumes are discretised into long elements, defining meshes several order of magnitudes smaller than tetrahedral or cubic meshes. We show how these volumes are constructed when the method is applied to a general mesh. We also propose a method for collision detection when two such objects interact. Finally, we show how we can perform dynamic simulation when the physics of the objects are modeled using bulk variables: pressure, density, volume and stress. This approach is particularly interesting for real time simulation of soft tissue undergoing small deformations.

Previous works have presented solutions for stability problems arising from the difference between the sampling rate requirements for haptic devices (about 1 kHz) and the update rates of the physical objects being simulated (about 10 Hz). These methods work well when the objects are convex and non-deformable but, when the object is deformable, these methods might fail in obtaining realistic force feedback and exact graphical rendering. The reason of this is due to the concavities and unknown shapes that may appear in the deformable objects. This paper proposes to perform haptic interaction with the local topology of the object, taking into account the unknown changes and the concavities in the object shape. This local model is updated at the simulation frequency rate.

This paper introduces a methodology to simulate a particular kind of the fracture phenomenon : the tearing one. The objective of the method is to provide realistic tearing simulations, occuring on 2D deformable objects, and working in real-time. This method can find applications in surgery simulators, where tearing human tissue is an important feature to provide. It can also be applied, in a more general scope, in virtual environment applications. The central idea in this scheme is to "separate" the physical simulation elements, instead of destroying or dividing them. This avoids the increase of physical elements that need to be simulated (which occurs when they are divided) and gives a more accurate simulation than when they are destroyed.

This paper presents a novel control architecture for a car-like vehicle moving in a dynamic and partially known environment. The key idea is to plan and carry out sensor-based maneuvers. The paper focuses on the reactive part of the architecture that features control experts, i.e., parametrized control programs adapted to a specific maneuver and capable to react in real-time to unforeseen events. This paper aims to show why and how we made use of artificial neural network to improve the performance of our control architecture. Simulation and experimental results obtained with an automatic car are presented to illustrate the advantages of our approach.

This paper proposes a method for interfacing a force-feedback device of type PHANToM to a spring-damper model of the human thigh. The model was defined from experimental data and it is simulated using implicit integration. The main difficulty encountered is that while the PHANToM needs to receive the force values at a rate of 1 KHz, the physical model runs at a maximum speed of 100 Hz. Supplying forces at this frequency leads to unrealistic vibration in the force feedback. The novelty of our approach is the use of a local model supplying reliable force values at a high frequency. The purpose of this work is to contribute for the implementation of an echographic simulator with force-feedback.

Presents an approach to implementing haptic interfaces in generic virtual reality systems. Typical implementations of virtual environment simulations with haptic rendering conceive the haptic interface intrinsically linked to the virtual scene update. In this framework, the haptic feedback estimation depends on the methods used to simulate the virtual scene and the haptic feedback rate depends on the scene update rate. This dependence ties the development of the simulation system and strongly limits the complexity of simulated scenes due to the high feedback rate (/spl sim/1 KHz) demanded by a realistic haptic rendering. We propose a new structure to systems having a haptic interface, decoupling the haptic rendering from the virtual environment simulation and introducing a "buffer model" between them. We successfully applied this approach to interface a deformable objects simulator with a Phantom haptic device.

Research in path planning, motion control, and sensing is well-developed in robotics. The purpose of this paper is to show how general ideas from this area can be used for navigation of virtual autonomous entities in partially known dynamic environments. The basic idea is to consider the virtual entity as a "Virtual Robot" controlled using a layered navigation system combining a general path planner, a motion controller and a simulated perception system. Particularly, we address our initial implementation for the case of a human character. In this scheme, the motion synthesis of the different components of the articulated character is performed in real-time using computer graphic techniques. The path planner is based on the Ariadne's Clew Algorithm (ACA). We propose a multi-purpose object oriented implementation of the ACA able to solve different path planning problems: path-planning in the map of a large-scale environment, avoidance of unexpected obstacles while following a path, manipulation of movable objects and inverse kinematics. A simple decisional process is proposed in order to drive our path planner, the motion controller and the perception system.

The paper presents an approach to detect and localize contact between deformable polyhedra, which can be convex or concave depending on the time step. Usual contact detection algorithms, defined for convex polyhedra, cannot be used efficiently, as they would imply completing the convex decomposition of the considered polyhedra at each time step, as it can change due to the deformability of these polyhedra. As the computation of this convex decomposition is very expensive (in complexity and computation time), we propose an algorithm to detect and localize the contact in linear time w.r.t. the number of vertices. This algorithm returns the direction of this contact and the value of the maximum intersection distance between the convex hulls of the two considered polyhedra. Experimental results taken from a dynamic simulation application are presented with their computation time, to complete the complexity analysis.

Proposes a mass-spring model of a human thigh based on real data acquired. It addresses both the difficulties of determining the parameters of this model to fit the measurements and the computational demands. Implicit integration is used to update the model through time. The motivation behind this work is to provide accurate force-feedback for an echographic simulator that could be used to train practitioners to detect a thrombosis.

The stabilization of the motion of a nonholonomic vehicle is considered. The control system developed has a two-level architecture. The lower control level operates within the kinematic model of the vehicle to stabilize its motion to a desired trajectory. The upper control level uses the dynamic model of the vehicle and stabilizes the feedback obtained on the lower control level. The operation of the control system is studied when unknown bounded disturbances affect the motion. The adaptive motion control is proposed to deal with uncertain dynamic parameters of the vehicle.

We describe models and algorithms designed to produce efficient and physically consistent dynamic simulations. These models and algorithms have been implemented in a unique framework, modeling both deformations and contacts through visco-elastic relations. Since this model of interaction (known as "penalty based") is much debated, we present it in detail. The "penalty" based model is said to have two major drawbacks: the difficulty in determining viscoelastic parameters, and in choosing the computation time step. We present a solution for both problems based on physical concepts. Finally, we show results comparing real data, "impulse" based simulation and "penalty" based simulation.

We describe models and algorithms designed to produce efficient and physically consistent dynamic simulations. These models and algorithms have been implemented in a unique framework modeling both deformations and contacts through visco-elastic relations. Since this model of interaction (known as "penalty based") is much debated, we present a detailed study of this model. Indeed, the "penalty" based model is supposed to have two major drawbacks: determining the visco-elastic parameters and choosing the computation time step. We present a solution for both problems based on physical concepts. Finally, we present results comparing real data, "impulse" based simulation and "penalty" based simulation.

Presents a control architecture for a car-like vehicle moving in a dynamic and partially known environment. The key idea is to plan and carry out sensor-based manoeuvres. The paper focuses on the reactive part of the architecture that features control experts, i.e. parameterized control programs adapted to a specific manoeuvre and capable to react in real-time to unforeseen events. Experimental results obtained with an automatic car are presented for two types of manoeuvres: lane following/changing and parallel parking.

Deals with path planning for car-like robots. Usual planners compute paths made of circular arcs tangentially connected by line segments, as these paths are locally optimal. The drawback of these paths is that their curvature profile is not continuous: to follow them precisely, a vehicle must stop and reorient its directing wheels at each curvature discontinuity (transition segment-circle). To remove this limitation, a new path planning problem is proposed: two curvature constraints are added to the classical kinematic constraints taken into account. Thus, the curvature must remain continuous, and its derivative is bounded (as the car-like robot can reorient its directing wheels with a limited speed only). For this problem, the existence of solutions and the characterization of those of optimal length are shown. A method solving the forward-only problem (i.e. the problem for a car moving only forward) is then presented, and this method is compared to the classical one w.r.t. the complexity and computation time, the length of the generated paths and the quality of the tracking.

Dynamic simulation is potentially a powerful tool for studying complex contact interactions between robots and their environments. One of the main problems of such a simulation is the determination of the model parameters which provide realistic behavior for objects. This paper describes how to identify such parameters for a masses/springs based system (the Robot/spl Phi/ system). This identification process is composed of two main steps: the first step consists in distributing the total mass of the object between the different particles while respecting the inertial properties of the object; the second one consists in finding the values of the physical parameters of the model such as elasticity, viscosity, plasticity, etc. A numerical solution of the first step is described, while a genetic algorithm based approach is proposed for the second step. This approach allows us to find the values of the parameters which provide a consistent behavior under a set of given constraints (position, velocity, volume, etc). It also allows us to minimize the computation time and to attach priorities with these constraints.

Dynamic simulation is potentially a powerful tool for studying complex contact interactions between robots and their environments. One of the main problems of such a simulation is the determination of the model parameters which provide realistic behavior for objects. This paper describes how to identify such parameters for a mass/spring based system. This identification process is composed of two main steps: 1) distributing the total mass of the object between different particles while respecting the inertial properties of the object; and 2) finding the values of the physical parameters of the model such as elasticity, viscosity, plasticity, etc. The numerical solution of the first step is described, while a genetic algorithm base approach is proposed for the second step. This approach allows us to find the values of the parameters which provide a consistent behavior under a set of given constraints (position, velocity, volume, etc.). It also allows us to minimize the computation time and to attach priorities with these constraints.

Start of the above-titled section of the conference proceedings record.

This paper describes the control approach developed to perform parallel parking and returning to traffic manoeuvres for a car capable of autonomous motion. The key idea is to carry out a motion control procedure involving a "localization-planning-execution" cycle until a specified location of the car relative to its environment is reached. Range measurements are used to model environmental objects around the car. The automatic manoeuvres developed are demonstrated on an experimental electric autonomous car in a usual traffic environment.

This paper presents a new approach to detect and localise contact between concave deformable polyhedra. In this case there are many contact points between two polyhedra, the proposed algorithm detects and localises the contact in linear time O(n). It returns also the direction of this contact and the value of the maximum inter-penetration between the two convex-hulls of these two polyhedra.

Practical aspects of motion generation and control for parking a nonholonomic autonomous vehicle are considered. An iterative algorithm for the parallel parking maneuver is proposed. It is based on ultrasonic range data processing. To control the steering angle and longitudinal velocity of the vehicle during the parking maneuver, sinusoidal reference functions are used. To prevent collisions, the maneuver is carried out as a reactive motion. The developed control is experimentally verified for a LIGIER electric autonomous vehicle.

An efficient computational model for the dynamics of a deformable robot fingertip is presented. The dynamic model is based on a discretization of the fingertip's volume into a lattice of masses locally interconnected by damped springs. The lattice's parameters are adjusted in correspondence with bulk properties of the fingertip's deformable material (rubber). In the task studied, the fingertip moves toward a rigid flat surface, contacts it, and presses against it. This motion is commanded by an external feedback controller which communicates with the dynamic model through a virtual control interface: The controller applies forces and torques to the dynamic model and the dynamic model responds in real-time with position/velocity/force feedback information. In this fashion, the controller interacts with the fingertip's model in the same way it would interact with the actual physical system. This type of paradigm is envisioned as a prototyping/testing tool in the design of control systems for deformable objects as well as for applications involving the haptic (i.e., sensorially realistic) interaction between a human and a virtual (deformable) object. Graphical snapshots of a real time simulation of the task under study are presented which reveal the physical and computational plausibility of the model.

Dynamic simulation can be a powerful tool for the study of complex contact interactions between robots and their environments, but a large amount of computation is often required to generate numerically accurate simulations. This paper describes an adaptive time step approach to dynamical simulation based on monitoring the conservation of energy. This approach allows us to insure numerical stability and computational efficiency at a very low computational overhead, and also provides estimates of the probable range of numerical errors in position and velocity. The approach is applicable to any physical-based dynamic simulation system and can be integrated with other optimization techniques.

Roadmaps, generated by pre-processing of the known environment, have been a popular approach to robot motion planning. Generally designed for static environments, roadmaps are often invalidated by any anomaly between the real world and the model of the environment. We investigate the effect on roadmaps when sensor information indicates such an error and describe an algorithm which, by performing further pre-processing on the known environment, generates a mapping between points in the workspace and the road map. Used during on-line planning the mapping enables a valid, although not necessarily connected, roadmap to be maintained if such an error is discovered. We then present a divide and conquer algorithm which uses guided random motion to attempt to reconnect paths affected by the error. This is the first step towards a global planner that could be used in evolving environments.

This work presents an approach to plan motion strategies for robotics tasks constrained by uncertainty in position, orientation, and control. Our approach operates in a (x, y, /spl theta/) configuration space and it combines two local functions: a contact-based attraction function and an exploration function. Compliant motions are used to reduce the position/orientation uncertainty. An explicit geometric model for the uncertainty is defined to evaluate the reachability of the obstacle surfaces when the robot translates in free space.

We describe in this paper a new motion planning approach for a nonholonomic mobile robot moving on an uneven terrain and subject to strong physical interaction constraints. The novelty of this method is that it deals with the dynamics of the robot and its physical interactions with the terrain at the planning time, together with the kinematic and the geometric constraints of the task. The planner basically combines a geometry-based reasoning strategy operating on a subset of the configuration space of the robot, and a local continuous motion generation technique based on the use of a physical model of the task. We will describe each level and its corresponding models, and present how they are integrated in order to find safe and executable motions for a rover.

Complex contact interactions between the robot and its environment (contact between a dextrous hand and a grasped object, contact between an all-terrain vehicle and the terrain, ..) depend on physical properties such as mass, mass distribution, rigidity/elasticity factors, viscosity, and collision forces. Classical geometrical models (representing the spatial properties of an object) are obviously not helpful to study such interactions. So one needs another model which represents not only the form of the object but also its motion, its deformation and, its interaction with the environment. Such a model is called the "dynamic model". This paper describes the Robot/spl Phi/ system, which enables one to physically represent robots and to study their physical behaviour. This system uses a hierarchical representation of objects in order to accelerate collision detection (linear time for rigid objects). An energy based adaptative time step approach was developed in order to detect and avoid numerical divergence and to reduce computational time.

Remote sensors such as CCD cameras can be used for a variety of robot sensing tasks, but given restrictions on camera location and imaging geometry, task constraints, and visual occlusion it can be difficult to find viewing positions from which the task can be completed. The complexity of these constraints suggests that automated, quantitative methods of sensor placement are likely to be useful, particularly when the workspace is cluttered and a mobile robot-mounted sensor is being used to increase the sensible region, circumvent occlusions, and so forth. We describe a camera placement planner designed to produce heuristically good static viewing positions for a robot-mounted CCD camera in an experimental workcell. It can be configured to produce viewpoints for a variety of tasks such as workpiece location, inspection and modelling; feedback control by visual servoing; and task progress monitoring. The planner uses a novel probability-based global search technique to optimize a viewpoint evaluation function that heuristically combines task, camera, robot and environmental constraints. The main advances over previous work are the incorporation of kinematic accessibility and collision constraints in the viewpoint evaluation and the introduction of a search technique powerful enough to handle the resulting strong nonlinearities.

This paper presents a complete dynamic modeling system, called Robot/spl Phi/. This system allows us to create a physical model of an object and to simulate its motion, its deformations, and its interaction with the environment and with other objects. This system takes into account three types of interactions: the collision, the static and dynamic friction, and the viscosity of the environment. An hierarchical representation of objects allows us to have a linear complexity when calculating the contact between objects. An adaptative time step allows the system to avoid numerical divergence, to optimise the computational time, and to control the incurred error.

This paper addresses motion planning for a mobile robot moving on a hilly three dimensional terrain and subjected to strong physical interaction constraints. The main contribution of this paper is a planning method which takes into account the dynamics of the robot, the robot/terrain interactions, the kinematic constraints of the robot, and classical constraints. The basic idea of our method is to integrate geometric and physical models of the robot and of the terrain in a two-stage trajectory planning process. Consisting in combining a "discrete search strategy" and a "continuous motion generation method". It will be shown how each planning step operates and how they interact in order to generate a safe and executable motion for the all-terrain vehicle.>

Planning robust grasping operations involving a dextrous robotics hand and an object located in a three dimensional workspace requires the combination of two main types of techniques, a geometric reasoning technique aimed at producing a grasping strategy (preshape of the hand, grasping parameters, type of motion to execute), and a physically based technique, allowing the analysis of the dynamic object/hand interactions. The paper focuses on the second type of technique which is clearly required to conclude on the feasibility of the chosen grasping strategy (stability in particular) and to determine the execution parameters of the selected grasp (type of control to apply onto the hand in particular). The purpose of the paper is to propose a new technique based upon the concept of "physical models" for solving this problem. The authors show how physical models can be constructed and used to solve the associated stability and control strategy problems. The authors also show how the related techniques have been combined with more classical geometric methods to solve the whole problem.>

This paper deals with the automation of dextrous grasping in a partly known environment using a stereo vision system and a multifingered hand mounted on a robot arm. Effective grasping requires a combination of sensing and planning capabilities. We propose an integrated approach that combines computer vision, path planning, and manipulator control in three complementary activities: the reconstruction of task-oriented models of the workspace, the determination of appropriate grasping configurations from computed 'preshapes' of the hand, and the automatic generation and execution of hand/arm motions using a hybrid geometric path planner and a hybrid control system. This paper outlines the architecture of our system, discusses the techniques we have developed on grasp planning, and finishes with a brief description of work-in-progress on the implementation and some preliminary experimental results.>

This paper deals with motion, planning for a mobile robot moving on a hilly three dimensional terrain and subjected to strong physical interaction. Constraints. The main contribution of this paper is a planning method which takes into account the dynamics of the robot, the robot/terrain interactions, the kinematic constraints of the robot, and classical constraints. The basic idea of the authors' method is to integrate geometric and physical models of the robot and of the terrain in a two-stage trajectory planning process consisting of combining a "discrete search strategy" and a "continuous motion generation method". It is shown how each planning step operates and how they interact in order to generate a "safe" and executable motion for the all-terrain vehicle.>

Planning robust grasping operations involving a dextrous robotics hand and an object located in a 3D workspace requires the combination of two main types of techniques: a geometric based reasoning aimed at producing a grasping strategy; and a physical analysis of the object/hand interactions. The second type of technique is clearly necessary to conclude on the feasibility of the chosen grasping strategy (stability in particular) and to determine the type of control to apply onto the hand. The purpose of this paper is to propose a technique based upon the concept of "physical models" for solving this problem. We show how physical models can be constructed and used to solve the associated stability and control strategy problems. We also show how the related techniques can be combined with more classical geometric methods to solve the whole problem. We describe the modeling of the task, the connection between geometric and physical constructions, the characteristics of the motion planning process, and the experimental results which have been obtained.>

This paper presents an approach to plan robust motion strategies of a robot navigating through an environment composed of polygonal obstacles subject to geometric uncertainty constraints. The contacts of the robot against the obstacles are used to reduce its position and orientation uncertainties and to guide the robot to its goal configuration. The authors describe a motion planner based on this approach which generates both, free space motions and compliant motions (contact based motions). An explicit geometric model for the uncertainty is used to estimate the reachability of the goal and the intermediate subgoals (these are generated when the final goal is not reachable from the current robot configuration). Two functions are combined to explore the valid space : (1) a contact-based potential field function is used to generate continuous motions pulling the robot towards target attractors; (2) an exploration function is used to determine possible subgoals allowing progress towards the ultimate goal when local minima of the previous function occur.>

This paper copes with the problem of motion execution monitoring for a car-like vehicle moving in a subset of the road network. The final goal is to design an architecture for planning and controlling the motion of the vehicle. This architecture must enable the vehicle to optimize its behavior autonomously and in real-time, i.e., to avoid stationary and moving obstacles in its local environment while respecting the highway code and its own kinematic and dynamic constraints. To resolve the problems of motion planning, motion execution monitoring and command generation (control), an intermediate step where the vehicle is still driven by a human driver so its control is replaced by an assistance of the driver through a man-machine interface is proposed. Work concerning the vehicle motion execution monitoring within this simplified architecture is reported. The framework of this program is the Pro-Lab II demonstrator whose purpose is to develop an electronic co-pilot to assist the human driver.

This paper addresses the motion prediction problem of a planetary vehicle under the following hypotheses: the vehicle must be able to move on both, natural and hostile terrains, it must have the ability of selecting and applying several navigation strategies depending on the characteristics of the terrain, and it must be capable of showing complex behaviors derived by both, its sophisticated mechanical structure and the vehicle/terrain physical interactions. An original method to simulate the dynamic behavior of the vehicle (i.e., vehicle/terrain interactions, sliding or gripping effects...) when executing motions having the previous characteristics is presented. This method is based on the concept of physical modeling which has been initially developed in the field of computer graphics and man/machine communication. The basic idea is to consider that motions and/or deformations of physical objects result from the application of physical laws involving a set of forces whose application points depend on the intrinsic structure of the interacting objects.

The authors address the problem of controlling a remote arm when a large communication delay exists between the control room and the remote workcell. To minimize the volume of information transiting through the communication link and to avoid the problems due to the delay of transmission, the system makes use of two identical world models of the remote workcell: one installed physically close to the operator and the other installed within the controller of the remote site. The communication link only transmits task level robot commands or goals to be achieved. Both sites are equipped with two sets of identical planners, one set is used to test if the generated task level commands can be processed by these planners and the other to plan and execute the actual commands on the remote workcell. After an overview of existing teleprogramming environments, the authors present a general description of the system. Finally they describe the experimental testbed and the results obtained with their method.

This paper deals with the problem of simulating the behavior of a mobile robot moving on a terrain along a precomputed nominal path. The nominal path is supposed to be provided by a planner. The purpose of the simulator to instantiate the nominal path into a complete trajectory, while verifying that a set of constraints is satisfied all along the motion. The simulator is based on an iterative algorithm to compute configurations for the robot at each time increment. Each iteration consists of two successive steps: determination of a stable configuration and of the associated contact points on the ground, and determination of the motion of all joints by minimization of the sliding at the contact points.

A trajectory planning problem called the highway problem is discussed. It consists of planning a time-optimal trajectory for a mobile robot which is travelling in a structured workspace amidst moving obstacles and is subject to constraints on its velocity and acceleration. In a structured workspace there are lanes characterized by one-dimensional curves along which the mobile robot can move. The mobile robot has to follow a lane, but it may also shift from its lane to an adjacent one. An efficient method which determines an approximate time-optimal solution to the highway problem is presented. The approach consists of discretizing time and selecting the accelerations to be applied to the mobile robot among a discrete set. These hypotheses make it possible to define a grid in the mobile robot's time-state space, i.e. the state space augmented in the time dimension. This grid is then searched to find a solution.>

This paper deals with trajectory planning for a mobile A which is subject to constraints on its velocity and acceleration and travels in a structured workspace W amidst fixed and moving obstacles. By structured workspace, we mean that there exist lanes within which A is able to move without colliding with the fixed obstacles of W. This paper presents an efficient method which determines an approximate time-optimal solution to this problem in the following way: given a set of adjacent lanes, one of which leads A to its goal, and knowing that A is able to shift from one lane to an adjacent one, we determine the trajectory of A along these lanes so as to avoid any collision with the moving obstacles of W while respecting the dynamic constraints of A (bounded acceleration and velocity). The technique we have chosen in order to determine the trajectory of A along the lanes is to discretize and then explore the time-state space of A (this time-state space is obtained by adding the time dime...

This paper is concerned with the problem of controlling the motion of a mobile robot moving in a time-varying environment. The study considers a car-like vehicle moving in a roadway-like environment. We present two approaches which enable the vehicle to execute a given nominal motion plan and to adjust it in order to avoid static and dynamic obstacles. The first approach is based on classical potential field techniques. The second one relies upon a multi-agent approach. I Introduction We are intersted in the problem of motion control of a carlike vehicle. To deal with this problem, we use a classical two layered system composed of a "trajectory planner" and a "motion controller". The purpose of the trajectory planner is to generate a nominal plan made up of a geometric path and a velocity profile along this path. The motion controller enables the autonomous vehicle to execute this nominal plan in a reactive way and to optimize its behaviour, i.e. to avoid moving obstacles while respec...

International audience

The problem of planning and controlling the motion of a car-like moving object in a dynamic and roadway-like environment is addressed. A motion controller that executes in a reactive way a given nominal motion plan is presented. Data concerning the actual environment of the vehicle considered are assumed to be obtained through perception. In order to get the required reactivity, a motion controller is developed which has two main components: the pilot which analyzes the current situation and adapts the nominal plan accordingly, and the executor which generates the required motion commands. The pilot operates at a symbolic level using a set of behavioral rules. The executor makes use of a potential field approach to generate the motion commands.>

This paper deals with the problem of planning safe trajectories for a manipulator robot moving in an environment including both static obstacles and objects (other robots, conveyors) whose positions may change during the interval of time separating two planning steps. In order to solve this problem for a general manipulator having six degrees of freedom, the authors have developed and implemented a method combining two different path planners: a local planner whose purpose is to take the manipulator away from the constrained initial and final configurations, and a global planner which is in charge of generating a safe trajectory for the first three degrees of freedom of the arm. Both the local and the global planners are based on a fast iterative algorithm for computing the distance between pairs of objects. These planners have been implemented within a robot programming system (called ACT) including a solid modeler dedicated to robotics applications and a connection to a robot controller.>

Deals with the problem of planning the motions of a complex land vehicle moving in a natural environment. The contribution presented is a motion generator which predicts the dynamic behaviour of the vehicle when executing a given nominal motion plan. This plan is expressed in terms of a channel to follow and of a set of intermediate subgoals to reach. Solving this motion generation problem requires to explicitly reason about the geometric and the physical aspects of the movements that the vehicle has to execute. In the authors' approach, this is done using two basic constructions derived from the concept of physical model: the 'generalized obstacles' are used for physically guiding the movements of the vehicle using an explicit model of the vehicle/terrain interactions, and the 'physical targets' are used to map the strategic information onto the physical representation of the world.>

The problem of making sensing and acting techniques cooperate in order to achieve a given manipulation task in a partially structured environment is treated in the context of automatic grasping by guiding the decisional process using a combination of partial geometric models and a vision data. The geometric models represent the known information concerning the robot workspace and the object to be grasped. The vision-based information is collected at execution time using a 2D camera and a 3D vision sensor, both located on the robot end effector. This means that robot motions and sensing operations have to be combined for the purpose of both acquiring the missing information and guiding the grasping movements. This is achieved by applying three processing phases respectively aimed at selecting a viewpoint avoiding occlusions, modeling the local environment of the object to be grasped, and determining the grasping parameters.>

The author describes a method for planning fine motion strategies by reasoning on an explicit representation of the contact space. This method reduces the algorithmic complexity inherent in the path planning problem by separating the computation of potential reachable positions and valid movements from the determination of those that are really executable by the robot. The algorithm developed operates in two phases: the construction of a state graph representing a set of potential solutions; and the searching of this graph in order to find a good reverse path defining a feasible fine motion program. The fine motion planner has been implemented in LUCID-LISP on a SUN 260. Simulations have given rise to real executions using a six-degree-of-freedom SCEMI robot equipped with a force sensor.>