Flow methods improve connectivity planning for multi-agent systems
Mixed-integer flow formulations for motion planning and decision-making of networked multi-agent systems
Multiagent Systems
Summary
When many robots or vehicles need to work together, they must keep good communication links between each other. The authors studied a math-based way to plan their movements that makes sure these connections stay strong. Their new method reduces some math problems to sizes that computers can handle better, allowing for plans with more robots than before. However, while some parts of their method make things theoretically simpler, this doesn’t always speed up the overall planning process in practice.
What this means in practice
- •For robotics engineers: Coordinate multiple robots while maintaining communication links using flow-based constraints for more scalable trajectory planning approaches.
- •For autonomous vehicle developers: Plan networked vehicle maneuvers with better connectivity guarantees and computational efficiency for larger fleets.
Authors
Angelo Caregnato-Neto, Paul-Louis Delacour, Raf Van de Plas, Tamás Keviczky, Janito Vaqueiro Ferreira
Abstract
This work investigates the use of flow-based connectivity maintenance constraints in mixed-integer linear programming (MILP) trajectory planning and decision-making models for networked multi-agent systems (MAS). We integrate flow-based encodings for standard and k-hop connectivity into MILP multi-vehicle maneuvering models that are widely used alongside receding horizon planning strategies. Their necessity and sufficiency is demonstrated, guaranteeing full coverage of potential network topologies. The flow formulation for standard connectivity decreases the growth of the required inequality constraints from exponential to polynomial w.r.t. the size of the MAS when compared to the state-of-the-art subtour elimination (SEC) method. The flow-based k-hop connectivity constraints decrease the number of required binary variables and decouple its growth from the number of hops. However, the impact of these formulations in performance is not straightforward due to the introduction of a substantial number of continuous flow optimization variables and, in the case of k-hop connectivity, additional inequality constraints. We investigate this trade-off through a statistical evaluation of costs and optimization times using a conventional branch-and-bound commercial solver and trials performed with randomized environments for increasingly larger MAS. The results show that the flow formulation outperforms SEC in standard connectivity problems, enabling the solutions to be computed for larger MAS considering the imposed optimization time limit. The reduction in number of binary variables enabled by the k-hop flow formulations decreases the theoretical worst-case number of iterations required by the branch-and-bound algorithm to compute the global optimal solution. Our results show that this advantage did not translate into improvements in the average performance when compared to the baseline.