Content area
With the increasing demand for autonomous robots operating in complex environments, motion planning in cluttered and unknown spaces has become a critical research area. A promising approach involves decomposing the environment into free regions and planning trajectories through these regions. However, the inherent complexity and nonconvexity of collision-free configuration spaces pose significant challenges in effectively modeling containment relationships, particularly when dealing with intricate obstacle layouts and arbitrary robot geometries. Existing free space decomposition methods suffer from significant limitations: they either lack theoretical safety guarantees or oversimplify robot geometries to achieve computational tractability. This dissertation addresses two critical problems: (i) how to effectively model containment relationships between arbitrary robot geometries and free regions through rigorous mathematical formulations, and (ii) how to develop effective motion planning strategies with safety assurance in unknown cluttered environments by utilizing these geometric relationships. To address these challenges, this dissertation investigates geometric relationships between general shapes described by polynomial sets and leverages polynomial optimization theory to model precise spatial constraints between robot geometries and free regions. By employing semidefinite relaxation techniques, we render these geometric constraints computationally tractable while preserving certifiable safety guarantees. Through the integration of conic programming solvers with nonlinear programming techniques, motion planning problems incorporating the developed safety constraints can be efficiently solved for both reactive control and trajectory planning through sequences of free regions. We validate our algorithms through comprehensive simulations and real-world experiments in complex environments. Results demonstrate that our polynomial optimization-based approach successfully provides certifiable safety guarantees while achieving real-time computational performance, enabling robots to navigate complex unknown environments with accurate geometric modeling and robust collision avoidance capabilities.