Deterministic RG-Trees via Voronoi diagrams
Journal of Computational Science, cilt.100, 2026 (SCI-Expanded, Scopus)
- Yayın Türü: Makale / Tam Makale
- Cilt numarası: 100
- Basım Tarihi: 2026
- Doi Numarası: 10.1016/j.jocs.2026.102977
- Dergi Adı: Journal of Computational Science
- Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Compendex, INSPEC
- Anahtar Kelimeler: Dynamic feasibility, Feedback motion planning, Reference governor, Safety, Voronoi diagram
- Orta Doğu Teknik Üniversitesi Adresli: Evet
Özet
Autonomous navigation in obstacle environments requires motion planners that ensure safety, dynamic feasibility, and real-time execution. Region-based feedback motion planning methods offer formal safety guarantees by integrating control design with spatial decomposition. This paper presents a novel end-to-end deterministic feedback motion planning framework that unifies efficient geometric path computation with region-based control via reference governors (RGs). A collision-free reference path is first generated using Voronoi diagrams, exploiting their global visibility and obstacle clearance properties. Around this path, a structured sequence of overlapping rectangular regions is automatically constructed. Within each region, RGs are applied to ensure dynamic feasibility and collision avoidance throughout the robot motion. We introduce gateway regions to enlarge region intersections and smooth transitions between regions. Furthermore, the use of pre-computed scalable RGs enables real-time implementation with negligible online computation. Overall, our method guarantees formal safety, constraint satisfaction, and completeness in the considered nominal setting, while yielding repeatable motion planning outcomes for a fixed environment, start, and goal. Comprehensive simulations in various complex environments, including comparisons with Kino-RRT* as a representative sampling-based kinodynamic planner and path-following nonlinear model predictive control (NMPC) as an optimization-based deterministic baseline, demonstrate the effectiveness, computational efficiency, and repeatability of the proposed framework.