Borrowing elementary ideas from solid mechanics and differential geometry, this presentation shows that the volume swept by a regular solid undergoing a wide class of volume-preserving deformations induces a rather natural metric structure with well-defined and computable geodesics on its configuration space. This general result applies to concrete classes of articulated objects such as robot manipulators, and we demonstrate as a proof of concept the computation of geodesic paths for a free flying rod and planar robotic arms as well as their use in path planning with many obstacles.

The words used to describe robotic performances include a degree of ambiguity that the human brain should solve without difficulty. However, the language used in -and about- robotics seems to escape from the ordinary processing of lexical ambiguity resolution. In this paper, we argue that there is no lack of an adequate language for robotics but that the lexicon at hand is forced by our representations. We investigate the main representational issues of the notions that express robotic actions and dispositions (i.e. behaviors).

We present an optimization framework for the design and analysis of underactuated biped walkers, characterized by passive or actuated joints with rigid or non-negligible elastic actuation/transmission elements. The framework is based on optimal control, dealing with geometric constraints and various dynamic objective functions, as well as boundary conditions, which helps in selecting optimal values both for the actuation and the transmission parameters. Solutions of the formulated problems are shown for different kinds of bipedal architectures, and comparisons drawn between traditional rigid robots and compliant ones show the energy-efficiency of compliant actuators in the context of locomotion.

transHumUs is an artistic work recently exhibited at the 56th Venice Biennale. The work aims at freeing trees from their roots. How to translate this poetic ambition into technological terms? This paper reports on the setup and the implementation of the project. It shows how state of the art mobile robotics technology can contribute to contemporary art development. The challenge has been to design original mobile platforms carrying charges of three tones, while moving noiseless according to tree metabolism, in operational spaces populated by visitors.

This paper addresses the motion planning problem of a jumping point-robot. Each jump consists in a ballistic motion linking two positions in contact with obstacle surfaces. A solution path is thus a sequence of parabola arcs. The originality of the approach is to consider non-sliding constraints at contact points: slipping avoidance is handled by constraining takeoff and landing velocity vectors to 3D friction cones. Furthermore the magnitude of these velocities is bounded. The ballistic motion lying in a vertical plane, we transform the 3D problem into a 2D one. We then solve the motion equations. The solution gives rise to an exact steering method computing a jump path between two contact points while respecting all constraints. The method is integrated into a standard probabilistic roadmap planner. Probabilistic completeness is proven. Simulations illustrate the performance of the approach.

We present a framework capable of automatically planning and animating dynamic multi-contact jumping trajectories for arbitrary legged characters and environments. Our contribution is the introduction of an approximate yet efficient multi-contact impulse formulation, used at the motion planning phase. We combine this criterion with a heuristic for estimating the contact locations without explicitly computing them, which breaks the combinatorial aspect of contact generation. This low dimensional formulation is used to efficiently extend an existing ballistic motion planner to legged characters. We then propose a procedural method to animate the planned trajectory. Our approach thus results from a trade-off between accuracy of the law of physics and computational efficiency. We empirically justify this approach by demonstrating a large variety of behaviors for four legged characters in five scenarios.

This paper discusses the problem of estimating the position of the center of mass for a polyarticulated system (e.g., a humanoid robot or a human body), which makes contact with its environment. The only sensors providing measurements on this point are either interaction force sensors or kinematic reconstruction applied to a dynamic model of the system. We first study the observability of the center-of-mass position using these sensors and we show that the accuracy domain of each measurement can be easily described through a spectral analysis. We finally introduce an original approach based on the theory of complementary filtering to efficiently merge these input measurements and obtain an estimation of the center-of-mass position. This approach is extensively validated in simulations by using a model of a humanoid robot through which we confirm the spectral analysis of the signal errors and show that the complementary filter offers a lower average reconstruction error than the classical Kalman filter. Some experimental applications of this filter on real signals are also presented.

This paper presents a geometric approach to the problem of designing visual feedback control laws to steer a nonholonomic vehicle, equipped with a fixed monocular camera, through a gate. The originality of our approach is to introduce and exploit the natural geometry induced by the presence of a gate in the environment, e.g. bundle of hyperbolae, ellipses and circles, providing stabilizing feedback control laws that steer the vehicle through the middle of the gate. Moreover, using visual servoing we prove that this geometry can be measured directly in the camera image plane. As a consequence, we provide an image-based control scheme, avoiding the use of a state observer. Simulations in a realistic scenario and experiments are provided to show the effectiveness of our feedback control laws.

This paper presents a geometric approach to the problem of steering a robot subject to nonholonomic constraints through a door by using only visual measurements coming from a single fixed on-board monocular camera. The door is represented by two landmarks located on its vertical supports. After exploring the geometric structure that naturally emerges from the problem statement, e.g., bundle of hyperbolae, ellipses, and circles, we exploit this planar geometry to provide stabilizing feedback control laws to drive the vehicle through the middle of the door. Using visual servoing, we prove that this geometry can be directly measured in the camera image plane. Hence, we provide an image-based control scheme, avoiding the use of a state observer. Simulations in a realistic scenario and experiments are provided to show the effectiveness of the feedback control laws.

