Completeness of Randomized Kinodynamic Planners with State-based Steering

Stéphane Caron, Quang-Cuong Pham and Yoshihiko Nakamura. Robotics and Autonomous Systems. Submitted November 2015. Published December 2016.

Abstract

Probabilistic completeness is an important property in motion planning. Although it has been established with clear assumptions for geometric planners, the panorama of completeness results for kinodynamic planners is still incomplete, as most existing proofs rely on strong assumptions that are difficult, if not impossible, to verify on practical systems. In this paper, we focus on an important class of kinodynamic planners, namely those that interpolate trajectories in the state space. We provide a proof of probabilistic completeness for these planners under assumptions that can be readily verified from the system’s equations of motion and the user-defined interpolation function. Our proof relies crucially on a property of interpolated trajectories, termed second-order continuity (SOC), which we show is tightly related to the ability of a planner to benefit from denser sampling. We analyze the impact of this property in simulations on a low-torque pendulum. Our results show that a simple RRT using a second-order continuous interpolation swiftly finds solution, while it is impossible for the same planner using standard Bezier curves (which are not SOC) to find any solution

BibTeX

@article{caron2016ras,
  title = {Completeness of Randomized Kinodynamic Planners with State-based Steering},
  author = {Caron, St{\'e}phane and Pham, Quang-Cuong and Nakamura, Yoshihiko},
  journal = {Robotics and Autonomous Systems},
  year = {2017},
  volume = {89},
  pages = {85--94},
  publisher = {Elsevier},
  url = {https://arxiv.org/pdf/1511.05259v2.pdf},
  doi = {10.1016/j.robot.2016.12.002},
}

Discussion

Feel free to post a comment by e-mail using the form below. Your e-mail address will not be disclosed.

📝 You can use Markdown with $\LaTeX$ formulas in your comment.

By clicking the button below, you agree to the publication of your comment on this page.

Opens your e-mail client.