Path Planning Algorithm Based on Obstacle Clustering Analysis and Graph Search

Path planning is receiving considerable interest in mobile robot research; however, a large number of redundant nodes are typically encountered in the path search process for large-scale maps, resulting in decreased algorithmic efficiency. To address this problem, this paper proposes a graph search...

Full description

Saved in:
Bibliographic Details
Published in:Symmetry (Basel) 2023-08, Vol.15 (8), p.1498
Main Authors: Wang, Lei, Sun, Lifan
Format: Article
Language:English
Subjects:
A algorithm
Algorithms
Analysis
Artificial intelligence
Barriers
Cluster analysis
Clustering
collision detection
Control engineering
Datasets
DBSCAN algorithm
effective edge points
Efficiency
Heuristic
Methods
Neighborhoods
Nodes
Optimization
Path planning
Restaurants
Robots
Search process
weighted graph
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Path planning is receiving considerable interest in mobile robot research; however, a large number of redundant nodes are typically encountered in the path search process for large-scale maps, resulting in decreased algorithmic efficiency. To address this problem, this paper proposes a graph search path planning algorithm that is based on map preprocessing for creating a weighted graph in the map, thus obtaining a structured search framework. In addition, the reductions in the DBSCAN algorithm were analyzed. Subsequently, the optimal combination of the minPts and Eps required to achieve an efficient and accurate clustering of obstacle communities was determined. The effective edge points were then found by performing obstacle collision detection between special grid nodes. A straight-line connection or A* planning strategy was used between the effective edge points to establish a weighted, undirected graph that contained the start and end points, thereby achieving a structured search framework. This approach reduces the impact of map scale on the time cost of the algorithm and improves the efficiency of path planning. The results of the simulation experiments indicate that the number of nodes to be calculated in the search process of the weighted graph decreases significantly when using the proposed algorithm, thus improving the path planning efficiency. The proposed algorithm offers excellent performance for large-scale maps with few obstacles.
ISSN:2073-8994
2073-8994
DOI:10.3390/sym15081498