A biped robot walking in a crowd must avoid falls and collisions at the same time. The latter is usually addressed through Passive Safety (PS), which guarantees that the robot is at rest when a collision is inevitable. Since PS may limit the robot's mobility, the purpose of this work is to introduce and explore the novel concept of Time To Danger (TTD) as an alternative. For a given robot motion, TTD is the time where the robot enters the region that a person can potentially occupy in the future. After having studied the properties of TTD, a novel locomotion strategy is proposed, which computes an optimal locomotion plan that guarantees balance preservation and TTD maximization, following a receding horizon Model Predictive Control scheme. Controlled experiments in a challenging simulated crowd scenario demonstrate how the novel locomotion strategy outperforms a Passive Safety-based locomotion strategy from a collision avoidance point of view.

We control a biped robot moving in a crowd with a Model Predictive Control (MPC) scheme that generates stable walking motions, with automatic footstep placement. Most walking strategies propose to re-plan the walking motion to adapt to changing environments only once at every footstep. This is because a footstep is planted on the ground, it usually stays there at a constant position until the next footstep is initiated, what naturally constrains the capacity for the robot to react and adapt its motion in between footsteps. The objective of this paper is to measure if re-planning the walking motion more often than once at every footstep can lead to an improvement in collision avoidance when navigating in a crowd. Our result is that re-planning twice (or more) during each footstep leads to a significant reduction of the number of collisions when walking in a crowd, but depends on the density of the crowd.

Recent works in the domain of Human-Robot Motion (HRM) attempted to plan collision avoidance behavior that accounts for cooperation between agents. Cooperative collision avoidance between humans and robots should be conducted under several factors such as speed, heading and also human attention and intention. Based on some of these factors, people decide their crossing order during collision avoidance. However, whenever situations arise in which the choice crossing order is not consistent for people, the robot is forced to account for the possibility that both agents will assume the same role i.e. a decision detrimental to collision avoidance. In our work we evaluate the boundary that separates the decision to avoid collision as first or last crosser. Approximating the uncertainty around this boundary allows our collision avoidance strategy to address this problem based on the insight that the robot should plan its collision avoidance motion in such a way that, even if agents, at first, incorrectly choose the same crossing order, they would be able to unambiguously perceive their crossing order on their following collision avoidance action.

Recent works in the area of human robot motion showed that behaving in a human-like manner allows a robot to reduce global cognitive effort for people in the environment. Given that collision avoidance situations between people are solved cooperatively, this work models the manner in which this cooperation is done so that a robot can replicate their behavior. To that end, hundreds of situations where two walkers have crossing trajectories were analyzed. Based on these human trajectories involving a collision avoidance task, we determined how total effort is shared between each walker depending on several factors of the interaction such as crossing angle, time to collision and speed. To validate our approach, a proof of concept is integrated into ROS with Reciprocal Velocity Objects (RVO) in order to distribute collision avoidance effort in a human-like way.

A prerequisite to safe robot motion is to avoid Inevitable Collision States (ICS). However, the characterization of the ICS set is a challenge. Several approximation methods have been proposed, most of which either are overly conservative or fail to provide proper motion safety guarantees. In order to to improve safety guarantees, we build upon Viability Theory and adapt an algorithm designed to approximate the Viability Kernel, a concept similar to ICS. Our algorithm is applied first to a challenging static environment scenario. It is then extended to handle dynamic environments. Although it is not possible in general to ensure safety forever, we manage nonetheless to achieve infinite motion safety in two special cases.

This paper addresses the problem of planning the motion of a mobile robot with a limited sensory field-of-view in an unknown dynamic environment. In such a situation, the upper-bounded planning time prevents from computing a complete motion to the goal, partial motion planning is in order. Besides the presence of moving obstacles whose future behaviour is unknown precludes absolute motion safety (in the sense that no collision will ever take place whatever happens) is impossible to guarantee. The stance taken herein is to settle for a weaker level of motion safety called passive motion safety: it guarantees that, if a collision takes place, the robot will be at rest. The primary contribution of this paper is PassPMP, a partial motion planner enforcing passive motion safety. PassPMP periodically computes a passively safe partial trajectory designed to drive the robot towards its goal state. Passive motion safety is handled using a variant of the Inevitable Collision State (ICS) concept called Braking ICS, i.e. states such that, whatever the future braking trajectory of the robot, a collision occurs before it is at rest. Simulation results demonstrate how PassPMP operates and handles limited sensory field-of-views, occlusions and moving obstacles with unknown future behaviour. More importantly, PassPMP is provably passively safe.

