Task and Motion Planning (TAMP) is a computationally challenging robotics problem due to the tight coupling of discrete symbolic planning and continuous geometric planning of robot motions. In particular, planning manipulation tasks in complex 3D environments leads to a large number of costly geometric planner queries to verify the feasibility of considered actions and plan their motions. To address this issue, we propose Geometric Reasoning Networks (GRN), a graph neural network (GNN)-based model for action and grasp feasibility prediction, designed to significantly reduce the dependency on the geometric planner. Moreover, we introduce two key interpretability mechanisms: inverse kinematics (IK) feasibility prediction and grasp obstruction (GO) estimation. These modules not only improve feasibility predictions accuracy, but also explain why certain actions or grasps are infeasible, thus allowing a more efficient search for a feasible solution. Through extensive experimental results, we show that our model outperforms state-of-the-art methods, while maintaining generalizability to more complex environments, diverse object shapes, multi-robot settings, and real-world robots.

Taking into account the effects of parameter uncertainties in the robot model is crucial to the robustness of motion generation. One approach to address this issue is to compute ‘uncertainty tubes’ enveloping the robot state for any combination of parameters within a given range, and to use these tubes to robustly check for collisions within a motion planning algorithm. However, computing these tubes for complex dynamical systems can be too computationally expensive due to the need to solve and integrate potentially numerous nonlinear ordinary differential equations (ODEs) associated with robot dynamics. To overcome this limitation, we propose a GRU-based architecture that provides fast and accurate estimation of these uncertainty tubes. We demonstrate that GRUs achieve the best compromise between prediction accuracy, prediction time, and network size compared to basic RNNs and LSTMs, justifying our choice. Finally, we showcase the efficiency of the learning process within a motion planning framework for an aerial vehicle.

The hybrid discrete/continuous nature of task and motion planning (TAMP) results often in a combinatorial explosion. This challenge is even more pronounced in multi-robot TAMP problems due to the increase in dimensionality of the action space. Previous works use action feasibility prediction as a heuristic to accelerate TAMP. However, these methods are limited to box-shaped objects and specific single or dual robot settings. In this paper, we propose a feasibility-enabled multi-robot TAMP algorithm capable of tackling complex multi-robot manipulation problems. Also, we expand on our previous work on action and grasp feasibility prediction [1] by extending its use to mesh-shaped objects. We demonstrate the performance of our method compared to a non feasibility-informed baseline, and show its ability to handle TAMP problems requiring the collaboration of multiple robots.

In Task and motion planning (TAMP), symbolic search is combined with continuous geometric planning. A task planner finds an action sequence while a motion planner checks its feasibility and plans the corresponding sequence of motions. However, due to the high combinatorial complexity of discrete search, the number of calls to the geometric planner can be very large. Previous works [1] [2] leverage learning methods to efficiently predict the feasibility of actions, much like humans do, on tabletop scenarios. This way, the time spent on motion planning can be greatly reduced. In this work, we generalize these methods to 3D environments, thus covering the whole workspace of the robot. We propose an efficient method for 3D scene representation, along with a deep neural network capable of predicting the probability of feasibility of an action. We develop a simple TAMP algorithm that integrates the trained classifier, and demonstrate the performance gain of using our approach on multiple problem domains. On complex problems, our method can reduce the time spent on geometric planning by up to 90%.

Closed-loop state sensitivity [1], [2] is a recently introduced notion that can be used to quantify deviations of the closed-loop trajectory of a robot/controller pair against variations of uncertain parameters in the robot model. While local optimization techniques are used in [1], [2] to generate reference trajectories minimizing a sensitivity-based cost, no global planning algorithm considering this metric to compute collision-free motions robust to parametric uncertainties has yet been proposed. The contribution of this paper is to propose a global control-aware motion planner for optimizing a state sensitivity metric and producing collision-free reference motions that are robust against parametric uncertainties for a large class of complex dynamical systems. Given the prohibitively high computational cost of directly minimizing the state sensitivity using asymptotically optimal sampling-based tree planners, the proposed RRT*-based SAMP planner uses an appropriate steering method to first compute a (near) time-optimal and kinodynamically feasible trajectory that is then locally deformed to improve robustness and decrease its sensitivity to uncertainties. The evaluation performed on planar/full-3D quadrotor UAV models shows that the SAMP method produces low sensitivity robust solutions with a much higher performance than a planner directly optimizing the sensitivity.

