Distributed Constraint Optimization Problems (DCOPs) are a powerful framework to model cooperative multi-agent systems wherein multiple agents communicate directly or indirectly with each other. The agents act autonomously in a common environment in order to optimize a global objective which is an aggregation of their corresponding constraint cost functions. Each of the functions is associated with a set of variables controlled by the corresponding agents. In DCOPs, agents need to coordinate value assignments to their variables in such a way that maximize their aggregated utility or minimize the overall cost [Modi et al., 2005; Petcu and Faltings, 2005]. A number of multi-agent coordination problems, such as meeting scheduling [Maheswaran et al., 2004], multi-robot coordination [Yedidsion and Zivan, 2016] and smart homes [Fioretto et al., 2017; Rust et al., 2016], have been dealt with this model.

The DCOP model is based on an assumption; that is, each of the variables that are involved in the constraints can take values from discrete domain(s) and a constraint is typically represented in a cost (i.e. utility) table. Nevertheless, a number of applications, such as target tracking sensor orientation [Fitzpatrick and Meetrens, 2003], cooperative air and ground surveillance [Grocholsky et al., 2006], Network coverage using low duty-cycled sensors [Hsin and Liu, 2004] and many others besides, can be best modeled with continuous-valued variables. Therefore, the traditional DCOP setting is not wellsuited to such algorithms. To address this, the regular DCOP model is extended for continuous-valued variables [Stranders et al., 2009]. Later, [Hoang et al., 2019] refer this continuous version of DCOP as Functional DCOPs (F-DCOPs).

In more detail, [Stranders et al., 2009] propose a new version of the Max-Sum algorithm (i.e. Continuous Max-Sum -CMS) in order to solve continuous-valued DCOPs. CMS approximates constraint utilities as piece-wise linear functions. However, this approximation has not been widely recognised due to the unavailability of real-world applications having piece-wise linear functions. Then, Hybrid CMS (HCMS) uses discrete Max-Sum as the underlying framework with the addition of a continuous non-linear optimization method [Voice et al., 2010]. Notably, none of CMS and HCMS provides quality guarantees on the solutions as both of them are based on discrete Max-Sum which does not provide any quality guarantees when applied to general graphs [Hoang et al., 2019]. To address this, three extensions of the Distributed Pseudo-tree Optimization Procedure (DPOP) [Petcu and Falt- ings, 2005] algorithm has been proposed. The first one is an exact algorithm-Exact Functional DPOP (EF-DPOP) and the remaining two are non-exact methods Approximate Functional DPOP (AF-DPOP) and Clustered AF-DPOP (CAFDPOP) [Hoang et al., 2019]. EF-DPOP can solve F-DCOPs with tree-structured graphs and with linear or quadratic utility functions. AF-DPOP and CAF-DPOP can solve F-DCOPs without imposing restriction on the graph structure. However, as they are based on DPOP, a key limitation of these approximate algorithms is that they require exponential memory.

Against this background, we extend the Cooperative Constraint Approximation (CoCoA) [van Leeuwen and Pawel- czak, 2017] algorithm so that it can solve functional DOCPs. We choose CoCoA as it is a non-iterative, semi-greedy approach that is able to find high-quality solutions with a smaller communication overhead than the state-of-the-art DCOP solvers. Our continuous version of CoCoA, that we call C-CoCoA, is an approximate local search algorithm that can solve F-DCOPs without any restriction on the graph structure and with a very lower communication cost. In CCoCoA, we combine the discrete CoCoA algorithm with continuous non-linear optimization methods. Our target is to improve on continuous optimization by using the CoCoA algorithm to make the initial choice less critical. We empirically show that C-CoCoA outperforms HCMS and AF-DPOP in terms of solution quality, number of messages and time.

In this section, we discuss the background which is necessary to completely understand our proposed algorithm. We first describe the traditional DCOP model and then F-DCOP model. We then discuss the CoCoA algorithm and the challenges we face to incorporate CoCoA with the F-DCOP model.

2.1 Distributed Constraint Optimization Problems

A DCOP is defined as a tuple , where,