Mobile robot companions are service robots that are mobile and designed to share our living space. For such robots, mobility is essential and their coexistence with humans adds new aspects to the mobility issue: the first one is to obtain appropriate motion and the second one is interaction through motion. We encapsulate these two aspects in the term Human-Robot Motion (HRM) with reference to Human-Robot Interaction. The long-term issue is to design robot companions whose motions, while remaining safe, are deemed appropriate from a human point of view. This is the key to the acceptance of such systems in our daily lives. The primary purpose of this paper is to explore how the psychological concept of attention can be taken into account in HRM. To that end, we build upon an existing model of attention that computes an attention matrix that describes how the attention of each person is distributed among the different elements, persons and objects, of his/her environment. Using the attention matrix, we propose the novel concept of attention field that can be viewed as an attention predictor. Using different case studies, we show how the attention matrix and the attention field can be used in HRM.

This paper addresses the problem of navigating a mobile robot with a limited field-of-view in a unknown dynamic environment. In such a situation, absolute motion safety, i.e. such that no collision will ever take place whatever happens, is impossible to guarantee. It is therefore settled for a weaker level of motion safety dubbed passive motion safety: it guarantees that, if a collision takes place, the robot will be at rest. Passive motion safety is tackled using a variant of the Inevitable Collision State (ICS) concept called Braking ICS, i.e. states such that, whatever the future braking trajectory of the robot, a collision occurs before it is at rest. Passive motion safety is readily obtained by avoiding Braking ICS at all times. Building upon an existing Braking ICS-Checker, i.e. an algorithm that checks if a given state is a Braking ICS or not, this paper presents a reactive collision avoidance scheme called PASSAVOID. The main contribution of this paper is the formal proof of PASSAVOID's passive motion safety. Experiments in simulation demonstrates how PASSAVOID operates.

This paper is concerned with the navigation of personal robots in human-populated environments. The behavior of a person among its peers is governed by a number of unspoken social rules, e.g. maintaining an appropriate distance. The primary contribution of this paper is a navigation scheme that is anthropomorphic, i.e. that emulates human behaviors and seeks to adhere to these social rules. Unlike previous works in this area, the focus herein is on dynamic scenarios. The navigation scheme proposed explicitly reasons on the future behavior of the people involved so as to produce better socially acceptable trajectories (not to mention safer trajectories as well). The navigation scheme relies upon a novel cost function called the social costmap that captures in a unified way the different social rules imposed by the people populating the robot's workspace.

In this paper, we present a generic architecture for perception of an intelligent vehicle in dynamic outdoor environment. This architecture is composed of two levels: a first level dedicated to real-time local simultaneous localization and mapping (SLAM) and a second one is dedicated to detection and tracking of moving objects (DATMO). The experimental results on datasets collected from different scenarios such as: urban streets, country roads and highways demonstrate the efficiency of the proposed algorithm on a Daimler Mercedes demonstrator in the framework of the European Project PReVENT-ProFusion2 and on a Volkswagen Demonstrator in the framework of the European Project Intersafe2.

This paper addresses the problem of provably safe navigation for a mobile robot with a limited field-of-view placed in a unknown dynamic environment. In such a situation, absolute motion safety (in the sense that no collision will ever take place whatever happens in the environment) is impossible to guarantee in general. It is therefore settled for a weaker level of motion safety dubbed passive motion safety: it guarantees that, if a collision is inevitable, the robot will be at rest. The primary contribution of this paper is a relaxation of the Inevitable Collision State (ICS) concept called Braking ICS. A Braking ICS is a state for which, no matter what the future trajectory of the robot is, it is impossible to stop before a collision takes place. Braking ICS are designed with a passive motion safety perspective for robots with a limited field-of-view in unknown dynamic environments. Braking ICS are formally defined and a number of important properties are established. These properties are then used to design a Braking ICS checker, i.e. an algorithm that checks whether a given state is a Braking ICS or not. In a companion paper, it is shown how the Braking ICS checker can be integrated into a reactive navigation scheme whose passive motion safety is provably guaranteed.

