iDb-A*: Iterative Search and Optimization for Optimal Kinodynamic Motion Planning
IEEE Transactions on Robotics · 2025 · 41 · 2031-2049
DOI: 10.1109/tro.2024.3502505 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE Transactions on Robotics, 2025. Verfasst von Joaquim Ortiz-Haro und 3 weiteren Autor:innen. Die Arbeit wurde bisher 15-mal zitiert (Crossref) und nennt 66 Literaturangaben. Gefördert von: Deutsche Forschungsgemeinschaft, German-Israeli Foundation for Scientific Research.
Abstract (Originalsprache)
Motion planning for robotic systems with complex dynamics is a challenging problem. While recent sampling-based algorithms achieve asymptotic optimality by propagating random control inputs, their empirical convergence rate is often poor, especially in high-dimensional systems such as multirotors. An alternative approach is to first plan with a simplified geometric model and then use trajectory optimization to follow the reference path while accounting for the true dynamics. However, this approach may fail to produce a valid trajectory if the initial guess is not close to a dynamically feasible trajectory. In this article, we present Iterative Discontinuity Bounded A* (iDb-A*), a novel kinodynamic motion planner that combines search and optimization iteratively. The search step utilizes a finite set of short trajectories (motion primitives) that are interconnected while allowing for a bounded discontinuity between them. The optimization step locally repairs the discontinuities with trajectory optimization. By progressively reducing the allowed discontinuity and incorporating more motion primitives, our algorithm achieves asymptotic optimality with excellent any-time performance. We provide a benchmark of 43 problems across eight different dynamical systems, including different versions of unicycles and multirotors. Compared to state-of-the-art methods, iDb-A* consistently solves more problem instances and finds lower-cost solutions more rapidly.
Förderung
- Deutsche Forschungsgemeinschaft
- German-Israeli Foundation for Scientific Research
Zitieren
APA
Ortiz-Haro, J., Hönig, W., Hartmann, V. N., & Toussaint, M. (2025). iDb-A*: Iterative Search and Optimization for Optimal Kinodynamic Motion Planning. IEEE Transactions on Robotics, 41, 2031-2049. https://doi.org/10.1109/tro.2024.3502505
Vancouver
Ortiz-Haro J, Hönig W, Hartmann VN, Toussaint M. iDb-A*: Iterative Search and Optimization for Optimal Kinodynamic Motion Planning. IEEE Transactions on Robotics. 2025;41:2031-2049. doi:10.1109/tro.2024.3502505
BibTeX
@article{OrtizHaro2025,
author = {Ortiz-Haro, Joaquim and Hönig, Wolfgang and Hartmann, Valentin N. and Toussaint, Marc},
title = {iDb-A*: Iterative Search and Optimization for Optimal Kinodynamic Motion Planning},
journal = {IEEE Transactions on Robotics},
year = {2025},
volume = {41},
pages = {2031--2049},
doi = {10.1109/tro.2024.3502505}
}
EUVIMED