A Particle Swarm Based Algorithm for Functional Distributed Constraint Optimization Problems

Moumita Choudhury, Saaduddin Mahmud, Md. Mosaddek KhanAAAI 2020 · DOI

Abstract

Functional Distributed Constraint Optimization Problems (F-DCOPs) provide a powerful framework for coordinating multi-agent systems with continuous variables. However, existing solvers often struggle with scalability or require specific function properties like differentiability. This paper introduces PFD (Particle Swarm based F-DCOP), a novel algorithm that adapts Particle Swarm Optimization (PSO) to a distributed environment. PFD achieves higher solution quality with significantly lower memory and computational overhead compared to previous state-of-the-art methods, while maintaining an anytime property.

What Problem Does This Paper Address?

In multi-agent systems, agents must often coordinate to minimize a global cost. Applications range from sensor networks scheduling sleep cycles to robots orienting toward a target. These scenarios are traditionally modeled as a Distributed Constraint Optimization Problem (DCOP).

Standard DCOPs assume variables are discrete. In many real-world scenarios, however, variables are continuous (e.g., angles, time, or power levels). Functional DCOPs (F-DCOPs) were created to handle these continuous domains, but existing solvers face significant trade-offs:

  1. Exact solvers (like EF-DPOP) suffer from exponential growth in memory and computation as the problem size increases.
  2. Approximate solvers (like HCMS) often rely on gradient-based methods, requiring functions to be differentiable, or use piece-wise linear approximations that may not accurately represent complex real-world applications.
Example of a Constraint Graph and associated continuous cost functions in an F-DCOP.

The authors aim to create a solver that is scalable, handles non-differentiable functions, and provides an "anytime" property, meaning it can be stopped at any moment to provide the best solution found up to that point.

Methods

The authors propose PFD, which translates the centralized Particle Swarm Optimization (PSO) meta-heuristic into a distributed functional framework. PSO is a population-based search where "particles" move through the search space, influenced by their own best-known position and the global best-known position of the swarm.

Key components of the PFD algorithm include:

  • BFS Pseudo-tree Construction: Agents are organized into a tree structure to define a clear message-passing order and hierarchy.
  • Distributed Evaluation: Instead of a central controller calculating fitness, agents calculate local constraint costs and pass them up the tree. The root agent aggregates these values to determine the "global best" particle position for the current iteration.
  • Guaranteed Convergence PSO (GCPSO): To prevent the swarm from getting stuck in local optima, the authors implement a specific update rule for the global best particle. This forces it to explore random nearby areas if its position hasn't improved for several iterations.
  • Anytime Mechanism: The algorithm ensures that as agents iterate, they keep track of the best global and personal positions found so far, guaranteeing that the reported solution quality never degrades over time.
The BFS pseudo-tree and ordered arrangement used for distributed message passing.

Evaluation and Key Insights

The paper evaluates PFD using synthetic benchmarks standard for DCOP research, including Random Graphs (Erdős–Rényi model), Scale-free Graphs, and Random Trees. They utilized binary quadratic cost functions with randomly chosen coefficients and wide variable domains.

Key Insights:

  • Simplicity and Versatility: Unlike gradient-based methods, PFD uses only basic arithmetic. This makes it computationally efficient and applicable to non-differentiable functions.
  • Memory Efficiency: While previous functional DPOP variants require memory that grows exponentially with the graph's width, PFD’s memory requirements are linear relative to the number of particles ($K$) and neighbors ($n$).
  • Swarm Intelligence in F-DCOPs: This work represents the first successful integration of PSO into the F-DCOP framework. The social behavior of particles allows agents to explore a much larger search space than local search methods like HCMS.

Key Results

  • Scalability: The state-of-the-art competitor, AF-DPOP, consistently ran out of memory when the number of agents reached 20. In contrast, PFD handled 50+ agents with ease.
  • Solution Quality: Across sparse, dense, and scale-free graphs, PFD consistently found lower-cost solutions than HCMS. While HCMS sometimes found a decent solution faster initially, PFD’s steady improvement eventually overtook it.
  • Anytime Performance: The authors theoretically proved and empirically demonstrated that PFD is a true anytime algorithm, with solution costs monotonically decreasing as iterations progress.

Limitations and Future Work

While PFD shows great promise, the empirical evaluation focused primarily on binary quadratic functions. Future testing on more complex, non-convex, or "rugged" landscapes would further validate its robustness. Additionally, PSO-based algorithms can be sensitive to hyperparameters like inertia weight and acceleration constants; an adaptive parameter approach might further improve performance. Finally, the authors suggest extending PFD to handle multi-objective F-DCOPs as a promising future direction.

Summary updated

BibTeX
@inproceedings{choudhury2020particle,
  author = {Moumita Choudhury and Saaduddin Mahmud and Md. Mosaddek Khan},
  title = {{A Particle Swarm Based Algorithm for Functional Distributed Constraint Optimization Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i05.6198},
}
Figure