Using multiple sensors in the context of environment perception for autonomous vehicles is quite common these days. Perceived data from these sensors can be fused at different levels like: before object detection, after object detection and finally after tracking the moving objects. In this paper we detail our object detection level fusion between laser and stereo vision sensors as opposed to pre-detection or track level fusion. We use the output of our laser processing to get a list of objects with position and dynamic properties for each object. Similarly we use the stereo vision output of another team which consists of a list of detected objects with position and classification properties for each object. We use Bayesian fusion technique on objects of these two lists to get a new list of fused objects. This fused list of objects is further used in tracking phase to track moving objects in an intersection like scenario. The results obtained on data sets of INTERSAFE-2 demonstrator vehicle show that this fusion has improved data association and track management steps.

For its own safety, a robot system should never find itself in a state where there is no feasible trajectory to avoid collision with an obstacle. Such a state is an Inevitable Collision State (ICS). The ICS concept is particularly useful for navigation in dynamic environments because it takes into account the future behaviour of the moving objects. Accordingly it requires a model of the future evolution of the environment. In the real-world, the future trajectories of the obstacles are generally unknown and only estimates are available. This paper introduces a probabilistic formulation of the ICS concept which incorporates uncertainty in the model of the future trajectories of the obstacles. It also presents two novel probabilistic ICS-checking algorithms that are compared with their deterministic counterpart.

Object-class independent motion estimation from range data is a challenging task. We present here a novel approach that is able to derive a dense motion field based on range images only. We propose to first segment the range image into segments using a recently proposed segmentation criterion. Motion is then estimated segment-wise with full 6 degrees of freedom. To that end, we introduce dynamic mapping, i.e. the accumulation of measurements for moving objects. We show experimentally that the approach is able to deliver a dense motion field which can then be used for object-class independent trajectory estimation.

Trajectory generation consists in computing a feasible trajectory between a start and a goal state-time, for a given robotic system. We presented in our previous works a trajectory generator called Tiji, geared towards complex dynamic systems subject to differential constraints. Moreover, it is able to handle a final time constraint, ie an interval of time during which the goal state must be reached, and to provide an admissible trajectory that ends close to the goal state-time if no solution exists to connect both states. This paper is a natural extension of these works, and presents several applications of our trajectory generator. Arbitrary robotic systems may be handled. Furthermore, the control-oriented nature of Tiji and its ability to handle a final time constraint makes it a useful tool to embed into various reactive approaches (trajectory tracking, obstacle avoidance). Simulation and experimental results illustrate the different systems and navigation approaches in which Tiji has been embedded.

This paper presents Tiji, a trajectory generation scheme, ie an algorithm that computes a feasible trajectory between a start and a goal state, for a given robotic system. Tiji is geared towards complex dynamic systems subject to differential constraints, such as wheeled vehicles, and its efficiency warrants it can be used in real-time. Above all, Tiji is able to compute a trajectory that reaches the goal state at a prescribed final time in order to avoid collision with the moving objects of the environment. The method proposed, which relies upon a parametric trajectory representation, is variational in nature. The trajectory parameters are incrementally updated in order to optimize of a cost function involving the distance between the end of the trajectory computed and the (goal state, final time) pair. Should the goal state be unreachable (if the final time is ill-chosen), the method returns a trajectory that ends as close as possible to the (goal state, final time) pair, which can be useful in certain applications.

This paper presents ICS-AVOID, a collision avoidance scheme based upon the concept of Inevitable Collision State (ICS), ie a state for which, no matter what the future trajectory of the robotic system is, a collision eventually occurs. By design, ICS-AVOID can handle dynamic environments since ICS do take into account the future behaviour of moving objects. ICS-AVOID is designed to keep the system away from ICS. By doing so, motion safety is guaranteed (by definition a robotic system in a non-ICS state has at least one collision-free trajectory that it can use). To demonstrate the efficiency of ICS-AVOID, it has been extensively compared with two state-of-the-art collision avoidance schemes: the first one is built upon the Dynamic Window approach and the second one on the Velocity Obstacle concept. The results obtained show that, when provided with the same amount of information about the future evolution of the environment, ICS-AVOID outperforms the other two schemes. The first reason for this has to do with the extent to which each collision avoidance scheme reasons about the future. The second reason has to do with the ability of each collision avoidance scheme to find a safe control if one exists. ICS-AVOID is the only one which is complete in this respect thanks to the concept of Safe Control Kernel.

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.

