A Human Aware Mobile Robot Motion Planner

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.     

Adaptive Partial Shortcuts: Path Optimization for Industrial Robotics

The quality of a path generated from an automated motion planning algorithm is of considerable importance, particularly when used in a real world robotic application. In this work a new path optimization algorithm, called the Adaptive Partial Shortcut algorithm, is presented. This algorithm optimizes paths as a post process to motion planning, and is designed specifically for use on industrial manipulators. The algorithm optimizes a robot’s degrees of freedom independently allowing it to produce manipulator paths of particularly high quality. This new algorithm utilizes an adaptive method of selecting the degree of freedom to optimize at each iteration, giving it a high level of efficiency. Tests conducted show the effectiveness of the algorithm; over a range of different test paths, the adaptive algorithm was able to generate solutions with a 60 % reduction in collision checks compared to the original partial shortcut approach.     

Autonomous multi-mobile robot system: simulation and implementation using fuzzy logic

In an autonomous multi-mobile robot environment, path planning and collision avoidance are important functions used to perform a given task collaboratively and cooperatively. This study considers these important and challenging problems. The proposed approach is based on a potential field method and fuzzy logic system. First, a global path planner selects the paths of the robots that minimize the potential value from each robot to its own target using a potential field. Then, a local path planner modifies the path and orientation from the global planner to avoid collisions with static and dynamic obstacles using a fuzzy logic system. In this paper, each robot independently selects its destination and considers other robots as dynamic obstacles, and there is no need to predict the motion of obstacles. This process continues until the corresponding target of each robot is found. To test this method, an autonomous multi-mobile robot simulator (AMMRS) is developed, and both simulation-based and experimental results are given. The results show that the path planning and collision avoidance strategies are effective and useful for multi-mobile robot systems.     

Probabilistically safe motion planning to avoid dynamic obstacles with uncertain motion patterns

This paper presents a real-time path planning algorithm that guarantees probabilistic feasibility for autonomous robots with uncertain dynamics operating amidst one or more dynamic obstacles with uncertain motion patterns. Planning safe trajectories under such conditions requires both accurate prediction and proper integration of future obstacle behavior within the planner. Given that available observation data is limited, the motion model must provide generalizable predictions that satisfy dynamic and environmental constraints, a limitation of existing approaches. This work presents a novel solution, named RR-GP, which builds a learned motion pattern model by combining the flexibility of Gaussian processes (GP) with the efficiency of RRT-Reach, a sampling-based reachability computation. Obstacle trajectory GP predictions are conditioned on dynamically feasible paths identified from the reachability analysis, yielding more accurate predictions of future behavior. RR-GP predictions are integrated with a robust path planner, using chance-constrained RRT, to identify probabilistically feasible paths. Theoretical guarantees of probabilistic feasibility are shown for linear systems under Gaussian uncertainty; approximations for nonlinear dynamics and/or non-Gaussian uncertainty are also presented. Simulations demonstrate that, with this planner, an autonomous vehicle can safely navigate a complex environment in real-time while significantly reducing the risk of collisions with dynamic obstacles.     

A direct variational method for planning monotonically optimal paths for redundant manipulators in constrained workspaces

This paper proposes a path planner for serial manipulators with a large number of degrees of freedom, working in cluttered workspaces. Based on the variational principles, this approach involves formulating the path planning problem as constrained minimization of a functional representing the total joint movement over the complete path. We use modified boundary conditions at both ends of the trajectory to find more suitable start and end configurations. The concept of monotonic optimality is introduced in order to optimize the manipulator paths between the resulting end configurations. For obstacle avoidance, volume and proximity based penalizing schemes are developed and used. The presented planner uses a global approach to search for feasible paths and at the same time involves no pre-processing task. A variety of test cases have been presented to establish the efficacy of the presented scheme in providing good quality paths. The extent of advantage accruing out of the measures of free end-configurations and monotonic optimality are also analyzed quantitatively.     

Planning the motions of a mobile robot in a sensory uncertaintyfield

