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.     

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.     

Path planning for robobt manipulators in polyhhedral objects environment

A recent development in robotics is the increase of intelligence in robots. One of the research fields is to enable robots to autonomously avoid collisions with surrounding objects. This article presents an efficient method for planning collision-free paths for an articulated robot that is surrounded by polyhedral objects. The algorithm plans a hypothetical Archimedes's spiral path from the initial position to the goal position. When a collision among the arms and obstacles is detected, the hypothetical path will be modified to avoid the collision. The algorithm applies geometric methods to determine the upper and lower bounds of the reachable area of the wrist and then determines a collision-free path point on that reachable area. Because the equations, which represent the upper and lower bounds, are simple, the algorithm can rapidly determine a collision-free path. Moreover, with minor modifications, this path planning algorithm can also be applied to other robots such as spherical, cylindrical, and Cartesian types of robots. © 1995 John Wiley & Sons, Inc.     

A real-time traffic control scheme of multiple AGV systems forcollision free minimum time motion: a routing table approach

A two-staged traffic control scheme, in which sets of candidate paths are prepared off-line prior to overall motion planning process, has been widely adopted for motion planning of mobile robots, but relatively little attention has been given to the application of the two-staged scheme to multiple automated guided vehicle systems (MAGVSs). In the paper, a systematic two-staged traffic control scheme is presented to obtain collision-free minimum-time motions of AGVs along loopless paths. The overall structure of the controller is divided into two tandem modules of off-line routing table generator (RTG) and an online traffic controller (OTC). First, an induced network model is established considering the configurational restrictions of guide-paths. With this model and a modified k-shortest path algorithm, RTG finds sets of k candidate paths from each station nodes to all the other station nodes off-line and stores them in the form of routing tables. Each time a dispatch command for an AGV is issued, OTC utilizes these routing tables to generate a collision-free minimum-time motion along a loopless path. Real-time computation is guaranteed in that the time-consuming graph searching process is executed off-line by RTG, and OTC looks for the minimum time motion among the k candidate paths. The traffic control scheme proposed is suitable for practical application in centralized MAGVS with zone blocking technique     

Dynamically-Stable Motion Planning for Humanoid Robots

We present an approach to path planning for humanoid robots that computes dynamically-stable, collision-free trajectories from full-body posture goals. Given a geometric model of the environment and a statically-stable desired posture, we search the configuration space of the robot for a collision-free path that simultaneously satisfies dynamic balance constraints. We adapt existing randomized path planning techniques by imposing balance constraints on incremental search motions in order to maintain the overall dynamic stability of the final path. A dynamics filtering function that constrains the ZMP (zero moment point) trajectory is used as a post-processing step to transform statically-stable, collision-free paths into dynamically-stable, collision-free trajectories for the entire body. Although we have focused our experiments on biped robots with a humanoid shape, the method generally applies to any robot subject to balance constraints (legged or not). The algorithm is presented along with computed examples using both simulated and real humanoid robots.     

A gradient-based path optimization method for motion planning

Most algorithms in probabilistic sampling-based path planning compute collision-free paths made of straight line segments lying in the configuration space. Due to the randomness of sampling, the paths make detours that need to be optimized. The contribution of this paper is to propose a basic gradient-based algorithm that transforms a polygonal collision-free path into a shorter one. While requiring only collision checking, and not any time-consuming obstacle distance computation nor geometry simplification, we constrain only part of the configuration variables that may cause a collision, and not entire configurations. Thus, parasite motions that are not useful for the problem resolution are reduced without any assumption. Experimental results include navigation and manipulation tasks, eg a manipulator arm-filling boxes and a PR2 robot working in a kitchen environment. Comparisons with a random shortcut optimizer and a partial shortcut have also been studied.     

A search algorithm for motion planning with six degrees of freedom

