Back to Search
Start Over
Path planning of a mobile robot among curved obstacles through tangent drawing and trapezoidal decomposition
- Source :
- Engineering Science and Technology, an International Journal, Vol 24, Iss 6, Pp 1415-1427 (2021)
- Publication Year :
- 2021
- Publisher :
- Elsevier, 2021.
-
Abstract
- Most of the previous studies on mobile robot path planning consider the obstacles as polygons. However, the complex shaped obstacles should be considered as curves rather than polygons, since the latter may result in non-optimal paths. Three new algorithms are proposed for finding the shortest path of a mobile robot among curved obstacles: TAD which uses a tangent drawing method, TRAD which uses trapezoidal decomposition, and TAD-TRAD which uses a combination of the TAD and the TRAD algorithms. The time complexities of the TAD algorithm, the TRAD algorithm, and the TAD-TRAD algorithm are O ( n 3 log n ) , O ( n log n ) , and O ( n ( log n ) 2 ) respectively, where n is the total number of arcs in all the obstacles. The TAD and the TAD-TRAD algorithms compute an optimal shortest path, whereas the TRAD algorithm computes an approximate shortest path, among curved obstacles. The TAD algorithm has a lower time complexity than existing algorithms which are implemented for the computation of the optimal shortest path. The TRAD algorithm has a lower time complexity than existing algorithms which compute an approximate shortest path and the TAD-TRAD algorithm has a lower time complexity than existing algorithms which compute an optimal shortest path. The experimental comparison of the TAD, TRAD, and TAD-TRAD algorithms on 200 randomly generated problems shows that the TAD-TRAD algorithm has the least running time. Moreover, the TAD-TRAD algorithm computes an optimal path using a lesser number of tangents and with lesser time complexity when experimental comparisons are performed with existing algorithms in the literature.
- Subjects :
- Computer Networks and Communications
Computer science
020209 energy
Computation
02 engineering and technology
Biomaterials
Mobile robot
0202 electrical engineering, electronic engineering, information engineering
Motion planning
Time complexity
Path planning
Tangent
Civil and Structural Engineering
Fluid Flow and Transfer Processes
Mechanical Engineering
020208 electrical & electronic engineering
Metals and Alloys
Binary logarithm
Engineering (General). Civil engineering (General)
Electronic, Optical and Magnetic Materials
Curved obstacle
Hardware and Architecture
Shortest path problem
Path (graph theory)
TA1-2040
Algorithm
Subjects
Details
- Language :
- English
- ISSN :
- 22150986
- Volume :
- 24
- Issue :
- 6
- Database :
- OpenAIRE
- Journal :
- Engineering Science and Technology, an International Journal
- Accession number :
- edsair.doi.dedup.....4d9c79f7d1336250de0e63adb25a6f6a