arXiv preprint ·
Mixed-integer flow formulations for motion planning and decision-making of networked multi-agent systems
- Published
- Source
- arXiv preprint, posted before peer review
- Published in
- arXiv
- DOI
- 10.48550/arxiv.2609.24474
- Original
- Read it at arXiv
- Cited by
- 0 works, as OpenAlex counts them
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Multiagent Systems
Eventual and Strong Eventual Notions in Public Announcements
Fully Byzantine-Resilient Multi-Agent Reinforcement Learning
Testing, not presuming, adequacy: calibrating generative social simulators against emergent network structure
When Does Execution Provenance Help Agent Memory Retrieval?
A Task-Oriented Multi-Agent Framework for Complex Wearable Health Analysis
Get the few papers worth your time in Multiagent Systems every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.