Max-Sum with Quadtrees for Decentralized Coordination in Continuous Domains

1 Introduction

The framework of Distributed Constraint Optimization Problems (DCOPs) [Modi et al., 2003] is associated with a broad range of methodologies for distributed problem solving and coordination, such as Factor Graphs [Kschischang et al., 2001] and the Max-Sum message passing algorithm [Farinelli et al., 2008]. Continuous DCOPs [Stranders et al., 2009; Sarker et al., 2021; Hoang et al., 2020], in which the control variables' domain is continuous, are of particular interest corresponding as they do to a multitude of real-world settings, and posing several issues and challenges originating from the continuity of the problem domains. Existing work on Max-Sum in continuous domains [Stranders et al., 2009; Voice et al., 2010] makes certain assumptions regarding the factors, such as the ability to model them in a specific form, or having access to the gradients. In this paper, we propose a novel, more flexible extension of the Max-Sum algorithm for continuous domains: one that lifts such requirements, and can be easily adapted to any Continuous DCOP.

To this end, we utilize Quadtrees [Finkel and Bentley, 1974], which are among the simplest geometric algorithms for data representation of a given set of points, but exhibit in general high efficiency in many applications. Their simplicity makes them more desirable than other existing approximations tied with Max-Sum, such as Continuous Piecewise Linear Functions (CPLFs), which are more restrictive both in terms of construction (with simplices) and management. Specifically, we embed Quadtrees in the Max-Sum algorithm, to effectively achieve a fine-grained discretization of the continuous domain-the degree of which is determined by the Quadtree function approximation process itself, in an "online", dynamic fashion. The Quadtrees' embedding in Max-Sum, is achieved via properly re-defining the necessary core Max-Sum operations (addition and marginal maximization) that are applied on the messages exchanged in order to achieve DCOP optimization.

Now, an emergent highly complex distributed coordination domain is the field of autonomous driving [Pendleton et al., 2017]. The need for coordination is particularly intense when lane-free vehicle movement is assumed, as is the case in novel traffic flow paradigms [Papageorgiou et al., 2021]. In lanefree traffic, vehicles are no longer restricted by specific lane positioning, thus they do not perform any lane-changing operation, but rather adjust their lateral placement smoothly. This inherently continuous domain enables much higher utilization of the available road capacity, and gives rise to the design of novel techniques and methodologies, as evident by the results of [Papageorgiou et al., 2021; Troullinos et al., 2021a; Malekzadeh et al., 2021]. A Factor Graph representation with vehicles in the roles of agents controlling acceleration-related variables is natural for this challenging dynamic coordination domain, and allows the use of DCOPs optimization algorithms such as Max-Sum.

Against this background, our main contributions are as follows: we put forward Max-Sum with Quadtrees (Max-SumQuad), a novel Max-Sum variant appropriate for any Continuous DCOP domain of interest; the proposed approach does not make use of restrictive assumptions regarding the form of the factors (e.g., access to their gradient, or modelling them as CPLFs), and does not require the determination of a fixed discretized subdomain of the continuous problem at hand; we apply our approach to the lane-free traffic multiagent coordination domain; our experimental evaluation showcases the effectiveness and adaptability of Max-Sum-Quad in this challenging and dynamic domain.

2 Background and RelatedWork

Consider a Factor Graph [Kschischang et al., 2001] representation of agents, meaning we have a factored representation of an objective function F (x) = ∑NF j=1 Fj(sj), sj ⊆ x, to be maximized for a given problem. We seek to obtain the configuration vector x∗ = arg maxx ∑NF j=1 Fj(sj), where NF is the number of different factors Fj, and each factor j is connected with a subset of control variables sj . The Max-Sum algorithm [Farinelli et al., 2008] provides a solution for this distributed optimization problem via message-passing. This requires two key operations, namely an addition and a marginal maximization one, considering a discrete domain for control variables xi ∈ x. First, let us briefly present and discuss the standard algorithm of Max-Sum.

