loading page

R2 and R2E: Optimal Any-Angle 2D Path Planning in Binary Occupancy Grids with Non-convex Obstacles
  • Yan Kai Lai,
  • Prahlad Vadakkepat,
  • Cheng Xiang
Yan Kai Lai
National University of Singapore Department of Electrical and Computer Engineering

Corresponding Author:[email protected]

Author Profile
Prahlad Vadakkepat
National University of Singapore Department of Electrical and Computer Engineering
Author Profile
Cheng Xiang
National University of Singapore Department of Electrical and Computer Engineering
Author Profile

Abstract

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.
Dec 2023Published in Robotics and Autonomous Systems on pages 104606. https://doi.org/10.1016/j.robot.2023.104606