The motion planning problem is of central importance to the fields of robotics, spatial planning, and automated design. In robotics we are interested in the automatic synthesis of robot motions, given high-level specifications of tasks and geometric models of the robot and obstacles. The “Movers'” problem is to find a continuous, collision-free path for a moving object through an environment containing obstacles. We present an implemented algorithm for the classical formulation of the three-dimensional Movers' problem: Given an arbitrary rigid polyhedral moving object P with three translational and three rotational degrees of freedom, find a continuous, collision-free path taking P from some initial configuration to a desired goal configuration.This paper describes an implementation of a complete algorithm (at a given resolution) for the full six degree of freedom Movers' problem. The algorithm transforms the six degree of freedom planning problem into a point navigation problem in a six-dimensional configuration space (called C-space). The C-space obstacles, which characterize the physically unachievable configurations, are directly represented by six-dimensional manifolds whose boundaries are five-dimensional C-surfaces. By characterizing these surfaces and their intersections, collision-free paths may be found by the closure of three operators which (i) slide along five-dimensional level C-surfaces parallel to C-space obstacles; (ii) slide along one- to four-dimensional intersections of level C-surfaces; and (iii) jump between six-dimensional obstacles. These operators are employed by a best-first search algorithm in C-space. We will discuss theoretical properties of the algorithm, including completeness (at a resolution). This paper describes the heuristic search, with particular emphasis on the heuristic strategies that evaluate local geometric information. At the heart of this paper lie the design and implementation of these strategies for planning paths along level C-surfaces and their intersection manifolds, and for reasoning about motions with three degrees of rotational freedom. The problems of controlling the interaction of these strategies, and of integrating diverse local experts for geometric reasoning provide an interesting application of search to a difficult domain with significant practical implications. The representations and algorithms we develop impact many geometric planning problems, and extend to Cartesian manipulators with six degrees of freedom.     

Dual-layer multi-robot path planning in narrow-lane environments under specific traffic policies

Collision-free path planning is indispensable for the multi-robot system. Many existing multi-robot path planning algorithms may no longer work properly in the narrow-lane environment. We propose in this paper a dual-layer algorithm to deal with the multi-robot path planning problem in the narrow-lane environment. In the first layer, the integer programming technique primarily based on distance metrics balances the optimality of the generated collision-free paths and the computation time of the algorithm. In the second layer, fast feasible heuristics are applied to make sure the solvability of the proposed integer programming approach in the first layer. In the dual-layer algorithm, specific traffic policies for each narrow lane are implemented to generate a collision-free path for every robot while maintaining the narrow lane free, besides the collision avoidance approach at the robotic level. With this, inter-robot collision in the narrow lane is avoided, and the algorithm’s efficiency in producing collision-free paths increases. Simulations have been launched considerably based on the proposed assessment metrics. According to the extensive simulation data, our algorithm suggests a higher overall performance in the narrow-lane environment when in contrast with the present optimal, sub-optimal, and polynomial-complexity algorithms.

     

An articulated limb motion planner for optimized movement

Task level animation of articulated figures, such as the human body, requires the ability to generate collision-free goal-directed motion of individual limbs in the presence of obstacles. This paper describes a new articulated limb motion planner for goal-directed point-to-point reaching motions. The produced motion avoids obstacles while optimizing an objective function. This two-phase algorithm uses heuristic guided Monte Carlo techniques to create a consistent underlying paradigm. The first phase consists of an existing potential field based random path planner which generates a population of candidate paths. This initial population is fed into the second phase, a genetic algorithm, which iteratively refines the population as it optimizes with respect to the objective function. The refinement process works on the principle of path coherency, the idea that a family of closely related collision-free paths lies in the vicinity of a given collision-free path. This paper focuses on seven different optimization functions. Optimized trajectories produced by the new motion planner are compared to those generated solely by the random path planner. The presented algorithm is flexible in that a wide range of objective functions can be optimized. Applications of the algorithm include task level animation, ergonomics and robotics.     

An Algorithm for Computing a Convex and Simple Path of Bounded Curvature in a Simple Polygon

Abstract. In this paper we study the collision-free path planning problem for a point robot, whose path is of bounded curvature (i.e., constrained to have curvature at most 1), moving in the plane inside an n -sided simple polygon P . Given two points s and t inside P and two directions of travel, one at s and one at t , the problem is to compute a convex and simple path of bounded curvature inside P from s to t consisting of straight-line segments and circular arcs such that (i) the radius of each circular arc is at least 1, (ii) each segment on the path is the tangent between the two consecutive circular arcs on the path, (iii) the given initial direction at s is tangent to the path at s and (iv) the given final direction at t is tangent to the path at t . We propose an O(n ⁴ ) time algorithm for this problem. Using the notion of complete visibility, P is pruned to another polygon P' such that any convex and simple path from s to t inside P also remains inside P' . Then our algorithm constructs the locus of center of a circle of unit radius translating along the boundary of P' and, using this locus, the algorithm constructs a convex and simple path of bounded curvature. Our algorithm is based on the relationship between the Euclidean shortest path, link paths and paths of bounded curvature, and uses several properties derived here on convex and simple paths of bounded curvature. We also show that the path computed by our algorithm can be transformed in O(n) time to a minimal convex and simple path of bounded curvature. Using this transformation and two necessary conditions proposed here for the shortest convex and simple path of bounded curvature, a minimal bounded curvature path is located in O(n ⁴ ) time whose length, except in special situations involving arcs of length greater than π , is at most twice the length of a shortest convex and simple path of bounded curvature.     

