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.
more »
« less
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.
more »
« less
- Award ID(s):
- 1734109
- NSF-PAR ID:
- 10287139
- Date Published:
- Journal Name:
- 2021 American Control Conference (ACC)
- Page Range / eLocation ID:
- 4196 to 4202
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
more » « less
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.
-
Safe path planning is critical for bipedal robots to operate in safety-critical environments. Common path planning algorithms, such as RRT or RRT*, typically use geometric or kinematic collision check algorithms to ensure collision-free paths toward the target position. However, such approaches may generate non-smooth paths that do not comply with the dynamics constraints of walking robots. It has been shown that the control barrier function (CBF) can be integrated with RRT/RRT* to synthesize dynamically feasible collision-free paths. Yet, existing work has been limited to simple circular or elliptical shape obstacles due to the challenging nature of constructing appropriate barrier functions to represent irregularly shaped obstacles. In this paper, we present a CBF-based RRT* algorithm for bipedal robots to generate a collision-free path through space with multiple polynomial-shaped obstacles. In particular, we used logistic regression to construct polynomial barrier functions from a grid map of the environment to represent irregularly shaped obstacles. Moreover, we developed a multi-step CBF steering controller to ensure the efficiency of free space exploration. The proposed approach was first validated in simulation for a differential drive model, and then experimentally evaluated with a 3D humanoid robot, Digit, in a lab setting with randomly placed obstacles.more » « less
-
null (Ed.)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 neighborhood 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.more » « less
-
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, we show that as the number of segments increases, the differences between the head path and tail path increase, necessitating greater lateral clearance margins.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.23919/ACC50511.2021.9483146
