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

Graduate School
Undergraduate School

E-Mail *Since the e-mail address is not displayed in Internet Explorer, please use another web browser:Google Chrome, safari.
 Reseacher Profiling Tool Kyushu University Pure
Academic Degree
Research on Distributed Constraint Satisfaction Problem
Country of degree conferring institution (Overseas)
Field of Specialization
Multi-agent Systems
Total Priod of education and research career in the foreign country
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
  • Research on constrained two-sided matching
    keyword : two-sided matching, strategyproofness, deferred acceptance mechanism
  • 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,