IM Planner: Efficient Path Planner Based on Incremental Patch Map in Unknown Environment

Navigating in unknown environments with multiple and irregular obstacles is a crucial task for autonomous mobile systems, such as autonomous driving vehicles and mobile robots. However, most of the existing path planners can only effectively solve this problem under the small-scale precise perception conditions, and cannot handle the large-scale and high-dynamic environments. In this article, we propose a new efficient path planner called IM Planner, which concentrates on the updating and utilization of incremental patch map (IM). IM adopts a hierarchical data structure, combining multiple adjacent girds into patches as the basic unit, which facilitates memory management and query operations, and provides accurate obstacle information. After partial sensor observations arrival, IM is continuously updated in patch blocks. At the same time, tightly coupled with IM, the nonoptimized search algorithm utilizes a bidirectional strategy, and integrates a fast and accurate collision detection model, which can generate safe, kinematically feasible, and smooth trajectories without postoptimization. Extensive experimental results show that IM Planner achieves enhanced efficiency and safety performance among the offline parking benchmark and the online CARLA simulation. The code is available at https://github.com/chenghuang66/IM-Planner.