Optimized and Efficient Path-Finding Algorithms

Abstract

Both employees and customers have suffered from understaffing and overcrowding. Using robots to replace the shortage of workers can reduce the workload on the workers and satisfy customers’ demands. However, to use a robot as a server, it needs to know a good path, and there are too many path-finding algorithms to implement.

In this study, we assessed the performance of Dijkstra and A* path-finding algorithms in a simulated restaurant setting with all possible routes mapped by Probabilistic Roadmap (PRM) and Voronoi diagram algorithms. The effectiveness of each path-finding algorithm was then evaluated based on the time taken, the length of the path, and the number of collisions in the completed route. This paper concludes with the advantages and disadvantages of each path-finding and path-planning algorithm as if the algorithm were implemented in restaurant robots.

Authors
Akar (Ace) Kaung — kaung006@umn.edu
Yanai Sun — sun00105@umn.edu

Recommended citation: Kaung, Akar (Ace), and Yanai Sun. (2022). Optimized and Efficient Path-Finding Algorithms. Independent Research.
Download Paper