跳到主要內容

臺灣博碩士論文加值系統

(23.20.20.52) 您好!臺灣時間:2022/01/24 18:17
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林偉立
論文名稱:分散式限制滿足問題之研究
論文名稱(外文):A study on distrbuted constraint satisfaction problems
指導教授:洪國寶洪國寶引用關係
學位類別:碩士
校院名稱:國立中興大學
系所名稱:資訊科學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:中文
中文關鍵詞:分散式限制滿足問題非同步回溯*演算法
相關次數:
  • 被引用被引用:3
  • 點閱點閱:1705
  • 評分評分:
  • 下載下載:255
  • 收藏至我的研究室書目清單書目收藏:0
在分散式限制滿足問題(Distributed Constraint Satisfaction Problems, DCSPs)中,非同步回溯(Asynchronous Backtracking, ABT)演算法允許鬆散偶合(loosely-coupled)的代理人執行非同步且並行的動作,來解決問題。代理人會儲存矛盾(nogoods),以避免錯誤的組合再次產生。但是我們發現到當問題的初始狀態和目標狀態距離較遠時,部分的代理人所記錄的矛盾量過多,產生矛盾激增(nogood explosion)效應。在此我們改良非同步回溯演算法,使用區域值旗標法來代替記錄矛盾,提出非同步回溯*(Asynchronous Backtracking*,ABT*)演算法。在實驗中,非同步回溯*演算法只須記錄少許的旗標即可得到和非同步回溯演算法相同的結果。使得代理人不會產生矛盾激增效應,同時也節省記憶矛盾所需的空間。

第1章 簡 介……………………………………………………….…1
1.1 研究動機………………………………………………….….…1
1.2 研究目的………………………………………………….….…2
1.3 研究貢獻………………………………………………….….…5
1.4 論文大綱………………………………………………….….…6
第2章 相關知識………………………………………………….…..7
2.1 限制滿足問題的種類及演算法………………………………..7
2.2 分散式限制滿足問題的種類及演算法……………………….12
第3章 分散式限制滿足………………………………………….….18
3.1 分散式限制滿足問題……………………………………….…18
3.2 非同步回溯演算法…………………………………………….21
第4章 非同步回溯*演算法………………………………………..25
4.1 區域值旗標法………………………………………………….25
4.2非同步回溯*演算法之範例…………………………………..34
4.3 演算法之正確性與完整性…………………………………….41
第5章 實驗……………………………………………………….….44
5.1 離散事件模擬……………………………………………….…44
5.2 實驗結果與分析……………………………………………...45
第6章 結論…………………………………………………………48
參考文獻……………………………………………………………..49

1. Armstrong, A. and E. Durfee (1997). Dynamic prioritization of complex agents in distributed constraint satisfaction problems. In Proceeding of Fifteenth International Joint Conference on Artificial Intelligence, pp. 620-625
2. Chandy, K. and L. Lamport (1985). Distributed snapshots: Determining global states of distrbu- ted systems. ACM Trans. on Computer Systems 3(1), 63-75.
3. Conry, S. E., K. Kuwabara, V. R. Lesser, and R. A. Meyer(1991). Multistage negotiation for distributed constraint satisfaction. IEEE Transactions on Systems, Man and Cybernetics 21(6). 1462-1477
4. Hirayama, K. and M. Yokoo(2000). An Approach to Over-constrained Distributed Constraint Satisfaction Problems: Distributed Hierarchical Constraint Satisfaction. Proceedings of the Fourth International Conference on Multiagent Systems (ICMAS-2000).
5. Hirayama, K. and M. Yokoo(1997). Distributed Partial constraint satisfaction problem. In Proceedings of the Third International Conference on Principles and Practice of Constraint Programming (CP-97), pp. 222-236.
6. Huhns, M. N. and D. M. Bridgeland (1991). Multiagent truth maintenance. IEEE Transactions on Systems, Man and Cybernetics 21(6), 1437-1445.
7. Minton, S., M. D. Johnston, A. B. Philips, and P. Laird(1992). Minimizing conflicts: a heuristic repair method for constraint satisfaction and scheduling problems. Artificial Intelligence 58(1-3),161-205.
8. Sycara, K. P., S. Roth, N. Sadeh, and M. S. Fox(1991). Distributed constrained heuristic search. IEEE Transactions on Systems, Man and Cybernetics 21(6), 1446-1461
9. Yokoo, M. (1993). Constraint relaxation in distributed constraint satisfaction problem. In 5th International Conference on Tools with Artificial Intelligence, pp. 56-63.
10. Yokoo, M. (1994). Weak-commitment search for solving constraint satisfaction problems. In Proceedings of the twelfth National Conference on Artificial Intelligence, pp. 313-318.
11. Yokoo, M., E. H. Durfee, T. Ishida, and K. Kuwabara(1992). Distributed constraint satisfaction for formalizing distributed problem solving. In Proceeding of the Twelfth IEEE International Conference on Distributed Computing Systems, pp. 614-621.
12. Yokoo, M. and K. Hirayama (2000). Algorithms for Distributed Constraint Satisfaction : A Review. Autonomous Agents and Multi-Agent Systems, Vol.3, No.2, pp. 189-212
13. Yokoo, M. and K. Hirayama (1996). Distributed breakout algorithm for solving distributed constraint satisfaction problem. In proceedings of the Second International Conference on Multi-Agent Systems, pp. 401-408. MIT Press.
14. Yokoo, M. and K. Hirayama (1998). Distributed constraint satisfaction algorithm for complex local problems. In Proceedings of the Third International Conference on Multi-Agent Systems. IEEE Computer Society Press.
15. Yokoo, M. T. Ishida, and K. Kuwabara (1990). Distributed constraint satisfaction for DAI problems. In 10th International Workshop on Distributed Artificial Intelligence.
16. Zhang, Y. and A. Mackworth (1991). Parallel and distributed algorithms for finite constraint satisfaction problems. In Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing, pp. 394-397.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top