Informed Hybrid Zonotope-based Motion Planning Algorithm
This addresses scalability issues in motion planning for robotics or autonomous systems, though it appears incremental as it builds on existing informed planners with specific improvements.
The paper tackles the computational challenge of optimal path planning in nonconvex free spaces by proposing HZ-MP, an informed Hybrid Zonotope-based Motion Planner that decomposes obstacle-free space and uses guided sampling to reduce wasted exploration. The result is a probabilistically complete and asymptotically optimal algorithm that converges to high-quality trajectories within a small number of iterations.
Optimal path planning in nonconvex free spaces poses substantial computational challenges. A common approach formulates such problems as mixed-integer linear programs (MILPs); however, solving general MILPs is computationally intractable and severely limits scalability. To address these limitations, we propose HZ-MP, an informed Hybrid Zonotope-based Motion Planner, which decomposes the obstacle-free space and performs low-dimensional face sampling guided by an ellipsotope heuristic, thereby concentrating exploration on promising transition regions. This structured exploration mitigates the excessive wasted sampling that degrades existing informed planners in narrow-passage or enclosed-goal scenarios. We prove that HZ-MP is probabilistically complete and asymptotically optimal, and demonstrate empirically that it converges to high-quality trajectories within a small number of iterations.