A Particle Swarm Based Algorithm for Functional Distributed Constraint Optimization Problems

Authors

  • Moumita Choudhury University of Dhaka
  • Saaduddin Mahmud University of Dhaka
  • Md. Mosaddek Khan University of Dhaka

DOI:

https://doi.org/10.1609/aaai.v34i05.6198

Abstract

Distributed Constraint Optimization Problems (DCOPs) are a widely studied constraint handling framework. The objective of a DCOP algorithm is to optimize a global objective function that can be described as the aggregation of several distributed constraint cost functions. In a DCOP, each of these functions is defined by a set of discrete variables. However, in many applications, such as target tracking or sleep scheduling in sensor networks, continuous valued variables are more suited than the discrete ones. Considering this, Functional DCOPs (F-DCOPs) have been proposed that can explicitly model a problem containing continuous variables. Nevertheless, state-of-the-art F-DCOPs approaches experience onerous memory or computation overhead. To address this issue, we propose a new F-DCOP algorithm, namely Particle Swarm based F-DCOP (PFD), which is inspired by a meta-heuristic, Particle Swarm Optimization (PSO). Although it has been successfully applied to many continuous optimization problems, the potential of PSO has not been utilized in F-DCOPs. To be exact, PFD devises a distributed method of solution construction while significantly reducing the computation and memory requirements. Moreover, we theoretically prove that PFD is an anytime algorithm. Finally, our empirical results indicate that PFD outperforms the state-of-the-art approaches in terms of solution quality and computation overhead.

Downloads

Published

2020-04-03

How to Cite

Choudhury, M., Mahmud, S., & Khan, M. M. (2020). A Particle Swarm Based Algorithm for Functional Distributed Constraint Optimization Problems. Proceedings of the AAAI Conference on Artificial Intelligence, 34(05), 7111-7118. https://doi.org/10.1609/aaai.v34i05.6198

Issue

Section

AAAI Technical Track: Multiagent Systems