• A = is a finite set of agents.

• X = is a finite set of discrete decision variables where each variable is controlled by one of the agents .

• D = is a set of finite discrete domains where each corresponds to the domain of variable .

• F = is a finite set of cost functions, with each defined over a set of variables and the cost C for the function is defined for every possible value assignment of , that is, C : .

• is a mapping function, which associates each variable to an agent . An agent can control multiple variables. However, for simplicity, we assume each agent controls only one variable.

A value assignment is complete if every variable is assigned a value. The goal in a DCOP is to find a complete assignment that minimizes the cost of the global objective function:

2.2 Functional Distributed Constraint Optimization Problems

A Functional DCOP (F-DCOP) can be described by a tuple , where A, F, and are exactly the same as those in a DCOP. X and D are defined as follows:

• X = is a finite set of continuous decision variables.

• D = is a set of continuous domains. Each variable can choose any value from a range, .

As aforementioned in the previous section, the difference between F-DCOPs and DCOPs is found in the representation of the cost function. In DCOPs, cost functions are represented in a tabular form. However, in F-DCOPs, we use a function to represent a constraint cost instead of the traditional tabular form. The goal of an F-DCOP is the same as a DCOP, which is finding a complete assignment that minimizes the cost of the global objective function. An example of an FDCOP is presented in Figure 1 where Figure 1(a) represents a constraint graph with four variables. Each variable is controlled by one of the agent . The edges between the variables represent the cost functions that are defined in Figure 1(b). The domain is defined as [-20, 20] in this example.

Figure 1: Example of an F-DCOP

2.3 Cooperative Constraint Approximation (CoCoA)

The CoCoA algorithm starts with randomly activating an agent. Upon activation, the agent sends an inquiry message to its neighboring agents. We define the set of direct neighbors of the agent is . When an agent sends an inquiry message to the neighboring agents , each calculates cost messages for every value in the domain of using Equation 2. Here, is the cost for the value of agent ’s domain which is calculated by the neighbor indicates that is assigned the value of ’s domain, , C is the cost for the function which is an element of all the constraint function set between agent and is the current partial assignment sent from to that contains the known assigned values of the neighbors of indicates that is assigned the value of agent ’s domain . Agent calculates for all the values of and the resulting cost map , . . . . , is sent to the inquiring agent . Then, finds the value of its variable from (Equation 3). Here, is the minimum aggregated cost received from the neighbors for each is a set of values from agent ’s domain for which the cost is minimum and is the received cost messages from its neighbors.

Notably, for more than one value in ’s domain in , the unique-first approach is followed to determine whether the current solution is accepted or not. In this approach, is compared with a bound . The initial value of is set to 1. This means that the value is acceptable if it is a unique local optimum. If , agent goes into HOLD state and waits for more information. Otherwise, a value is selected randomly from and is assigned to its controlled variable. After assigning a value to , every agent updates its current partial assignment and repeats the algorithm. If the value assignment is not possible for all the agents, is increased by 1, and the algorithm is repeated. This approach prevents the agents from assigning a value prematurely to their variables.

2.4 Challenges

We need to address the following challenges to develop an F-DCOP algorithm that adapts CoCoA.

• Infinite Domain: For F-DCOPs, the domain is an infi-nite number of values within a range. In effect, an agent needs to assign a value to its variables from an infinite number of points. Thus, an F-DCOP solver requires an extensive amount of time and memory to converge.

• Discretization: F-DCOP solvers need to discretize the continuous state space to operate. The choice of discrete points can be random; however, setting up the number of discrete points is critical. The quality of solutions found by an F-DCOP algorithm increases with the increasing number of points.

• Initializing Parameters: If the cost functions are not convex, initializing the parameters in continuous non-linear optimization methods is significant. Because, even with infinite computing power and time, the gradient approach can still stuck with local minimum or saddle point.

In the following section, we devise a novel method to apply CoCoA in F-DCOPs.