In this paper, we propose a general manipulation planner for dual-arm industrial manipulators. According to the context, the planner automatically determines whether both arms have to be used simultaneously or not. The approach is based on (i) the extension of an object placement algorithm previously developed in [23], and (ii) the introduction of several types of re-grasping motions dedicated to dual-arm manipulators. Such motions induce a special topological structure in the manipulation space that can be captured into a manipulation graph. The graph is then used to solve the manipulation problem by a simple graph search algorithm. After searching for a solution path, we further consider optimizing the path by minimizing the number of re-grasps. The effectiveness of the approach is demonstrated on the dual-arm manipulator HiroNX working in a realistic factory environment.

Passivity-based walkers represent a model for human walking and a solution for low-energy locomotion for humanoid robots. The presence of an upper-body and even a head in this kind of systems is necessary as a better model for humans and to improve their usability. The benefits of these additions have never been studied, and no work experimented the addition of a head limb to a passivity-based walker. So, we aim, in this paper, to study the effects of the addition of these modifications on walkers with fully passive lower limbs. By comparing three systems (a passive compass, an upper-body stabilizing walker and a head stabilizing walker) simulations show that: (ii) upper-body stabilization improves the stability of the walking limit cycle; (ii) in return, the stabilization of the upper body requires a noticeable amount of the kinetic energy of the walker, and a significant energy supply (steeper slopes for the passive case) is necessary to guarantee the stability of the gait, especially for the case of head stabilization; and (iii) in a dynamical context, such as steep slopes, the upper-body and head stabilization have close performances for absorbing perturbations and smoothing the impacts, but with a slight advantage for the latter.

Efficient methods to perform motion recognition have been developed using statistical tools. Those methods rely on primitive learning in a suitable space, for example, the latent space of the joint angle and/or adequate task spaces. Learned primitives are often sequential: A motion is segmented according to the time axis. When working with a humanoid robot, a motion can be decomposed into parallel subtasks. For example, in a waiter scenario, the robot has to keep some plates horizontal with one of its arms while placing a plate on the table with its free hand. Recognition can thus not be limited to one task per consecutive segment of time. The method presented in this paper takes advantage of the knowledge of what tasks the robot is able to do and how the motion is generated from this set of known controllers, to perform a reverse engineering of an observed motion. This analysis is intended to recognize parallel tasks that have been used to generate a motion. The method relies on the task-function formalism and the projection operation into the null space of a task to decouple the controllers. The approach is successfully applied on a real robot to disambiguate motion in different scenarios where two motions look similar but have different purposes.

Concurrent advancements in mechanical design and motion planning algorithms allow state-of-the-art humanoid robots to exhibit complex and realistic behavior. In face of this added complexity and the need for humanlike behavior, research has begun to look toward studies in human neuroscience to better organize and guide humanoid robot motion. In this paper, we present one such method of generating anthropomorphic motion by building the “invariants” of human movements and applying them as kinematic tasks. Whole-body motion of 14 healthy participants was recorded during a walking and grasping task. The recorded data were statistically analyzed to extract invariants which best described the observed motion. These invariants were expressed as a set of rules that were used to synthesize the stereotypy in human motion. We propose an algorithm that reproduces the key parameters of motion, taking into account the knowledge from human movement and the limitations of the target anthropomorph. The results are then generalized such that we can generate motion for targets which were not originally recorded. The algorithmic output is applied in a task-based prioritized inverse kinematics solver to generate dynamically stable and realistic anthropomorphic motion. We illustrate our results on the humanoid HRP-2 by making it walk to and grasp objects at various positions. Our approach complements classical optimization or motion-planning-based methods and provides interesting perspectives toward the use of human movements for deducing effective cost functions in optimization techniques or heuristics for planning algorithms.

This paper proposes a new framework to recover balance against external forces by combining disturbance suppression and reactive stepping. In the view point of the feedback control, a reactive step can help to diminish the disturbance caused by an external force that should be compensated to maintain balance. In other words, if the adequate step is performed, the feedback controller does not have to compensate all of the external force by itself. Under this concept, we propose an original solution to distribute the compensation between a feedback controller and a reactive step, according to the period of support phase and a disturbance characteristic. We first clearly distinguish between the role of the disturbance suppression and the reactive stepping. Then, based on this distinction, the small disturbance of external force or happening late during the single-support phase, is mainly suppressed by state feedback. The large disturbance which is out of capability by feedback controller and at the beginning of the single-support phase, is absorbed by modifying reactively the next steps. The proposed method is validated through experimental results with the HRP-2 humanoid robot.

We present a fast algorithm to approximate the swept volume (SV) boundary of arbitrary polygon soup models. Despite the extensive research on calculating the volume swept by an object along a trajectory, the efficient algorithms described have imposed constraints on both the trajectories and geometric models. By proposing a general algorithm that handles flat surfaces as well as volumes and disconnected objects, we allow SV calculation without resorting to preprocessing mesh repair nor deforming offsets. This is of particular interest in the domain of product lifecycle management (PLM), which deals with industrial computer aided design (CAD) models that are malformed more often than not. We incorporate the bounded distance operator used in path planning to efficiently sample the trajectory while controlling the total error. We develop a triangulation scheme that draws on the unique data set created by an advancing front level-set method to tessellate the SV boundary in linear time. We analyze its performance, and demonstrate its effectiveness both theoretically and on real cases taken from PLM.

