In this work, we introduce the Tangent Line Decomposition (TLD) algorithm, a new approach to finding collision-free paths in 2D polygon and 3D polyhedron environments.
TLD simplifies path planning by breaking it into smaller steps, focusing on one key obstacle at a time. Instead of building a complete graph, it uses a best-first search to reduce unnecessary computations. While the paths generated by TLD may not always be optimal, they can serve as a helpful starting point for other algorithms to refine further.
In our experiments, TLD showed improvements over the baseline LTA* method, achieving faster planning speeds in both 2D and 3D environments. The approach is also flexible, working in both convex and concave obstacle settings when combined with convex decomposition.
We look forward to sharing more details at ICRA 2025 and learning from others in the field!
