092-802-3585

092-802-3576

Research on Distributed Constraint Satisfaction Problem

Multi-agent Systems

When there exist multiple agents in a shared environment, there usually exist constraints among possible actions of these agents. A distributed constraint satisfaction problem (distributed CSP) is a problem to find a consistent combination of actions that satisfies these inter-agent constraints. A distributed CSP is a fundamental problem for achieving the coordination among agents, and this problem can formalize various application problems in DAI, such as MultiAgent truth maintenance tasks and distributed resource allocation problems.

I have developed a basic algorithm called asynchronous backtracking that is guaranteed to be complete, i.e., when there exists a consistent solution, the agents can eventually find it, and if there exists no solution since the constraints are too tight, the agents can eventually find out the fact that there exists no solution. Furthermore, this basic algorithm can be extended to a more efficient asynchronous weak-commitment search algorithm by introducing dynamic ordering among agents. The notion of weak-commitment is also effective for solving normal, centralized constraint satisfaction problems.

Furthermore, I'm conducting researches on mechanism design in multi-agent systems (e.g., auctions), iterative improvement algorithms for solving distributed CSPs, algorithms for over-constrained distributed CSPs, Multi-agent Real-time search algorithms, methods for solving CSPs using reconfigurable hardware (field programmable gate arrays), and landscape analysis of CSPs.

Research Interests

• Mechanism Design, Internet Auctions
  keyword : Multi-agent Systems, Economics, Game theory
  1998.08.
• Distributed Constraint Reasoning
  keyword : Search, Constraint Satisfaction, Multi-agent systems
  1989.01.

Academic Activities Awards

• This award is given to a paper that has published at least 10 years ago and has a significant influence to the research community of autonomous agents and multiagent systems. The award is give to the following papers:Makoto Yokoo, Edmund H. Durfee, Toru Ishida, and Kazuhiro Kuwabara,``The Distributed Constraint Satisfaction Problem: Formalization and Algorithms'', IEEE Transactions on Knowledge and Data Engineering10:673-685, 1998, together with, Makoto Yokoo and Katsutoshi Hirayama, ``Distributed Breakout Algorithm for Solving Distributed Constraint Satisfaction Problems'', Second International Conference on Multiagent Systems (ICMAS-96), pp.401-408,1996.