Incremental Distance Transform for Online Motion Planning Based on Combined Wavefront

Recently, the distance transform (DT) has become an essential component in many online motion planning systems for obstacle avoidance in unknown and unstructured environments. However, numerous repeated calculations for each voxel lead to extreme time consumption. Inspired by the spatial clustering effect of voxels, a DT method based on the combined wavefront is proposed to enhance mapping efficiency. Firstly, the distance maps (DMs) model of DT divides the workspace into voxels and stores occupancy probability, distance, and the closest obstacle index information. Secondly, utilizing depth and pose data from sensors such as LiDAR and radar, the proposed method calculates the occupancy probability and generates an initial combined wavefront. This wavefront records voxels whose occupancy changes from free to occupied or vice versa. Finally, a dynamic propagating algorithm is employed to move the combined wavefront forward and update the distance and closest obstacle index of the DMs. Simulated and real-world experiments demonstrate that the proposed method achieves comparable accuracy while having lower initial and incremental mapping time compared to different mainstream methods. Furthermore, the practicality of the approach is proven through its integration into a quadrotor motion planning system and successful onboard flight tests.