In this paper, we address task and motion plan-ning (TAMP) which is an important yet challenging robotics problem. It is known to suffer from the high combinatorial complexity of discrete search, often requiring a large number of geometric planning calls. We build upon recent works in TAMP by taking advantage of learning methods to provide action feasibility information as a heuristic to the symbolic planner, thus guiding it to a geometrically feasible solution and reducing geometric planning time. We propose AGFP-Net, a multi-task neural network predicting not only action feasibility, but also the feasibility of a set of grasp types. We also propose an improved feasibility-informed TAMP algorithm capable of solving more complex problems, and handling goals which are not fully specified. Comparative results obtained on different problems of varying complexity show that our method is able to greatly reduce task and motion planning time.

SUMMARY: MoMA-LoopSampler is a sampling method that globally explores the conformational space of flexible protein loops. It combines a large structural library of three-residue fragments and a novel reinforcement-learning-based approach to accelerate the sampling process while maintaining diversity. The method generates a set of statistically likely loop states satisfying geometric constraints, and its ability to sample experimentally observed conformations has been demonstrated. This paper presents a web user interface to MoMA-LoopSampler through the illustration of a typical use-case. AVAILABILITY AND IMPLEMENTATION: MoMA-LoopSampler is freely available at: https://moma.laas.fr/applications/LoopSampler/. We recommend users to create an account, but anonymous access is possible. In most cases, jobs are completed within a few minutes. The waiting time may increase depending on the server load, but it very rarely exceeds an hour. For users requiring more intensive use, binaries can be provided upon request. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

MOTIVATION: Loop portions in proteins are involved in many molecular interaction processes. They often exhibit a high degree of flexibility, which can be essential for their function. However, molecular modeling approaches usually represent loops using a single conformation. Although this conformation may correspond to a (meta-)stable state, it does not always provide a realistic representation. RESULTS: In this paper, we propose a method to exhaustively sample the conformational space of protein loops. It exploits structural information encoded in a large library of three-residue fragments, and enforces loop-closure using a closed-form inverse kinematics solver. A novel reinforcement-learning-based approach is applied to accelerate sampling while preserving diversity. The performance of our method is showcased on benchmark datasets involving 9-, 12- and 15-residue loops. In addition, more detailed results presented for streptavidin illustrate the ability of the method to exhaustively sample the conformational space of loops presenting several meta-stable conformations. AVAILABILITY AND IMPLEMENTATION: We are developing a software package called MoMA (for Molecular Motion Algorithms), which includes modeling tools and algorithms to sample conformations and transition paths of biomolecules, including the application described in this work. The binaries can be provided upon request and a web application will also be implemented in the short future. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

The study of the conformational energy landscape of a molecule is essential for the understanding of its physicochemical properties . This requires the exploration of a continuous, high-dimensional space to identify the most probable conformations and the transition paths between them. The problem is computationally difficult, in particular for highly-flexible biomolecules such as Intrinsically Disordered Proteins (IDPs). In recent years, a robotics-inspired algorithm called Transition-based Rapidly-exploring Random Tree (TRRT) has been proposed to solve this problem, and has been shown to provide good results with small and middle-sized biomolecules. Aiming to treat larger systems, we propose a hybrid strategy for the efficient parallelization of a multi-tree variant of TRRT, called Multi-TRRT, enabling an efficient execution in (possibly large) computer clusters. The parallel algorithm uses OpenMP multi-threading for computation inside each multi-core processor and MPI to perform the communication between processors. Results show a near-linear speedup for a wide range of cluster configurations. Although the paper mainly deals with the application of the proposed parallel algorithm to the investigation of biomolecules, the explanations concerning the methods are general, aiming to inspire future work on the parallelization of related algorithms.

Sampling-based algorithms for path planning, such as the Rapidly-exploring Random Tree (RRT), have achieved great success, thanks to their ability to efficiently solve complex high-dimensional problems. However, standard versions of these algorithms cannot guarantee optimality or even high-quality for the produced paths. In recent years, variants of these methods, such as T-RRT, have been proposed to deal with cost spaces: by taking configuration-cost functions into account during the exploration process, they can produce high-quality (i.e., low-cost) paths. Other novel variants, such as RRT*, can deal with optimal path planning: they ensure convergence toward the optimal path, with respect to a given path-quality criterion. In this paper, we propose to solve a complex problem encompassing this two paradigms: optimal path planning in a cost space. For that, we develop two efficient sampling-based approaches that combine the underlying principles of RRT* and T-RRT. These algorithms, called T-RRT* and AT-RRT, offer the same asymptotic optimality guarantees as RRT*. Results presented on several classes of problems show that they converge faster than RRT* toward the optimal path, especially when the topology of the search space is complex and/or when its dimensionality is high.