The paper in question [G. Arechavaleta, J. P. Laumond, H. Hicheur, and A. Berthoz, “An optimality principle governing human walking,” IEEE Trans. Robot., vol. 24, no. 1, pp. 5-14, Feb. 2008] suggested that human-walking paths minimize variation in curvature and hence can be approximated by the solution to an optimal control problem. This conclusion was reached by analysis of experimental data based on the maximum principle. We correct two errors in this analysis and consider their consequences.

This paper proposes a unified optimization framework to solve the time-parameterization problem of humanoid-robot paths. Even though the time-parameterization problem is well known in robotics, the application to humanoid robots has not been addressed. This is because of the complexity of the kinematical structure as well as the dynamical motion equation. The main contribution of this paper is to show that the time parameterization of a statically stablepathto be transformed into a dynamically stabletrajectorywithin the humanoid-robot capacities can be expressed as an optimization problem. Furthermore, we propose an efficient method to solve the obtained optimization problem. The proposed method has been successfully validated on the humanoid robot HRP-2 by conducting several experiments. These results have revealed the effectiveness and the robustness of the proposed method.

Probabilistic path planning techniques have proven to be vital for finding and validating solutions for difficult industrial assembly tasks. Nevertheless, the failure of a path planner to find a solution to a task does not suggest how to correct the error. We suggest a methodology to identify possible bottlenecks and present an algorithm to analyze the extent to which the design must be modified in order for the task to complete successfully. We validate our algorithm on two industrial problems involving design errors, and explain how to interpret the results in order to improve the design.

We present a novel method for prioritizing both linear equality and inequality systems and provide one algorithm for its resolution. This algorithm can be summarized as a sequence of optimal resolutions for each linear system following their priority order. We propose an optimality criterion that is adapted to linear inequality systems and characterize the resulting optimal sets at every priority level. We have successfully applied our method to plan local motions for the humanoid robot HPR-2. We will demonstrate the validity of the method using an original scenario where linear inequality constraints are solved at lower priority than equality constraints.

A method of regrasp planning for humanoid robot manipulation is proposed. We adopt pivoting manipulation for the humanoid robot to move a bulky object without lifting in a stable and dexterous manner. In order to carry the object to a desired place, the humanoid should sometimes move through narrow areas surrounded by obstacles. We propose a roadmap multiplexing planning to allow the robot to leave the object near narrow places and to regrasp it from another position to continue carrying. We utilize visibility probabilistic roadmap (PRM) method as a preprocessing to capture the critical configurations for regrasping. Then a diffusion method is employed to plan the overall manipulation path including regrasping. The proposed method is verified through planning simulation including whole-body motions.

We present a novel method of guiding a humanoid robot, including stepping, by allowing a user to move its head. The motivation behind this approach comes from research in the field of human neuroscience. In human locomotion it has been found that the head plays a very important role in guiding and planning motion. We use this idea to generate humanoid whole-body motion derived purely as a result of moving the head joint. The input to move the head joint is provided by a user via a 6D mouse. The algorithm presented in this study judges when further head movement leads to instability, and then generates stepping motions to stabilize the robot. By providing the software with autonomy to decide when and where to step, the user is allowed to simply steer the robot head (via visual feedback) without worrying about stability. We illustrate our results by presenting experiments conducted in simulation, as well as on our robot, HRP2.

Abstract This paper deals with whole‐body motion planning and dynamic control for humanoid from two aspects: locomotion including manipulation and reaching. In the first part, we address a problem of simultaneous locomotion and manipulation planning that combines a geometric and kinematic motion planner with a dynamic humanoid motion generator. The second part deals with whole‐body reaching tasks by using a generalized inverse kinematics (IK) method to fully exploit the high redundancy of the humanoid robot. Through experiments using humanoid platform HRP‐2 No. 14 installed at LAAS‐CNRS, we first verify the validity of each method. An integrated experiment is then presented that unifies the both results via visual perception to execute an object‐fetching task. Copyright © 2009 John Wiley & Sons, Ltd.

Many collision detection methods exist, each specialized for certain data types under certain constraints. In order to enable rapid development of efficient collision detection procedures, we propose an extensible software architecture that allows for cross-queries between data types, while permitting the time and memory optimizations needed for high-performance. By decomposing collision detection into well-defined algorithmic and data components, we can use the same tree-descent algorithm to execute proximity queries, regardless the data type. We validate our implementation on a path planning problem in which a vision guided humanoid represented by an OBB tree explores a dynamic environment composed of voxel maps.

In this paper we consider the problem of maintaining visibility of a moving evader by a mobile robot, the pursuer, in an environment with obstacles. We simultaneously consider bounded speed for both players and a variable distance separating them. Unlike our previous efforts [R. Murrieta-Cid et al., 2007], we give special attention to the combinatorial problem that arises when searching for a solution through visiting several locations. We approach evader tracking by decomposing the environment into convex regions. We define two graphs: one is called the mutual visibility graph (MVG) and the other the accessibility graph (AG). The MVG provides a sufficient condition to maintain visibility of the evader while the AG defines possible regions to which either the pursuer or the evader may go to. The problem is framed as a non cooperative game. We establish the existence of a solution, based on a k- Min approach, for the following givens: the environment, the initial state of the evader and the pursuer, including their maximal speeds. We show that the problem of finding a solution to this game is NP-complete.

