Kyushu University Academic Staff Educational and Research Activities Database
Researcher information (To researchers) Need Help? How to update
Makoto Yokoo Last modified date:2017.05.29

Graduate School
Undergraduate School

Academic Degree
Research on Distributed Constraint Satisfaction Problem
Field of Specialization
Multi-agent Systems
Outline Activities
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
  • Distributed Constraint Reasoning
    keyword : Search, Constraint Satisfaction, Multi-agent systems
Academic Activities
1. 横尾 真, Combinatorial Auctions, 2006.04.
  • 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 Engineering
    10: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,