To address the challenges discussed in the previous section, we propose C-CoCoA, a non-exact algorithm that uses Cooperative Constraint Approximation (CoCoA) as the underlying algorithmic framework. To be precise, we combine the discrete CoCoA algorithm and the continuous non-linear optimization technique. C-CoCoA is also a non-iterative algorithm like CoCoA in the sense that each agent can only assign its value once and once assigned, it cannot change its value.

3.1 C-CoCoA: Algorithm Description

C-CoCoA (i.e. Algorithm 1) defines as the set of direct neighbors of the agent . We assume that, an agent communicates only with those agents whose variables affect ’s cost function. In other words, communicates only with . This ensures a low communication overhead as well as a fully decentralized solution. For this reason, the total cost of an individual agent only depends on rather than the size of the constraint graph. We also assume that each agent knows its neighbors’ discretized domain and the nodes of the constraint graph are reachable from any other node.

The C-CoCoA algorithm uses the same message passing technique as described in Section 2.3 for the discrete CoCoA, using the current discretizations of the domain of each variable . However, as the cost functions are not in the tabular form, each agent calculates the cost by evaluating , where is the set of variables related to .

The key difference between the C-CoCoA and discrete CoCoA is that, in C-CoCoA each agent calculates the cost by considering its domain discretizations ,..., (Algorithm 1: Line 1) instead of the actual continuous domain, where k is the total number of random discrete points taken from . We select the discrete points randomly because, as aforementioned, we use the non-linear optimization technique to adjust these random discrete points later. For the example of Figure 1, for simplicity, let us assume that k = 2. So, we discretize the domains of and into 2

random discrete points (: [1, 2], : [3, 4], : [7, 8] and : [5, 9]) from the domain range [-20, 20].

The states of the agents are defined as IDLE, ACTIVE, HOLD and DONE [van Leeuwen and Pawelczak, 2017]. The current partial assignment (CPA) denotes the known assigned values of the neighbors of . We define a set that contains the set of agents who finish their variable assignments. Therefore, is the set of unassigned agents (value assignment to their variables is not finished). Then in the initialization step, each agent initializes its state to IDLE, the current partial assignment with an empty assignment and with an empty set. (Algorithm 1: Line 5-8). After this step, similar to the discrete CoCoA algorithm, our algorithm activates an agent randomly, because, starting with any agent yields the same result. Agent activates each agent (Procedure 2) and sends an inquiry message (Procedure 1) to each of the (Algorithm 1: Line 9-13). We define as the overall cost map that contains the minimum cost for each of the discrete points of ’s domain and is calculated by the agent . We define each element of the cost map as ,

where, C is the minimum cost and denotes the value of ’s domain that gives the minimum cost C. The agent then calculates using the Equation 3. contains the values of that is near-optimal within the discretized points ,..., of the agent ’s domain. also stores the values of in a set (Algorithm 1: Line 14-15). For the example of Figure 1, we assume that the agent is selected randomly. then activates its neighbors , and sends an inquiry message to all of them. Upon receiving the inquiry message, and calculate the cost map 3: 13, 3: 107: 154, 7: 1615: 30, 5: 35} respectively (Figure 2) and send these cost maps to the inquiring agent . After receiving the cost map, calculates by using the Equation 3 and for this example assigns and = 3, = 7, = 5}. We describe this example elaborately in the Figure 2.

Similar to the discrete CoCoA algorithm, more than one value in ’s domain can achieve the minimum cost [van Leeuwen and Pawelczak, 2017], that is . In this case, we follow a unique-first approach which is described in the CoCoA algorithm (Section 2.3). Algorithm 1: Line 31-34, describes the case when . In this case, goes into HOLD state and waits until another agent has completed its assignment and repeats the Algorithm 1 from Line 9. Otherwise (when ), a value is selected randomly from the set . We assign this value to and add this to the set (Algorithm 1: Line 17-18). This assignment is near-optimal within the discretized domain. In order to find the best solution within the actual domain , we use a non-linear optimization technique. We choose gradient-based optimization approach because we can implement it in a decentralized way using only local information. Now, for employing the gradient-based non-linear optimization, agent calculates the local objective function (Algorithm 1: Line 19) by

using the following equation:

where, is the cost function that is related to agent and its direct neighbor . For the example of Figure 1, agent assigns = 1 from and appends this value with the set . Hence, the set 5}. Thereafter, the agent calculates the local objective function = .

for optimizing its local objective function where, is the set of all the related variables with (Algo- rithm 1: Line 20). Agent assigns every variable with the corresponding value from the set as the initial values in the gradient-based optimization method (Algorithm 1: Line 21-22). Specifically, the agent minimizes the local objective function and updates the value of each vari- able according to the following equation:

where is the learning rate of the algorithm (Algorithm 1: Line 23-24). For the example of Figure 1, = . Agent initializes all the variables in from the set in the gradient-based optimization. In this example, the initial values are set as . Then the agent starts updating the values of the variables by using the Equation 5.

The agent continues this update process until it converges or a maximum number of iterations is reached. After termination, the current value of is actually the approximate optimal assignment for the variable (Algorithm 1: Line 25). Then the agent updates its state to DONE, updates the set and communicates to its neighbors in a SetValue message (Algorithm 1: Line 26-30). By receiving this message, each neighbor updates its CPA with the value of and repeats the Algorithm 1 from Line 9 for the unassigned agents (). When the set is empty (all the agents finish their variable assignment), the algorithm terminates. For our example, after 100 iterations, the final assignments for these variables are . Then the agent assigns with this final value. Agent ’s state is marked as done, is added to the set and sends a SetValue message to all the neighbors of ). The neighbors update their CPA with and repeats the Algorithm 1 from Line 9 for the unassigned agents. Note that, each agent can only assign its value once and once assigned it cannot change its value. To be precise, each agent updates its value locally with gradient descent and sends the setValue() message only once to a neighbor and thus C-CoCoA is a non-iterative approach.

(a) Inquiry messages from

(c) Inquiry messages from

Figure 2: Message passing process of the C-CoCoA algorithm to solve the F-DCOP shown in Figure 1.

This section describes a complete example of our algorithm C-CoCoA. We use the F-DCOP shown in Figure 1 as the example problem and show the result that is obtained by the C-CoCoA algorithm. In this example, we assume that the variable is controlled by the agent and : [1, 2], : [3, 4], : [7, 8], : [5, 9] are the 2 random discrete points taken from the actual domain [-20, 20]. We also assume that, is the cost for the value of agent ’s domain which is calculated by neighbor and is the overall cost map that is calculated by the neighbor . We use the arrows between the nodes of the constraint graph to indicate the direction of the corresponding messages. Figure 2 shows the message passing process and the results are as follows:

• C-CoCoA Algorithm starts by randomly selecting an agent sends inquiry message to and , blue arrows represent the inquiry messages, grey node represents the inquiring agent. and calculates the cost map, , yellow nodes represent the active neighbors (Figure 2(a)).

• Agent calculates = 13, = 25, therefore, appends [3: 13] with . The agent also calculates = 10, = 20, therefore, appends [3: 10] with sends the final cost map = [3: 13, 3: 10] to . Agent calculates = 154, = 200, therefore, appends [7: 154] with . The agent also calculates = 161, = 208, therefore, appends [7: 161] with sends the final = [7: 154, 7: 161] to . Agent calculates = 30, = 90, therefore, appends [5: 30] with . The agent also calculates = 35, = 99, therefore, appends [5: 35] with sends the final = [5: 30, 5: 35] to .

• Agent receives cost maps from and , red arrows represent the cost messages (Figure 2(b)). Agent calculates using Equation 3. For the discretized domain value 1, calculates cost = 13 + 154 + 30 = 197. For the discretized domain value 2, calculates cost = 10 + 161 + 35 = 206. Therefore, = 1 and 5}. After 100 iterations of the gradient-based approach, we get, = -0.572.

• After the completion of , algorithm selects the agent sends inquiry message to and , blue arrows represent the inquiry messages (Figure 2(c)). Agents and calculate the cost maps.