2.1 The Max-SumAlgorithm

Consider a Factor Graph representation as the one in Fig. 1. Note that factors Fj connect different variables, and may potentially associate more than two (e.g., F4). The corresponding vector sj contains all variables xi that are connected to factor Fj. For instance, on this figure: s4 = [x2, x3, x4]T . Thus, in general, the factors can depend on any subset sj ⊆ x of the control variables. To avoid confusion, notice that the indexing of factors and variables is different. The process involves a message-passing operation, and two types of messages are required:

From variable i to factor j:

where Mi is the set of factor indices that variable i is connected to. For example, in Fig. 1, M2 = {2, 3, 4}.

So, qi→j(xi) measures an estimate of each value of xi which is sent to factor j. Essentially, qi→j(xi) propagates what is received from all the other factors Mi \ j, and aij is a normalization constant that satisfies ∑xi qi→j(xi) = 0. This normalization is important when the Factor Graph contains cycles since message values would accumulate indefinitely. Convergence in cyclic factor graphs is not guaranteed, but the use of a normalization factor has proven to be quite effective in many studies [Kok and Vlassis, 2006; Murphy et al., 1999; Farinelli et al., 2008].

From factor j to variable i:

where Nj is the set that contains the variable indices connected to factor j, and the maximization process involves the all the variables sj connected to factor Fj (besides xi).

For instance, in Fig. 1, N2 = {1, 2}, i.e., variables x1, x2 are connected to factor F2. Now, rj→i(xi) is what each factor Fj sends to a connected variable xi (for each discrete value of xi), which is the maximum value considering that all other variables xk of factor Fj will be tuned so as to maximize both Fj and the corresponding message sent from k to factor j (qk→j(xi)). The message-passing process is illustrated in Fig. 1.

The process described above is iterative, where in every iteration we utilize the last evaluations for all messages qi→j(xi), rj→i(xi) (we may initiate the process with neutral messages). This operation is performed until either a stopping criterion is met (e.g., time, iterations number), or if all message values converge (given a threshold value).

Finally, each agent can compute the optimal value of x∗i , as: x∗i = argmaxxi ∑j∈Mi rj→i(xi), i.e., each agent selects the value that maximizes the received messages from all nearby factors.

2.2 RelatedWork

To the best of our knowledge, there are two distinct methodologies to extend Max-Sum to continuous domains. The first one involves the use of CPLFs to represent the factors [Stranders et al., 2009] and by extension the messages that agents exchange. The authors formally define the addition and marginal maximization operations for CPLFs, and can therefore apply Max-Sum with such a function representation. However, the formulation in [Stranders et al., 2009] requires each factor to be modelled as a CPLF. By contrast, in our work factors can have any form; and embedding Quadtrees in Max-Sum equips the latter with a flexible, dynamic discretization ability that is key for effective performance in demanding Continuous DCOP settings.

The second line of research involves a hybrid approach [Voice et al., 2010] that utilizes the standard algorithm of Max-Sum, relying on discretization of the continuous values domain; but with the discretized points being updated in each iteration using non-linear programming techniques. This process requires access to each factor's gradient. More recent literature regarding solving Continuous DCOPs involves different methodologies, such as Local Search [Sarker et al., 2021], Distributed Pseudo-tree Optimization Procedures tied with analytical solutions when possible [Hoang et al., 2020], Particle Swarm Algorithms [Choudhury et al., 2020] and even Bayesian Methods [Fransman et al., 2019].

Regarding the lane-free traffic application domain, many works already exist that propose relevant vehicle movement strategies [Papageorgiou et al., 2021; Troullinos et al., 2021a; Yanumula et al., 2021]. Other work in traffic-related literature decomposing the multiagent system via a graph structure includes [Kuyer et al., 2008; van der Pol and Oliehoek, 2016] that tackle urban traffic lights control problems via a Coordination Graph [Guestrin et al., 2002] scheme; and [Yu et al., 2020] that uses coordination graphs for lane-based collaborative autonomous driving.

