Conditional Max-Sum for Asynchronous Multiagent Decision Making
Dimitrios Troullinos, Georgios Chalkiadakis, Ioannis Papamichail, Markos Papageorgiou · 2025
Read Conditional Max-Sum for Asynchronous Multiagent Decision Making by Dimitrios Troullinos, Georgios Chalkiadakis, Ioannis Papamichail, Markos Papageorgiou (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-13194.txt.
Introduction
Dimitrios Troullinos and co-authors coordinated agents that act out of sync in two thousand twenty-five. Multiagent decisions often assume tidy, simultaneous updates. Real systems, like lane-free traffic, never wait politely. Their method extends a classic message-passing scheme. Factor graphs frame the joint decision problem. Messages pass between agents over the graph.
Conditional Max-Sum revises how messages are computed. It tolerates agents reassigning choices at any moment. The test domain is coordinated lane-free driving. Cars choose lateral alignment cooperatively. A rule layer handles the low-level control. Strategy sits in the graph layer above it. The mix aims at smoother, safer traffic flow.
Catalog record
| CREATOR | Dimitrios Troullinos, Georgios Chalkiadakis, Ioannis Papamichail, Markos Papageorgiou |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 86 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2502-13194
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Conditional Max-Sum for Asynchronous Multiagent Decision Making Note: This is the extended version with the Appendix of the paper appearing in the Proc. of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025). The accompanying codebase is available at https://bitbucket.org/dtrou/conditional-max-sum-in-lane-free-traffic . Dimitrios Troullinos, Georgios Chalkiadakis, Ioannis Papamichail, Markos Papageorgiou Abstract . In this paper we present a novel approach for multiagent decision making in dynamic environments based on Factor Graphs and the Max-Sum algorithm, considering asynchronous variable reassignments and distributed message-passing among agents. Motivated by the challenging domain of lane-free traffic where automated vehicles can communicate and coordinate as agents, we propose a more realistic communication framework for Factor Graph formulations that satisfies the above-mentioned restrictions, along with Conditional Max-Sum : an extension of Max-Sum with a revised message-passing process that is better suited for asynchronous settings. The overall application in lane-free traffic can be viewed as a hybrid system where the Factor Graph formulation undertakes the strategic decision making of vehicles, that of desired lateral alignment in a coordinated manner; and acts on top of a rule-based method we devise that provides a structured representation of the lane-free environment for the factors, while also handling the underlying control of vehicles regarding core operations and safety. Our experimental evaluation showcases the capabilities of the proposed framework in problems with intense coordination needs when compared to a domain-specific baseline without communication, and an increased adeptness of Conditional Max-Sum with respect to the standard algorithm. Y. Vorobeychik, S. Das, A. Nowé (eds.) Conference: Proc. of the 24th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2025); May 19 – 23, 2025; Detroit, Michigan, USA 908 CCS: Computing methodologies Multi-agent systems CCS: Computing methodologies Cooperation and coordination CCS: Applied computing Transportation Figure 1. (a) An example of a typical FG; (b) The corresponding distributed structure for FGs. On the top, there is an example of a typical Factor Graph containing factors, variables and illustrating the exchanged messages based on the Max-Sum algorithm, and on the bottom, we have the proposed distributed structure of the same Factor Graph. 1. Introduction Distributed Constraint Optimization Problems (DCOPs) ( Fioretto et al., 2018 ) effectively tackle multiagent decision making in large problems that can be formulated with a highly decomposable structure. DCOPs have been widely studied with several extensions that address broader domains such as dynamic and/or sequential environments. Algorithmic solutions for Dynamic DCOPs usually expect that agents update their existing configuration concurrently in an online dynamic environment, or that multiple message-passing iterations can be taken before agents update their current configuration as a group. These limitations can hinder the actual use of DCOPs in many multiagent environments requiring more flexible frameworks that incorporate communication or timing-related restrictions. Existing research either tackles the asynchrony of the agents’ decision making problem without taking into account large-scale and open distributed environments, by resorting to pseudo-tree graph structures that are more immutable than Factor Graphs ( Petcu and Faltings, 2006 ) ; or requires the synchronization of agents’ decisions at every time-step ( Fioretto et al., 2018 ) . Figure 2. FG example of connected lane-free vehicles. Example of three lane-free vehicles on a highway, and illustration of the distributed Factor Graphs application for the coordination of their lateral alignment. To this end, we propose a distributed communication framework for Factor Graphs (FGs) that relies on information broadcasting for communication among agents, in a way that treats agents as independent entities and not as a unified system. A visual illustration of the framework juxtaposed with the corresponding conventional FG (contains variables x_{i} that agents control, and decomposed factors F_{j} of local utilities depending on variables x_{i} ) can be found in Fig. 1 (discussed in length in Sec. 3 ). FG formulations are often tied with the Max-Sum algorithm, which showcases great adaptability under different environments ( Farinelli et al., 2008 ; Ramchurn et al., 2010 ; Troullinos et al., 2022b ) , and through its numerous extensions ( Stranders et al., 2009 ; Rogers et al., 2011 ; Zivan et al., 2023 ) that solve different types of DCOPs. In a similar vein, we put forward an extension of Max-Sum, termed as Conditional Max-Sum , which addresses the asynchrony on the agents’ variable updates. Conventional Max-Sum is not fully fitted for asynchronous decision-making since it is designed for static environments; while existing research on Asynchronous Max-Sum ( Zivan et al., 2023 ) has a different focus, as it examines the effect of asynchronous communication schemes in static problems, instead of asynchronous updates in sequential problems. The proposed approach is applied in lane-free traffic ( Papageorgiou et al., 2021 ) , a novel paradigm that investigates traffic environments where autonomous vehicles can fully utilize the lateral road capacity and do not obey the lane principle. This gives rise to a challenging multiagent coordination environment, with a FG formulation that we illustrate in Fig. 2 . There, the vehicles have to coordinate their lateral placement through the control variable x_{i} , and update their desired lateral placement x_{i}^{*} , i.e., their target to reach. Existing work ( Troullinos et al., 2022b ) in lane-free driving as a multiagent problem relies on the conventional framework of FGs and Max-Sum. As such, it does not take into account realistic restrictions regarding distributed communication and asynchrony of an open environment—especially in this setting where each agent is an independent moving vehicle with observations and dependencies that constantly change over time. Summing up our contributions, here we propose a distributed communication framework for FGs which allows for asynchronous decision making, giving rise to the Conditional Max-Sum algorithm. Moreover, we instantiate our framework in a realistic lane-free traffic environment for which we devise a novel formulation based on FGs. Our experimental evaluation demonstrates the coordination efficacy of the overall framework in this domain, and autonomous vehicles under Conditional Max-Sum exhibiting an increased ability to respond quickly and better target their desired speed objective with smoother lateral maneuvers. 2. Background and Related Work 2.1. Factor Graphs and the Max-Sum Algorithm Factor Graphs (FGs) ( Kschischang et al., 2001 ) originate from probabilistic graphical models but are also well integrated within distributed AI as a common tool for DCOP formulation ( Farinelli et al., 2008 ; Fioretto et al., 2018 ) . Given an FG structure as the one in Fig. 1 (a), we seek to obtain all control variable configurations x_{i}\in\mathbf{x} that maximize the sum of the factors, i.e., solve the optimization problem: \mathbf{x}^{*}={\arg\max}_{\mathbf{x}}\sum_{j}F_{j}(\mathbf{s}_{j}) , where \mathbf{s}_{j}\subseteq\mathbf{x} . Note that factors F_{j} connect different variables, and may potentially associate more than two (e.g., F_{l} ). The corresponding vector \mathbf{s}_{j} contains all variables x_{i} connected to factor F_{j} . For instance, in Fig. 1 (a): \mathbf{s}_{l}=[x_{k},x_{m},x_{n}]^{T} . In general, the factors can depend on any subset \mathbf{s}_{j}\subseteq\mathbf{x} of the control variables. Max-Sum ( Farinelli et al., 2008 ) is an iterative, inference-based algorithm that provides an approximate solution for this optimization problem through a message-passing operation involving two types of messages. The first type of messages concerns values sent from variable i to factor j : q_{i\rightarrow j}(x_{i})=c_{ij}+\sum_{k\in M_{i}\setminus j}r_{k\rightarrow i}(x_{i}) , where M_{i} is the set of factor indices that variable i is