Planning collision-free paths for robotic arm among obstacles

A theory for planning collision-free paths of a moving object among obstacles is described. Using the concepts of state space and rotation mapping, the relationship between the positions and the corresponding collision-free orientations of a moving object among obstacles is represented as some set of a state space. This set is called the rotation mapping graph (RMG) of that object. The problem of finding collision-free paths for an object translating and rotating among obstacles is thus transformed to that of considering the connectivity of the RMG. Since the connectivity of the graph can be solved by topological methods, the problem of planning collision-free paths is easily solved in theory. Using this theory, a topological method for planning collision-free paths of a rod-object translating and rotating among obstacles is presented. If a nonrigid robotic arm is viewed as a composite rod with some degrees of freedom, the planning of collision-free paths of a robotic arm can be solved in a similar way to a rod.     

Robot programming using augmented reality: An interactive method for planning collision-free paths

Current robot programming approaches lack the intuitiveness required for quick and simple applications. As new robotic applications are being identified, there is a greater need to be able to programme robots safely and quickly. This paper discusses the use of an augmented reality (AR) environment for facilitating intuitive robot programming, and presents a novel methodology for planning collision-free paths for an n-d.o.f. (degree-of-freedom) manipulator in a 3D AR environment. The methodology is interactive because the human is involved in defining the free space or collision-free volume (CFV), and selecting the start and goal configurations. The methodology uses a heuristic beam search algorithm to generate the paths. A number of possible scenarios are discussed.     

Planning Smooth and Obstacle-Avoiding B-Spline Paths for Autonomous Mining Vehicles

We study the problem of automatic generation of smooth and obstacle-avoiding planar paths for efficient guidance of autonomous mining vehicles. Fast traversal of a path is of special interest. We consider fourwheel four-gear articulated vehicles and assume that we have an a priori knowledge of the mine wall environment in the form of polygonal chains. Computing quartic uniform B-spline curves, minimizing curvature variation, staying at least at a proposed safety margin distance from the mine walls, we plan high speed paths. We present a study where our implementations are successfully applied on eight path-planning cases arising from real-world mining data provided by the Swedish mining company Luossavaara-Kiirunavaara AB (LKAB). The results from the study indicate that our proposed methods for computing obstacle-avoiding minimum curvature variation B-splines yield paths that are substantially better than the ones used by LKAB today. Our simulations show that, with an average 32.13%, the new paths are faster to travel along than the paths currently in use. Preliminary results from the production at LKAB show an overall 5%-10% decrease in the total time for an entire mining cycle. Such a cycle includes both traveling, ore loading, and unloading.     

Obstacle avoidance for autonomous land vehicle navigation in indoorenvironments by quadratic classifier

A vision-based approach to obstacle avoidance for autonomous land vehicle (ALV) navigation in indoor environments is proposed. The approach is based on the use of a pattern recognition scheme, the quadratic classifier, to find collision-free paths in unknown indoor corridor environments. Obstacles treated in this study include the walls of the corridor and the objects that appear in the way of ALV navigation in the corridor. Detected obstacles as well as the two sides of the ALV body are considered as patterns. A systematic method for separating these patterns into two classes is proposed. The two pattern classes are used as the input data to design a quadratic classifier. Finally, the two-dimensional decision boundary of the classifier, which goes through the middle point between the two front vehicle wheels, is taken as a local collision-free path. This approach is implemented on a real ALV and successful navigations confirm the feasibility of the approach.     

Collision-free human-robot collaboration based on context awareness

Recent advancements in human-robot collaboration have enabled human operators and robots to work together in a shared manufacturing environment. However, current distance-based collision-free human-robot collaboration system can only ensure human safety but not assembly efficiency. In this paper, the authors present a context awareness-based collision-free human-robot collaboration system that can provide human safety and assembly efficiency at the same time. The system can plan robotic paths that avoid colliding with human operators while still reach target positions in time. Human operators’ poses can also be recognised with low computational expenses to further improve assembly efficiency. To support the context-aware collision-free system, a complete collision sensing module with sensor calibration algorithms is proposed and implemented. An efficient transfer learning-based human pose recognition algorithm is also adapted and tested. Two experiments are designed to test the performance of the proposed human pose recognition algorithm and the overall system. The results indicate an efficiency improvement of the overall system.     

