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.

### Sponsors

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).

### Representative Publications

- Khoi D. Hoang, Ferdinando Fioretto, Ping Hou,
**William Yeoh**, Makoto Yokoo, and Roie Zivan. “Proactive Dynamic Distributed Constraint Optimization Problems.”*Journal of Artificial Intelligence Research (JAIR)*, 74, pages 179-225, 2022. - Roie Zivan, Omer Perry, Ben Rachmut, and
**William Yeoh**. “The Effect of Asynchronous Execution and Message Latency on Max-sum.” In*Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP)*, pages 60:1–60:18, 2021. - Ben Rachmut, Roie Zivan, and
**William Yeoh**. “Latency-Aware Local Search for Distributed Constraint Optimization.” In*Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS)*, pages 1019-1027, 2021. - Khoi D. Hoang,
**William Yeoh**, Makoto Yokoo, and Zinovi Rabinovich. “New Algorithms for Continuous Distributed Constraint Optimization Problems.” In*Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS)*, pages 502-510, 2020. - Atena M. Tabakhi,
**William Yeoh**, and Makoto Yokoo. “Parameterized Heuristics for Incomplete Weighted CSPs with Elicitation Costs.” In*Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS)*, pages 476-484, 2019. - Khoi D. Hoang, Ferdinando Fioretto,
**William Yeoh**, Enrico Pontelli, and Roie Zivan. “A Large Neighboring Search Schema for Multi-Agent Optimization.” In*Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP)*, pages 688-706, 2018. - Md. Mosaddek Khan, Long Tran-Thanh,
**William Yeoh**, and Nicholas R. Jennings. “A Near-Optimal Node-to-Agent Mapping Heuristic for GDL-based DCOP Algorithms in Multi-Agent Systems.” In*Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS)*, pages 166-172, 2018. - Atena M. Tabakhi, Tiep Le, Ferdinando Fioretto, and
**William Yeoh**. “Preference Elicitation for DCOPs.” In*Proceedings of the International Conference on Principles and Practice of Constraint Programming (CP)*, pages 278-296, 2017. - Khoi D. Hoang, Ping Hou, Ferdinando Fioretto,
**William Yeoh**, Roie Zivan, and Makoto Yokoo. “Infinite-Horizon Proactive Dynamic DCOPs.” In*Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS)*, pages 212-220, 2017. - Ferdinando Fioretto,
**William Yeoh**, and Enrico Pontelli. “A Dynamic Programming-based MCMC Framework for Solving DCOPs with GPUs.” In*.* - Khoi D. Hoang, Ferdinando Fioretto, Ping Hou, Makoto Yokoo,
**William Yeoh**, and Roie Zivan. “Proactive Dynamic Distributed Constraint Optimization.” In*Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS),*pages 597-605, 2016. - Tiep Le, Ferdinando Fioretto,
**William Yeoh**, Tran Cao Son, and Enrico Pontelli. “ER-DCOPs: A Framework for Distributed Constraint Optimization with Uncertainty in Constraint Utilities.” In*Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS),*pages 606-614, 2016. - Ferdinando Fioretto,
**William Yeoh**, and Enrico Pontelli. “Multi-Variable Agent Decomposition for DCOPs.” In*Proceedings of the AAAI Conference on Artificial Intelligence (AAAI),*pages 2480-2486, 2016.