Japanese version is Here
Makoto Yokoo
Overview
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.
Recent Publications
- Robust Double Auction Protocol against False-name Bids,
Decision Support Systems}, to appear.
- The Effect of False-name Bids in Combinatorial Auctions:
New Fraud in Internet Auctions,
Games and Economic Behavior, Volume 46, Issue 1, Pages 174-188,
2004.
Abstract
PDF
- On Market-Inspired Approaches to Propositional Satisfiability,
Artificial Intelligence Journal, vol.144, pp.125-156, 2003.
- Defection-Free Exchange Mechanisms based on an Entry Fee
Imposition
Artificial Intelligence Journal, Vol.142, pp.265-286, 2002,
-
Secure Generalized Vickrey Auction using Homomorphic Encryption,
Seventh International Financial Cryptography Conference
(FC-03), 2003.
- An Average-case Budget-Non-Negative Double Auction Protocol,
First International joint Conference on Autonomous Agents
and Multiagent Systems (AAMAS-2002), 2002.
- Local Search for Distributed SAT with Complex Local Problems,
First International joint Conference on Autonomous Agents
and Multiagent Systems (AAMAS-2002), 2002.
- Designing an Auciton Protocol under Asymmetric Information on
Nature's Selection,
First International joint Conference on Autonomous Agents
and Multiagent Systems (AAMAS-2002), 2002.
- Secure Multi-agent Dynamic Programming based on Homomorphic
Encryption and its Application to Combinatorial Auctions
First International joint Conference on Autonomous Agents
and Multiagent Systems (AAMAS-2002), 2002.
- Secure Combinatorial Auctions
by Dynamic Programming with Polynomial Secret Sharing,
Sixth International Financial Cryptography Conference
(FC-02), 2002.
Abstract
PDF
- Robust Combinatorial Auction Protocol against False-name Bids,
Artificial Intelligence Journal,
Vol.130, No.2, 2001.
Abstract
PDF
- Solving Satisfiability Problems using Reconfigurable Computing,
IEEE Transactions on VLSI, Vol.9, No.1, 2001.
Abstract
PDF
- Bundle Design in Robust Combinatorial Auction Protocol against
False-name Bids,
17th International Joint Conference on Artificial Intelligence
(IJCAI-2001), 2001.
Abstract
PDF
- Robust Multi-unit Auction Protocol against False-name Bids,
17th International Joint Conference on Artificial Intelligence
(IJCAI-2001), 2001.
Abstract
PDF
- On Market-Inspired Approaches to Propositional Satisfiability,
17th International Joint Conference on Artificial Intelligence
(IJCAI-2001), 2001.
Abstract
PDF
- Robust Double Auction Protocol against False-name Bids,
21st International Conference on Distributed Computing Systems
(ICDCS-2001), 2001.
Abstract
PDF
- An Efficient Approximate Algorithm for Winner Determination
in Combinatorial Auctions,
Second ACM Conference on Electronic Commerce
(EC-2000), 2000.
Abstract
- Robust Combinatorial Auction Protocol against False-name Bids,
Seventeenth National Conference on Artificial Intelligence
(AAAI-2000), 2000.
Abstract
PDF
- An Approach to Over-constrained Distributed Constraint
Satisfaction Problems: Distributed Hierarchical Constraint Satisfaction
Proceedings of the Fourth International
Conference on Multiagent Systems (ICMAS-2000), 2000.
Abstract
PDF
- Defection-Free Exchange Mechanisms for Information Good
Proceedings of the Fourth International
Conference on Multiagent Systems (ICMAS-2000), 2000.
- Frequency Assignment for Cellular Mobile
Systems Using Constraint Satisfaction Techniques
Proceedings of the IEEE Annual Vehicular Technology Conference
(VTC2000-Spring), 2000.
Abstract
PDF
- The Effect of Nogood Learning in Distributed Constraint Satisfaction
Proceedings of the 20th International Conference on Distributed Computing Systems
(ICDCS-2000), 2000.
Abstract
PDF
- The Effect of False-name Declarations in Mechanism Design:
Towards Collective Decision Making on the Internet
Proceedings of the 20th International Conference on Distributed Computing Systems
(ICDCS-2000), 2000.
Abstract
PDF (extended version)
- Algorithms for Distributed Constraint Satisfaction: A Review
Autonomous Agents and Multi-Agent Systems,
Vol.3, No.2, pp.189--212, 2000.
Abstract
PDF
- Solving Satisfiability Problems on FPGAs using Experimental Unit
Propagation
Proceedings of the Fifth International
Conference on Principles and Practice of Constraint Programming
(CP-99), 1999.
Abstract
PDF
- A Limitation of the Generalized Vickrey Auction in Electronic
Commerce : Robustness against False-name Bids
Proceedings of the 16th National Conference on Artificial Intelligence
(AAAI-99), 1999.
Abstract
PDF (extended version)
- Search Algorithms for Agents
in Multiagent Systems: A Modern Approach to Distributed Artificial
Intelligence, G. Weiss (ed), MIT Press, 1999.
- Distributed Constraint Satisfaction Problem: Formalization and
Algorithms
IEEE Trans. on Knowledge and Data Engineering, vol.10, No.5, 1998.
Abstract
PDF
- Distributed Constraint Satisfaction Algorithm for Complex Local Problems
Proceedings of the Third International
Conference on Multiagent Systems (ICMAS-98),
pp.372--379, 1998.
Abstract
PDF
- Solving Satisfiability Problems Using Logic Synthesis and
Reconfigurable Hardware
Proceedings of the 31st Hawaii International
Conference on System Sciences (HICSS-31)
Abstract
PDF
- Why Adding More Constraints Makes a Problem
Easier for Hill-climbing Algorithms: Analyzing Landscapes of CSPs
Proceedings of the Third International
Conference on Principles and Practice of Constraint Programming (CP-97),
pp.356--370, 1997.
Abstract
PDF
OHP
- Distributed Partial Constraint Satisfaction Problem
Proceedings of the Third International
Conference on Principles and Practice of Constraint Programming (CP-97),
pp.222--236, 1997.
Abstract
PDF
-
Multiagent Real-Time-A* with Selection:
Introducing Competition in Cooperative Search
Proceedings of the Second International
Conference on Multiagent Systems (ICMAS-96),
pp.409--416, 1996.
Abstract
OHP
- Distributed Breakout Algorithm for Solving Distributed Constraint
Satisfaction Problems
Proceedings of the Second International
Conference on Multiagent Systems (ICMAS-96),
pp.401--408, 1996.
Abstract
PDF
OHP
- Solving Satisfiability Problems using Field Programmable Gate Arrays: First Results
Proceedings of the Second International
Conference on Principles and Practice of Constraint Programming (CP-96),
pp.497--509, 1996.
Abstract
PDF
OHP
- Asynchronous Weak-commitment Search for Solving Distributed Constraint Satisfaction Problems
First International
Conference on Principles and Practice of Constraint Programming (CP-95),
pp.407-422,1995.
Abstract
OHP
- Weak-commitment Search for Solving Constraint Satisfaction Problems
12th National Conference on Artificial Intelligence (AAAI-94), pp. 313--318,1994.
Abstract
PDF
OHP
- Constraint Relaxation in Distributed Constraint Satisfaction Problem
5th International Conference on Tools with Artificial Intelligence, pp. 56--63,
1993.
Abstract
PDF
- Distributed
Constraint Satisfaction for Formalizing Distributed Problem Solving
12th International Conference on Distributed Computing Systems
(ICDCS-92), pp. 614-621, 1992.
Abstract
PDF
Professional Activities
E-Mail: yokoo@is.kyushu-u.ac.jp