Motion planning with hybrid dynamics and temporal goals
- 1 December 2010
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2648 (01912216) , 1108-1115
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.Keywords
This publication has 25 references indexed in Scilit:
- Coverage-guided test generation for continuous and hybrid systemsFormal Methods in System Design, 2009
- Temporal logic motion planning for dynamic robotsAutomatica, 2009
- Hybrid systems: from verification to falsification by combining motion planning and discrete searchFormal Methods in System Design, 2008
- Sampling-Based Resolution-Complete Algorithms for Safety Falsification of Linear SystemsLecture Notes in Computer Science, 2008
- OOPS for Motion Planning: An Online, Open-source, Programming System2007
- Sampling-based planning, control and verification of hybrid systemsIEE Proceedings - Control Theory and Applications, 2006
- Incremental Search Methods for Reachability Analysis of Continuous and Hybrid SystemsLecture Notes in Computer Science, 2004
- Efficient Model Checking of Safety Properties2003
- Triangle: Engineering a 2D quality mesh generator and Delaunay triangulator1996
- The algorithmic analysis of hybrid systemsTheoretical Computer Science, 1995