Failures in mobile robot navigation are often caused by errors in localizing the robot relative to its environment. This paper explores the idea that these errors can be considerably reduced by planning paths taking the robot through positions where pertinent features of the environment can be sensed. It introduces the notion of a “sensory uncertainty field” (SUF). For every possible robot configuration q, this field estimates the distribution of possible errors in the robot configuration that would be computed by a localization function matching the data given by the sensors against an environment model, if the robot was at q. A planner is proposed which uses a precomputed SUF to generate paths that minimize expected errors or any other criterion combining, say, path length and errors. This paper describes in detail the computation of a specific SUF for a mobile robot equipped with a classical line-striping camera/laser range sensor. It presents an implemented SUF-based motion planner for this robot and shows paths generated by this planner. Navigation experiments were conducted with mobile robots using paths generated by the SUF-based planner and other paths. The former paths were tracked with greater precision than the others. The final section of the paper discusses additional research issues related to SUF-based planning     

Optimal path planning of redundant free-floating revolute-jointed space manipulators with seven links

The path planning of free-floating manipulators is of great interest in space operations. The manipulators in the free-floating mode exhibit nonholonomic characteristics due to the nonintegrability of the angular momentum, which makes the problem complicated. This paper analyzes the path planning of redundant, free-floating space manipulators with revolute joints and 7 degrees of freedom. The primary task of manipulators is to move the manipulator arms so that the desired end-effector position and orientation can be achieved. The motion of the manipulators can produce an attitude disturbance of the base, which has an adverse impact on the spacecraft operation. Thus, it is necessary to minimize the base attitude disturbance in order to reduce the fuel consumption for attitude maintenance. Practically, the path planning of redundant free-floating manipulators with higher degrees of freedom (7 degrees of freedom in this paper) in three-dimensional space is more complicated than path planning with fewer degrees of freedom, including planar or fixed base cases. This paper provides a tractable planning method to solve this problem, which could avoid the pseudo inverse of the Jacobian matrix. The sine functions, whose arguments are the polynomial functions with unknown coefficients, are used to specify the joint paths. The PSODE algorithm (particle swarm optimization combined with differential evolution) is applied to optimize the unknown coefficients of the polynomials in order to achieve the desired end-effector position and orientation and simultaneously minimize the base attitude disturbance. The simulations demonstrate that this method could provide satisfactory smooth paths for redundant free-floating space manipulators.     

Planning of collision-free paths for a reconfigurable dual manipulator equipped mobile robot

In this paper, we study the problem of finding a collision-free path for a mobile robot which possesses manipulators. The task of the robot is to carry a polygonal object from a starting point to a destination point in a possibly culttered environment. In most of the existing research on robot path planning, a mobile robot is approximated by a fixed shape, i.e., a circle or a polygon. In our task planner, the robot is allowed to change configurations for avoiding collision. This path planner operates using two algorithms: the collision-free feasible configuration finding algorithm and the collision-free path finding algorithm. The collision-free feasible configuration finding algorithm finds all collision-free feasible configurations for the robot when the position of the carried object is given. The collision-free path finding algorithm generates some candidate paths first and then uses a graph search method to find a collision-free path from all the collision-free feasible configurations along the candidate paths. The proposed algorithms can deal with a cluttered environment and is guaranteed to find a solution if one exists.     

Fuzzy Logic Based Behavior Fusion for Navigation of an Intelligent Mobile Robot

This paper presents a new method for behavior fusion control of a mobile robot in uncertain environments.Using behavior fusion by fuzzy logic,a mobile robot is able to directly execute its motion according to range information about environments,acquired by ultrasonic sensors,without the need for trajectory planning.Based on low-level behavior control,an efficient strategy for integrating high-level global planning for robot motion can be formulated,since,in most applications,some information on environments is prior knowledge.A global planner,therefore,only to generate some subgoal positions rather than exact geometric paths.Because such subgoals can be easily removed from or added into the plannes,this strategy reduces computational time for global planning and is flexible for replanning in dynamic environments.Simulation results demonstrate that the proposed strategy can be applied to robot motion in complex and dynamic environments.     

Biologically inspired node generation algorithm for path planning of hyper-redundant manipulators using probabilistic roadmap

This article describes a biologically inspired node generator for the path planning of serially connected hyper-redundant manipulators using probabilistic roadmap planners. The generator searches the configuration space surrounding existing nodes in the roadmap and uses a combination of random and deterministic search methods that emulate the behaviour of octopus limbs. The strategy consists of randomly mutating the states of the links near the end-effector, and mutating the states of the links near the base of the robot toward the states of the goal configuration. When combined with the small tree probabilistic roadmap planner, the method was successfully used to solve the narrow passage motion planning problem of a 17 degree-of-freedom manipulator.     

