Informed Hybrid Zonotope-based Motion Planning Algorithm
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Motion PlanningSimilar Papers 제목 키워드 기반
Hybrid System Planning using a Mixed-Integer ADMM Heuristic and Hybrid Zonotopes
Embedded optimization-based planning for hybrid systems is challenging due to the use of mixed-integer programming, which is computationally intensive and often sensitive to the specific numerical formulation. To address…
Autonomous DrivingMotion PlanningMixed-Integer MPC-Based Motion Planning Using Hybrid Zonotopes with Tight Relaxations
Autonomous vehicle (AV) motion planning problems often involve non-convex constraints, which present a major barrier to applying model predictive control (MPC) in real time on embedded hardware. This paper presents an ap…
Model Predictive ControlMotion PlanningEnergy-Aware Predictive Motion Planning for Autonomous Vehicles Using a Hybrid Zonotope Constraint Representation
Uncrewed aerial systems have tightly coupled energy and motion dynamics which must be accounted for by onboard planning algorithms. This work proposes a strategy for coupled motion and energy planning using model predict…
Autonomous VehiclesModel Predictive ControlMotion PlanningMotion Planning with Metric Temporal Logic Using Reachability Analysis and Hybrid Zonotopes
Metric temporal logic (MTL) provides a formal framework for defining time-dependent mission requirements on autonomous vehicles. However, optimizing control decisions subject to these constraints is often computationally…
Autonomous VehiclesMotion PlanningOn the Difficulty of Intersection Checking with Polynomial Zonotopes
Polynomial zonotopes, a non-convex set representation, have a wide range of applications from real-time motion planning and control in robotics, to reachability analysis of nonlinear systems and safety shielding in reinf…
Motion Planning