• Agent calculates = 21.756, therefore, appends [-0.572: 21.756] with . The agent also calculates = 36.899, therefore, appends [-0.572: 36.899] with sends the final = [-0.572: 21.756, -0.572: 36.899] to . Agent calculates = 86, = 113, therefore, appends [7: 86] with . The agent also calculates = 86, = 112, therefore, appends [7: 86] with sends the final = [7: 86, 7: 86] to .

• Agent receives cost maps from and , red arrows represent the cost messages (Figure 2(d)). Agent calcu-

lates using Equation 3. For the discretized domain value 3, calculates cost = 21.756 + 86 = 107.756. For the discretized domain value 4, calculates cost = 36.899 + 86 = 122.899. Therefore, = 3 and . After 100 iterations of the gradient-based approach, we get, = -0.122.

• Agents and calculate the values for their variables by repeating the algorithm. We get = 0.124 and = 0.911 when it terminates. Hence, the near-optimal assignment is, = = -0.572, = -0.122, = 0.124 and = 0.911}

In C-CoCoA, we define the total number of agents |A| = n and is the set of direct neighbors of the agent . After the activation of an agent , it sends messages (UpdateState and InquiryMSG) to its neighbors as well as receives messages from its neighbors against the reply of the inquiry messages. Therefore, at this stage (Algorithm 1: Line 11-13), the number of messages is . Then, after a successful assignment to its variable, the agent sends messages (UpdateState and SetValue) to its neighbors (Algorithm 1: Line 28-30). As a result, the number of messages transmitted so far is . However, an agent sends additional messages each time it enters into the HOLD state (Algorithm 1: Line 33-34). Although an agent may never enter into the HOLD state, in the worst case, it may enter into the HOLD state k times at most, where, k is the total number of discrete points taken from the agents’ domain. For this reason, is the total number of messages an agent sends and receives, where, H = 0, 1, ..., k defines the number of times an agent enters into the HOLD state. In the worst case, the graph is complete where, and H = k. Therefore, the total number of messages sent or received by an agent is O(5n + kn) in the worst case.

The size of each UpdateState message is constant and in each of the InquiryMSG and SetValue message, the agent sends the that contains the set of known assigned values of all the neighbors . Hence, the size of each InquiryMSG and SetValue message is sends total InquiryMSG and SetValue messages to its neighbors. So, the summation of message size complexity of InquiryMSG and SetValue messages is . When the neighboring agents send inquiry message to , it sends a reply message of size k as well that contains the cost map . Therefore, sends reply messages of size k to the neighbors. Hence, the total message size for an agent is in the worst case in CCoCoA.

After the initialization and the transmission of UpdateState and InquiryMSG (Algorithm 1: Line 5-13), the computational complexity of an agent is (is the

Figure 3: Solution cost comparison of C-CoCoA and the competing algorithms varying the number of agents.

complexity of calculating an InquiryMSG). In the gradient-based optimization, an agent needs com- putational complexity, where, b is the number of times an agent updates the values of the variables (Algorithm 1: Line 21-24). After a successful assignment or each of the unsuccessful attempt (HOLD state) to assign a value, an agent again iterates over the set of its neighbors (Algorithm 1: Line 28-34). This step adds complexity. After adding all these, the overall computational complexity is ; where, in the worst case and H = k.

In this section, we empirically evaluate the performance of C-CoCoA with HCMS and AF-DPOP. The performance metrics are solution quality, time, and number of messages. Two types of graphs are used for comparison, namely, Random Graphs and Random Trees. Although [Hoang et al., 2019] proposed three versions of Functional DPOP, we only compare with AF-DPOP in this paper. The reason is AF-DPOP is reported to provide the best solution among the approximate algorithms proposed in their work. However, CMS is not used in the benchmark since it uses only piecewise linear functions which are not applicable for most of the real-world problems. For all the experiments, binary quadratic functions are used which are of the form . However, it is worth mentioning that although we choose binary quadratic functions for evaluation, C-CoCoA is broadly applicable to other classes of problems. We choose coefficients of the cost functions (a, b, c) randomly between and set the domains of each agent to . The averages are taken over 50 randomly generated problems. The experiments are carried out on a machine with an Intel core i5-6500 cpu, 3.2 GHz processor and 8 GB RAM.

