20. Conditional max-sum for asynchronous multiagent decision making

Video Playlist 20: Conditional max-sum for asynchronous multiagent decision making

The videos included in this playlist are a part of the results discussed in the paper titled "Conditional max-sum for asynchronous multiagent decision making". Considering automated vehicles that can communicate and coordinate as agents in lane-free traffic environments, in this paper we propose a more realistic communication framework for Factor Graph formulations considering asynchronous variable reassignments and distributed message-passing among agents; 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. The asynchrony of the agents’ decision updates poses an additional challenge in the examined scenarios. The Factor Graph formulation motivates all agents to align laterally so that the necessary overtakes can take place in a coordinated manner, and vehicles can thereby track their respective desired speed goal. We compare the performance of the proposed framework first with the extension we put forward, Cond-Max-Sum, along with the standard algorithm (Max-Sum), another variant (No-Max-Sum) that we discuss in the paper, and with MOBIL (adapted for lane-free environments through the use of lateral regions) as a baseline that does not rely on online communication of agents.

Lane-free coordination problem

In this video, we track the blue vehicle/agent located at the beginning of the road, which has the highest desired speed objective and therefore needs to overtake all other agents in front. We put side-by-side all methods under the same initial conditions. After the initial period where veh-1 needs to slow down since other vehicles are in front, it then reacts and coordinates better with its surroundings under Cond-Max-Sum, with earlier overtakes that do not affect negatively the goals of other agents on average, as evident in the measured metrics. Cond-Max-Sum achieves this with fewer lateral maneuvers when compared to the standard algorithm, due to the message passing being better adapted to the asynchronous setting.

Lane-free coordination problem

Open highway environment

In this video, we track the blue vehicle/agent in the center, which has a desired speed goal of 31.77 m/s with surrounding traffic having different desired speed goals within the range [25, 35] m/s. As such, multiple situations that require coordination emerge. We put side-by-side all examined methods under the same initial conditions (to the extent that is possible in this open environment). While we track the blue agent, it is important to notice the overall behaviour of its surroundings. It is evident that with Cond-Max-Sum, undesirable situations where vehicles need to remain behind slower moving vehicles are dissolved more quickly or may be avoided all together.