2.3 Quadtree Representation of a Function

Consider a real function f(x), where f : Rn → R, and all variables xi ∈ x lie within certain bounds, specifically, ∀xi ∈ x, 0 ≤ xi ≤ 1. If x ∈ R2 , the space R2 is a unit square, and a Quadtree [Har-Peled, 2011] can establish a representation f (Qt) (x) of function f(x), meaning that a tree structure will approximate f(x). This operation is performed by recursively partitioning a 2-dimensional unit square region into 4 subregions. Now, if x ∈ RN , a generalized version of a Quadtree can be utilized, that recursively partitions a Ndimensional unit hypercube region into 2N subregions. The same principle applies even to 1-D, by partitioning the space into 2 subregions each time.

The process initiates from the root node r of the tree to be constructed, which obtains the value of the center point within the N-dimensional unit hypercube region Sr, where N = dim(xm). Then, the root node is partitioned into 2N child nodes c, corresponding to subregions of the unit hypercube, and they obtain the value of their respective center point xm; and recursively perform the same operation.

A threshold value ϵq dictates the finalization of this operation. Any given node p with center point (of its region Sp) xp will stop further partitioning, if the condition |f(xp) - f(xc)| ≤ ϵq is met for the center point (xc), which in turn is associated with the partitioned subregion Sc of a child node c. This criterion essentially provides us the dynamic aspect of the algorithm, determining both the position of the discrete points and the number of them according to the granularity of the approximating function f(). 1 The process outlined above is used for image compression with Quadtrees [Shusterman and Feder, 1994]. Figure 2 exhibits a simple example of a Quadtree approximation for a given function in a 2-dimensional surface. In this Figure, (a) showcases the actual function and a projection of the Quadtree approximation that shows the discrete points selected along with the regions, while (b) visualizes the tree depth of each region and the respective points. Finally, (c) indicates how the Quadtree is actually formed, and can be easily traversed.

Algorithm 1 lists the entire procedure [Shusterman and Feder, 1994], as outlined above. Notice that additional variables are included, namely minD,maxD corresponding to the minimum and maximum tree depth respectively, i.e., the resulting Quadtree function's leaf nodes are bounded within a predefined range of depths. In more detail, the leaf nodes' depth indicates the size of the subregion, and thus the resolution of the approximated function, meaning that as the depth

1 As we discuss in Sec. 3, this translates to the computation of the messages in Max-Sum, using this dynamic discretization procedure.

Algorithm 1 Construct a Quadtree Function

1: function QT(f(), reg, curD,minD,maxD, ϵq) 2: xp ← getCenterPointOfRegion(reg) 3: curNode ← newNode(curD, reg, f (xp)) 4: QTNodes(curD) ←QTNodes(curD)∪curNode 5: if curD ≥ maxD then 6: return curNode 7: end if 8: for each chReg ∈ partition(reg) do 9: xc ← getCenterP ointOfRegion(chReg) 10: conv ← |f (xp) - f (xc)| ≤ ϵq 11: if (conv ∧ (curD ≥ minD)) then 12: continue 13: end if 14: chNode ←QT(f(), chReg, curD + 1, . . .) 15: curNode →ADDCHILD(chNode) 16: end for 17: return curNode 18: end function

of the tree increases, the function's resolution becomes better. However, this constitutes a trade-off with respect to time and memory needed for this operation. Hence the reason we wish to have control over the minimum and maximum depth of the tree, guaranteeing a minimum resolution of the approximating function, and upper bounding the time and memory required for the approximation procedure.

Provided with a Quadtree representation f (Qt) (x), obtaining the value of any point x within the available region is equivalent to performing a search operation on a B-tree, where we start from the root node, and traverse the tree based on the corresponding subregions that contain x. Essentially, we obtain the value f(xc) of the closest center point xc from the available tree nodes (not necessarily a leaf node).