Safety is an important issue of driverless car. Yet, most current approaches fail to ensure safety even in a fully informed situation. In this paper we discuss how the safety criteria apply when the robot uses its on board sensors to evolve in an environment populated with static and moving obstacles. The sensors can only provide a partial and uncertain knowledge of the surroundings. We show that the usual safety notion does not apply for this relevant case and discuss which safety guarantees can be given and how to achieve them.

Path deformation is a technique that was introduced to generate robot motion wherein a path, that has been computed beforehand, is continuously deformed on-line in response to unforeseen obstacles. In an effort to improve path deformation, this paper presents a trajectory deformation scheme. The main idea is that by incorporating the time dimension and hence information on the obstaclespsila future behaviour, quite a number of situations where path deformation would fail can be handled. The trajectory represented as a space-time curve is subject to deformation forces both external (to avoid collision with the obstacles) and internal (to maintain trajectory feasibility and connectivity). The trajectory deformation scheme has been tested successfully on a planar robot with double integrator dynamics and a car-like vehicle.

An inevitable collision state (ICS) for a robotic system is a state for which, no matter what the future trajectory of the system is, a collision eventually occurs. ICS can be used for both motion planning (to reduce the search space) and reactive navigation (for obvious safety reasons, a robotic system should never ever move to an ICS). ICS are particularly suited for navigation in dynamic environments since they take into account the future behaviour of the moving objects. Using ICS in practice is difficult given the intrinsic complexity of their characterization. The main contribution of this paper is a generic and efficient ICS-Checker, ie an algorithm that determines whether a given state is an ICS or not, for planar robotic systems with arbitrary dynamics moving in dynamic environments. The efficiency is obtained by applying the following principles: (a) reasoning on 2D slices of the state space of the robotic system, (b) precomputing off-line as many things as possible, and (c) exploiting graphics hardware performances. The ICS-Checker has been applied to two different robotic systems: a car-like vehicle and a spaceship. It has also been integrated in a reactive navigation scheme to safely drive the car-like vehicle.

Motion safety for robotic systems operating in the real world is critical (especially when their size and dynamics make them potentially harmful for themselves or their environment). Motion safety is a taken-for-granted and ill-defined notion in the Robotics literature and the primary contribution of this paper is to propose three safety criteria that helps in understanding a number of key aspects related to the motion safety issue. A number of navigation schemes used by robotic systems operating in the real-world are then evaluated with respect to these safety criteria. It is established that, in all cases, they violate one or several of them. Accordingly, motion safety, especially in the presence of moving objects, cannot be guaranteed (in the sense that these robotic systems may end up in a situation where a collision inevitably occurs later in the future). Finally, it is shown that the concept of inevitable collision states introduced by Fraichard and Asama (2004) does respect the three above-mentioned safety criteria and therefore offers a theoretical answer to the motion safety issue.

An inevitable collision state (ICS) for a robotic system is a state for which, no matter what the future trajectory followed by the system is, a collision with an obstacle eventually occurs. The ICS concept takes into account both the dynamics of the robotic system and the future motion of the moving objects of the environment. For obvious safety reasons, a robotic system should never ever end up in an ICS hence the interest of the ICS concept when it comes to safely drive robotic systems in dynamic environments. In theory, determining whether a given state is an ICS requires to check for collision all possible future trajectories of infinite duration that the robotic system can follow from this particular state! In practise, it is fortunately possible to build a conservative approximation of the ICS set by considering only a finite subset of the whole set of possible future trajectories. The primary contribution of the paper is a general principle to select the subset of trajectories based upon the concept of imitating maneuvres, i.e., trajectories leading the robotic system to duplicate the behaviour of the environment objects (fixed or moving), it is shown how a good approximation of the ICS set can be obtained. The second contribution of the paper is an ICS-Checker for a car-like vehicle moving in a dynamic environment. This ICS-Checker integrates the above-mentioned selection principle. It is efficient and could be used in practise to compute truly safe motions for a car-like vehicle amidst moving objects.

Path deformation is a technique that was introduced to generate robot motion wherein a path, that has been computed beforehand, is continuously deformed on-line in response to unforeseen obstacles. This paper introduces the first trajectory deformation scheme as an effort to improve path deformation. The main idea is that by incorporating the time dimension and hence information on the obstacles' future behaviour, quite a number of situations where path deformation would fail can be handled. The trajectory deformation scheme presented operates in two steps, ie, a collision avoidance step and a connectivity maintenance step, hence its name 2-step-trajectory-deformer (2-STD). In the collision avoidance step, repulsive forces generated by the obstacles deform the trajectory so that it remains collision-free. The purpose of the connectivity maintenance step is to ensure that the deformed trajectory remains feasible, ie, that it satisfies the robot's kinematic and/or dynamic constraints. Moreover, unlike path deformation wherein spatial deformation only takes place, 2-STD features both spatial and temporal deformation. It has been tested successfully on a planar robot with double integrator dynamics moving in dynamic environments.

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

