横尾 真 Makoto Yokoo
研究の概要
複数の自律的なエージェントが同時に存在する場合，
これらのエージェントの取り得る行動の間にはなんらかの制約があると考えられます．
分散制約充足問題とは，
これらのエージェントが互いに制約を満足する行動の組合せを発見する問題です．
この問題はエージェント間の協調を実現するための非常に基本的な問題であり，
複数エージェント間の資源分配問題，複数知識ベース間の整合性管理などの様々な応用問題を
表現することができます．
これまでに，各エージェントが全体を制御するエージェントなしに非同期，並行的に動作し，
完全性（制約を満たす解が存在するなら必ず解が得られ，解が存在しないなら，
解が無いことを発見して停止すること）が保証される，分散制約充足問題を解く
分散アルゴリズムの考案，アルゴリズムの高速化手法の検討を行ってきました．
この高速化手法は
一つのエージェントが問題全体を解く通常の制約充足問題にも適用することができます．
この他, オークション等のマルチエージェントシステムのメカニズムデザイン,
反復改善型の分散制約充足アルゴリズム, 過制約な問題への対応方法,
再構成可能なハードウェアを用いた制約充足問題の解法,
マルチエージェント実時間探索アルゴリズム,
制約充足問題の地形の解析
などの研究を進めています.
表彰
- 2004年 Association for
Computing Machinery (ACM) Special Interest Group on Artificial Intelligence
(SIGART) Autonomous Agent Research Award 受賞
- 2003年 Association for
Computing Machinery (ACM)
Recognition of Service Award 受賞
- 2002年人工知能学会論文賞,
``架空名義入札に頑健な複数ユニットオークションプロトコル''
-
電子情報通信学会情報セキュリティ研究専門委員会
暗号と情報セキュリティシンポジウム (SCIS2002) 論文賞,
``セキュアな動的計画法と組合せオークションへの応用''
-
Pacific-Rim International Workshop on Multi-agents
(PRIMA-2002) Best Paper Award,
``False-name-proof Multi-unit Auction Protocol utilizing Greedy
Allocation based on Approximate Evaluation Values''
-
国際会議論文 ``On Market-Inspired Approaches to Propositional Satisfiability'',
17th International Joint Conference on Artificial Intelligence
(IJCAI-2001)が優秀論文として, 国際論文誌 Artificial Intelligenceに推薦.
- 国際会議論文 ``Robust Combinatorial Auction Protocol against False-name Bids'',
17th National Conference on Artificial Intelligence
(AAAI-2000)が優秀論文として, 国際論文誌 Artificial Intelligenceに推薦.
- 国際会議論文 ``Defection-Free Exchange Mechanisms for Information Good'',
Fourth International
Conference on Multiagent Systems (ICMAS-2000)が優秀論文として, 国際論文誌
Autonomous Agents and Multi-Agent Systemsに推薦.
- 1999年 人工知能学会全国大会優秀論文賞,
``電子商取引における一般化 Vickrey オークションの問題点:
架空名義入札に対する頑健性''
- 1995年 情報処理学会 坂井記念特別賞受賞
- 1992年人工知能学会論文賞, ``エージェントの組織による実時間連続問題解決''
担当科目
学位論文
- 分散制約充足問題に関する研究, 博士 (工学),
東京大学大学院 工学系研究科 電子情報専攻, 1995年6月15日
アブストラクト
学歴
- 1984年3月: 東京大学 工学部 電子工学科卒業
- 1986年3月: 東京大学 工学系研究科, 電気工学専攻, 修士課程修了
職歴
- 2004年4月 - : 九州大学大学院システム情報科学研究院知能情報学部門 教授
- 1986年4月 - 2004年3月: NTT勤務
- 1990年9月 - 1991年8月: ミシガン大学, the Department
of Electrical Engineering and Computer Science, 客員研究員
最近の主な発表論文等
- Robust Double Auction Protocol against False-name Bids,
Decision Support Systems}, to appear.
- 留保価格設定が不要な耐架空名義入札マルチ
ユニットオークションプロトコル,
電子情報通信学会論文誌, 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
- 架空名義入札に頑健な組合せオークションプロトコルにおける
バンドルの設計方法,
コンピュータソフトウェア (ソフトウェア科学会論文誌), vol.20,
No.4, pp.25--34, 2003.
- On Market-Inspired Approaches to Propositional Satisfiability,
Artificial Intelligence Journal, vol.144, pp.125-156, 2003.
- 平均的に予算非負なダブルオークションプロトコル,
人工知能学会誌, vol. 18, No. 1, 2003.
- Defection-Free Exchange Mechanisms based on an Entry Fee
Imposition
Artificial Intelligence Journal, Vol.142, pp.265-286, 2002,
-
自然の選択の情報に非対称性が存在する場合のオークションプロトコルの設計,
コンピュータソフトウェア (ソフトウェア科学会論文誌),
Vol.20, No.1,
pp.16--26, 2003.
-
Secure Generalized Vickrey Auction using Homomorphic Encryption,
Seventh International Financial Cryptography Conference
(FC-03), 2003.
-
逐次型オークションの入札戦略決定手法：準線形効用と予算制約の導入,
電子情報通信学会論文誌,
vol.J85-D-I, No.10, pp.974-984, 2002
- 架空名義入札に頑健な組合せオークションプロトコル,
情報処理学会論文誌,
Vol.43, No.6, pp.1814-1824, 2002.
- 架空名義入札に頑健な複数ユニットオークションプロトコル,
人工知能学会誌, Vol.17, No.4,
pp.390-397, 2002.
- 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.
アブストラクト
PDF
- 架空名義入札に頑健なダブルオークションプロトコル,
電子情報通信学会論文誌, Vol.J84-D-I, No.8, 2001.
- 組合せオークションの高速な準最適勝者決定アルゴリズム,
人工知能学会誌, Vol.16, No.5, 2001.
- 再構成可能なハードウェアを用いた充足可能性問題の解法,
電子情報通信学会論文誌, Vol.~J84-D-I, No.4, 2001.
- 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.
アブストラクト
PDF
- Robust Multi-unit Auction Protocol against False-name Bids,
17th International Joint Conference on Artificial Intelligence
(IJCAI-2001), 2001.
アブストラクト
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.
アブストラクト
PDF
- An Efficient Approximate Algorithm for Winner Determination
in Combinatorial Auctions,
Second ACM Conference on Electronic Commerce
(EC-2000), 2000.
アブストラクト
- Robust Combinatorial Auction Protocol against False-name Bids,
Seventeenth National Conference on Artificial Intelligence
(AAAI-2000), 2000.
アブストラクト
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.
アブストラクト
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.
アブストラクト
PDF
- The Effect of Nogood Learning in Distributed Constraint Satisfaction
Proceedings of the 20th International Conference on Distributed Computing Systems
(ICDCS-2000), 2000.
アブストラクト
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.
アブストラクト
PDF (extended version)
- 架空名義表明のメカニズムデザインに対する影響：
インターネットでの集団意思決定に向けて,
コンピュータソフトウェア (ソフトウェア科学会論文誌), Vol.17,
No.5, 2000.
- 不正行為を防ぐ電子商取引メカニズム,
人工知能学会誌, Vol.15, No.5, 2000.
- 制約充足テクニックを用いた移動体通信の周波数割当問題の解法,
情報処理学会論文誌, Vol.41, No.4, 2000.
- Algorithms for Distributed Constraint Satisfaction: A Review
Autonomous Agents and Multi-Agent Systems,
Vol.3, No.2, pp.189--212, 2000.
アブストラクト
PDF
- 電子商取引における一般化 Vickrey オークションの問題点:
架空名義入札に対する頑健性
コンピュータソフトウェア(ソフトウェア科学会論文誌), Vol.17, No.2,
pp.1--9,
2000.
アブストラクト
- 複雑な局所問題に対応する分散制約充足アルゴリズム
人工知能学会誌, Vol.15, No.2, pp.348--354, 2000.
アブストラクト
- 分散制約充足におけるnogood学習の効果
人工知能学会誌, Vol.15, No.2, pp.355--361, 2000.
アブストラクト
- 多状態コミットメント探索とその評価
人工知能学会誌, Vol.14, No.5, pp. 860--869, 1999.
- 分散不完全制約充足問題
人工知能学会誌, Vol.14, No.4, pp. 636--645, 1999.
- 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.
アブストラクト
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.
アブストラクト
PDF (extended version)
- 制約充足問題の地形の解析
コンピュータソフトウェア(ソフトウェア科学会論文誌), Vol. 16, No.3,
1999.
アブストラクト
- 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.
アブストラクト
PDF
- Distributed Constraint Satisfaction Algorithm for Complex Local Problems
Proceedings of the Third International
Conference on Multiagent Systems (ICMAS-98),
pp.372--379, 1998.
アブストラクト
PDF
- 分散breakout: 反復改善型分散制約充足アルゴリズム
情報処理学会論文誌, Vol.39, No.6. pp. 1889--1897, 1998.
アブストラクト
- Solving Satisfiability Problems Using Logic Synthesis and
Reconfigurable Hardware
Proceedings of the 31st Hawaii International
Conference on System Sciences (HICSS-31)
アブストラクト
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.
アブストラクト
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.
アブストラクト
PDF
-
淘汰を用いたマルチエージェント実時間探索の高速化：
協調探索への競争の導入,
コンピュータソフトウェア(ソフトウェア科学会論文誌), Vol. 14, No.4,
1997.
アブストラクト
- CSPの新しい展開：分散／動的／不完全CSP
人工知能学会誌, Vol.12, No.3, 1997.
アブストラクト
-
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.
アブストラクト
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.
アブストラクト
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.
アブストラクト
PDF
OHP
- 柔軟で動的なエージェントの組織構造を用いた分散制約充足アルゴリズム
人工知能学会誌, Vol.11, No.6, 1996.
アブストラクト
- 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.
アブストラクト
OHP
- 分散制約充足問題における制約緩和
情報処理学会論文誌, Vol.36, No.2. pp. 275--282, 1995.
アブストラクト
- チュートリアル：分散探索とその周辺
コンピュータソフトウェア, Vol.12, No.1. pp. 33--42, 日本ソフトウェア科
学会, 1995.
アブストラクト
- Weak-commitment Search for Solving Constraint Satisfaction Problems
12th National Conference on Artificial Intelligence (AAAI-94), pp. 313--318,1994.
アブストラクト
PDF
OHP
- 弱コミットメント戦略を用いた制約充足問題の解法
情報処理学会論文誌, Vol.35, No.8. pp. 1540--1548, 1994.
アブストラクト
- Constraint Relaxation in Distributed Constraint Satisfaction Problem
5th International Conference on Tools with Artificial Intelligence, pp. 56--63,
1993.
アブストラクト
PDF
- Distributed
Constraint Satisfaction for Formalizing Distributed Problem Solving
12th International Conference on Distributed Computing Systems
(ICDCS-92), pp. 614-621, 1992.
アブストラクト
PDF
- 分散制約充足による分散協調問題解決の定式化とその解法
電子情報通信学会論文誌,Vol. J75-D-I, No.8, pp. 704-713, 1992.
アブストラクト
- 並列論理型言語上での制約充足方式の比較
情報処理学会論文誌, vol.32, No.3, pp.296-303, 1991.
アブストラクト
- ATMSを用いた分散制約充足問題の解法
情報処理学会論文誌, Vol. 31, No. 1, pp. 106-114, 1990.
アブストラクト
学会活動
E-Mail: yokoo@inf.kyushu-u.ac.jp