skip to main content

Title: Efficient Robot Motion Planning via Sampling and Optimization
Robot motion planning is one of the important elements in robotics. In environments full of obstacles, it is always challenging to find a collision-free and dynamically feasible path between the robot's initial configuration and goal configuration. While many motion planning algorithms have been proposed in the past, each of them has its pros and cons. This work presents a benchmark which implements and compares existing planning algorithms on a variety of problems with extensive simulation. Based on that, we also propose a hybrid planning algorithm, RRT*-CFS, that combines the merits of sampling-based planning methods and optimization-based planning methods. The first layer, RRT*, quickly samples a semi-optimal path. The second layer, CFS, performs sequential convex optimization given the reference path from RRT*. The proposed RRT*-CFS has feasibility and convergence guarantees. Simulation results show that RRT*-CFS benefits from the hybrid structure and performs robustly in various scenarios including the narrow passage problems.
; ; ;
Award ID(s):
Publication Date:
Journal Name:
2021 American Control Conference (ACC)
Page Range or eLocation-ID:
4196 to 4202
Sponsoring Org:
National Science Foundation
More Like this
  1. This paper presents an integrated motion planning system for autonomous vehicle (AV) parking in the presence of other moving vehicles. The proposed system includes 1) a hybrid environment predictor that predicts the motions of the surrounding vehicles and 2) a strategic motion planner that reacts to the predictions. The hybrid environment predictor performs short-term predictions via an extended Kalman filter and an adaptive observer. It also combines short-term predictions with a driver behavior cost-map to make long-term predictions. The strategic motion planner comprises 1) a model predictive control-based safety controller for trajectory tracking; 2) a search-based retreating planner for finding an evasion path in an emergency; 3) an optimization-based repairing planner for planning a new path when the original path is invalidated. Simulation validation demonstrates the effectiveness of the proposed method in terms of initial planning, motion prediction, safe tracking, retreating in an emergency, and trajectory repairing.
  2. The existing vehicle obstacle avoidance path planning methods generally aim at obtaining the collision-free path, ignoring the impact of the planned path on the vehicle stability in the obstacle avoidance process, so that the controlled vehicle has the risk of rollover in the obstacle avoidance process. To solve the above problems, a two-layer obstacle avoidance path planning algorithm considering path pre-planning and re-planning is proposed in this paper. In the path pre-planning layer, an improved APF algorithm with road boundary function constraints is proposed. By introducing the repulsion field adjustment factor, the shortcomings of GNRON and local optimization existing in the existing artificial potential field method are effectively solved. In the path re-planning layer, taking the rollover stability index as the constraint, a pre-planning result optimization method based on particle swarm optimization algorithm is proposed. The simulation results show that the obstacle avoidance path planning algorithm proposed in this paper can not only generate the obstacle avoidance path in real-time, but also reduce the yaw rate and yaw angle of the main vehicle in the process of obstacle avoidance, and effectively improve the rollover stability of the vehicle in the process of obstacle avoidance.

  3. Using sampling to estimate the connectivity of high-dimensional configuration spaces has been the theoretical underpinning for effective sampling-based motion planners. Typical strategies either build a roadmap, or a tree as the underlying search structure that connects sampled configurations, with a focus on guaranteeing completeness and optimality as the number of samples tends to infinity. Roadmap-based planners allow preprocessing the space, and can solve multiple kinematic motion planning problems, but need a steering function to connect pairwise-states. Such steering functions are difficult to define for kinodynamic systems, and limit the applicability of roadmaps to motion planning problems with dynamical systems. Recent advances in the analysis of single query tree-based planners has shown that forward search trees based on random propagations are asymptotically optimal. The current work leverages these recent results and proposes a multi-query framework for kinodynamic planning. Bundles of kinodynamic edges can be sampled to cover the state space before the query arrives. Then, given a motion planning query, the connectivity of the state space reachable from the start can be recovered from a forward search tree reasoning about a local neighborhood of the edge bundle from each tree node. The work demonstrates theoretically that considering any constant radial neighborhoodmore »during this process is sufficient to guarantee asymptotic optimality. Experimental validation in five and twelve dimensional simulated systems also highlights the ability of the proposed edge bundles to express high-quality kinodynamic solutions. Our approach consistently finds higher quality solutions compared to SST, and RRT, often with faster initial solution times. The strategy of sampling kinodynamic edges is demonstrated to be a promising new paradigm.« less
  4. Worm-like robots have demonstrated great potential in navigating through environments requiring body shape deformation. Some examples include navigating within a network of pipes, crawling through rubble for search and rescue operations, and medical applications such as endoscopy and colonoscopy. In this work, we developed path planning optimization techniques and obstacle avoidance algorithms for the peristaltic method of locomotion of worm-like robots. Based on our previous path generation study using a modified rapidly exploring random tree (RRT), we have further introduced the Bézier curve to allow more path optimization flexibility. Using Bézier curves, the path planner can explore more areas and gain more flexibility to make the path smoother. We have calculated the obstacle avoidance limitations during turning tests for a six-segment robot with the developed path planning algorithm. Based on the results of our robot simulation, we determined a safe turning clearance distance with a six-body diameter between the robot and the obstacles. When the clearance is less than this value, additional methods such as backward locomotion may need to be applied for paths with high obstacle offset. Furthermore, for a worm-like robot, the paths of subsequent segments will be slightly different than the path of the head segment. Here,more »we show that as the number of segments increases, the differences between the head path and tail path increase, necessitating greater lateral clearance margins.« less
  5. Shell, Dylan A ; Toussaint, Marc (Ed.)
    We present a learning-based approach to prove infeasibility of kinematic motion planning problems. Sampling-based motion planners are effective in high-dimensional spaces but are only probabilistically complete. Consequently, these planners cannot provide a definite answer if no plan exists, which is important for high-level scenarios, such as task-motion planning. We propose a combination of bidirectional sampling-based planning (such as RRT-connect) and machine learning to construct an infeasibility proof alongside the two search trees. An infeasibility proof is a closed manifold in the obstacle region of the configuration space that separates the start and goal into disconnected components of the free configuration space. We train the manifold using common machine learning techniques and then triangulate the manifold into a polytope to prove containment in the obstacle region. Under assumptions about learning hyper-parameters and robustness of configuration space optimization, the output is either an infeasibility proof or a motion plan. We demonstrate proof construction for 3-DOF and 4-DOF manipulators and show improvement over a previous algorithm.