Dear Editor, The distributed constraint optimization problems (DCOPs) [1]–[3] provide an efficient model for solving the cooperative problems of multiagent systems, which has been successfully applied to model the real-world problems like the distributed scheduling [4], sensor network management [5], [6], multi-robot coordination [7], and smart grid [8]. However, DCOPs were not well suited to solve the problems with continuous variables and constraint cost in functional form, such as the target tracking sensor orientation [9], the air and ground cooperative surveillance [10], and the sensor network coverage [11]. Therefore, the continuous DCOPs (C-DCOPs) [12] have been proposed to model such problems with continuous variables, whose goal is that all agents coordinate with each other to find the assignment to all variables such that it minimizes the sum of all constraints. Correspondingly, researchers propose various C-DCOP algorithms to deal with the modification of the C-DCOP formulation. Note that the anytime property is crucial for a C-DCOP algorithm since it guarantees to obtain the monotonic solutions in real-time. Specifically, an anytime algorithm should fulfill two conditions: 1) It can return a valid solution even if the agents are interrupted at any time before the algorithm terminates [1]; 2) The solution quality can only remain the same or increase if more steps are performed [13]. Existing C-DCOP algorithms either cannot guarantee the anytime property or utilize breadth first search (BFS) pseudo-trees, which results in privacy violations [14].

Distributed Constraint Optimization Problems (DCOPs) are an efficient framework widely used in multi-agent collaborative modeling. The traditional DCOP framework assumes that variables are discrete and constraint utilities are represented in tabular forms. However, the variables are continuous and constraint utilities are in functional forms in many practical applications. To overcome this limitation, researchers have proposed Continuous DCOPs (C-DCOPs), which can model DCOPs with continuous variables. However, most of the existing C-DCOP algorithms rely on gradient information for optimization, which means that they are unable to solve the situation where the utility function is a non-differentiable function. Although the Particle Swarm-Based C-DCOP (PCD) and Particle Swarm with Local Decision-Based C-DCOP (PCD-LD) algorithms can solve the situation with non-differentiable utility functions, they need to implement Breadth First Search (BFS) pseudo-trees for message passing. Unfortunately, employing the BFS pseudo-tree results in expensive computational overheads and agent privacy leakage, as messages are aggregated to the root node of the BFS pseudo-tree. Therefore, this paper aims to propose a fully distributed C-DCOP algorithm to solve the utility function form problem and avoid the disadvantages caused by the BFS pseudo-tree. Inspired by the population-based algorithms, we propose a fully decentralized local search algorithm, named Population-based Local Search Algorithm (PLSA), for solving C-DCOPs with three-fold advantages: (i) PLSA adopts a heuristic method to guide the local search to achieve a fast search for high-quality solutions; (ii) in contrast to the conventional C-DCOP algorithm, PLSA can solve utility functions of any form; and (iii) compared to PCD and PCD-LD, PLSA avoids complex message passing to achieve efficient computation and agent privacy protection. In addition, we implement an extended version of PLSA, named Population-based Global Search Algorithm (PGSA), and empirically show that our algorithms outperform the state-of-the-art C-DCOP algorithms on three types of benchmark problems.

Continuous Distributed Constraint Optimization Problem (C-DCOPs) are a powerful framework to model problems with continuous variables in multi-agent systems. Previous works about C-DCOP algorithms mainly use pseudo-trees to guarantee the anytime property or are without anytime property guarantees. However, there is a risk of privacy leakage in the pseudo-tree due to utility passing between agents. Therefore, based on the basic constraint graph instead of the pseudo-tree, we (i) extend the Maximum Gain Message (MGM) algorithm by combining the local search strategy to solve C-DCOPs, named Continuous MGM (C-MGM), and it’s able to guarantee the monotonicity of the solution quality; (ii) propose a Parallel C-MGM (C-PMGM) algorithm to improve the solution quality through parallel random search; and (iii) introduce the differential search into C-PMGM to design a Parallel Differential Search C-MGM (C-PDSM) algorithm, which constructs a heuristic method to speed up convergence and improve solution quality. Compared to other anytime C-DCOP algorithms using pseudo-trees, the proposed three algorithms can exhibit better performance in avoiding privacy violations. We theoretically prove that the proposed algorithms are the anytime algorithms and empirically demonstrate that our algorithms outperform the state-of-the-art C-DCOP algorithms.