In this paper, the imitation of human captured motions by a humanoid robot is considered. The main objective is to reproduce an imitated motion which should be as close as possible to the original human captured motion. To achieve this goal, the imitation problem is formulated as an optimization problem and the physical limits of the humanoid robot are considered as constraints. The optimization problem is then solved recursively by using an efficient dynamics algorithm, which allows the calculation of the gradient function with respect to the control parameters analytically. The simulation results using OpenHRP platform, which is a dynamical simulator for humanoid robot motions, have pointed out that the imitated motions preserve the salient characteristics of the original human captured motion. Moreover the optimization procedure converges well thanks to the analytical calculation of the gradient function.

This paper emphasizes on the capacity of a humanoid robot to perform tasks that are difficult for other types of robots. It deals with manipulation of bulky objects. Such tasks require complicated manipulations involving the whole-body and fine coordination between legs, arms and torso motions. We introduce here a whole-body motion planner that allows a humanoid robot to autonomously plan a pivoting strategy that accounts for the various constraints: collision avoidance, legs-arms coordination and stability control. Based on a previous result by the authors [1] proving the small-time controllability of a pivoting system, the planner is proven to inherit from the probabilistic completeness of the samplingbased motion planning method it is built on. The geometric and kinematic capacity of the proposed planner is mainly demonstrated through simulations and experiments.

This paper proposes an whole body motion planning method for humanoid robots in which dynamics is integrated. The method consists of two stages. A collision-free and statically stable path is planned in the first stage and it is transformed into a dynamically stable trajectory in the second stage. Contributions of the method is summarized as follows. (1) A local method plans a C1path while avoiding collisions between non-strictly convex objects. (2) The second stage gives the minimum time trajectory by time parameterization under dynamic balance constraints. (3) Any path reshaping for recovering collision-freeness is not required since the second stage doesnpsilat change shape of the path. Effectiveness of the method is examined by applying it to scenarios of a humanoid robot HRP-2.

In this paper, we investigate different possible strategies underlying the formation of human locomotor trajectories in goal-directed walking. Seven subjects were asked to walk within a motion capture facility from a fixed starting point and direction, and to cross over distant porches for which both position and direction in the room were changed over trials. Stereotyped trajectories were observed in the different subjects. The underlying idea to attack this question has been to relate this problem to an optimal control scheme: the trajectory is chosen according to some optimization principle. This is our basic starting assumption. The subject being viewed as a controlled system, we tried to identify several criteria that could be optimized. Is it the time to perform the trajectory? The length of the path? The minimum jerk along the path? We found that the variation (time derivative) of the curvature of the locomotor paths is minimized. Moreover, we show that the human locomotor trajectories are well approximated by the geodesics of a differential system minimizing the norm of the control. Such geodesics are made of arcs of clothoids. The clothoid or Cornu spiral is a curve, whose curvature grows with the distance from the origin.

We propose a general and practical planning framework for generating 3-D collision-free motions that take complex robot dynamics into account. The framework consists of two stages that are applied iteratively. In the first stage, a collision-free path is obtained through efficient geometric and kinematic sampling-based motion planning. In the second stage, the path is transformed into dynamically executable robot trajectories by dedicated dynamic motion generators. In the proposed iterative method, those dynamic trajectories are sent back again to the first stage to check for collisions. Depending on the application, temporal or spatial reshaping methods are used to treat detected collisions. Temporal reshaping adjusts the velocity, whereas spatial reshaping deforms the path itself. We demonstrate the effectiveness of the proposed method through examples of a space manipulator with highly nonlinear dynamics and a humanoid robot executing dynamic manipulation and locomotion at the same time.

We present a fast GPU-based algorithm to approximate the swept volume (SV) boundary of arbitrary polygon soup models. Despite the extensive research on calculating the volume swept by an object along a trajectory, the efficient algorithms described have imposed constraints on both the trajectories and geometric models. By proposing a general algorithm that handles flat surfaces as well as volumes and disconnected objects, we allow SV calculation without resorting to pre-processing mesh repair. This is of particular interest in the domain of product lifecycle management (PLM), which deals with industrial computer aided design (CAD) models that are malformed more often than not. We incorporate the bounded distance operator used in path planning to efficiently sample the trajectory while controlling the total error. We develop a triangulation scheme that draws on the unique data set created by an advancing front level-set method to tessellate the SV boundary in linear time. We analyze its performance, and demonstrate its effectiveness both theoretically and on real cases taken from PLM.

Pivoting manipulation has such advantages as dexterity and safety over other methods to move bulky or heavy objects. In this paper we aim to show that a polyhedral object can be displaced to arbitrary position and orientation on a plane (i.e. such a pivoting system is controllable). More than that we show it is small time controllable, i.e. the reachable space from a starting point contains always a neighbor no matter how cluttered the environment is. As a consequence of this analysis, we propose a steering method to plan a manipulation path to be performed by a humanoid robot: first we use a classical nonholonomic path planner that accounts for the robot motion constraints, and then we transform that path into a sequence of pivoting operations. While the feasibility of elementary pivoting tasks has been already experienced by the humanoid robot HRP-2, we present here the very first simulations of the plans generated by our steering method.