Thus, given a function f(x), we can use Algorithm 1 to construct an approximate function f (Qt) (x), and then we can obtain an approximation of y = f (Qt) (x) for every x.

3 Max-Sumwith Quadtrees

Messages in Max-Sum, i.e., the qi→j(xi), rj→i(xi) functions, are 1-D, since they are associated with a single scalar variable xi (which is discrete) [Farinelli et al., 2008]. However, in most multiagent settings of interest, agents have more than one variables under their control-and in many cases the variables are continuous. For instance, consider the application domain of interest in our work here, that is,lanefree autonomous driving, where vehicles need to coordinate their movement. In such an environment, each vehicle (agent) needs to control two continuous valued variables, one for the longitudinal (gas/break) movement, and one for the lateral (steering wheel) axis. As such, the message functions can entail more information via having a vector xi as input.

So, to utilize Max-Sum in continuous domains requires us to represent a continuous function of multiple variables; we do not restrict to pairwise factors [Stranders et al., 2009], thus the messages can have a high dimensionality. Thus, the use of Quadtrees for calculating these messages adds much desired flexibility regarding the dimensionality of variables and messages. We should mention here that a trade-off emerges from this flexibility, since having N-dimensional variables adds to the complexity of performing the (addition and marginal maximization) operations needed inMax-Sum. However, this trade-off is relevant to the problem at hand, therefore having such flexibility is not in any way limiting. To this end, given a Factor Graph representation of agents, we now model each agent i controlling a set of variables xi ⊆ x, and thus all functions corresponding to the messages are now sent between factors j and agents i with dimension Xi = |xi|.

Moreover, we need to define appropriately how the addition and the marginal maximization operations [Stranders et al., 2009] are carried out given the Quadtrees representation and the vector input of the messages. To begin, let us reformulate the Max-Sum equations [Farinelli et al., 2008] using a vector input xi for all messages. Consider a factor Fj(sj) that depends on |Mj | variables, and one of the two core MaxSum equations-the one corresponding to the messages sent from a factor j to a connected agent i:

where (Qt) indicates that these functions have the form of a Quadtree representation of a real multivariate function f : RN → R.

Now, the whole process initiates from factor Fj(sj), which is a real multivariate function Fj : Rn → R, with n being the size of vector sj. The union of vectors {xk : k ∈ Nj \ i} is in fact the vector sj \ xi, i.e., ∪k∈Nj\ixk = sj \ xi, meaning that a function that depends on sj entails all variables within this union. Therefore, the following summation process:

also approximates (with a Quadtree) a real multivariate function Qsum : Rn → R. Consequently, the operation of addition needs to be defined for Quadtrees in order to calculate Eq. 4, along with the following:

where R(Qt) j→i (sj) is again a Quadtree, and depends on the same vector (set of variables) sj as the two addend functions.

The final step in Eq. 3 is to maximize R(Qt) j→i (sj) w.r.t. variables xi, thus the operation of a marginal maximization needs to be defined:r(Qt)

which yields the final result for the message function to be exchanged r(Qt) j→i (xi), in the form of a Quadtree. Likewise, for messages sent from an agent i to a connected factor j, we have from [Farinelli et al., 2008]:

Here, we need to perform a summation of:

involving many variable representations of r(Qt) k→i , but they all depend on the same variables xi. So, the summation here results also in a two variable representation R(Qt) sum(xi), and we obtain the final result q(Qt) i→j (xi) by adding a normalization constant aij to it.

Evidently, in the case where xi is actually in a continuous domain, and not discretized, this summation process is not quite clear, as we do not have a specific set of values for xi, but rather a range of values. Therefore, this issue depends on the representation of real functions that is chosen, hence this choice dictates the calculation of aij. We show how to estimate aij in Sec. 3.3.

