FreeD*: a mechanism for finding a short and collision free path

Abstract

Path planning is extensively used in different fields not only in robotics but also in games, manufacturing, auto-motive applications, and so on. Robot path planning is one of the major research issues in the area of autonomous mobile robot. The critical step in path planning problem is to find the shortest path from the start position to a defined goal position through a known, unknown, or partially known environment. Hazardous events that may devastate some parts of the intended area convert those areas to untraversable areas. These events introduce topological constraints for the robot motion because of information discrepancy about the environment before and after the damage. In this study, the authors propose a novel method, FreeD*, to find the shortest path by exploiting the benefits of D*, Dijkstra, and artificial potential field (APF) algorithms. The generated path using D* is optimised using Dijkstra by combining D* sub-paths into a single diagonal path if there is no known obstacle between them. Then, APF is used in unknown obstacle avoidance. The simulation results using Webots simulator demonstrate the effectiveness of FreeD* in avoiding unknown obstacles with shortest path.

Keywords

• motion control
• mobile robots
• collision avoidance
• short collision free path
• robot path planning
• autonomous mobile robot
• path planning problem
• shortest path
• start position
• defined goal position
• partially known environment
• intended area
• untraversable areas
• robot motion
• generated path
• single diagonal path
• automotive applications
• unknown environment
• freed^*
• artificial potential field algorithms
• hazardous events