Clearance-Based Performance-Efficient Path Planning Using Generalized Voronoi Diagram

被引：3

作者：

Lee, JunTak ^{[1
]}

Kang, Tae -Won ^{[2
]}

Choi, Yong-Sik ^{[2
]}

Jung, Jin-Woo ^{[1
]}

机构：

[1] Dongguk Univ, Dept Comp Sci & Engn, Seoul, South Korea

[2] Dongguk Univ, Dept Artificial Intelligence, Seoul, South Korea

来源：

INTERNATIONAL JOURNAL OF FUZZY LOGIC AND INTELLIGENT SYSTEMS | 2023年 / 23卷 / 03期

基金：

新加坡国家研究基金会;

关键词：

Generalized Voronoi diagram; Path finding; DP algorithm; A-star algorithm; ALGORITHM;

D O I：

10.5391/IJFIS.2023.23.3.259

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

The Voronoi diagram is one of the most well-known methods in clearance-based pathfinding. The generalized Voronoi diagram, which is derived from the Voronoi diagram, accepts a polygon as input. This study proposes a method for generating and simplifying a generalized Voronoi diagram. A generalized Voronoi diagram is generated by creating a Voronoi diagram with points representing polygons. The Douglas-Peucker line simplification algorithm is used to simplify the diagram, and the A-star algorithm is used to determine the optimal path. By comparing the simplified and non-simplified versions, we determine that the simplifying process decreases the run time while preserving most of the clearance; however, the distance inefficiency of the Voronoi diagram is not overcome. Additional research is required to determine a more distance-efficient path.

引用

页码：259 / 269

页数：11

共 15 条

[11] An energy-efficient path planning algorithm for unmanned surface vehicles
Niu, Hanlin
Lu, Yu
Savvaris, Al
Tsourdos, Antonios
[J]. OCEAN ENGINEERING, 2018, 161 : 308 - 321
[12] Seidel R., 1991, Computational Geometry: Theory and Applications, V1, P51, DOI 10.1016/0925-7721(91)90012-4
[13] Toan TQ, 2017, IEEE INT SIBER CONF
[14] Wu S.T., 2004, J BRAZILIAN COMPUTER, V9, P67, DOI DOI 10.1590/S0104-65002004000100006
[15] Xiaoxiao Li, 2020, 2020 2nd International Conference on Artificial Intelligence and Advanced Manufacture (AIAM 2020), P99, DOI 10.1109/AIAM50918.2020.00025

← 1 2 →