Example 1 (Illustration on a simple Factor Graph). We use the Factor Graph representation in Fig. 3 to showcase the use of Quadtrees within Max-Sum. We have agents {1, 2}, and a factor F1 connected only to agent 1, while F2 is connected to both agents. We initialize all messages to 0, therefore the first calculation of all q(Qt) i→j (xi) messages (Eq. 7) is again 0, which is depicted as a Quadtree covering the whole region, with a single point with 0 value at its center. Then, r(Qt) j→i (xi) messages are calculated (Eq. 3), and a respective Quadtree is constructed according to connected factor j of each message. Notice the dynamic discretization process, with the point selection (and size) decided in an online fashion.

Moving on to the second iteration, q(Qt) i→j (xi) messages are updated, essentially propagating the received messages of the corresponding agent i, meaning that the resulting Quadtrees in fact directly propagate messages, i.e., q(Qt) 1→2 (x1) at the second iteration propagates r(Qt) 1→1 (x1), and similarly q(Qt) 1→1 (x1) propagates r(Qt) 2→1 (x1). Accordingly, q(Qt) 2→2 (x2) remains zero, since no other factor is connected to agent 2, thus no other messages are there to be propagated.

Finally, we update r(Qt) j→i (xi) messages. Now, r(Qt) 1→1 (x1) message remains the same since F1 is not connected to other agents, and consequently there is no other incoming message to be propagated. Similarly for r(Qt) 2→1 (x1). While F2 is connected also to x2, q(Qt) 2→2 (x2) = 0 across all region, therefore this will not affect the resulting Quadtree for this message. However, this is not the case for r(Qt) 2→2 (x2), since message q(Qt) 1→2 (x1) is now updated, and consequently it will result in a Quadtree with a potentially different set of points to account for the different granularity of the approximated message, stemming from the operations needed to calculate it.

3.1 Addition Operation for Quadtree Functions

Consider two Quadtree representations f (Qt) 1 (x) and f (Qt) 2 (x). We are interested to construct a Quadtree representation g(Qt) (x) that approximates: g(x) = f1(x) + f2(x). The simplest way to do that is to start constructing the tree of g(Qt) (x), as one would do for a real function (see Algorithm 1), but instead of using a real function f(x) to obtain values for each node, one can use the Quadtree search operation (see Sec. 2.3) to obtain the values of v1 = f (Qt) 1 (x), v2 = f (Qt) 2 (x) and add these to obtain the value vnode = v1 + v2 of each node. Therefore, we utilize Algorithm 1, and set as input function: f(x) = f (Qt) 1 (x) + f (Qt) 2 (x). By so doing, the resulting Quadtree would indeed approximate the addition operation between two Quadtree representations. In a similar manner, we can perform addition between a quadtree representation and a real function (a process that is imposed by Eq. 5).

3.2 Marginal Maximization for Quadtrees

The Marginal Maximization operation is vital in the process of Max-Sum. Let us revisit equation Eq. 6 that imposes the need of this operation. As mentioned, R(Qt) j→i (sj), depends on all variables of factor j. Yet, for the maximization procedure, variables xi are bounded each time, so we need to maximize for all the remaining ones, i.e., we need the value: maxsj \xi [R(Qt) j→i ({sj \ xi}|xi)] given the provided bounded values of xi. Thus, to attain a Quadtree function of r(Qt) j→i (xi) (see Eq. 6), we again construct it via Alg. 1, and set:

where for every function call required within the algorithm (i.e., given a set of values for xi corresponding to a discrete point and a tree node), we construct in turn a Quadtree for variables sj \ xi to obtain the max value of the term R(Qt) j→i ({sj \ xi}|xi). While constructing the tree, we keep track of the node with the maximum value observed, therefore we have direct access to the requested value as soon as the tree construction process is terminated.

3.3 Normalization Constant Estimation

We have a Quadtree q(Qt) i→j (xi) that approximates the real function qi→j : Rn →R. A normalization constant is important when the Factor Graph contains cycles (as in our domain of interest). As [Farinelli et al., 2008] suggests, aij is set so as to satisfy ∑xi q(Qt) i→j (xi) = 0.

