Motion planning with hybrid dynamics and temporal goals

Abstract

In this paper, we consider the problem of motion planning for mobile robots with nonlinear hybrid dynamics, and high-level temporal goals. We use a multi-layered synergistic framework that has been proposed recently for solving planning problems involving hybrid systems and high-level temporal goals. In that framework, a high-level planner employs a user-defined discrete abstraction of the hybrid system as well as exploration information to suggest high-level plans. A low-level sampling-based planner uses the dynamics of the hybrid system and the suggested high-level plans to explore the state-space for feasible solutions. In previous work, we have proposed a geometry-based approach for the construction of the discrete abstraction for the case when the robot is modeled as a continuous system. Here, we extend the approach for the construction of the discrete abstraction to the case when the robot is modeled as nonlinear hybrid system. To use the resulting abstraction more efficiently, we also propose a lazy-search approach for high-level planning that reduces the size of the search space by reusing previously constructed high-level plans for initializing the search. Our proposed techniques result in computational speedups of close to 10 times over other possible approaches for second-order nonlinear hybrid robot models in challenging workspace environments with obstacles and for a variety of temporal logic specifications.