Identifying and Mitigating the Challenges with Vehicle Path Planning in the Presence of Dynamic Obstacles

A critical first step for a robot navigating an obstacle field is to plan a collision-free path through the environment. Historically, solutions for path planning largely use grid-based search methods particularly when guarantees are required that do not permit randomization-based methods. In large operational domains, gridding the search environment necessitates significant memory overhead and corresponding performance loss. To avoid gridded maps, grid-free path planners can achieve significant benefits to performance and memory overhead. These methods utilize visibility graphs with edge costs rather than grids with cell weights to represent possible path choices. This work presents methods to extend known 2D grid-free static environment path planners into higher dimensions to use these same planners for dynamic obstacle path planning via timespace representations. Such extensions to include time trajectories into the visibility graph readily admit path planning through highly dynamic obstacle fields; however, the resulting path plans can be sub-optimal. After reviewing the challenges of timespace grid-free path planning, this paper presents methods to recover near-optimal path plans in timespace, with only slight performance impacts, including example results.