Starting from Eq. 7, and using a Quadtree approximation, we define an auxiliary function for convenience:

where q(Qt) i→j,n (xi) is simply q(Qt) i→j (xi) but without the normalization constant. Therefore, the normalization constant should satisfy:

where:

In the standard/discrete Max-Sum algorithm we would normally sum over all the possible combinations and solve for aij, but this is not straightforward in our case. If we attempted an analytical solution, we would probably replace the sum with an integral [Kschischang et al., 2001]. Here, we should properly define this process for a Quadtree function. We remind the reader that we have a tree structure that approximates the actual function for a unit hybercube space, and each leaf node of the tree represents the value of the function for a specific subregion. Consequently, this summation could be approximated by summing over all leaf node values and multiply them with the corresponding area.

Thus, we define the set of all leaf nodes Lq for a Quadtree function q(Qt) i→j (xi), and the two functions s(l), v(l) that return the surface area and the function value of a leaf node l respectively.

Therefore, we define:

where ∑∀l∈Lq s(l) = 1, since the total surface is a unit hypercube. Thus, in the context of Max-Sum, we can employ the Quadtree of q(Qt) i→j,n (xi), without normalization, and then, using the definition above we can obtain a value for aij . In the equation below, Lq is the set of all leaf nodes for q(Qt) i→j,n (xi).

which yields:

After the Quadtree function is constructed for q(Qt) i→j,n (xi), then the normalization constant is calculated and incorporated accordingly.

3.4 Variable Configuration

Finally, after the optimization process is carried out, each agent i needs to select the configuration of xi that maximizes:

We obtain the sum of ∑j∈Mi r(Qt) j→i (xi) by simply constructing a Quadtree function, meaning that we gain direct access to the maximization node, and consequently to the subregion that has the maximum value observed. Finally, we assign the center point of the appointed region to x∗i .

4 Experimental Evaluation

In this section we present our lane-free traffic application domain, and our experimental evaluation results. 2

We consider a highway populated with many vehicles entering from an origin point, where each vehicle possesses a desired speed parameter vd, chosen at random within a specified speed region [vd,low, vd,high]. The induced speed deviations among nearby vehicles, along with heavier traffic in a lane-free environment, constitute a complex multi-agent environment appropriate for the application of our method.

2 The source code for Max-Sum-Quad implementation can be found in: https://bit.ly/3MLRVLk

Here we follow the methodology of [Troullinos et al., 2021a], since, to the best of our knowledge, this is the only work tackling Continuous DCOPs in the lane-free traffic domain-albeit using discretization. Specifically, we model each vehicle as an agent that controls two acceleration parameters, one longitudinal and one lateral. [Troullinos et al., 2021a] define a set of 5 actions per agent, discretizing the joint action space of the two acceleration, i.e., converting the actual 2-D action space into a vector of 5 different combinations for agents. While this coarse-grained discretization may be adequate up to a certain point, heavier traffic (induced either by larger traffic flows, or larger vehicles) may require a finer discretization, i.e., better resolution with respect to the available actions of the agents. In this case, there is the issue of properly pre-defining the points in the 2-dimensional control space, as vehicles may face various traffic conditions, and therefore a predefined set of points could be potentially large, and adjusted through a meticulous experimental process. Max-Sum-Quad lifts the need of pre-selecting this set of points.

4.1 Formulation of the Problem

For a given instance of the traffic environment, we define a Factor Graph representation of vehicles, as illustrated in Fig. 4. The graph contains two types of factors. The first factor type Fs(ax, ay) is connected with a single vehicle (the two variables of each vehicle) and accounts for the vehicle's desired speed, while the second one Fp(ax,1, ay,1, ax,2, ay,2) is pairwise, in the sense that it connects two vehicles at a time, i.e., 4 variables. This type of factor aims to properly adjust the vehicles' movement so as to avoid collisions. The factors' parameters reflect the vehicles' control variables, i.e., the longitudinal and lateral acceleration ax, ay respectively (in m/s2 ). The form of the first type of factor is:

