Author name cluster

Dingding Chen

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

1 author row

AAMAS Conference 2022 Conference Paper

Beyond Uninformed Search: Improving Branch-and-bound Based Acceleration Algorithms for Belief Propagation via Heuristic Strategies

Junsong Gao
Ziyu Chen
Dingding Chen
Wenxin Zhang

Belief propagation algorithms including Max-sum and its variants are important methods for solving DCOPs. However, they may face a tough challenge when handling n-ary constraints since the computational overheads grow exponentially with the number of variables that a utility function holds. In this paper, we update the state-of-the-art technique called Function Decomposing and State Pruning (FDSP) which can significantly reduce such an expenditure, by introducing two heuristic techniques. By introducing a round-robin mechanism to control the order of exploration, we propose Concurrent-search-based FDSP (CONC-FDSP). Besides, we propose Best-first-search-based FDSP (BFS-FDSP) by using the 𝐴∗ search to find the optimal path to the solution. Finally, we demonstrate their efficiency in solving the benchmarks compared with the state-of-the-art.

PDF

JAAMAS Journal 2020 Journal Article

A hybrid tree-based algorithm to solve asymmetric distributed constraint optimization problems

Dingding Chen
Yanchen Deng
Wenxin Zhang

Abstract Asymmetric distributed constraint optimization problems (ADCOPs) have emerged as an important formalism in multi-agent community due to their ability to capture personal preferences. However, the existing search-based complete algorithms for ADCOPs only exploit local knowledge to calculate lower bounds, which leads to inefficient pruning and prohibits them from solving large scale problems. On the other hand, inference-based complete algorithms (e. g. , DPOP) for distributed constraint optimization problems are able to aggregate the global cost promptly but cannot be directly applied into ADCOPs due to a privacy concern. Thus, in this paper, we investigate the possibility of combining inference and search to effectively solve ADCOPs at an acceptable loss of privacy. Specifically, we propose a hybrid complete ADCOP algorithm called PT-ISABB which uses a tailored inference algorithm to provide tight lower bounds and upper bounds, and a tree-based complete search algorithm to guarantee the optimality. Furthermore, we introduce two suboptimal variants of PT-ISABB based on bounded-error approximation mechanisms to enable trade-off between theoretically guaranteed solutions and coordination overheads. We prove the correctness of PT-ISABB and its suboptimal variants. Finally, the experimental results demonstrate that PT-ISABB exhibits great superiorities over other state-of-the-art search-based complete algorithms and its suboptimal variants can quickly find a solution within the user-specified bounded-error.

Details DOI

AAAI Conference 2020 Conference Paper

HS-CAI: A Hybrid DCOP Algorithm via Combining Search with Context-Based Inference

Dingding Chen
Yanchen Deng
Ziyu Chen
Wenxing Zhang
Zhongshi He

Search and inference are two main strategies for optimally solving Distributed Constraint Optimization Problems (DCOPs). Recently, several algorithms were proposed to combine their advantages. Unfortunately, such algorithms only use an approximated inference as a one-shot preprocessing phase to construct the initial lower bounds which lead to inefﬁcient pruning under the limited memory budget. On the other hand, iterative inference algorithms (e. g. , MB-DPOP) perform a context-based complete inference for all possible contexts but suffer from tremendous trafﬁc overheads. In this paper, (i) hybridizing search with context-based inference, we propose a complete algorithm for DCOPs, named HS- CAI where the inference utilizes the contexts derived from the search process to establish tight lower bounds while the search uses such bounds for efﬁcient pruning and thereby reduces contexts for the inference. Furthermore, (ii) we introduce a context evaluation mechanism to select the context patterns for the inference to further reduce the overheads incurred by iterative inferences. Finally, (iii) we prove the correctness of our algorithm and the experimental results demonstrate its superiority over the state-of-the-art.

PDF Details

AAAI Conference 2019 Conference Paper

A Generic Approach to Accelerating Belief Propagation Based Incomplete Algorithms for DCOPs via a Branch-and-Bound Technique

Ziyu Chen
Xingqiong Jiang
Yanchen Deng
Dingding Chen
Zhongshi He

Belief propagation approaches, such as Max-Sum and its variants, are important methods to solve large-scale Distributed Constraint Optimization Problems (DCOPs). However, for problems with n-ary constraints, these algorithms face a huge challenge since their computational complexity scales exponentially with the number of variables a function holds. In this paper, we present a generic and easy-touse method based on a branch-and-bound technique to solve the issue, called Function Decomposing and State Pruning (FDSP). We theoretically prove that FDSP can provide monotonically non-increasing upper bounds and speed up belief propagation based incomplete DCOP algorithms without an effect on solution quality. Also, our empirically evaluation indicates that FDSP can reduce 97% of the search space at least and effectively accelerate Max-Sum, compared with the state-of-the-art.

PDF Details

IJCAI Conference 2019 Conference Paper

AsymDPOP: Complete Inference for Asymmetric Distributed Constraint Optimization Problems

Yanchen Deng
Ziyu Chen
Dingding Chen
Wenxin Zhang
Xingqiong Jiang

Asymmetric distributed constraint optimization problems (ADCOPs) are an emerging model for coordinating agents with personal preferences. However, the existing inference-based complete algorithms which use local eliminations cannot be applied to ADCOPs, as the parent agents are required to transfer their private functions to their children. Rather than disclosing private functions explicitly to facilitate local eliminations, we solve the problem by enforcing delayed eliminations and propose AsymDPOP, the first inference-based complete algorithm for ADCOPs. To solve the severe scalability problems incurred by delayed eliminations, we propose to reduce the memory consumption by propagating a set of smaller utility tables instead of a joint utility table, and to reduce the computation efforts by sequential optimizations instead of joint optimizations. The empirical evaluation indicates that AsymDPOP significantly outperforms the state-of-the-art, as well as the vanilla DPOP with PEAV formulation.

PDF Details

AAMAS Conference 2019 Conference Paper

PT-ISABB: A Hybrid Tree-based Complete Algorithm to Solve Asymmetric Distributed Constraint Optimization Problems

Yanchen Deng
Ziyu Chen
Dingding Chen
Xingqiong Jiang
Qiang Li

Asymmetric Distributed Constraint Optimization Problems (AD- COPs) have emerged as an important formalism in multi-agent community due to their ability to capture personal preferences. However, the existing search-based complete algorithms for AD- COPs can only use local knowledge to compute lower bounds, which leads to inefficient pruning and prohibits them from solving large scale problems. On the other hand, inference-based complete algorithms (e. g. , DPOP) for Distributed Constraint Optimization Problems (DCOPs) require only a linear number of messages, but they cannot be directly applied into ADCOPs due to a privacy concern. Therefore, in the paper, we consider the possibility of combining inference and search to effectively solve ADCOPs at an acceptable loss of privacy. Specifically, we propose a hybrid complete algorithm called PT-ISABB which uses a tailored inference algorithm to provide tight lower bounds and a tree-based complete search algorithm to exhaust the search space. We prove the correctness of our algorithm and the experimental results demonstrate its superiority over other state-of-the-art complete algorithms.

PDF