The overall performance of sampling-based motion planning algorithms strongly depends on the use of suitable sampling and connection strategies, as well as on the accuracy of the distance metric considered to select neighbor states. Defining appropriate strategies and metrics is particularly hard when considering robot dynamics, which is required to treat constrained motion planning problems for quadrotors. This paper presents an accurate but computationally fast quasi-metric to determine the proximity of dynamic states of a quadrotor, and an incremental state-space sampling technique to avoid generating local trajectories that violate kinodynamic constraints. Results show that the integration of the proposed techniques in RRT-based and PRM-based algorithms can drastically decrease computing time, up to two orders of magnitude.

Obtaining accurate representations of energy landscapes of biomolecules such as proteins and peptides is central to structure-function studies. Peptides are particularly interesting, as they exploit structural flexibility to modulate their biological function. Despite their small size, peptide modeling remains challenging due to the complexity of the energy landscape of such highly-flexible dynamic systems. Currently, only sampling-based methods can efficiently explore the conformational space of a peptide. In this paper, we suggest to combine two such methods to obtain a full characterization of energy landscapes of small yet flexible peptides. First, we propose a simplified version of the classical Basin Hopping algorithm to quickly reveal the meta-stable structural states of a peptide and the corresponding low-energy basins in the landscape. Then, we present several variants of a robotics-inspired algorithm, the Transition-based Rapidly-exploring Random Tree, to quickly determine transition state and transition path ensembles, as well as transition probabilities between meta-stable states. We demonstrate this combined approach on the terminally-blocked alanine.

Planning physically realistic and easily controllable motions of flying robots requires considering dynamics. This paper presents a local trajectory planner, based on a simplified dynamic model of quadrotors, which fits the requirements to be integrated into a global motion planning approach. It relies on a closed-form solution to compute curves in the kinodynamic state space that tend to minimize the flying time. These curves have suitable continuity properties and guarantee respect of physical limits of the system (i.e. bounds for the time-derivatives of the pose coordinates). The paper explains how this local planner can be used within different motion planning approaches that enable the treatment of difficult problems in constrained environments.

The Transition-based RRT (T-RRT) is a variant of RRT developed for path planning on a continuous cost space, i.e. a configuration space featuring a continuous cost function. It has been used to solve complex, high-dimensional problems in robotics and structural biology. In this paper, we propose a multiple-tree variant of T-RRT, named Multi-T-RRT. It is especially useful to solve ordering-and-pathfinding problems, i.e. to compute a path going through several unordered way-points. Using the Multi-T-RRT, such problems can be solved from a purely geometrical perspective, without having to use a symbolic task planner. We evaluate the Multi-T-RRT on several path planning problems and compare it to other path planners. Finally, we apply the Multi-T-RRT to a concrete industrial inspection problem involving an aerial robot.

The Transition-based RRT (T-RRT) algorithm enables to solve motion planning problems involving configuration spaces over which cost functions are defined, or cost spaces for short. T-RRT has been successfully applied to diverse problems in robotics and structural biology. In this paper, we aim at enhancing T-RRT to solve ever more difficult problems involving larger and more complex cost spaces. We compare several variants of T-RRT by evaluating them on various motion planning problems involving different types of cost functions and different levels of geometrical complexity. First, we explain why applying as such classical extensions of RRT to T-RRT is not helpful, both in a mono-directional and in a bidirectional context. Then, we propose an efficient Bidirectional T-RRT, based on a bidirectional scheme tailored to cost spaces. Finally, we illustrate the new possibilities offered by the Bidirectional T-RRT on an industrial inspection problem.

This paper addresses the problem of parallelizing the Rapidly-exploring Random Tree (RRT) algorithm on large-scale distributed-memory architectures, using the message passing interface. We compare three parallel versions of RRT based on classical parallelization schemes. We evaluate them on different motion-planning problems and analyze the various factors influencing their performance.

For a versatile human-assisting mobile-manipulating robot such as the PR2, handing over objects to humans in possibly cluttered workspaces is a key capability. In this paper we investigate the motion planning of handovers while accounting for the human mobility. We treat the human motion as part of the planning problem thus enabling to find broader type of handing strategies. We formalize the problem and propose an algorithmic solution taking into account the HRI constraints induced by the human receiver presence. Simulation results with the PR2 robot illustrate the efficacy of the approach.

