Makoto Yokoo

Recent Topics


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.