where:

and:

Essentially, Fs is responsible for 'motivating' the vehicle to follow its desired speed vd (due to rx), and also to have a lateral speed close to 0 (due to ry). Notation ′ in Eq.16 denotes

that these variables have the value as a result of the input variables, e.g., v′x is the longitudinal speed in the next time-step based on ax. Moving on to the pairwise factor Fp:

where it depends on the accelerations of two connected vehicles (1, 2), therefore it has 4 input parameters. The form of Ec and Eb is adopted from [Troullinos et al., 2021a], but we included some minor adjustments relevant to Eb, which perform better specifically in denser traffic. Both Ec and Eb are ellipsoid fields, with the form:

where parameters a, b dictate the ellipses' stretch in each dimension. Specifically for Eb field, that captures a broader region, we provide with some small adjustments regarding the relevant parameters ab, bb dictating the ellipses' reach:

where the speeds variables vx,1, vx,2, vy,1, vy,2 for the terms relevant to τx, τy are not the resulting ones based on the acceleration input, but rather the current ones, hence the lack of notation (′ ). This choice appears to diminish instabilities caused in heavier traffic scenarios. We refer the interested reader to [Troullinos et al., 2021a] for more details regarding the ellipsoid functions used.

4.2 Implementation Details

As mentioned, we consider a unit hypercube space for Quadtrees, meaning that all control variables should reside within the range [0, 1]. Therefore, we perform a normalization, so that 0 corresponds to the minimum acceleration (ax∨y,min) and 1 to the maximum value (ax∨y,max), for both acceleration axes. We have ay,min = -ay,max in all cases, since it is sensible that the available values for acceleration towards the left (ay > 0) or right (ay < 0) should be symmetric. Note that due to the Quadtree function approximation, the control values that can be obtained always correspond to the center point of a maximizing subregion of the whole space. Essentially, this means that the values ax,max, ax,min, ay,max are not attainable, and the actual maximum and minimum control values are determined by the maximum tree depth (maxD). For example, in the longitudinal axis, we have ax : [ax,min, ax,max] = [-3.5, 3.5], and a maximum tree depth of maxD = 2. Consequently, the length for each subregion at depth 2 is ax,max-ax,min 2maxD = 1.75, and thus the actual minimum and maximum values are within the range ax : [-3.5 + 1.75 2 , 3.5 - 1.75 2 ] = [-2.625, 2.625], since the corresponding center points lie in the middle of each subregion. The same principle applies for the lateral axis as well.

An important aspect is the fact that the traffic environment is dynamic, hence we need to revise the control variables in every instance, meaning that the Factor Graph is updated in every time-step, and then Max-Sum(-Quad) performs one iteration so that each agent can obtain a new solution. In this manner, the computed Quadtree message functions are retained after each time-step (provided that the correlated agents preserve their existing connection), so that we do not start computing a new solution from scratch every time.

Parameter choices regarding the traffic environment, tuning of the algorithm, the factors, and Quadtrees can be found in Table 1.

4.3 Experiments and Results

A primary objective in our experiments is to demonstrate the efficiency of our approach for intensified traffic conditions, contrasting its performance with that of [Troullinos et al., 2021a], and to showcase the dynamic discretization of Quadtrees experimentally. Experimental evaluation is conducted using the simulation tool of [Troullinos et al., 2021b], which is an extension of the SUMO microscopic simulation platform [Lopez et al., 2018] for lane-free traffic environments. To this end, we set the factors' safety parameters so that vehicles employ a much more aggressive driving style (smaller reaction times and safety distances); and by examining two different configurations of vehicle dimensions (Table 1) as they contribute to traffic density in lane-free traffic.