Synthesizing human motion signals is difficult because of its multi-dimensional and nonlinear nature. However, the locomotion is a synchronized motion, which means that these signals are related. Using this property, we propose a new method for modeling the human locomotion and identifying this model. The input signals of our model is the trajectory of pelvis and the outputs are corresponding motion signals of whole human body. To identify this system, we considered it as black-box, for which we propose an adapted method of identification using motion capture. We show that the identified model allows to generate various human locomotion in a fast and efficient way

In this paper we address smooth and collision-free whole-body motion planning for humanoid robots. A two-stage iterative planning framework is introduced where geometric motion planner and dynamic pattern generator interacts by exchanging the trajectory, to obtain 3D whole-body dynamic motions simultaneous tasks including locomotion, in complex environments. We propose a practical method for smooth motion reshaping to avoid collisions in generated dynamic motion. Based on motion editing techniques in computer graphics animation, smooth collision-avoiding motion is generated through trajectory deformation. The validity of the proposed reshaping method is verified by computer simulations and experiments using humanoid platform HRP-2

Abstract This paper introduces a framework for real‐time simulation and rendering of crowds navigating in a virtual environment. The solution first consists in a specific environment preprocessing technique giving rise to navigation graphs, which are then used by the navigation and simulation tasks. Second, navigation planning interactively provides various solutions to the user queries, allowing to spread a crowd by individualizing trajectories. A scalable simulation model enables the management of large crowds, while saving computation time for rendering tasks. Pedestrian graphical models are divided into three rendering fidelities ranging from billboards to dynamic meshes, allowing close‐up views of detailed digital actors with a large variety of locomotion animations. Examples illustrate our method in several environments with crowds of up to 35 000 pedestrians with real‐time performance. Copyright © 2006 John Wiley & Sons, Ltd.

Abstract Virtual mannequins need to navigate in order to interact with their environment. Their autonomy to accomplish navigation tasks is ensured by locomotion controllers. Control inputs can be user‐defined or automatically computed to achieve high‐level operations (e.g. obstacle avoidance). This paper presents a locomotion controller based on a motion capture edition technique. Controller inputs are the instantaneous linear and angular velocities of the walk. Our solution works in real time and supports at any time continuous changes of inputs. The controller combines three main components to synthesize locomotion animations in a four‐stage process. First, the Motion Library stores motion capture samples. Motion captures are analysed to compute quantitative characteristics. Second, these characteristics are represented in a linear control space. This geometric representation is appropriate for selecting and weighting three motion samples with respect to the input state. Third, locomotion cycles are synthesized by blending the selected motion samples. Blending is done in the frequency domain. Lastly, successive postures are extracted from the synthesized cycles in order to complete the animation of the moving mannequin. The method is demonstrated in this paper in a locomotion‐planning context. Copyright © 2006 John Wiley & Sons, Ltd.

This paper presents an approach to automatically compute animations for virtual (human-like and robot) characters cooperating to move bulky objects in cluttered environments. The main challenge is to deal with 3D collision avoidance while preserving the believability of the agent's behaviors. To accomplish the coordinated task, a geometric and kinematic decoupling of the system is proposed. This decomposition enables us to plan a collision-free path for a reduced system, then to animate locomotion and grasping behaviors independently, and finally to automatically tune the animation to avoid residual collisions. These three steps are applied consecutively to synthesize an animation. The different techniques used, such as probabilistic path planning, locomotion controllers, inverse kinematics and path planning for closed kinematic chains are explained, and the way to integrate them into a single scheme is described.

This paper shows how to compute the nonholonomic distance between a polygonal car-like robot and polygonal obstacles. The solution extends previous work of Reeds and Shepp by finding the shortest path to a manifold (rather than to a point) in configuration space. Based on optimal control theory, the proposed approach yields an analytic solution to the problem

This paper deals with motion planning algorithms for the large space robot manipulators with complicated dynamic behavior. We propose two "two-stage" iterative algorithms, which provide collision-free robot motion taking into account robot's dynamics. The approach is based on new efficient methods for robot manipulator dynamics simulation and probabilistic methods for motion planning in highly cluttered environments. The algorithms are applicable for the robot manipulators of general class with arbitrary kinematics and dynamics parameters. We have demonstrated the approach for a particular task of servicing the satellite by a large space manipulator. This task is one of the most challenging since large space manipulators have extremely complicated dynamic behavior caused by elasticity of their structure, huge payloads they work with and zero-gravity conditions. Experiments involving a 15.5 meters long manipulator carrying a satellite inside a space shuttle with clearance less than 3 cm are presented. Several movies demonstrate the results.

