R2 and R2E: Optimal Any-Angle 2D Path Planning in Binary Occupancy Grids with Non-convex Obstacles

A novel any-angle vector-based path planner, R2, is introduced in this paper. R2 is optimal, online and can work on any binary occupancy grid with non-convex obstacles. R2 delays line-of-sight checks and expands only the most promising turning points. Two novel concepts for vector-based algorithms delaying line-of-sight checks, pseudo targets and the progression rule, are introduced. The progression rule tracks the angular progression of searches along obstacle contours, bypassing convex hulls in non-convex obstacles where paths do not exist. Pseudo targets are imaginary turning points and are placed at non-convex corners. Pseudo targets improve cost-to-go estimates, allowing the path cost estimate to increase monotonically during searches without verifying line-of-sight. As R2 has exponential search times in the worst case, R2 is extended to R2E to improve average search times on maps with many non-convex or disjoint obstacles. Both variants are shown to return paths very rapidly if the map is sparse, the shortest path has few turning points, and if the shortest path is long.