  This paper introduces a new method for robot motion planning and navigation
in uneven environments through a surfel representation of underlying point
clouds. The proposed method addresses the shortcomings of state-of-the-art
navigation methods by incorporating both kinematic and physical constraints of
a robot with standard motion planning algorithms (e.g., those from the Open
Motion Planning Library), thus enabling efficient sampling-based planners for
challenging uneven terrain navigation on raw point cloud maps. Unlike
techniques based on Digital Elevation Maps (DEMs), our novel surfel-based
state-space formulation and implementation are based on raw point cloud maps,
allowing for the modeling of overlapping surfaces such as bridges, piers, and
tunnels. Experimental results demonstrate the robustness of the proposed method
for robot navigation in real and simulated unstructured environments. The
proposed approach also optimizes planners' performances by boosting their
success rates up to 5x for challenging unstructured terrain planning and
navigation, thanks to our surfel-based approach's robot constraint-aware
sampling strategy. Finally, we provide an open-source implementation of the
proposed method to benefit the robotics community.