Random Graphs: We use three different settings for random graphs - sparse, dense and scale-free. For all the algorithms, we choose the number of discrete points to be 3. However, we compare the performance of C-CoCoA varying the number of discrete points later in this section. For C-CoCoA, we set the maximum number of iterations for Equation 5 to be 100 and (which is the best result found on the empirical evaluation). Moreover, we stop HCMS after 100 iterations in Figures 3a, 3b, 3c and 4. Note that, although AF-DPOP requires fewer messages than HCMS, we do not limit the number of messages for HCMS since AF-DPOP requires much more computation to calculate one message. The detailed analysis of computation, time, and number of messages for each of the algorithms are given in Table 1. Figure 3a shows the comparison of average costs on Erd˝os-R´enyi topology [Erd˝os and R´enyi, 1960] with sparse settings (edge probability 0.2) varying the number of agents. This figure shows that C-CoCoA performs better than both HCMS and AF-DPOP on average. For , AF-DPOP runs out of memory. Thus, we omit the result of AF-DPOP for .

We choose dense graphs as our second random graph settings. Figure 3b shows the cost comparison between the CCoCoA and HCMS on Erd˝os-R´enyi topology with dense settings (edge probability 0.6). C-CoCoA shows comparatively better performance than HCMS. Note that, AF-DPOP is not used in the dense graph setting due to the huge computation overhead. We then choose scale-free graphs as our final random graph setting to show the comparison with AF-DPOP in random graphs. Figure 3c shows that C-CoCoA outperforms both HCMS and AF-DPOP by a significant margin.

Table 1 shows the comparison between C-CoCoA and HCMS on three random graph settings in terms of solution cost (C), time in sec (T) and the number of messages (M). We set the number of agents to 50 for sparse and scale-free graphs and 30 for the dense graph. Other settings are the same as the above experiments. Moreover, we stop HCMS after 500 iterations (I). C-CoCoA outperforms both HCMS and AF-DPOP in terms of solution quality, time, and number of messages in sparse and dense graphs. Note that, even after increasing the number of iterations for HCMS to 500, CCoCoA still manages to outperform it by a significant margin (16% for sparse graph and 8% for the dense graph). Moreover, HCMS requires roughly 40 times more messages in the sparse graph and 200 times more messages in the dense graph than C-CoCoA. For 50 agents, AF-DPOP runs out of memory in sparse and dense settings. Thus, we omit the result of AF-DPOP for sparse and dense graph. In the scale-free setting, C-CoCoA outperforms HCMS and AF-DPOP in terms of solution quality and computation time. The closest competitor of C-CoCoA in the scale-free setting is HCMS which is outperformed by a 19% margin in terms of solution quality and AF-DPOP is outperformed by 57% margin roughly. Although AF-DPOP requires much less messages compared to HCMS and C-CoCoA, it requires much more time than both of these algorithms. It is worth noting that all the results are statistically significant for p-value <0.05.

Random Trees: We use the random tree configuration in our last experimental setting since the memory requirement of AF-DPOP is less on trees. The experimental configura-

Table 1: Comparison between C-CoCoA and the competing algo- rithms in terms of Solution Cost, Time and No. of messages

Figure 4: Solution Cost Comparison of C-CoCoA and the competing algorithms varying the number of agents (random trees)

tions are similar to the random graph settings. Figure 4 shows the comparison graph between C-CoCoA and the competing algorithms on random trees. The closest competitor of CCoCoA in this setting is HCMS. On an average, C-CoCoA outperforms HCMS which in turn outperforms AF-DPOP.

