Vector-based Estimation of Corridor Width via the Visibility Graph to Mitigate the Effect of Obstacle Uncertainty on Path Cost

With an accurate map of the environment, a map-based planner seeks a global path that avoids collisions with obstacles. However, if map errors in obstacle size and position are discovered during path execution where corridor width is insufficient, replanning may be necessary to divert from the original path plan, yet this may be impossible or may incur severe path costs. A common method to plan paths uses visibility graphs, and the algorithm herein leverages these to estimate corridor width by employing geometric ray projections implicit in determining point-to-point connectivity. Thus, if the visibility graph is already being calculated, this method requires little additional computational effort to enable path planning in consideration of corridor width. Simulations are presented that use county-scale floodplain maps in central Pennsylvania to analyze the ability to incentivize corridor width to navigate between start-goal pairs. The results show that, with corridor incentives, replanning is 30% more likely to be feasible for intermediate obstacle dilation values. Further, pre-planned corridor-aware paths are feasible with approximately twice as much size dilation versus nominal visibility graph planning methods.