Finding paths in high-dimensional spaces becomes difficult when we wish to optimize the cost of a path in addition to obeying feasibility constraints. Recently the T-RRT algorithm was presented as a method to plan in high-dimensional cost spaces and it was shown to perform well across a variety of problems. However, since the T-RRT relies solely on sampling to explore the space, it has difficulty navigating cost-space chasms narrow low-cost regions surrounded by increasing cost. Such chasms are particularly common in planning for manipulators because many useful cost functions induce narrow or lower dimensional low-cost areas. This paper presents the GradienT-RRT algorithm, which combines the T-RRT with a local gradient method to bias the search toward lower-cost regions. GradienT-RRT is effective at navigating chasms because it explores low-cost regions that are too narrow to explore by sampling alone. We compare the performance of T-RRT and GradienT-RRT on planning problems involving cost functions defined in workspace, task space, and C-space. We find that GradienT-RRT outperforms T-RRT in terms of the cost of the final path while maintaining better or comparable computation time. We also find that the cost of paths generated by GradienT-RRT is far less sensitive to changes in a key parameter, making it easier to tune the algorithm. Finally, we conclude with a demonstration of GradienT-RRT on a planning-with-uncertainty task on the physical HFRB robot.

This paper addresses the problem of improving the performance of the Rapidly-exploring Random Tree (RRT) algorithm by parallelizing it. For scalability reasons we do so on a distributed-memory architecture, using the message-passing paradigm. We present three parallel versions of RRT along with the technicalities involved in their implementation. We also evaluate the algorithms and study how they behave on different motion planning problems.

This paper presents a new method to compute enveloping grasps with a multi-fingered robotic hand. The method is guided by the idea that a good grasp should maximize the contact surface between the held object and the hand's palmar surface. Starting from a given hand pregrasp configuration, the proposed method finds the hand poses that maximize this surface similarity. We use a surface descriptor that is based on a geodesic measure and on a continuous representation of the surfaces, unlike previous shape matching methods that rely on the Euclidean distance and/or discrete representation (e.g. random point set). Using geodesic contours to describe local surfaces enables us to detect details such as a handle or a thin part. Once the surface matching returns a set of hand poses, sorted by similarity, a second step is performed to adjust the hand configuration with the purpose of eliminating penetration of the object. Lastly, the grasp stability is tested in order to definitely validate the candidate grasps.

This paper addresses the motion planning problem while considering Human-Robot Interaction (HRI) constraints. The proposed planner generates collision-free paths that are acceptable and legible to the human. The method extends our previous work on human-aware path planning to cluttered environments. A randomized cost-based exploration method provides an initial path that is relevant with respect to HRI and workspace constraints. The quality of the path is further improved with a local path-optimization method. Simulation results on mobile manipulators in the presence of humans demonstrate the overall efficacy of the approach.

This paper builds on the combination of robotic path planning algorithms and molecular modeling methods for computing large-amplitude molecular motions, and introduces voxel maps as a computational tool to encode and to represent such motions. We investigate several applications and show results that illustrate the interest of such representation.

This paper proposes a planning framework to deal with the problem of computing the motion of a robot with dual arm/hand, during an object pick-and-place task. We consider the situation where the start and goal configurations of the object constrain the robot to grasp the object with one hand, to give it to the other hand, before placing it in its final configuration. To realize such a task, the proposed framework treats the grasp computation, for one or two multi-fingered hands, of an arbitrarily-shaped object, the exchange configuration and finally the motion of the robot arms and body. In order to improve the planner performance, a context-independent grasp list is computed offline for each hand and for the given object as well as computed offline roadmap that will be adapted according to the environment composition. Simulation results show the planner performance on a complex scenario.

This paper addresses path planning to consider a cost function defined over the configuration space. The proposed planner computes low-cost paths that follow valleys and saddle points of the configuration-space costmap. It combines the exploratory strength of the Rapidly exploring Random Tree (RRT) algorithm with transition tests used in stochastic optimization methods to accept or to reject new potential states. The planner is analyzed and shown to compute low-cost solutions with respect to a path-quality criterion based on the notion of mechanical work. A large set of experimental results is provided to demonstrate the effectiveness of the method. Current limitations and possible extensions are also discussed.

