A Comparative Study of Path-Planning Algorithms for Autonomous Mobile Robot Navigation

Abstract

An autonomous mobile robot must find its way from where it is to where itmust go without colliding with the obstacles around it, and the algorithm that computes this route, the path planner, largely determines how good the route is and how quickly it is found. This study compares several widely used path-planning algorithms for mobile robot navigation, by the quality of the paths they produce and the effort they require. Three representative algorithms were considered: an uninformed graph search that explores outward from the start, an informed graph search that uses a heuristic to guide its exploration toward the goal, and a sampling-based planner that builds a tree of random feasible motions through the space, and each was used to plan a path from a start to a goal in an environment containing obstacles. The two graph-search algorithms found the shortest, or very nearly the shortest, path, but the uninformed search explored far more of the environment to do so, while the informed search, guided by its heuristic toward the goal, reached the same path having explored much less, and so was faster. The sampling-based planner found a feasible path quickly even though the path was not the shortest and was less smooth, and it scaled better to larger and higher-dimensional spaces where the graph searches become expensive. No single algorithm was best in every respect; the graph searches offered optimality at greater cost in confined spaces, and the sampling-based planner offered speed and scalability at the cost of optimality. The study shows that the choice of path-planning algorithm should be guided by whether optimality, speed, or scalability matters most for the robot and its environment. KEYWORDS: Path planning, Mobile robots, A* algorithm, Dijkstra'salgorithm, Rapidly-exploring random tree, Autonomous navigation, Motionplanning, Obstacle avoidance, Sampling-based planning