Robot planning algorithm fusing visibility graph and stable sparse rapidly-exploring random tree

Abstract

The invention relates to a robot planning algorithm fusing a visibility graph and a rapidly-exploring random tree. The robot planning algorithm comprises the following steps that S1, based on the visibility graph, a topological graph is established to model the environment; S2, a shortest path is obtained through a dijkstra algorithm and serves as a reference path; S3, the reference path is divided, by combining an SST algorithm, average sampling strategies are utilized for random sampling within a certain range of the reference path; S4, the algorithm efficiency is improved through Bias-goal;S5, within the current extension range, a tree node nearest to the range of a current sampling point area is selected according to the Dubins distance; S6, transverse control strategies are adopted to select the controlled quantity to integrate a system model, and optimally dissipated nodes are preferentially expanded; and S7, if no collision occurs in the extension process, whether generated newnodes are optimal in a local neighborhood or not is studied, if yes, the nodes are added into the tree structure, and dominant nodes in the current area are trimmed. A path generated by the visibility graph can be optimized through the stable sparse rapidly-exploring random tree, so that the optimal path conforming to restriction of the nonholonomic restriction robot is obtained.

Description

technical field [0001] The invention belongs to the field of artificial intelligence automatic control, and more specifically relates to a fusion visual map method and a stable sparse random fast tree robot planning algorithm. Background technique [0002] Visibility Graph was proposed by Lozano and Wesley. The visualization method equates all actual obstacles to a collection of polygons projected into a plane. And expand the points corresponding to the starting point and the target point in space to the polygon set, and then combine the vertices of all obstacles (let V0 be the set of vertices of all obstacles), the starting point s and the target point g with a straight line Connected, and at the same time, it is required that the connection between the three parties cannot pass through obstacles, that is, the straight line is "visible", assigning weights to the edges in the graph, constructing a graph G(V,E), and the node set V=V0∪( s, g), E is the set of all arcs (Pi, P...

AI Technical Summary

Problems solved by technology

[0006] For the planning problem of robots with non-holonomic constraints in an unstructured road environment, there is no complete and mature technology at present. The existing technologies have the following problems: 1. It cannot ensure that the generated path is as short as possible; 2. The generated path is not perfect. Satisfy the non-integrity constraints of the robot; 3. The algorithm converges slowly

[0008] The application of the RRT algorithm is limited by the quality of the path, and cannot be optimized with the increase in the number of samples; the path generated by the RRT algorithm is not optimal, and is subject to random sampling. The paths generated each time are different, and the path cannot be guaranteed quality

Images