The paper addresses the problem of autonomous navigation of a car-like robot evolving in an urban environment. Such an environment exhibits an heterogeneous geometry and is cluttered with moving obstacles. Furthermore, in this context, motion safety is a critical issue. The proposed approach to the problem lies in the coupling of two crucial robotic capabilities, namely perception and planning. The main contributions of this work are the development and integration of these modules into one single application, considering explicitly the constraints related to the environment and the system

Abstract — Image segmentation is a critical task in computer vision. In the context of motion detection, a very popular segmentation approach is background substraction which consists in classifiying the pixels as background and foreground. Then, the foreground pixels are grouped together to find objects, this task is known as object extraction. There are several different approaches to object extraction (eg connected component labeling, morphological operators, size thresholding and clustering) amongst them, cluster based approaches are, probably, the ones with a stronger theoretical foundation. However, their application to object extraction is difficult because of three problems: a) need to know the number of objects to be detected beforehand, b) high sensibility to initialization due to a trend to get stuck in local minima and c) high complexity which difficults their application in real-time. This paper proposes an algorithm which aims to combine the strong theoretical foundations of clustering with the speed of other approaches. This is possible due to the introduction of a novel Self Organizing Network (SON) which has a robust initialization schema and is able to find the number of clusters in the image. The algorithm has a time complexity of order NM where N is the number of foreground pixels in the image and M is the number of nodes in the SON. I.

To reach a given goal, a mobile robot first computes a motion plan (i.e. a sequence of actions that takes it to its goal), and then executes it. Markov decision processes (MDPs) have been successfully used to solve these two problems. Their main advantage is that they provide a theoretical framework to deal with the uncertainties related to the robot's motor and perceptive actions during both planning and execution stages. While a previous paper addressed the motion planning stage, this paper deals with execution stage. It describes an approach based on Markov localization and focuses on experimental aspects, in particular, the learning of the transition function (that encodes the uncertainties related to the robot actions) and the sensor model. Experimental results carry out with a real robot demonstrate the robustness of the whole navigation approach.

This paper addresses the problem of motion planning (MP) in dynamic environments. It is first argued that dynamic environments impose a real-time constraint upon MP: it has a limited time only to compute a motion, the time available being a function of the dynamicity of the environment. Now, given the intrinsic complexity of MP, computing a complete motion to the goal within the time available is impossible to achieve in most real situations. Partial motion planning (PMP) is the answer to this problem proposed in this paper. PMP is a motion planning scheme with an anytime flavor: when the time available is over, PMP returns the best partial motion to the goal computed so far. Like reactive navigation scheme, PMP faces a safety issue: what guarantee is there that the system will never end up in a critical situation yielding an inevitable collision? The answer proposed in this paper to this safety issue relies upon the concept of inevitable collision states (ICS). ICS takes into account the dynamics of both the system and the moving obstacles. By computing ICS-free partial motion, the system safety can be guaranteed. Application of PMP to the case of a car-like system in a dynamic environment is presented.

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.

To reach a given goal, a mobile robot first computes a motion plan (if a sequence of actions that will take it to its goal), and then executes it Markov decision processes (MDPs) have been successfully used to solve these two problems. Their main advantage is that they provide a theoretical framework to deal with the uncertainties related to the robot's motor and perceptive actions during both planning and execution stages. This paper describes a MDP-based planning method that uses a hierarchic representation of the robot's state space (based on a quadtree decomposition of the environment). Besides, the actions used better integrate the kinematic constraints of a wheeled mobile robot. These two features yield a motion planner more efficient and better suited to plan robust motion strategies.

In this paper we address the problem of obstacles avoidance for car-like robots. We present a generic nonholonomic path deformation method that has been applied on two robots. The principle is to perturb the inputs of the system in order to move away from obstacles and to keep the nonholonomic constraints satisfied. We present an extension of the method to car-like robots. We have integrated the method on two robots (Dala and CyCab) and carried out experiments that show the portability and genericity of the approach.

