Distributed Constraint Satisfaction: Foundations of Cooperation in Multi-agent SystemsWhen multiple agents are in a shared environment, there usually exist con straints among the possible actions of these agents. A distributed constraint satisfaction problem (distributed CSP) is a problem in which the goal is to find a consistent combination of actions that satisfies these inter-agent constraints. More specifically, a distributed CSP is a constraint satisfaction problem (CSP) in which multiple agents are involved. A constraint satisfaction problem is a problem in which the goal is to find a consistent assignment of values to variables. Even though the definition of a CSP is very simple, a surprisingly wide variety of artificial intelligence (AI) problems can be formalized as CSPs. Therefore, the research on CSPs has a long and distinguished history in AI (Mackworth 1992; Dechter 1992; Tsang 1993; Kumar 1992). A distributed CSP is a CSP in which variables and constraints are distributed among multiple autonomous agents. Various application problems in Multi-agent Systems (MAS) that are concerned with finding a consistent combination of agent actions can he formalized as dis tributed CSPs. Therefore, we can consid(~r distributed CSPs as a general framework for MAS, and algorithms for solving distributed CSPs as impor tant infrastructures for cooperation in MAS. This book gives an overview of the research on distributed CSPs, as well as introductory material on CSPs. In Chapter 1. we show the problem defi nition of normal, centralized CSPs and describe algorithms for solving CSPs. |
Contents
2 | 47 |
Asynchronous WeakCommitment Search | 69 |
Distributed Breakout | 81 |
Copyright | |
5 other sections not shown
Other editions - View all
Distributed Constraint Satisfaction: Foundations of Cooperation in Multi ... Makoto Yokoo Limited preview - 2012 |
Distributed Constraint Satisfaction: Foundations of Cooperation in Multi ... Makoto Yokoo No preview available - 2011 |
Common terms and phrases
3-Coloring Problems 3-SAT Problems agent x agent_view Algorithm Execution algorithms for solving application problems Artificial Intelligence asynchronous backtracking algorithm asynchronous weak-commitment search Average Number Branch and Bound changes its value Chapter check_agent_view consistency algorithms consistent value Constraint Network Constraint Satisfaction Problem constraint violations current_eval Dechter distributed breakout algorithm domain efficient empty set evaluation value Example of Algorithm find a solution formalization forward-checking Freuder graph-coloring problem GSAT higher priority agents hill-climbing algorithms importance values k-consistent maximal basins min-conflict backtracking min-conflict heuristic Multi-Agent Systems neighbors node nogood message NP-complete number of constraint number of local-minima number of restarts number of solutions number of steps number of variables optimal solution partial solution phase transition plan fragments priority value problem instances procedure randomly ratio rithm satisfy all constraints solution-reachable solving CSPs solving distributed CSPs tentative initial values tree search algorithms trials truth maintenance system variable values vars-left weak-commitment search algorithm x₁ Yokoo