The classical DCOP model deals with discrete variables. But this assumption of the variables being discrete is not applicable to many real-world problems. Hence, the F-DCOP framework has been proposed which is a variant of DCOPs that has continuous variables. In this paper, we propose an algorithm C-CoCoA that uses Cooperative Constraint Optimization (CoCoA) technique as the underlying algorithmic framework to solve F-DCOPs. To be exact, C-CoCoA combines the discrete CoCoA algorithm with the gradient-based non-linear optimization method to solve F-DCOPs. Finally, the empirical analysis shows that C-CoCoA outperforms the state-of-the-art F-DCOP solvers, HCMS and AF-DPOP. In all the experimental settings, C-CoCoA shows better results than the other benchmarking algorithms in terms of solution quality, time, and number of message passing. In the future, we would like to further investigate the potential of C-CoCoA on various F-DCOP applications. We would also like to explore the ways to extend C-CoCoA to solve multi-objective and asymmetric F-DCOPs.

[Erd˝os and R´enyi, 1960] Paul Erd˝os and Alfr´ed R´enyi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17–60, 1960.

[Fioretto et al., 2017] Ferdinando Fioretto, William Yeoh, and Enrico Pontelli. A multiagent system approach to scheduling devices in smart homes. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent

Systems, pages 981–989. International Foundation for Autonomous Agents and Multiagent Systems, 2017.

[Fitzpatrick and Meetrens, 2003] Stephen Fitzpatrick and L Meetrens. Distributed sensor networks a multiagent perspective, chapter distributed coordination through anarchic optimization, 2003.

[Grocholsky et al., 2006] Ben Grocholsky, James Keller, Vijay Kumar, and George Pappas. Cooperative air and ground surveillance. IEEE Robotics & Automation Magazine, 13(3):16–25, 2006.

[Hoang et al., 2019] Khoi D Hoang, William Yeoh, Makoto Yokoo, and Zinovi Rabinovich. New algorithms for functional distributed constraint optimization problems. arXiv preprint arXiv:1905.13275, 2019.

[Hsin and Liu, 2004] Chih-fan Hsin and Mingyan Liu. Net- work coverage using low duty-cycled sensors: random & coordinated sleep algorithms. In Proceedings of the 3rd international symposium on Information processing in sensor networks, pages 433–442. ACM, 2004.

[Maheswaran et al., 2004] Rajiv T Maheswaran, Milind Tambe, Emma Bowring, Jonathan P Pearce, and Pradeep Varakantham. Taking dcop to the real world: Efficient complete solutions for distributed multi-event scheduling. In Proceedings of the Third International Joint Conference on Autonomous Agents and Multiagent Systems-Volume 1, pages 310–317. IEEE Computer Society, 2004.

[Modi et al., 2005] Pragnesh Jay Modi, Wei-Min Shen, Milind Tambe, and Makoto Yokoo. Adopt: Asynchronous distributed constraint optimization with quality guarantees. Artificial Intelligence, 161(1-2):149–180, 2005.

[Petcu and Faltings, 2005] Adrian Petcu and Boi Faltings. A scalable method for multiagent constraint optimization. Technical report, 2005.

[Rust et al., 2016] Pierre Rust, Gauthier Picard, and Fano Ramparany. Using message-passing dcop algorithms to solve energy-efficient smart environment configuration problems. In IJCAI, pages 468–474, 2016.

[Stranders et al., 2009] Ruben Stranders, Alessandro Farinelli, Alex Rogers, and Nick R Jennings. Decentralised coordination of continuously valued control parameters using the max-sum algorithm. In Proceedings of The 8th International Conference on Autonomous Agents and Multiagent Systems-Volume 1, pages 601–608. International Foundation for Autonomous Agents and Multiagent Systems, 2009.

[van Leeuwen and Pawelczak, 2017] Cornelis Jan van Leeuwen and Przemyslaw Pawelczak. Cocoa: A non-iterative approach to a local search (a) dcop solver. In Thirty-First AAAI Conference on Artificial Intelligence, 2017.

[Voice et al., 2010] Thomas Voice, Ruben Stranders, Alex Rogers, and Nicholas R Jennings. A hybrid continuous max-sum algorithm for decentralised coordination. In ECAI, pages 61–66, 2010.

[Yedidsion and Zivan, 2016] Harel Yedidsion and Roie Zi- van. Applying dcop mst to a team of mobile robots with directional sensing abilities. In Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, pages 1357–1358. International Foundation for Autonomous Agents and Multiagent Systems, 2016.