Cellular ants: A method to create collision free trajectories for a cooperative robot team

Creating collision-free trajectories for mobile robots, known as the path planning problem, is considered to be one of the basic problems in robotics. In case of multiple robotic systems, the complexity of such systems increases proportionally with the number of robots, due to the fact that all robots must act as one unit to complete one composite task, such as retaining a specific formation. The proposed path planner employs a combination of Cellular Automata (CA) and Ant Colony Optimization (ACO) techniques in order to create collision-free trajectories for every robot of a team while their formation is kept immutable. The method reacts with obstacle distribution changes and therefore can be used in dynamical or unknown environments, without the need of a priori knowledge of the space. The team is divided into subgroups and all the desired pathways are created with the combined use of a CA path planner and an ACO algorithm. In case of lack of pheromones, paths are created using the CA path planner. Compared to other methods, the proposed method can create accurate collision-free paths in real time with low complexity while the implemented system is completely autonomous. A simulation environment was created to test the effectiveness of the applied CA rules and ACO principles. Moreover, the proposed method was implemented in a system using a real world simulation environment, called Webots. The CA and ACO combined algorithm was applied to a team of multiple simulated robots without the interference of a central control. Simulation and experimental results indicate that accurate collision free paths could be created with low complexity, confirming the robustness of the method.     

Two dimensional collision-free path planning using linear parametric curve

An effective algorithm for planning a collision-free path based on linear parametric curve is developed. A collision-free path is viewed as a series of segmented polynomial curves in a space that does not interfere with any object in a given work space. It is assumed that the path connecting start and target points has no width. The algorithm presented here uses a linear parametric curve as a base curve and maps objects in Euclidean Space (ES) into objects in Control Point Space (CPS) through intersection checks between path and obstacles. A path having a single control point is investigated here. The Free Space (FS) of CPS identifies a collision-free path in ES, hence any point in the FS of CPS is a candidate for a collision-free path. A CPS completely occupied by obstacle images indicates no collision-free path is available with a single control point and a search based on a multiple control point is required. The shortest path with minimum search time is obtained by setting CPS in elliptic coordinate. Considerations are given to get a path with the smallest maximum curvature by selecting the control point toward the bisection line of ST and smoothing the path. ©1997 John Wiley & Sons, Inc.     

Mission design for a group of autonomous guided vehicles

In this paper, a generic approach for the integration of vehicle routing and scheduling and motion planning for a group of autonomous guided vehicles (AGVs) is proposed. The AGVs are requested to serve all the work stations in a two-dimensional environment while taking into account kinematics constraints and the environment’s geometry during their motion. The problem objective is the simultaneous determination of time-optimum and collision-free paths for all AGVs. The proposed method is investigated and discussed through a number of simulated experiments using a variety of environments and different initial conditions.     

Observability-based local path planning and obstacle avoidance using bearing-only measurements

In this paper we present an observability-based local path planning and obstacle avoidance technique that utilizes an extended Kalman Filter (EKF) to estimate the time-to-collision (TTC) and bearing to obstacles using bearing-only measurements. To ensure that the error covariance matrix computed by an EKF is bounded, the system should be observable. We perform a nonlinear observability analysis to obtain the necessary conditions for complete observability of the system. These conditions are used to explicitly design a path planning algorithm that enhances observability while simultaneously avoiding collisions with obstacles. We analyze the behavior of the path planning algorithm and specially define the environments where the path planning algorithm will guarantee collision-free paths that lead to a goal configuration. Numerical results show the effectiveness of the planning algorithm in solving single and multiple obstacle avoidance problems while improving the estimation accuracy.     

A simple algorithm for intelligent manipulator collision-free motion

The collision-free planning of motion is a fundamental problem for artificial intelligence applications in robotics. The ability to compute a continuous safe path for a robot in a given environment will make possible the development of task-level robot planning systems so that the implementation details and the particular robot motion sequence will be ignored by the programmer.A new approach to planning collision-free motions for general real-life six degrees of freedom (d.o.f.) manipulators is presented. It is based on a simple object model previously developed. The complexity of the general collision detection problem is reduced, and realistic collision-free paths are efficiently found onCS planes. A heuristic evaluation function with a real physical sense is introduced, and computational cost is reduced to the strictly necessary by selecting the most adequate level of representation. A general algorithm is defined for 6 d.o.f. robots that yields good results for actual robot models with complex design structures with the aid of various heuristic techniques. The problem of adaptive motion is also considered.