Understanding life at the atomic level requires the development of new methodologies, able to overcome the limitations of available experimental and computational techniques for the analysis of processes involving molecular motions. With this goal in mind, we develop new methods, combining robotic path planning algorithms and molecular modeling techniques, for computing large-amplitude motions. This paper builds on these new methods, and introduces voxel maps as a computational tool to encode and to represent such motions. Voxel maps can be used to represent relative motions of two molecules, as well as conformational changes in macromolecules. We investigate several applications and show results that illustrate the interest of such representation. In particular, voxel maps are used to display channels into proteins, to analyze protein-ligand specificity, and to represents protein loop and domain motions.

This paper presents a new method for planning motions of multi-arm systems in constrained workspaces, for which state-of-the-art planners behave poorly. The method is based on the decomposition of the system into parts. Compact roadmaps are first computed for each part, and then, a super-graph is constructed by the composition of elementary roadmaps. Results presented for a three-arm system and a model of the complex DLR's Justin robot show a significant performance gain of such a two-stage roadmap construction method with respect to single-stage methods applied to the whole system.

This paper presents a new method called Transition-based RRT (T-RRT) for path planning in continuous cost spaces. It combines the exploration strength of the RRT algorithm that rapidly grow random trees toward unexplored regions of the space, with the efficiency of stochastic optimization methods that use transition tests to accept or to reject a new potential state. This planner also relies on the notion of minimal work path that gives a quantitative way to compare path costs. The method also integrates self tuning of a parameter controlling its exploratory behavior. It yields to solution paths that efficiently follow low cost valleys and the saddle points of the cost space. Simulation results show that the method can be applied to a large set of applications including terrain costmap motions or planning low cost motions for free flying or articulated robots.

Sampling-based path planning algorithms are powerful tools for computing constrained disassembly motions. This paper presents a variant of the Rapidly-exploring Random Tree (RRT) algorithm particularly devised for the disassembly of objects with articulated parts. Configuration parameters generally play two different roles in this type of problems: some of them are essential for the disassembly task, while others only need to move if they hinder the progress of the disassembly process. The proposed method is based on such a partition of the configuration parameters. Results show a remarkable performance improvement as compared to standard path planning techniques. The paper also shows practical applications of the presented algorithm in robotics and structural bioinformatics.

This paper addresses the problem of computing pathways for a ligand to exit from the active site of a protein. Such problem can be formulated as a mechanical disassembly problem for two articulated objects. Its solution requires searching paths in a constrained high-dimensional configuration-space. Indeed, the ligand passageway inside the protein is often extremely cluttered so that current path planning techniques are unable to solve the disassembly problem in reasonable computing time. The techniques presented in this paper are based on the RRT algorithm. First we discuss some simple and general modifications of the basic algorithm that significantly improve its performance. Then we describe a new variant of the planner that treats ligand and protein degrees of freedom separately. This new algorithm outperforms the basic RRT, particularly for very constrained problems, and is able to handle models with hundreds of degrees of freedom. We analyze the effects of each RRT variant via several examples of different complexity. Although discussions and results of this paper focus on molecular models, the ideas behind the algorithms are general and can be applied to path planners for disassembling articulated mechanical parts.

Robot navigation in the presence of humans raises new issues for motion planning and control when the humans must be taken explicitly into account. We claim that a human aware motion planner (HAMP) must not only provide safe robot paths, but also synthesize good, socially acceptable and legible paths. This paper focuses on a motion planner that takes explicitly into account its human partners by reasoning about their accessibility, their vision field and their preferences in terms of relative human-robot placement and motions in realistic environments. This planner is part of a human-aware motion and manipulation planning and control system that we aim to develop in order to achieve motion and manipulation tasks in the presence or in synergy with humans.

This paper presents the combined results of two studies that investigated how a robot should best approach and place itself relative to a seated human subject. Two live Human Robot Interaction (HRI) trials were performed involving a robot fetching an object that the human had requested, using different approach directions. Results of the trials indicated that most subjects disliked a frontal approach, except for a small minority of females, and most subjects preferred to be approached from either the left or right side, with a small overall preference for a right approach by the robot. Handedness and occupation were not related to these preferences. We discuss the results of the user studies in the context of developing a path planning system for a mobile robot.

