Distributed constraint satisfaction : foundations of cooperation in multi-agent systems
著者
書誌事項
Distributed constraint satisfaction : foundations of cooperation in multi-agent systems
（Springer series on agent technology / editors, T. Ishida, N. Jennings, K. Sycara）
Tokyo : Springer, c2001
大学図書館所蔵 件 / 全12件
-
該当する所蔵館はありません
- すべての絞り込み条件を解除する
注記
Includes bibliographical references (p. [137]-141) and index
"With 82 figures and 22 tables"--T.p.
内容説明・目次
内容説明
Distributed Constraint Satisfaction gives an overview of Constraint Satisfaction Problems (CSPs), adapts related search algorithms and consistency algorithms for applications to multi-agent systems, and consolidates recent research devoted to cooperation in such systems. The techniques introduced are applied to various problems in multi-agent systems. Among the new approaches is a hybrid-type algorithm for weak-commitment search combining backtracking and iterative improvement. Also, an extension of the basic CSP formalization called "Partial CSP" is introduced in order to handle over-constrained CSPs.
目次
1. Constraint Satisfaction Problem.- 1.1 Introduction.- 1.2 Problem Definition.- 1.3 Algorithms for Solving CSPs.- 1.3.1 Backtracking.- 1.3.2 Iterative Improvement.- 1.3.3 Consistency Algorithms.- 1.4 Hybrid-Type Algorithm of Backtracking and Iterative Improvement.- 1.4.1 Weak-Commitment Search Algorithm.- 1.4.2 Example of Algorithm Execution.- 1.4.3 Evaluations.- 1.4.4 Algorithm Complexity.- 1.5 Analyzing Landscape of CSPs.- 1.5.1 Introduction.- 1.5.2 Hill-Climbing Algorithm.- 1.5.3 Analyzing State-Space.- 1.5.4 Discussions.- 1.6 Partial Constraint Satisfaction Problem.- 1.6.1 Introduction.- 1.6.2 Formalization.- 1.6.3 Algorithms.- 1.7 Summary.- 2. Distributed Constraint Satisfaction Problem.- 2.1 Introduction.- 2.2 Problem Formalization.- 2.3 Application Problems.- 2.3.1 Recognition Problem.- 2.3.2 Allocation Problem.- 2.3.3 Multi-agent Truth Maintenance.- 2.3.4 Time-Tabling/Scheduling Tasks.- 2.4 Classification of Algorithms for Solving Distributed CSPs.- 2.5 Summary.- 3. Asynchronous Backtracking.- 3.1 Introduction.- 3.2 Assumptions.- 3.3 Simple Algorithms.- 3.3.1 Centralized Method.- 3.3.2 Synchronous Backtracking.- 3.4 Asynchronous Backtracking Algorithm.- 3.4.1 Overview.- 3.4.2 Characteristics of the Asynchronous Backtracking Algorithm.- 3.4.3 Example of Algorithm Execution.- 3.4.4 Algorithm Soundness and Completeness.- 3.5 Evaluations.- 3.6 Summary.- 4. Asynchronous Weak-Commitment Search.- 4.1 Introduction.- 4.2 Basic Ideas.- 4.3 Details of Algorithm.- 4.4 Example of Algorithm Execution.- 4.5 Algorithm Completeness.- 4.6 Evaluations.- 4.7 Summary.- 5. Distributed Breakout.- 5.1 Introduction.- 5.2 Breakout Algorithm.- 5.3 Basic Ideas.- 5.4 Details of Algorithm.- 5.5 Example of Algorithm Execution.- 5.6 Evaluations.- 5.7 Discussions.- 5.8 Summary.- 6. Distributed Consistency Algorithm.- 6.1 Introduction.- 6.2 Overview of Distributed ATMS.- 6.2.1 ATMS.- 6.2.2 Distributed ATMS.- 6.3 Distributed Consistency Algorithm Using Distributed ATMS..- 6.4 Example of Algorithm Execution.- 6.5 Evaluations.- 6.6 Summary.- 7. Handling Multiple Local Variables.- 7.1 Introduction.- 7.2 Agent-Prioritization Approach.- 7.3 Asynchronous Weak-Commitment Search with Multiple Local Variables.- 7.3.1 Basic Ideas.- 7.3.2 Details of Algorithm.- 7.3.3 Example of Algorithm Execution.- 7.4 Evaluations.- 7.5 Summary.- 8. Handling Over-Constrained Situations.- 8.1 Introduction.- 8.2 Problem Formalization.- 8.3 Distributed Maximal CSPs.- 8.3.1 Problem Formalization.- 8.3.2 Algorithms.- 8.3.3 Evaluations.- 8.4 Distributed Hierarchical CSPs.- 8.4.1 Problem Formalization.- 8.4.2 Asynchronous Incremental Relaxation.- 8.4.3 Example of Algorithm Execution.- 8.4.4 Algorithm Completeness.- 8.4.5 Evaluations.- 8.5 Summary.- 9. Summary and Future Issues.
「Nielsen BookData」 より
