Orchestrating Robot Fleet Trajectories: Bridging discrete planning and continuous control for non-holonomic fleets
2026 (English)Doctoral thesis, monograph (Other academic)
Abstract [en]
This manuscript addresses the problem of planning collision-free motions for a multi-robot system with non-holonomic dynamics, in environments with static obstacles, while minimizing a user-defined c ost f unction. The dynamics are a non-convex set of ODEs with no closed-form solution, and enforcing collision-avoidance introduces inter-dependencies between robots’ configuration spaces, leading to exponential growth of the search space. These properties make the multi-robot planning problem particularly challenging and worth solving. We situate our work within tightly-coupled planning approaches, contrasting trajectory optimization and graph-search methods, which offer complementary relaxations of the problem.
We show that the interplay between discrete and continuous spaces is a defining characteristic of multi-robot planning. To address it, we propose a framework that sequences a graph-based multi-robot planning method with a distributed consensus optimization approach. A discrete graph abstracts the problem into transitions on a robot-polygon occupancy graph, capturing environment connectivity, polygonal capacities, and penalties for shared regions. We demonstrate a polynomial reduction of this graph to a dynamic network that enables efficient computation of discrete trajectories minimizing polygonal transitions, path length, or makespan.
The discrete plan partitions the problem into subsets of non-overlapping robots and polygons, this parameterizes simpler optimization instances to be solved concurrently with a distributed optimization consensus method. We integrate a single-robot sequential programming method to handle dynamics nonconvexities with a proximal consensus scheme coordinating inter-robot collision constraints. This hybrid framework bridges graph-based and optimization-based methods in a non-committal manner, allowing decisions to be deferred to later phases. The proposed methodologies, individually and within the framework, are experimentally validated and shown to scale to tens of non-holonomic robots navigating environments with hundreds of polygons while finding locally optimal trajectories.
Place, publisher, year, edition, pages
Örebro: Örebro University , 2026. , p. 151
Series
Örebro Studies in Technology, ISSN 1650-8580 ; 120
Keywords [en]
trajectory optimization, multi-robot path planning, time-expanded networks, convex-programming, proximal methods, graph-based methods and decomposition
National Category
Computer Sciences
Identifiers
URN: urn:nbn:se:oru:diva-131754ISBN: 9789175298245 (print)OAI: oai:DiVA.org:oru-131754DiVA, id: diva2:2108256
Public defence
2026-11-13, Örebro universitet, Forumhuset, Hörsal F, Fakultetsgatan 1, Örebro, 13:30 (English)
Opponent
Supervisors
2026-10-062026-10-062026-10-28Bibliographically approved