In this paper we consider the problem of maintaining surveillance of a moving the target by a nonholonomic mobile observer. The observer's goal is to maintain visibility of the target from a predefined, fixed distance, l. The target escapes if (a) it moves behind an obstacle to occlude the observer's view, (b) it causes the observer to collide with an obstacle, or (c) it exploits the nonholonomic constraints on the observer motion to increase its distance from the observer beyond the surveillance distance l. We deal specifically with the situation in which the only constraint on the target's velocity is a bound on speed (i.e., there are no nonholonomic constraints on the target's motion), and the observer is a nonholonomic, differential drive system having bounded speed. We develop the system model, from which we derive a lower bound for the required observer speed. Finally, we consider the effect of obstacles on the observer's ability to successfully track the target.

The paper presents an efficient collision-free path planner for mechanical part disassembly simulation. The principle of the algorithm involves computing a first path while allowing some penetration within the obstacles. Then the current paths are iteratively re-shaped by decreasing the allowed penetration threshold. The process is controlled by a dynamic collision checker. The cases of failure of the iterative process are automatically detected and solved.

This paper presents a motion planner for a digital mannequin carrying objects in cluttered environments. The goal is to account for 3-dimensional obstacle avoidance, eye-convincing locomotion as well as manipulation constraints within an integrated motion planning approach. This approach combines probabilistic path planning methods, a motion capture based walking controller and inverse kinematics techniques.

This paper presents some evolutions over the locomotion planning problem for digital actors. The solution is based both on probabilistic motion planning and on motion capture blending and warping. The paper particularly focuses on a new collision avoidance technique: while the legs and the pelvis of the digital actor follow a planned path, the animation of the upper part of the body is updated for 3D collision avoidance purposes.

Closed kinematic chains in mechanical systems represent a challenge for their motion analysis, and therefore, for path planning. Closed mechanisms appear in different areas where path planning algorithms are applied. We propose a method to handle them within probabilistic roadmap (PRM) techniques. This method is an extension of the approach proposed by Han et al. (2000). Our main contribution concerns the generation of random configurations. The structure of the mechanism is analyzed in a preprocessing step. Then, in the roadmap construction phase, an algorithm called the random loop generator uses data from this analysis. This algorithm increases the probability of randomly generating valid configurations of the closed mechanism. Experimental results demonstrate the efficiency of the approach.

This paper addresses the manipulation planning problem which deals with motion planning for robots manipulating movable objects among static obstacles. We propose a manipulation planner capable of handling continuous domains for modeling both the possible grasps and the stable placements of a single movable object, rather than discrete sets generally assumed by the existing planners. The algorithm relies on a topological property that characterizes the existence of solutions in the subspace of configurations where the robot grasps the object placed at a stable position. This property leads to reduce the problem by structuring the search-space. It allows us to devise a manipulation planner that directly captures in a probabilistic roadmap the connectivity of sub-dimensional manifolds of the composite configuration space. First experiments demonstrate the feasibility and the efficiency of the approach.

This paper presents a method for animating human characters, especially dedicated to walk planning problems. The method is integrated in a randomized motion planning scheme, including a steering method dedicated to human walk. This steering method integrates a character motion controller assuming realistic animations. The navigation of the character through a virtual environment is modeled as a composition of Bezier curves. The controller is based on motion capture data editing techniques. This approach satisfies some essential computer graphics criteria: a realistic result, a low response time, a collision-free motion in possibly constrained 3D environments. The approach has been implemented and successfully demonstrated on several examples.

Presents a geometry-based approach for multiple mobile robot motion coordination. The problem is to coordinate the motions of several robots moving along fixed independent paths to avoid mutual collisions. The proposed algorithm is based on a bounding box representation of the obstacles in the so-called coordination diagram. The algorithm is resolution-complete but it is shown to be complete for a large class of inputs. Despite the exponential dependency of the coordination problem, the algorithm efficiently solves problems involving up to ten robots in worst-case situations and more than 100 robots in practical ones.

Reports on our current effort for applying probabilistic path planning techniques to logistics and operation in huge industrial installations (e.g., power plants). We show how the specific domain constraints impose a dedicated software architecture to take advantage of the generality of probabilistic approaches. In addition, such an architecture should be compatible with existing CAD systems making critical the interface issues. We conclude with three study cases currently under development within the European project MOLOG.

Presents a variant of a probabilistic approach to motion planning. The objective is to face large, complex industrial environments for maintenance purpose. The contribution is based on a structuring of the workspace into boxes that limits the size of the graph to be searched. The algorithm was integrated in a commercial CAD system and real-size experiments are presented.

Existing methods for nonholonomic motion planning can only be applied to exactly nilpotentizable or flat systems. For nonholonomic systems that do not fall into the above classes, we conjecture that globally defined nilpotent approximations will allow the synthesis of efficient steering and stabilization strategies. In the paper, a car towing two off-hooked trailers is considered as a case study. First, it is shown how to derive a nilpotent approximation that is valid in the neighborhood of both regular and singular points. Then, such approximate model is used to compute steering controls. Simulation results are reported to show the satisfactory performance of the method.

Presents a variant of probabilistic roadmap algorithms that appeared as a promising approach to motion planning. We exploit a free-space structuring of the configuration space into visibility domains in order to produce small roadmaps. The algorithm has been implemented within a software platform allowing us to address a large class of mechanical systems. Experiments show the efficiency of the approach in capturing narrow passages of collision-free configuration spaces.