The presence of humans should be explicitly taken into account in all steps of robot's design and particularly for robot motion. The robot should reason about human partner's accessibility, his vision field and potential shared motions and behave as a social being by respecting social rules and protocols. This paper describes the algorithms and results of a navigation planner that takes into account the human presence explicitly. This planner is part of a human-aware motion and manipulation planning and control system that we aim to develop in order to achieve motion and manipulation tasks in presence and/or in synergy with human

Sampling-based planners have solved difficult problems in many applications of motion planning in recent years. In particular, techniques based on the Rapidly-exploring Random Trees (RRTs) have generated highly successful single-query planners. Even though RRTs work well on many problems, they have weaknesses which cause them to explore slowly when the sampling domain is not well adapted to the problem. In this paper we characterize these issues and propose a general framework for minimizing their effect. We develop and implement a simple new planner which shows significant improvement over existing RRT-based planners. In the worst cases, the performance appears to be only slightly worse in comparison to the original RRT, and for many problems it performs orders of magnitude better.

Sampling based planners have become increasingly efficient in solving the problems of classical motion planning and its applications. In particular, techniques based on the rapidly-exploring random trees (RRTs) have generated highly successful single-query planners. Recently, a variant of this planner called dynamic-domain RRT was introduced by Yershova et al. (2005). It relies on a new sampling scheme that improves the performance of the RRT approach on many motion planning problems. One of the drawbacks of this method is that it introduces a new parameter that requires careful tuning. In this paper we analyze the influence of this parameter and propose a new variant of the dynamic-domain RRT, which iteratively adapts the sampling domain for the Voronoi region of each node during the search process. This allows automatic tuning of the parameter and significantly increases the robustness of the algorithm. The resulting variant of the algorithm has been tested on several path planning problems.

This paper presents a path planner for robots operating in dynamically changing environments with both static and moving obstacles. The proposed planner is based on probabilistic path planning techniques and it combines techniques originally designed for solving multiple-query and single-query problems. The planner first starts with a preprocessing stage that constructs a roadmap of valid paths with respect to the static obstacles. It then uses lazy-evaluation mechanisms combined with a single-query technique as local planner in order to rapidly update the roadmap according to the dynamic changes. This allows to answer queries quickly when the moving obstacles have little impact on the free-space connectivity. When the solution can not be found in the updated roadmap, the planner initiates a reinforcement stage that possibly results into the creation of cycles representing alternative paths that were not already stored in the roadmap. Simulation results show that this combination of techniques yields to efficient global planner capable of solving with a real-time performance problems in geometrically complex environments with moving obstacles.

Despite the increasing interest in parallel mechanisms during the last years, few researchers have addressed the motion planning problem for such systems. The few existing techniques lie in a representation of the workspace of the mechanism (or its boundary). However, obtaining this representation is generally too difficult, only partial solutions exist for particular cases. In this paper we propose a general approach based on probabilistic motion planning techniques. This approach does not need any modeling of the robot's workspace. It combines random sampling techniques with simple but general geometric algorithms that guide the sampling toward feasible configurations satisfying the closure constraints of the parallel mechanism. The efficiency and the generality of the method are demonstrated onto several complex mechanisms mode up with serial or parallel associations of Stewart platforms, or created with several redundant robots manipulating an object.

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.

A methodology for computing the maximum velocity profile for a planned trajectory of the robot is described in this paper. The profile is computed considering the robot and environment dynamics as well as the constraints of the sensing apparatus. The mobile objects can be arbitrary in number and their direction and velocity of motion is not known. The only known information about the moving objects is the maximum velocity they can possess. The robot that moves with the computed velocity profile can assure from its side that it would not collide onto any of the numerous moving objects that could intercept its future trajectory. The methodology has been incorporated onto a motion planner for a nonholonomous robot and the results presented. The motivation here is to facilitate the process of having safe and understanding robots. Hence the planned velocity profiles are in general conservative though the robot could perhaps do better on-line. However at planning time the robot's immobility before collision is guaranteed.

We propose in this paper a resolution scheme that is aimed to be relevant for a large class of manipulation planning problems. This endeavor complements our efforts in developing manipulation planning algorithms. Indeed, we are convinced that a higher level of problems complexity, and particularly those involving multiple robots and multiple objects, will be accessible thanks to the introduction of a symbolic reasoning level. The resolution scheme relies on probabilistic roadmap methods (PRMs) and on a reasoning level that adaptively controls the construction and extension of a number of roadmaps. We consider this symbolic level as a step towards a systematic approach to integrate task planning and geometric planning in better conditions than through a gross, and somewhat, artificial hierarchical decomposition. This paper describes the main ingredients of the proposed framework, and its first results.

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.

