Surface Optimal Path Planning Using an Extended Dijkstra Algorithm
Extensive studies have been conducted on the Dijkstra algorithm owing to its bright prospect. However, few of them have studied the surface path planning of mobile robots. Currently, some application fields (e.g., wild ground, planet ground, and game scene) need to solve the optimal surface path. Th...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2020-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9165710/ |
| _version_ | 1818920837377425408 |
|---|---|
| author | Min Luo Xiaorong Hou Jing Yang |
| author_facet | Min Luo Xiaorong Hou Jing Yang |
| author_sort | Min Luo |
| collection | DOAJ |
| description | Extensive studies have been conducted on the Dijkstra algorithm owing to its bright prospect. However, few of them have studied the surface path planning of mobile robots. Currently, some application fields (e.g., wild ground, planet ground, and game scene) need to solve the optimal surface path. This paper proposes an extended Dijkstra algorithm. We utilize the Delaunay triangulation to model the surface environment. Based on keeping the triangle side length unchanged, the triangle mesh on the surface is equivalently converted into a triangle on the two-dimensional plane. Through this transformation, we set up the two-dimensional developable passable channel of the surface and solve the optimal route on this channel. Traversing all the two-dimensional developable and passable paths of the surface, we can get the shortest route among all the optimal paths. Then the inverse transformation from the two-dimensional plane coordinates to the corresponding surface coordinates obtains the surface optimal path. The simulation results show that, compared with the traditional Dijkstra algorithm, this method improves the accuracy of the surface optimization path in single-robot single-target and multi-robot multi-target path planning tasks. |
| first_indexed | 2024-12-20T01:28:06Z |
| format | Article |
| id | doaj.art-3ab3a6dd64c8405cb2776aa9759928bd |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-20T01:28:06Z |
| publishDate | 2020-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-3ab3a6dd64c8405cb2776aa9759928bd2022-12-21T19:58:11ZengIEEEIEEE Access2169-35362020-01-01814782714783810.1109/ACCESS.2020.30159769165710Surface Optimal Path Planning Using an Extended Dijkstra AlgorithmMin Luo0https://orcid.org/0000-0002-3154-1657Xiaorong Hou1https://orcid.org/0000-0001-8217-8491Jing Yang2School of Automation Engineering, University of Electronic Science and Technology of China, Chengdu, ChinaSchool of Automation Engineering, University of Electronic Science and Technology of China, Chengdu, ChinaSchool of Automation Engineering, University of Electronic Science and Technology of China, Chengdu, ChinaExtensive studies have been conducted on the Dijkstra algorithm owing to its bright prospect. However, few of them have studied the surface path planning of mobile robots. Currently, some application fields (e.g., wild ground, planet ground, and game scene) need to solve the optimal surface path. This paper proposes an extended Dijkstra algorithm. We utilize the Delaunay triangulation to model the surface environment. Based on keeping the triangle side length unchanged, the triangle mesh on the surface is equivalently converted into a triangle on the two-dimensional plane. Through this transformation, we set up the two-dimensional developable passable channel of the surface and solve the optimal route on this channel. Traversing all the two-dimensional developable and passable paths of the surface, we can get the shortest route among all the optimal paths. Then the inverse transformation from the two-dimensional plane coordinates to the corresponding surface coordinates obtains the surface optimal path. The simulation results show that, compared with the traditional Dijkstra algorithm, this method improves the accuracy of the surface optimization path in single-robot single-target and multi-robot multi-target path planning tasks.https://ieeexplore.ieee.org/document/9165710/Dijkstra algorithmpath planningsurfaceDelaunay triangulationmobile robotsoptimization methods |
| spellingShingle | Min Luo Xiaorong Hou Jing Yang Surface Optimal Path Planning Using an Extended Dijkstra Algorithm IEEE Access Dijkstra algorithm path planning surface Delaunay triangulation mobile robots optimization methods |
| title | Surface Optimal Path Planning Using an Extended Dijkstra Algorithm |
| title_full | Surface Optimal Path Planning Using an Extended Dijkstra Algorithm |
| title_fullStr | Surface Optimal Path Planning Using an Extended Dijkstra Algorithm |
| title_full_unstemmed | Surface Optimal Path Planning Using an Extended Dijkstra Algorithm |
| title_short | Surface Optimal Path Planning Using an Extended Dijkstra Algorithm |
| title_sort | surface optimal path planning using an extended dijkstra algorithm |
| topic | Dijkstra algorithm path planning surface Delaunay triangulation mobile robots optimization methods |
| url | https://ieeexplore.ieee.org/document/9165710/ |
| work_keys_str_mv | AT minluo surfaceoptimalpathplanningusinganextendeddijkstraalgorithm AT xiaoronghou surfaceoptimalpathplanningusinganextendeddijkstraalgorithm AT jingyang surfaceoptimalpathplanningusinganextendeddijkstraalgorithm |