William Yeoh

"An expert is one who knows more and more about less and less"
- Nicholas Murray Butler


>> Research

Distributed Constraint Optimization (DCOP) is a model that includes a set of agents, where each agent can take on values from its domain. Constraints exist between agents and the cost of each constraint is dependent upon the values taken by the respective agents. All the agents will then need to coordinate their choice of values so that the total cost of unsatisfied constraints is minimized.

This model is rapidly becoming popular for formulating and solving agent-coordination problems including the scheduling of meetings, target allocation in sensor networks and coordination of UAVs. 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.

Unfortunately, solving a DCOP problem optimally is known to be NP-hard. Thus, it is my research interest to find intelligent ways to speed up DCOP algorithms with the hope of making them more applicable to larger and thus more real-world applications.

>> Publications

>>> Conference Papers
  • W. Yeoh, A. Felner and S. Koenig, "BnB-ADOPT : An Asynchronous Branch-and-Bound DCOP Algorithm", in Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2008 [pdf][bib]
     
  • X. Sun, S. Koenig and W. Yeoh, "Generalized Adaptive A*", in Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2008 [pdf][bib]
     
  • W. Yeoh, S. Koenig and X. Sun, "Trading Off Solution Cost for Smaller Runtime in DCOP Search Algorithms [Short Paper]", in Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2008 [pdf][bib]
>>> Workshop Papers
  • W. Yeoh, S. Koenig and X. Sun, "Trading Off Solution Cost for Smaller Runtime in DCOP Search Algorithms [Extended Version]", in Proceedings of the International Workshop on Distributed Constraint Reasoning (DCR), 2008 [pdf][bib]
     
  • W. Yeoh, A. Felner, S. Koenig, "BnB-ADOPT : An Asynchronous Branch-and-Bound DCOP Algorithm", in Proceedings of the International Workshop on Distributed Constraint Reasoning (DCR), 2007 [pdf][bib]
     
  • W. Yeoh, S. Koenig, A. Felner, "IDB-ADOPT : A Depth-First Search DCOP Algorithm", in Proceedings of the International Workshop on Distributed Constraint Reasoning (DCR), 56-70, 2007 [pdf][bib]