Experimental results are provided in Figs. 5, 6, where we compare each method and vehicle configuration, for various inflow rates [5400 - 12000] veh hr at the origin point of the highway. In total, we compare four different cases, as evident in the relevant figures, where QT-3.2 & QT-3.9 correspond to the Max-Sum-Quad approach, with the relevant parameters tuning provided in Table 1. The numbers "3.2" & "3.9" simply indicate the associated vehicles' length dimensions. Moreover, DISCR-5-3.9 & DISCR-21-3.9 adopt the standard Max-Sum algorithm, with a discretization of the 2dimensional acceleration space of 5 and 21 different points respectively. DISCR-5-3.9 corresponds to the equivalent of a fully partitioned Quadtree with maximum depth of 1, i.e., 1 point at the center and the 4 center points of the respective subregions, and DISCR-21-3.9 is the discretization of a fully partitioned Quadtree at depth of 2, containing all points of DISCR-5-3.9, along with 16 more points at tree depth of 2.

As evident in Fig. 5, the induced aggressive behaviour of vehicles, stemming from the parameter choices regarding safety distances and reaction time, substantially improves the performance of all examined scenarios with respect to the formulation of [Troullinos et al., 2021a] with safer parameter choices, where average speeds are ranging from 28.61 ms to 27.64 ms (and only up to 9000 veh hr ). It is noticeable also that the size of the vehicles affects performance, especially as the inflow increases. Now, in order to properly assess the performance of Max-Sum-Quad, we focus on more intense conditions, with larger vehicle dimensions. DISCR-5-3.9, due to its coarse discretization, is not collision-free at higher inflow rates (we observe 3 collision occurrences at 9000 veh hr ), meaning that the selection of 5 points is not adequate. DISCR-213.9 manages to improve upon DISCR-5-3.9 due to the finer discretization, and without any observed collisions. However, our approach manages to provide an intermediate solution, but now with a "dynamic discretization" procedure, one that does not require the user to discretize the domain beforehand. With Max-Sum-Quad, we did not observe any collisions in our experiments.

In Fig. 6 we showcase the associated average number of points selected by Quadtrees in this domain, and we observe that in the most demanding scenario, the constructed Quadtrees on average result in 11.6 points-i.e., Max-SumQuad achieves similar performance with 56% of the standard Max-Sum Algorithm with 21 points. This also showcases that the dynamic discretization process automatically adapts to more intense traffic conditions, since we have a noticeable increase on the size of Quadtree nodes on average (cf. Fig. 6). Evidently, smaller vehicles require more refined partitioning on average, in more intense traffic conditions. This result is non-intuitive, in the sense that the scenario with larger vehicles is more demanding in terms of collision avoidance. However, this might be an indication that the resolution level of Quadtrees is affected by the fact that for the same inflow rate, the vehicles operate with slightly higher speed (on average).

Summing up, the imposed challenging traffic scenarios, populated as they are with vehicles driving aggressively, necessitate a more refined selection of available actions to handle the more demanding cases that now frequently arisee.g., when many vehicles are nearby and some attempt overtaking. Our results show that our approach offers vehicles a dynamic selection of available actions, affected by messages in the form of Quadtrees. Evidently, Max-Sum-Quad adapts to the problem at hand without requiring a manual discretization process by the user, and it also adjusts automatically the level of discretization for each message in an online fashion.

5 Conclusions and FutureWork

In this work, we presented an extension of the well-known Max-Sum algorithm for Continuous DCOPs, with application in the novel lane-free autonomous driving domain. Our results confirm that embedding Quadtrees in Max-Sum, render the latter appropriate for demanding Continuous DCOPs.

In future work, we plan to explore different domains of application, such as Random Graphs which are commonly used in related work (see Sec. 2.2), and compare the efficiency of the proposed method with other approaches in the literature. Another direction is to establish theoretical guarantees for Max-Sum-Quad and consider alternative function approximation techniques.

Acknowledgements

The research leading to these results has received funding from the European Research Council under the European Union's Horizon 2020 Research and Innovation programme/ ERC Grant Agreement n. [833915], project TrafficFluid.