Path planning method for improving RRT algorithm reconnection strategy

Abstract

The invention discloses a path planning method for improving an RRT algorithm reconnection strategy, and the method comprises the steps: loading and initializing a grid map, determining a starting point and a target point, and initializing a random tree; obtaining a random sampling point based on a target-oriented sampling strategy; expanding tree nodes by using a target offset and obstacle tangential offset strategy; creating a new father node of the extension point near the obstacle by using a dichotomy method, and updating the random tree according to the new extension point when it is judged that no collision occurs; carrying out pruning and reconnection on other nodes except the extended node in the super-body sphere under a certain radius near the extended node by utilizing triangular inequality constraint; judging whether the distance between the new extension point and the target point is smaller than a first distance threshold value or not; if yes, generating a global path; and if not, returning to the step of generating the random sampling point based on the preset target-oriented strategy random sampling function and continuing to execute.

Description

technical field [0001] The present invention relates to the technical field of autonomous navigation, and in particular uses an RRT path planning related algorithm. The present invention relates to a robot path planning method based on a pruning and reconnection strategy of an improved RRT algorithm. Background technique [0002] In recent years, autonomous mobile robots have played an important role in areas such as safety inspections, emergency rescue, and unmanned transportation. As a basic research topic of mobile robots, path planning has received extensive attention. Given partial information about the surrounding environment, mobile robots need to autonomously plan optimal or suboptimal collision-free paths between two specified locations that satisfy certain conditions (such as distance or smoothness). It is critical to the performance of unmanned autonomous systems, such as unmanned aerial vehicles, unmanned ground vehicles, and unmanned underwater vehicles. Impro...

AI Technical Summary

Problems solved by technology

Grid-based search algorithms, such as Dijkstra algorithm, theta* algorithm, A* algorithm, D*-lite algorithm, etc.; meta-heuristic algorithms, such as genetic algorithm (Genetic Algorithm, GA), particle swarm algorithm (Particle Swarm Algorithm, PSO) ), ant colony algorithm (Ant Colony Algorithm, ACO), etc., which are inspired by the phenomenon of biological swarm intelligence in nature, and proposed by imitating the behavior of social animals. This type of algorithm does not require the continuity of the objective function and constraints, and is very suitable for solving The NP problem (Non-deterministic Polynomial Problem, non-deterministic polynomial problem) has a strong adaptability to the uncertainty in the data, but on the one hand, due to the lack of global information, it is often easy to fall into a local minimum, and only approximate On the other hand, since this type of algorithm needs to iteratively converge, the solution is inefficient and takes too long

Images