distributed constraint optimization

A distributed constraint optimization problem (DCOP) is a problem where multiple agents coordinate with each other to take on values such that the sum of the resulting constraint costs, that are dependent on the values of the agents, is minimal. DCOPs are a popular way of formulating and solving multi-agent coordination problems such as the distributed scheduling of meetings, distributed coordination of unmanned air vehicles and the distributed allocation of targets in sensor networks. Privacy concerns in the scheduling of meetings and the limitation of communication and computation resources of each sensor in a sensor network makes centralized constraint optimization difficult. Therefore, the nature of these applications call for a distributed approach.

Our current research focus is three fold:

  • We seek to speed and scale up DCOP algorithms so that they can be amenable for real-world deployment. We have proposed methods that (1) exploit domain properties of the problems; (2) are parallelizable and, thus, sped up using graphical processing units (GPUs); (3) prune the search space through consistency propagation techniques; etc.
  • We are investigating ways to enrich the DCOP model and extend DCOP algorithms to better account for imperfect communication (e.g., message delays and message losses).
  • We plan to enrich DCOPs so that they can be used to model dynamic and uncertain problems through integration with concepts from decentralized Markov decision processes (Dec-MDPs). The proposed models and algorithms will serve as a bridge between DCOPs and Dec-MDPs, balancing the tradeoffs between expressivity and scalability.

To learn more, please see our tutorial on multi-agent distributed constrained optimization, which we gave at AAAI 2020.

sponsors

Explainable Distributed Constraint Optimization.
Binational Science Foundation (2023 – 2026).

Communication-Aware Distributed Constraint Optimization Problems: Foundations, Models, and Algorithms.
Binational Science Foundation (2019 – 2022).

CAREER: Decentralized Constraint-based Optimization for Multi-Agent Planning and Coordination.
National Science Foundation (2016 – 2021).

BSF: 2014012: Robust Solutions for Distributed Constraint Optimization Problems.
National Science Foundation (2015 – 2019).


selected publications

  1. JAAMAS
    Effect of Asynchronous Execution and Imperfect Communication on Max-Sum Belief Propagation
    Roie Zivan, Ben Rachmut, Omer Perry, and 1 more author
    Autonomous Agents and Multi-Agent Systems, 2023
  1. JAIR
    Communication-Aware Local Search for Distributed Constraint Optimization
    Ben Rachmut, Roie Zivan, and William Yeoh
    Journal of Artificial Intelligence Research, 2022
  2. JAIR
    Proactive Dynamic Distributed Constraint Optimization Problems
    Khoi D. Hoang, Ferdinando Fioretto, Ping Hou, and 3 more authors
    Journal of Artificial Intelligence Research, 2022
  1. DAI
    Incomplete Distributed Constraint Optimization Problems: Model, Algorithms, and Heuristics
    Atena M. Tabakhi, William Yeoh, and Roie Zivan
    In International Conference on Distributed Artificial Intelligence, 2021
    :trophy: Best Paper Award
  1. AAMAS
    New Algorithms for Continuous Distributed Constraint Optimization Problems
    Khoi D. Hoang, William Yeoh, Makoto Yokoo, and 1 more author
    In International Conference on Autonomous Agents and Multiagent Systems, 2020
  1. JAIR
    Distributed Gibbs: A Linear-Space Sampling-Based DCOP Algorithm
    Duc Thien Nguyen, William Yeoh, Hoong Chuin Lau, and 1 more author
    Journal of Artificial Intelligence Research, 2019
  1. JAIR
    Distributed Constraint Optimization Problems and Applications: A Survey
    Ferdinando Fioretto, Enrico Pontelli, and William Yeoh
    Journal of Artificial Intelligence Research, 2018
  2. CP
    A Large Neighboring Search Schema for Multi-agent Optimization
    Khoi D. Hoang, Ferdinando Fioretto, William Yeoh, and 2 more authors
    In International Conference on Principles and Practice of Constraint Programming, 2018