TY - CHAP
T1 - Path planning by search algorithms in graph-represented workspaces
AU - Perez, Ivan Dario Vanegas
AU - Montiel, Oscar
AU - Orozco-Rosas, Ulises
N1 - Publisher Copyright:
© 2021, The Editor(s) (if applicable) and The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - Path planning is an essential task in autonomous mobile robotics that demands to navigate following a minimum-cost path, which involves partitioning the landscape in nodes and the use of combinatorial optimization methods to find the optimal sequence of nodes to follow. Traditional algorithms such as the A* and Dijkstra are computationally efficient in landscapes with a reduced number of nodes. Most of the practical applications require to use a significantly large number of nodes up to the point that the problem might be computationally explosive. This work contributes to state-of-the-art with two heuristics for the A* algorithm that allows finding the optimal path in landscapes with a large number of nodes. The heuristics used the Euclidean and Manhattan distance in the estimation function. We present a comparative analysis of our proposal against the Dijkstra’s and A* algorithms. All the experiments were achieved using a simulation-platform specially designed for testing important algorithm features, such as the grid size, benchmark problems, the design of custom-made test sceneries, and others. Relevant results are drawn to continue working in this line.
AB - Path planning is an essential task in autonomous mobile robotics that demands to navigate following a minimum-cost path, which involves partitioning the landscape in nodes and the use of combinatorial optimization methods to find the optimal sequence of nodes to follow. Traditional algorithms such as the A* and Dijkstra are computationally efficient in landscapes with a reduced number of nodes. Most of the practical applications require to use a significantly large number of nodes up to the point that the problem might be computationally explosive. This work contributes to state-of-the-art with two heuristics for the A* algorithm that allows finding the optimal path in landscapes with a large number of nodes. The heuristics used the Euclidean and Manhattan distance in the estimation function. We present a comparative analysis of our proposal against the Dijkstra’s and A* algorithms. All the experiments were achieved using a simulation-platform specially designed for testing important algorithm features, such as the grid size, benchmark problems, the design of custom-made test sceneries, and others. Relevant results are drawn to continue working in this line.
KW - Algorithms
KW - Graph traversal
KW - Knowledge representation
KW - Path planning
KW - Simulation
UR - http://www.scopus.com/inward/record.url?scp=85095851374&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-58728-4_4
DO - 10.1007/978-3-030-58728-4_4
M3 - Capítulo
AN - SCOPUS:85095851374
T3 - Studies in Computational Intelligence
SP - 79
EP - 93
BT - Studies in Computational Intelligence
PB - Springer Science and Business Media Deutschland GmbH
ER -