This paper deals with motion planning and control for mobile robots. The various components of an integrated architecture for the mobile robot Hilare pulling a trailer are presented. The nonholonomic path planner is based on an original steering method accounting for the small-time controllability of the system. Then the path is transformed into a trajectory by including the dynamical constraints of the system (bounded velocity and bounded acceleration). Finally, the motion control is addressed. Due to the geometric transformation for a virtual robot, we show how to reduce the problem to a classical approach of trajectory tracking for a mobile robot moving forward only. The experimental results presented include two types of robot-trailer connection systems.

This paper shows how to compute the nonholonomic distance between a pointwise car-like robot and polygonal obstacles. Geometric constructions to compute the shortest paths from a configuration (given orientation and position in the plane of the robot) to a position (i.e., a configuration with unspecified final orientation) are first presented. The geometric structure of the reachable set (set of points in the plane reachable by paths of given length /spl Lscr/) is then used to compute the shortest paths to straight-line segments. Obstacle distance is defined as the length of such shortest paths. The algorithms are developed for robots that can move both forward and backward (Reeds and Shepp's car) or only forward (Dubins' car). They are based on the convexity analysis of the reachable set.

This paper presents a robust method to control a mobile robot towing a trailer. Both problems of trajectory tracking and steering to a given configuration are addressed. This second issue is solved by an iterative trajectory tracking. Perturbations are taken into account along the motions. Experimental results on the mobile robot Hilare illustrate the validity of our approach.

This paper deals with distance computation between a forward moving car-like robot and polygonal obstacles. We propose efficient geometric algorithms to compute the shortest paths to obstacles. We then derive the "visibility" domain in the presence of obstacles, i.e. the set of positions reachable from a starting configuration, by a collision-free shortest path unaffected by the presence of the obstacles.

The paper presents a geometric algorithm dealing with collision checking in the framework of multiple mobile robot coordination. We consider that several mobile robots have planned their own collision-free path by taking into account the obstacles, but ignoring the presence of other robots. We first compute the domain swept by each robot when moving along its path - such a domain is called a trace. Then the algorithm computes the coordination configurations for one robot with respect to the others, i.e. the configurations along the path where the robot enters the traces of the other robots or exits from them. This information may be exploited to coordinate the motions of all the robots.

Deals with nonholonomic motion planning including obstacle avoidance capabilities. We show that the methods developed in the absence of obstacles can be extended to the problem of obstacle avoidance, provided that they verify a topological property. Such steering methods allow us to design exact and complete collision-free path planners for a large family of systems. We show that the steering method using sinusoidal inputs applied to chained form systems fulfills the required conditions, and we illustrate its integration in collision-free path planning schemes through the tractor-trailers example.

A method combining planning and reactive control for car-like nonholonomic mobile robots is discussed. Firstly, a "bubble" for a car-like mobile robot is defined as the locally reachable space from a given configuration considering the obstacles and using the appropriate metric. Then a flexible feasible trajectory, based on the elastic band concepts, is constructed. This trajectory is smoothed using Bezier curves satisfying a minimum curvature constraint, and a parameterization is proposed which satisfies the robot kinematics constraints.

This paper describes a real experiment in nonholonomic motion planning and control. It was performed on the mobile robot Hilare-2-bis pulling a trailer.

Several schemes have been proposed in the path planning literature to plan collision-free and feasible trajectories for nonholonomic mobile robots. A classical scheme is the two-step approach which consists in first computing a collision-free holonomic path, and then in transforming this path by a sequence of feasible ones. The quality of the solution and the computational cost of the second step depend on the shape of the holonomic path. In this paper, we introduce a nonholonomic cost of the geometric path to be approximated and we propose a configuration space structuring that allows us to compute an holonomic path minimizing at best the nonholonomic cost. The algorithms have been implemented and we present simulation results which illustrate the efficacy of the planner to produce good solutions with respect to the nonholonomic constraints of a mobile robot.

This paper gives an account of the convergence property of potential field based path planning algorithms that use random motions to escape local minima. Their probabilistic convergence is proved and we provide a finite estimate of the convergence time. The proof is based on the study of Markov chains and diffusion processes.

This paper deals with nonholonomic motion planning including obstacle avoidance capabilities. We show that the methods developed in absence of obstacles can be extended to the problem of obstacle avoidance, provided that they verify a topological property. This property is proved for the method using sinusoidal inputs applied to chained form systems, and illustrated through the tractor-trailer example.

Clothoids are very useful for smoothing the motion of a mobile robot moving along a trajectory. This paper addresses the problem of smoothing mobile robot motions when cusps, i.e., changes of motion direction along the trajectory, are imposed. We pinpoint some special curves (that we call "anticlothoids") and we discuss how they can be used together with clothoids in order to smooth a predefined trajectory.>

We calculate the partition of the configuration space R/sup 2//spl times/S/sup 1/ of a car-like robot, only moving forwards, with respect to the type of the length optimal paths. This kind of robot is subject to kinematic constraints on its path curvature and its orientation. Starting from the results on shortest paths, we give new optimality conditions on these paths, and compute the partition for any horizontal plane of the configuration space.>

