Rapidly-exploring random tree path smoothing method

A random tree and path technology, applied to road network navigators, navigation, instruments, etc., can solve problems such as detours, shortened path length, and many path turns, achieving obvious effects, shortened path length, and improved smoothness

Active Publication Date: 2019-09-27
ANHUI UNIV OF SCI & TECH
View PDF4 Cites 12 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

[0005] In view of the fact that the path generated by the traditional RRT algorithm may contain edges and corners, the path has many turning points, and there are detours, the present invention proposes a simple and effective path smoothing algorithm based on Douglas-Peucke (D-P) algorithm and B-spline function , so that the path length is significantly shortened, the inflection points are significantly reduced, and the path is smoother

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Rapidly-exploring random tree path smoothing method
  • Rapidly-exploring random tree path smoothing method
  • Rapidly-exploring random tree path smoothing method

Examples

Experimental program
Comparison scheme
Effect test

Embodiment Construction

[0036] In conjunction with the accompanying drawings, the specific implementation steps of the present invention are described in detail as follows:

[0037] 1) Given a map of the environment where the robot is located, read the environment map, convert the map matrix to a binary value, and generate a two-dimensional integer array with values ​​of 0 and 1, where 0 represents a passable point and 1 represents an obstacle point.

[0038] 2) The starting node q of the given robot start with the target node q goal , judge the given start node q start and the target node q goal Whether the value of the coordinate value in the two-dimensional integer array map has 1, if it is not 1, go to step 3); if there is 1, then re-enter the starting node or the target node;

[0039] 3) Start with node q start As the root node of the rapidly expanding random tree spanning tree, build a random tree T 1 ;

[0040] 4) in the map q start Nearby randomly selects a sampling point q based on pr...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

PUM

No PUM Login to view more

Abstract

The invention discloses a rapidly-exploring random tree path smoothing method. The method in the invention is a path smoothing method based on a Douglas-Peucker algorithm and a B spline function. The method comprises the following steps: firstly, extracting a plurality of nodes from a path node generated by a rapidly-exploring random tree algorithm to serve as a key road sign by using the Douglas-Peucker algorithm; then, fitting a key road sign by adopting the B spline function to obtain a smooth path with a continuous curvature, so that smoothing of the planned path is realized, and the problems that excessive redundant points exist in the path generated by the rapidly-exploring random tree algorithm and the turning points of the path are large are solved.

Description

technical field [0001] The invention relates to the field of intelligent robot path planning, in particular to a fast expanding random tree path smoothing method. Background technique [0002] Path planning for autonomous mobile robots refers to finding an optimal or sub-optimal path that can avoid obstacles in the environment where the robot is located after a given starting point and ending point according to certain performance indicators, which is the key to autonomous navigation of the robot. technical link. Traditional path planning algorithms include visual graph method, Voronoi diagram method, Delaunay triangulation method, etc., but their generality is not good, and the algorithm is limited by the use environment; in order to overcome the shortcomings of traditional algorithms, researchers propose some intelligent optimization algorithms , for example: ant colony algorithm, genetic algorithm, etc. Due to the shortcomings of convergence speed and real-time performan...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

Application Information

Patent Timeline
no application Login to view more
IPC IPC(8): G01C21/00G01C21/34
CPCG01C21/00G01C21/3446
Inventor 姜媛媛陶德俊刘延彬时美乐余泳
Owner ANHUI UNIV OF SCI & TECH
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Try Eureka
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap