RRT-based grid map traversal algorithm

Abstract

The invention discloses a raster map traversal algorithm based on RRT. The raster map traversal algorithm comprises the following steps: (1) determining a search range according to a to-be-explored raster map; (2) taking the position of the robot as a starting point in the search range determined in the step (1), taking the starting point as a root node, and storing the starting point into a father node set; (3) defining the pixel state of the pixel points in the obstacle area or the position area in the grid map as black, expanding in a radius r form on the basis of the coordinates of the pixel points in the obstacle area or the position area, and defining the pixel state of the area obtained through expansion as black; (4) carrying out grid map traversal in the search range by adopting an RRT algorithm. According to the method, the grid map is subjected to expansion processing, unnecessary features in the map are reduced, expansion can be carried out even in an area with unknown features, the expanded features serve as detection objects in the collision detection stage in the RRT exploration process, and the leakage detection phenomenon can be perfectly solved.

Description

technical field [0001] The invention relates to the technical field of robots, in particular to an RRT-based raster map traversal algorithm. Background technique [0002] The current strategy for exploring grid maps based on RRT is to start from the parent node, randomly generate a series of corresponding child nodes around it, and perform collision detection and distance calculation on them in turn, so as to obtain the most suitable child nodes, and The child node is connected to the parent node and added to the entire dendrogram. In this process, the way of collision detection is to connect the current newly generated child node with the parent node, traverse each point on this line with a certain step size, and check whether there is a certain point on this line It is a black pixel (obstacle part), if it exists, delete the connection line and discard the point. In this process, if the thickness of the obstacle is small, there will be a phenomenon of missing detection, w...

AI Technical Summary

Problems solved by technology

In this process, if the thickness of the obstacle is small, there will be a phenomenon of missing detection, which will cause the child node to rush out of the boundary of the obstacle, resulting in wrong exploration

[0003] In the process of collision detection, since the grid map is composed of square pixels, if the thickness of obstacles is small and the arrangement is non-orthogonal, there will be two squares connected by corner points. At this time, if the step size of collision detection If the setting is not small enough, it will cause missed detection. If the step size of collision detection is too small, it will cause a large load of calculation examples; if the given grid map is established by the slam method, for some features less Obstacles, with fewer black pixels, cannot perfectly describe the boundary of the entire map, and will also cause missed detection in collision detection

For raster maps, this design suffers from poor robustness

Images