An important skill of autonomous robots is the ability to carry out manipulation tasks. The solution to a manipulation problem generally consists in a sequence of elementary paths where an object is moved by a robot or it stays at a stable placement while the robot performs a re-grasping motion. Most existing planners require a finite set of configurations to achieve this task decomposition. We recently proposed an approach to automatically compute such intermediate configurations from continuous sets of stable placements and possible grasps of the movable object. This paper describes an improved algorithm based on this approach. It also presents several complex manipulation problems that illustrate the efficiency of the planner.

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.

Presents the global nearness diagram navigation system for mobile robots. The GND generates motion commands to drive a robot safely between locations, whilst avoiding collisions. This system has all the advantages of using the reactive scheme nearness diagram (ND), while having the ability to reason and plan globally (reaching global convergence to the navigation problem). This framework has been extensively tested using a holonomic mobile base equipped with a laser range-finder. Experiments in unknown, unstructured, dynamic and complex environments are reported to validate the system.

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.

In mobile robotics, pure geometric representations may not be well suited for navigation in large scale environments. New models combine topological and metrical information to give compact and efficient representations. We briefly review the outlines of the construction of our Voronoi-like graph and give further details about its implementation in a real environment. Several trials made around our lab demonstrate the ability of our modeling scheme to recognize topological features of the environment and use them to detect loops and relocalize the robot position.

This article presents an algorithm that determines safe motions for an articulated rover on rough terrains. It relies on the evaluation of a set of elementary trajectories on a digital elevation map built as the rover moves. The algorithm relies on the explicit computation of geometric constraints on the rover chassis. It has been integrated within a continuously running navigation loop on board the robot Lama, and tested under various terrain conditions.

The authors previously (1998) argued that the LAAS architecture is one of the most suitable for mobile robot control. This statement may seem over-optimistic, not to say pretentious and unverifiable. After all, can we compare architectures? can we set up benchmarks? or can we measure how good an architecture is compared to another? An architecture defines organization principles, integration methods and supporting tools. Comparing those tools, methods and principles may sometime end up in sterile controversies. However, we think there are means to measure the overall quality (or interest) of an architecture. Development time is for example one relevant criterion. Basically, using a specific architecture, how long does it take to integrate a complete demonstration, including nontrivial decisional capabilities, from the low level functional modules up to the supervisory level? This may seem a rather weak measure of architecture quality; however, it encompasses properties such as genericity and adaptability, ease of design and programming, extensibility and robustness. In this paper we describe our recent experience in integrating a complete demonstration from scratch in 40 days using the LAAS architecture.

In the field of mobile robotics, one important issue is to allow the robot to navigate in an a priori unknown and non-specific large scale environment. Large dimensions raise strong limitations of geometric modeling, and topological or mixed metric-topological models are now studied to better fit the problem. We present a method for incrementally building a topological model of an indoor environment from sensor range data. The approach consists in merging each local perception of the topology with the current state of the global graph. This local topology is captured through the construction of a Voronoi-like graph that takes into account not only visible features but also visibility constraints (hidden regions, limited sensing ranges,...). We give the outline of the method and show first encouraging results on real data.

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.

Deals with motion planning for a mobile robot on rough terrain. Hait and Simeon (1996) proposed a geometrical planner for articulated robots which can take into account uncertainty of the terrain and of the position of the robot. This paper aims at improving the robustness of the trajectory using a landmark based approach. We consider regions of the terrain where natural landmarks are visible. We propose a two-step planning approach taking advantage of these regions to reduce position uncertainty. First a path is determined between the initial and goal configurations, based on simplified models of the constraints. Then a trajectory is planned along this path, verifying the validity and visibility constraints.

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.

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.

This paper presents on operational framework to bridge the gap between planning with uncertainty and real-time sensor-based motion control. The environment being known, a planner produces a plan composed of free space and sensor-based motion commands. The representations of uncertainty and its evolution, environment landmarks, and actions generated at the planning level are discussed. Sensor-based actions and command definitions for a nonholonomic mobile robot based on a task-potential field approach are developed. These various elements are integrated in a system that actually generates the motions of the Hilare2 mobile robot.