From Reeds and Shepp's to continuous-curvature paths

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

Enhanced path smoothing based on conjugate gradient descent for firefighting robots in petrochemical complexes*

The firefighting robot system (FFRS) comprises several autonomous robots that can be deployed to fire disasters in petrochemical complexes. For autonomous navigation, the path planner should consider the robot constraints and characteristics. Specifically, three requirements should be satisfied for a path to be suitable for the FFRS. First, the path must satisfy the maximum curvature constraint. Second, it must be smooth for robots to easily execute the trajectory. Third, it must allow reaching the target location in a specific heading. We propose a path planner that provides smooth paths, satisfy the maximum curvature constraint, and allows a suitable robot heading. The path smoother is based on the conjugate gradient descent, and three approaches are proposed for this path planner to meet all the FFRS requirements. The effectiveness of these approaches is qualitatively and quantitatively evaluated by examining the generated paths. Finally, the path planner is applied to an actual robot to verify the suitability of the generated paths for the FFRS, and planning is applied to another type of robot to demonstrate the wide applicability of the proposed planner.     

Anytime motion planning for prehensile manipulation in dense clutter

ABSTRACT

Many methods have been developed for planning the motion of robotic arms for picking and placing, ranging from local optimization to global search techniques, which are effective for sparsely placed objects. Dense clutter, however, still adversely affects the success rate, computation times, and quality of solutions in many real-world setups. The proposed method achieves high success ratio in clutter with anytime performance by returning solutions quickly and improving their quality over time. The method first explores the lower dimensional end effector's task space efficiently by ignoring the arm, and build a discrete approximation of a navigation function. This is performed online, without prior knowledge of the scene. Then, an informed sampling-based planner for the entire arm uses Jacobian-based steering to reach promising end effector poses given the task space guidance. This process is also comprehensive and allows the exploration of alternative paths over time if the task space guidance is misleading. This paper evaluates the proposed method against alternatives in picking or placing tasks among varying amounts of clutter for a variety of robotic manipulators with different end-effectors. The results suggest that the method reliably provides higher quality solution paths quicker, with a higher success rate relative to alternatives.     

Fuzzy-GA-based trajectory planner for robot manipulators sharing a common workspace

This paper presents a novel fuzzy genetic algorithm (GA) approach to tackling the problem of trajectory planning of two collaborative robot manipulators sharing a common workspace, where the manipulators have to consider each other as a moving obstacle whose trajectory or behaviour is unknown and unpredictable, as each manipulator has individual goals and where both have the same priority. The goals are not restricted to a given set of joint values, but are specified in the workspace as coordinates at which it is desired to place the end-effector of the manipulator. By not constraining the goal to the joint space, the number of possible solutions that satisfies the goal increases according to the number of degrees of freedom of the manipulators. A simple GA planner is used to produce an initial estimation of the movements of the robots' articulations and collision free motion is obtained by the corrective action of the collision-avoidance fuzzy units.     

Path planning for deformable linear objects

We present a new approach to path planning for deformable linear (one-dimensional) objects such as flexible wires. We introduce a method for efficiently computing stable configurations of a wire subject to manipulation constraints. These configurations correspond to minimal-energy curves. By restricting the planner to minimal-energy curves, the execution of a path becomes easier. Our curve representation is adaptive in the sense that the number of parameters automatically varies with the complexity of the underlying curve. We introduce a planner that computes paths from one minimal-energy curve to another such that all intermediate curves are also minimal-energy curves. This planner can be used as a powerful local planner in a sampling-based roadmap method. This makes it possible to compute a roadmap of the entire "shape space," which is not possible with previous approaches. Using a simplified model for obstacles, we can find minimal-energy curves of fixed length that pass through specified tangents at given control points. Our work has applications in cable routing, and motion planning for surgical suturing and snake-like robots.     

Autonomous Driving with Concurrent Goals and Multiple Vehicles: Mission Planning and Architecture