This paper considers the problem of motion planning for a car-like robot (i.e., a mobile robot with a nonholonomic constraint whose turning radius is lower-bounded). We present a fast and exact planner for our mobile robot model, based upon recursive subdivision of a collision-free path generated by a lower-level geometric planner that ignores the motion constraints. The resultant trajectory is optimized to give a path that is of near-minimal length in its homotopy class. Our claims of high speed are supported by experimental results for implementations that assume a robot moving amid polygonal obstacles. The completeness and the complexity of the algorithm are proven using an appropriate metric in the configuration space R/sup 2//spl times/S/sup 1/ of the robot. This metric is defined by using the length of the shortest paths in the absence of obstacles as the distance between two configurations. We prove that the new induced topology and the classical one are the same. Although we concentrate upon the car-like robot, the generalization of these techniques leads to new theoretical issues involving sub-Riemannian geometry and to practical results for nonholonomic motion planning.>

Deals with the computation of the shortest path metric for a nonholonomic car-like robot. Bounds on the length d/sub RS/(o,c) of the shortest path linking the configuration o=(0,0,0) to any configuration c=(x,y,/spl theta/) .

Shows how to compute the region of accessibility for a model of a car that moves forwards and backwards with a lower bounded turning radius and a constant velocity. This problem deals with the computation of the shortest paths when the starting configuration i.e., position and direction, is completely specified and the goal is only defined by a position letting free the direction. The authors first exhibit the shortest path for any goal position and show its uniqueness. Then they compute the boundary of the region reachable by such paths. Such regions are useful in motion planning for a nonholonomic mobile robot.

This paper presents a proof of controllability for a multibody mobile robot (e.g., a car pulling and pushing trailers like a luggage carrier in an airport). Such systems appear as canonical systems to illustrate the tools from differential geometric control theory required by nonholonomic motion planning. Three modeling steps are considered: geometric, differential, and control steps. The author derives the kinematic equations for four distinct multibody mobile robot systems: a convoy driven by 1) a unicycle, 2) a two-driving wheels vehicle, 3) a real car and 4) the first two bodies. He shows that these four control systems correspond to the same differential model, which is then used to give the same proof of controllability. Previous work proved the controllability of two-body systems and three-body systems. The main result of this paper is prove the controllability for a general n-body system.>

The authors address the motion planning problem for a robot and a movable object within polygonal obstacles. Motion planning in this context appears as a constrained instance of the coordinated motion planning problem for two robots. The object cannot move itself, it only does when the robot grasps it. A topological property that characterizes the existence of solutions in the subspace of configurations where the robot touches the object is discussed. This property provides a general resolution scheme which is applied to the special case of a convex polygonal robot moving in translation with a convex polygonal object amidst polygonal obstacles. The algorithm has been implemented, and experimental results are discussed.>

The authors introduce space structuring based on the applicability of different path planning methods as a promising way to improve efficiency in mobile robot path planning. They present a preprocessing of the environment populated with simple polygonal obstacles aimed at the early discovery of a collision-free path for a mobile robot among obstacles between a start configuration and a goal configuration in cluttered environments, prior to the application of a path planning method. The preprocessing is done only once for one robot and one environment. Space structuring is based on obstacle growing with circles relative to the robot. Experimental results show the practicality of the method.>

Methods for steering car-like robots with trailers are investigated. A connection is demonstrated between Murray and Sastry's (1990, 1991) work of steering with integrally related sinusoids and Sussmann and Liu's (1991) recent work on asymptotic behavior of systems with high-frequency sinusoids as inputs. The merits of coordinate transformations, relative to the convergence properties, are discussed. Simulation results for a car-like robot with two trailers are presented.>

A technique for stabilizing nonholonomic systems to trajectories is presented. It is well known that such systems cannot be stabilized to a point using smooth static-state feedback. The authors suggest the use of control laws for stabilizing a system about a trajectory, instead of a point. Given a nonlinear system and a desired nominal feasible trajectory, an explicit control law which will locally exponentially stabilize the system to the desired trajectory is given. The theory is applied to several examples, including a car-like robot.>

Deals with the problem of motion planning for a car-like robot (i.e. a nonholonomic mobile robot whose turning radius is lower bounded). The authors present a fast and exact planner based upon recursive subdivisions of a collision-free path generated by a lower-level geometric planner which ignores the motion constraints. The resultant trajectory is optimized to give a path which is of near-minimal length in its homotopy class. The claims of high speed are supported by experimental results for several implementations which assume different geometric models of the robot.>

Deals with methods using approximate cells decomposition of the configuration space in path planning for mobile robots in the plane. It is shown that optimal decomposition can be attained in the case of a polygonal robot amidst convex polygonal obstacles by choosing as reference point the center of the ring of minimal surface enclosing the robot, and gives as main result the position of this reference point.>

In order to understand its environment, a mobile robot should be able to model consistently this environment, and to locate itself correctly. One major difficulty to be solved is the inaccuracies introduced by the sensors. The approach proposed in this paper to cope with this problem relies on 1) defining general principles to deal with uncertainties : the use of a multisensory system, favo ring of the data collected by the more accurate sensor in a given situation, averaging of different but consistent measurements of the same entity weighted with their associated uncertainties, and 2) a methodology enabling a mobile robot to define its own reference landmarks while exploring its environment. These ideas are presented together with an example of their application on the mobile robot HILARE.