This paper proposes a technique to obtain long term estimates of the motion of a moving object in a structured environment. Objects moving in such environments often participate in typical motion patterns which can be observed consistently. Our technique learns those patterns by observing the environment and clustering the observed trajectories using any pairwise clustering algorithm. We have implemented our technique using both simulated and real data coming from a vision system. The results show that the technique is general, produces long-term predictions and is fast enough for its use in real time applications.

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.

This paper presents Continuous Curvature (CC) Steer, a steering method for car-like vehicles, i.e., an algorithm planning paths in the absence of obstacles. CC Steer is the first to compute paths with: 1) continuous curvature; 2) upper-bounded curvature; and 3) upper-bounded curvature derivative. CC Steer also verifies a topological property that ensures that when it is used within a general motion-planning scheme, it yields a complete collision-free path planner. The coupling of CC Steer with a general planning scheme yields a path planner that computes collision-free paths verifying the properties mentioned above. Accordingly, a car-like vehicle can follow such paths without ever having to stop in order to reorient its front wheels. Besides, such paths can be followed with a nominal speed which is proportional to the curvature derivative limit. The paths computed by CC Steer are made up of line segments, circular arcs, and clothoid arcs. They are not optimal in length. However, it is shown that they converge toward the optimal "Reeds and Shepp" paths when the curvature derivative upper bound tends to infinity. The capabilities of CC Steer to serve as an efficient steering method within two general planning schemes are also demonstrated.

A prerequisite to the design of future Advanced Driver Assistance Systems for cars is a sensing system providing all the information required for high-level driving assistance tasks. Carsense is a European project whose purpose is to develop such a new sensing system. It will combine different sensors (laser, radar and video) and will rely on the fusion of the information coming from these sensors in order to achieve better accuracy, robustness and an increase of the information content. This paper demonstrates the interest of using probabilistic reasoning techniques to address this challenging multi-sensor data fusion problem. The approach used is called Bayesian Programming. It is a general approach based on an implementation of the Bayesian theory. It was introduced first to design robot control programs but its scope of application is much broader and it can be used whenever one has to deal with problems involving uncertain or incomplete knowledge.

An inevitable collision state for a robotic system can be defined as a state for which, no matter what the future trajectory followed by the system is, a collision with an obstacle eventually occurs. An inevitable collision state takes into account both the dynamics of the system and the obstacles, fixed or moving. The main contribution of this paper is to lay down and explore this novel concept (and the companion concept of inevitable collision obstacle). Formal definitions of the inevitable collision states and obstacles are given. Properties fundamental for their characterisation are established. This concept is very general and can be useful both for navigation and motion planning purposes (for its own safety, a robotic system should never find itself in an inevitable collision state). The interest of this concept is illustrated by a safe motion planning example.

A prerequisite to the design of future advanced driver assistance systems for cars is a sensing system that provides all the information required for high-level driving assistance tasks. Carsense is a European project whose purpose is to develop such a new sensing system. It combines different sensors (laser, radar and video) and relies on the fusion of the information coming from these sensors in order to achieve better accuracy, robustness and an increase of the information content. This paper demonstrates the interest of using probabilistic reasoning techniques to address this challenging multi-sensor data fusion problem. The approach used is called Bayesian programming. It is a general approach based on an implementation of the Bayesian theory. It was introduced initially to design robot control programs but its scope of application including uncertain or incomplete knowledge handling problems.

Addresses continuous-curvature path planning for cars. It presents an improved version of a previous steering method (i.e. an algorithm computing paths in the absence of obstacles) for cars and the embedding of this steering method in a global path planning scheme.

Addresses path planning with uncertainty for a car-like robot subject to configuration uncertainty. The robot estimates its configuration with odometry and an absolute localization device based on environmental feature matching. The issue is to compute safe paths that guarantee that the goal will be reached in spite of the uncertainty. The solution proposed relies upon the automatic construction of a set of landmarks characterized by (1) a region of the configuration space, (2) the 'best' features for localization in this region, and (3) a perception uncertainty field that measures how well a feature is perceived at each configuration in the region. The landmarks are used within an efficient roadmap-based path planning algorithm that returns a safe motion plan that alternates motion along safe paths and localization, operations.

This paper presents the first path planner taking into account both nonholonomic and uncertainty constraints. The case of a car-like robot subject to cumulative and unbounded configuration uncertainty related to bounded control and sensing errors is considered. Assuming the existence of landmarks allowing the robot to relocalize itself in particular places, we present an algorithm that computes paths that are both feasible and robust. In other words, they respect the nonholonomic constraints of a car-like robot and the robot is assured to reach its goal by following them, as long as its control and sensing errors remain within bounded sets.

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.