This paper presents the algorithms that have been developed and integrated onto the HILARE 2 mobile robot for achieving robust navigation, in presence of control and sensing errors, in an a priori known office-like environment. The mobile robot is equipped with a belt of 32 sonars and a laser range finder. Sonar data are used for the wall-following, move to contact and parallel actions. The laser is used for edge detection and matching during a wall-following. A VME rack supporting 6 CPU boards of the Motorola 680x0 family is mounted on the robot running under the VxWorks real-time system.

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 addresses motion planning for a mobile robot moving on a rough terrain. Simeon and Dacre-Wright proposed (1993) a geometrical planner for a particular architecture of robot, based on a discrete search technique operating in the (x, y, /spl theta/) configuration space of the robot, and on the evaluation of elementary feasible paths between two configurations. The overall efficiency of the approach was made possible by the use of fast algorithms for solving the placement problem and checking the validity of such placements. The contribution of this paper is twofold. First, we study the extension of this approach to an articulated vehicle composed of three axles connected to the chassis by joints allowing the roll and pitch movements. We also propose new algorithms to improve the robustness of the planner by considering additional constraints: uncertainties in the terrain model and existence of a free channel around the computed trajectory. Some simulation results presented at the end of the paper show the effectiveness of the planner which turns out to be both fast and capable of solving difficult problems.

This paper addresses the problem of planning the motions of a circular mobile robot moving amidst polygonal obstacles with uncertainty in robot control and sensing. The robot is equipped with sensors which, if properly used, may provide information to overcome the uncertainty accumulated during the motions. The position sensor is based on dead-reckoning, the error then results in a cumulative uncertainty. A proximity sensor may be used to localize the robot with respect to the obstacles of the environment. The robot can also gain information by entering inside landmark areas where the position error is assumed to be bounded. The authors describe a planner which produces robust motion strategies composed of sensor-based motion commands which guarantee that, given an explicit model of the error accumulated by the motion commands, the robot can reach safely its goal with an error lower than a pre-specified value. It is based on a propagation of a numerical potential and on a geometric analysis of the reachability of environmental features. This planner exhibits a set of powerful capabilities: while it allows motion primitives which accumulate uncertainty to be considered, it is able, whenever possible, to navigate without relocalizing the robot when the task does not impose it, and also to make a proper use of the sensors. Several examples run with the planner are presented.

This paper reports on a recent work we have conducted concerning the development and the implementation of a robust motion planner for a mobile robot in a polygonal environment and in presence of uncertainty in robot control and sensing. Such a planner takes explicitly into account the uncertainty in robot control and produces a robust motion plan composed of sensor-based motion commands. The main originality of this approach is that it is able to account for a set of motion commands which may accumulate errors. It is based on a geometric analysis of the reachability and it generates motion strategies which may allow the robot to reduce its uncertainty.>

This paper presents the approach, algorithms and processes we developed to perform cross-country autonomous navigation. After a presentation of the teleprogramming context, we introduce an adaptive navigation approach, well suited for the characteristics of complex natural environments. The main perception, motion planning and decisional processes required by the robot during navigation are briefly presented. An on board control architecture that manages all these processes is then described, and first results of an experiment currently developed at LAAS are discussed.>

This paper presents a 3D navigation subsystem providing specific treatments needed for the perception and the navigation of an all-terrain mobile robot. This subsystem was developed and integrated in the global framework of the EDEN experimentation. After a brief description of this outdoor navigation experimentation, we describe the natural environment representations we use. Two important perception functions based on 3D data are involved here: fast construction of elevation maps and robot localization. We then describe the 3D motion planner dedicated to the navigation on rugged terrains. The current state of integration of the experiment is finally presented by the mean of experimental results obtained from the natural environment of the mobile robot ADAM.>

The authors address the motion planning problem for wheeled vehicles moving on rough terrains. First, they formalize the placement problem for the case of a rather complex locomotion system consisting of n wheels attached to the robot body by passive suspensions. They next analyze the geometric and kinematic constraints acting on the placements of the robot. Finally, they present a planning method that computes a safe and feasible path between two given placements of the robot. The approach basically consists in searching a path into a graph built incrementally during the exploration of a discrete 3-D configuration space. The algorithms have been implemented, and simulation results are reported.

Addresses the problem of autonomous navigation of mobile robots on rough terrains. The contribution is a geometrical path planning algorithm that considers the geometry of the robot and its kinematic constraint in order to plan trajectories on a 3D terrain represented by polygonal patches. A first version of this planner has been implemented and simulation results that show the effectiveness of the approach are presented at the end of the paper.>