We introduce a new distributed planning paradigm, which permits optimal execution and dynamic replanning of complex multi-goal missions. In particular, the approach permits dynamic allocation of goals to vehicles based on the current environment model while maintaining information-optimal route planning for each individual vehicle to individual goals. Complex missions can be specified by using a grammar in which ordering of goals, priorities, and multiple alternatives can be described. We show that the system is able to plan local paths in obstacle fields based on sensor data, to plan and update global paths to goals based on frequent obstacle map updates, and to modify mission execution, e.g., the assignment and ordering of the goals, based on the updated paths to the goals.The multi-vehicle planning system is based on the GRAMMPS planner; the on-board dynamic route planner is based on the D* planner. Experiments were conducted with stereo and high-speed ladar as the to sensors used for obstacle detection. This paper focuses on the multi-vehicle planner and the systems architecture. A companion paper (Brumitt et al., 2001) analyzes experiments with the multi-vehicle system and describes in details the other components of the system.     

A knowledge-based task-level programming and execution environment for robots

A knowledge-based framework to support task-level programming and operational control of robots is described. Our bask intention is to enhance the intelligence of a robot control system so that it may carefully coordinate the interactions among discrete, asynchronous and concurrent events under the constraints of action precedence and resource allocation. We do this by integrating both off-line and on-line planning capabilities in a single framework. The off-line phase is equipped with proper languages for describing workbenches, specifying tasks, and soliciting knowledge from the user to support the execution of robot tasks. A static planner is included in the phase to conduct static planning, which develops local plans for various specific tasks. The on-line phase is designed as a dynamic control loop for the robot system. It employs a dynamic planner to tackle any contingent situations during the robot operations. It is responsible for developing proper working paths and motion plans to achieve the task goals within designated temporal and resource constraints. It is implemented in a distributed and cooperative blackboard system, which facilitates the integration of various types of knowledge. Finally, any failures from the on-line phase are fed back to the off-line phase. This forms the interaction between the off-line and on-line phases and introduces an extra closed loop opportunistically to tune the dynamic planner to adapt to the variation of the working environment in a long-term manner.     

Asynchronous double-precision windows based unmanned aerial vehicle real-time path planning

A real-time path planning approach based on asynchronous double-precision windows is proposed for unmanned aerial vehicles (UAVs). In this proposed method, cursory paths and elaborate paths are planned respectively in the global and local windows. Specifically, global cursory path planner and local elaborate path planner are integrated by rolling two windows on different frequencies with different modes. Simulation results demonstrate that the proposed approach is effective for realizing a balance between t...     

Near-time optimal robot motion planning foe on-line applications

Solving current formulations of the time-optimal point-to-point motion problem for robotic manipulators is a computationally intensive task. Thus, most existing solutions are not suitable for on-line motion planning applications, such as the interception of moving targets, where time-optimality of the motion is advantageous. A novel technique is proposed in this article that separates the time-optimal point-to-point motion problem into the following two sub-problems: (1) selection of a near-time-optimal path between the two endpoints, and (2) generation of time-optimal motion along the selected path (i.e., constrained continuous path motion). Although our approach uses known path-constrained time-optimal-motion algorithms for the second sub-problem, a new method is proposed for the selection of near-time-optimal paths. Based on a study of the characteristics of global-time-optimal paths, the near-optimal path is selected as a minimum-curvature joint spline, tangent to one of the manipulator's acceleration directions at the start point, and tangent to the required manipulator velocity direction at the end point. The algorithm for determining the overall near-optimal path is described herein, along with an example. Simulation test results and computation-time studies indicate that the proposed method is suitable for on-line motion planning applications. © 1995 John Wiley & Sons, Inc.     

Complete and Rapid Regrasp Planning with Look-up Table

A pick-and-place operation in a 3-dimensional environment is a basic operation for humans and multi-purpose manipulators. However, there may be a difficult problem for such manipulators. Especially, if the object cannot be moved with a single grasp, regrasping, which can be a time-consuming process, should be carried out. Regrasping, given initial and final poses of the target object, is a construction of sequential transition of object poses that are compatible with two poses in the point of grasp configuration. This paper presents a novel approach for solving the regrasp problem. The approach consists of a preprocessing and a planning stage. Preprocessing, which is done only once for a given robot, generates a look-up table which has information on kinematically feasible task space of the end-effector throughout the entire workspace. Then, using this table, the planning automatically determines a possible intermediate location, pose and regrasp sequence leading from the pick-up to put-down grasp. With a redundant robot, it is shown experimentally that the presented method is complete in the entire workspace and can be implemented in real-time applications due to rapid regrasp planning time. The regrasp planner was combined with an existing path.