This paper presents a set of paths, called bi-elementary paths. These paths are smooth and feasible for a car-like robot (i.e. their tangent direction is continuous and they respect a minimum turning radius constraint), and they can be followed by a real vehicle without stopping (i.e. they have a continuous curvature profile)-which is not the case of Dubins' curves. These paths are composed of arcs of a clothoid (a clothoid is a curve whose curvature is a linear function of its arc length), and are used to define a simplified, i.e. non-complete, planner. This simplified planner is, in turn, used in two global planning schemes, namely the Ariadne's Clew algorithm and probabilistic path planning. This paper proves an important property of the bi-elementary paths, from which the completeness of the two global planners is deduced.

We consider path planning for a car-like vehicle. Previous solutions to this problem computed paths made up of circular arcs connected by tangential line segments. Such paths have a discontinuous curvature profile. Accordingly a vehicle following such a path has to stop at each curvature discontinuity in order to re-orientate its front wheels. To remove this limitation, we add a continuous-curvature constraint to the problem at hand. In addition, we introduce a constraint on the curvature derivative, so as to reflect the fact that a car-like vehicle can only re-orientate its front wheels with a finite velocity. We propose an efficient solution to the problem at hand that relies upon the definition of a set of paths with continuous curvature and maximum curvature derivative. These paths contain at most eight pieces, each piece being either a line segment, a circular arc of maximum curvature, or a clothoid arc. They are called simple continuous curvature paths. They are used to design a local path planner. The experimental results are presented.

This paper describes an 'execution monitor' (EM); it is the key component of a control architecture designed to provide a car-like vehicle moving in a dynamic and partially known environment with motion autonomy. Specifically EM endows the vehicle with the reactive capabilities required in an uncertain environment. Its purpose is to generate the commands for the servo-systems of the vehicle so as to follow a given nominal trajectory while reacting in real-time to unexpected events. EM is designed as a fuzzy controller, i.e. a control system based upon fuzzy logic, thus permitting approximate reasoning and a 'natural' description of the reactive behaviour of the vehicle. Besides EM differs from classical fuzzy controllers in two novel ways that improve it and allow for a partial automation of its design through the use of supervised learning. The characteristic features of EM along with the supervised learning process are presented in the paper.

This paper presents a continuous-curvature path planner (CCPP) for a car-like robot. Previous collision-free path planners for car-like robots compute paths made up of straight segments connected with tangential circular arcs. The curvature of this type of path is discontinuous so much so that if a car-like robot were to actually follow such a path, it would have to stop at each curvature discontinuity so as to reorient its front wheels. CCPP is one of the first planner to compute collision-free paths with continuous curvature profiles. These paths are made up of clothoid arcs, i.e. curves whose curvature is a linear function of their arc length. CCPP uses a general planning technique called the Ariadne's Clew algorithm. It is based upon two complementary functions: SEARCH and EXPLORE. EXPLORE builds an approximation of the region of the configuration space reachable from a start configuration by incrementally placing a set of reachable landmarks in the configuration space. SEARCH checks the existence of a solution path between a landmark newly placed and the goal configuration.

This paper addresses motion planning for a car-like robot moving in a changing planar workspace, i.e. with moving obstacles. First, this motion planning problem is formulated in the state-time space framework. The state-time space of a robot is its state space plus the time dimension. In this framework part of the constraints at hand are translated into static forbidden regions of state-time space, and a trajectory maps to a state-time curve which must respect the remaining constraints. Then an approximate solution to the problem is presented.>

This paper address dynamic trajectory planning, which is defined as trajectory planning for a robot subject to dynamic constraints and moving in a dynamic workspace, i.e., with moving obstacles. The authors propose the concept of state-time space as a tool to formulate dynamic trajectory planning problems. The state-time space of a robot is its state space augmented by the time dimension. The constraints imposed by both the moving obstacles and the dynamic constraints can be represented by static forbidden regions of state-time space. Since a trajectory maps to a curve in state-time space, dynamic trajectory planning simply consists in finding a curve in state-time space. This concept is used to determine a time-optimal trajectory for a car-like robot subject to dynamic constraints and moving along a given path on a dynamic planar workspace.

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

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