Waypoint-Based Global Optimal Path Planning Algorithm for Mobile Robots

Dynamic programming has long been used for optimal path generation. Different from the most research works in this area which discretize the workspace and use cells for path planning, we propose a global optimal path planning method using waypoints. Although the waypoints of a simple environment with a few rectangular obstacles can be pre-defined manually, it is almost impossible to manually define the global optimal waypoints for a complex environment with many obstacles of different shapes. In this paper, we propose a global optimal path planning algorithm using automatically generated waypoints based on dynamic programming. We have shown that the proposed algorithm can find an exact optimal solution or the shortest path to the goal position from any starting point in environments with multiple convex polygon obstacles.