Distributed Constraint Satisfaction Problems: 2 Asynchronous Algorithms Thomas Léauté Presentation Outline 1. 2. The Asynchronous Backtracking Algorithm 3. The Asynchronous Weak-Commitment Search Algorithm 4. Conclusion and Introduction to the Task Allocation Problem M. Yokoo, E. Durfee, T. Ishida and K. Kuwabara, Distributed Constraint Satisfaction Problem: Formalization and Algorithms, IEEE Transactions on Knowledge and Data Engineering, VOL. 10, NO. 5, Sept/Oct 1998 16.412J - Cognitive Robotics April 7, 2004 Introduction to CSPs and DCSPs B, R x 1 G, B, R x 2 G x 4 B, R x 3 ≠ ≠ ≠ ≠ ? Problem (CSP) is a triple (X, D, C), where – X is a list of variables x 1 , x 2 , …, x n – D is a list of finite, discrete value domains D 1 , D 2 , …, D n assigned to the variables – C is a set of constraints C 1 , C 2 , …, C n on the variables, a constraint being a predicate: ? to the variables that satisfies all the constraints C k : D k 1 × D k 2 × ...× D k j → true, false{ } 1. Introduction to CSPs and DCSPs Formal definition: a Constraint Satisfaction A solution to the problem is an assignment 1. Introduction to CSPs and DCSPs ? ? problem*: Distributed Constrained Heuristic Search, t A1 t A2 t A3 t A4 t A5 t B1 t B2 Activity A 1 Activity A 2 Activity A 3 Activity A 4 Activity A 5 Activity B 1 Activity B 2 Agent A Agent B R 1 R 2 R 3 Shared resources d A1 d A2 d A5 d A4 d A3 d B1 d B2 ? the variables AND the constraints among the agents Distributed Constrained Heuristic Search, t A1 t A2 t A3 t A4 t A5 t B1 t B2 Activity A 1 Activity A 2 Activity A 3 Activity A 4 Activity A 5 Activity B 1 Activity B 2 Agent A Agent B R 1 R 2 R 3 Shared resources d A1 d A2 d A5 d A4 d A3 d B1 d B2 Many AI problems can be formulated as CSPs Example of a multi-agent scheduling 1. Introduction to CSPs and DCSPs * K. Sycara, S. Roth, N. Nadeh and M. Fox, IEEE Transactions on Systems, Man, and Cybernetics, VOL. 21, NO. 6, Nov/Dec 1991 Split the problem in coupled sub-problems: distribute 1. Introduction to CSPs and DCSPs * K. Sycara, S. Roth, N. Nadeh and M. Fox, IEEE Transactions on Systems, Man, and Cybernetics, VOL. 21, NO. 6, Nov/Dec 1991 1. Introduction to CSPs and DCSPs ? Centralized method: one leader agent gathers all the information from other agents and solves the problem – Prohibitive cost of collecting information – Security/Privacy reasons – Not computationally efficient 1. Introduction to CSPs and DCSPs ? Synchronous Backtracking method: t A1 Agent A Highest t A2 t A2 Priority … t B1 t B1 t B1 Agent B Lowest … Priority – Sequential => not computationally efficient Try to choose value Change value Extract & record conflicts Send OK? messages {}? Send BACKTRACK messages Wait Record new constraint need link? NEW_LINK Wait check view Update view possible impossible yes no OK? message BACKTRACK message yes no good violation! Broadcast NO_SOLUTION and terminate Terminate NO_SOLUTION match? yes no Add child NEW_LINK Send OK? 2. The Asynchronous Backtracking Algorithm 2. Asynchronous Backtracking ? Assumptions: – Given priority order on the agents – An agent must be able to send messages to any other agent – Each agent has exactly ONE single variable ? Key ideas: – Agents work concurrently (= “asynchronously”), exchanging messages to collect required information – Conflict-directed search Try to choose value The agent selects a value for its variable satisfying the constraints whose enforcement it is responsible for 2. Asynchronous Backtracking Try to choose value possible If there is at least one value satisfying the constraints, the agent picks one and changes the assignment to its variable 2. Asynchronous Backtracking Change value Try to choose value Send OK? messages possible The agent communicates its new assignment to its children through “OK?” messages 2. Asynchronous Backtracking The agent then waits for answers to his OK? messages from its children (and for other OK? messages from its parents) Try to choose value Send OK? messages possible 2. Asynchronous Backtracking Change value Change value Wait If the agent receives an OK? message from one of its parents, it updates its “view”, i.e. its knowledge of the values of the other variables Try to choose value Send OK? messages possible OK? message Update view 2. Asynchronous Backtracking B C D E F G H 1 ? 3 4 ? ? ? A’s view The agent then checks its view, making sure that the new values do not violate any constraint it is responsible for Try to choose value Send OK? messages possible view Update view 2. Asynchronous Backtracking B C D E F G H 1 ? 3 4 ? ? ? A’s view Change value Wait Change value OK? message Wait check If all the constraints it is responsible for are still Try to choose value Send OK? messages possible view Update view good OK? message 2. Asynchronous Backtracking B C D E F G H 1 ? 3 4 ? ? ? A’s view If the agent detects violated constraints, it tries to change the value of its variable to resolve all the violations Try to choose value Send OK? messages possible view Update view good violation! 2. Asynchronous Backtracking B C D E F G H 1 ? 3 4 ? ? ? A’s view satisfied, the agent keeps waiting for messages Change value Wait check Change value Wait check OK? message If the agent finds no satisfying value for its variable, it extracts and records a list of conflicts (a conflict being a partial assignment violating at least one constraint) Extract & record conflicts Try to choose value Send OK? messages possible view Update view OK? message good violation! 2. Asynchronous Backtracking If one of the conflicts is the empty set, this means any overset of {} is a conflict, so that there is no solution to the DSCP. The agent broadcasts a NO_SOLUTION message and terminates. Extract & record conflicts {}?NO_SOLUTION yes Try to choose value Send OK? messages possible view Update view good violation! 2. Asynchronous Backtracking impossible Change value Wait check Broadcast and terminate impossible Change value Wait check OK? message Otherwise, for each new conflict, the agent sends a BACKTRACK message describing the conflict to the lowest priority agent whose variable is involved in the conflict. Then it waits for this agent to send back the new assignment to its variable. Extract & record conflicts {}? yes NO_SOLUTION Try to choose value Send OK? messages possible view Update view OK? message good violation! no 2. Asynchronous Backtracking If the agent receives a BACKTRACK message, but the conflict and the agent’s view do not match, one of them must be obsolete; then it ignores the BACKTRACK Extract & record conflicts {}? yes NO_SOLUTION Try to choose value Send OK? messages possible view Update view good violation! no BACKTRACK message no 2. Asynchronous Backtracking Send BACKTRACK messages impossible Broadcast and terminate Change value Wait check Send BACKTRACK messages impossible Broadcast and terminate Change value Wait check OK? message match? Otherwise, it records the conflict as a new constraint it must enforce Extract & record conflicts {}? yes NO_SOLUTION Try to choose value Send OK? messages possible view Update view OK? message good violation! no BACKTRACK message no yes Record new constraint 2. Asynchronous Backtracking Extract & record conflicts {}? yes NO_SOLUTION Try to choose value Send OK? messages possible view Update view good violation! no BACKTRACK message no yes need link? NEW_LINK yes no It requests a new link if necessary Record new constraint 2. Asynchronous Backtracking Send BACKTRACK messages impossible Broadcast and terminate Change value Wait check match? Send BACKTRACK messages impossible Broadcast and terminate Change value Wait check OK? message match? Wait Try to choose value Extract & record conflicts Send OK? messages {}? need link? NEW_LINK view Update view possible yes no OK? message BACKTRACK message yes no good violation! NO_SOLUTION yes no Add child NEW_LINK Send OK? When an agent receives a NEW_LINK request, it adds the sender to its children list and responds through an OK? message Record new constraint 2. Asynchronous Backtracking If the agent receives a NO_SOLUTION message, it terminates Try to choose value Extract & record conflicts Send OK? messages {}? need link? NEW_LINK view Update view possible yes no yes no good violation! NO_SOLUTION yes no NO_SOLUTION Add child NEW_LINK Send OK? Record new constraint 2. Asynchronous Backtracking Change value Send BACKTRACK messages Wait Wait check impossible Broadcast and terminate match? Change value Send BACKTRACK messages Wait Wait check impossible OK? message BACKTRACK message Broadcast and terminate match? Terminate B, R x 1 G, B, R x 2 G x 4 B, R x 3 ≠ ≠ ≠ ≠ 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 G, B, R x 2 G x 4 B, R x 3 Constraints: x 4 ≠x 3 , x 4 ≠x 2 , x 4 ≠x 1 Constraints: x 2 ≠x 1 ≠ ≠ ≠ ≠ 2. Asynchronous Backtracking: The Graph Coloring Example 2. Asynchronous Backtracking: The Graph Coloring Example NAME VALUE DOMAIN VIEW CHILDREN PARENTS KNOWN CONFLICTS CONSTRAINTS TO ENFORCE B, R x 1 B, G, R x 2 G x 4 B, R x 3 B, R 1 G, B, R 2 G 4 B, R 3 Each agent chooses an assignment to its variable Try to choose value 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 Each agent sends OK? messages to its children Send OK? messages (OK?, x 1 =B) (OK?, x 1 =B) (OK?, x 2 =G) (OK?, x 3 =B) B, R 1 B, R 3 G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 (OK?, x 1 =B) (OK?, x 1 =B) (OK?, x 2 =G) (OK?, x 3 =B) View: x 1 =B, x 2 =G, x 3 =B View: x 1 =B Agent x 2 and Agent x 4 update their view Update view B, R 1 B, R 3 G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 View: x 1 =B, x 2 =G, x 3 =B View: x 1 =B Agent x 2 and Agent x 4 check their view against their constraints, and Agent x 4 discovers a violation check view B, R 1 B, R 3 Constraints: x 4 ≠x 3 , x 4 ≠x 2 , x 4 ≠x 1 Constraints: x 2 ≠x 1 G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 View: x 1 =B, x 2 =G, x 3 =B Agent x 4 tries to change its assignment, which is impossible B, R 1 B, R 3 Try to choose value Constraints: x 4 ≠x 3 , x 4 ≠x 2 , x 4 ≠x 1 G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example Conflicts: {x 1 =B, x 2 =G, x 3 =B} B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 View: x 1 =B, x 2 =G, x 3 =B Agent x 4 extracts and records the conflicts B, R 1 B, R 3 Extract & record conflicts Constraints: x 4 ≠x 3 , x 4 ≠x 2 , x 4 ≠x 1 G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 {} is not among the new conflicts, so Agent x 4 sends BACKTRACK messages B, R 1 B, R 3 Send BACKTRACK messages (BACKTRACK, {x 1 =B, x 2 =G, x 3 =B}) G, B, R 2 Conflicts: {x 1 =B, x 2 =G, x 3 =B} View: x 1 =B, x 2 =G, x 3 =B Constraints: x 4 ≠x 3 , x 4 ≠x 2 , x 4 ≠x 1 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 match? Agent x 3 receives the message and checks the conflict against its view View: {} (BACKTRACK, {x 1 =B, x 2 =G, x 3 =B}) G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 Agent x 3 records the conflict as a new constraint Constraints: View: {} {x 1 ≠B or x 2 ≠G or x 3 ≠B} Record new constraint G, B, R 2 (BACKTRACK, {x 1 =B, x 2 =G, x 3 =B}) 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 Agent x 3 checks if it needs new links to enforce it need link? Constraints: {x 1 ≠B or x 2 ≠G or x 3 ≠B} G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 Agent x 3 sends NEW_LINK requests NEW_LINK (NEW_LINK) ( N E W _ L I N K ) Constraints: {x 1 ≠B or x 2 ≠G or x 3 ≠B} G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 Agents x 1 and x 2 receive the NEW_LINK requests and add Agent x 3 to their children list Add child (NEW_LINK) ( N E W _ L I N K ) New child: Agent x 3 New child: Agent x 3 G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 Agents x 1 and x 2 send OK? to confirm new links (OK?, x 2 =G) Send OK? New child: Agent x 3 New child: Agent x 3 ( O K ? , x 1 = B ) G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 Agent x 3 receives messages and updates its view (OK?, x 2 =G) ( O K ? , x 1 = B ) Update view View: x 1 =B, x 2 =G Constraints: {x 1 ≠B or x 2 ≠G or x 3 ≠B} G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 Agent x 3 checks its view, and discovers that one constraint (the new one) is violated View: x 1 =B, x 2 =G check view Constraints: {x 1 ≠B or x 2 ≠G or x 3 ≠B} G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 Agent x 3 tries to change its value to R View: x 1 =B, x 2 =G Try to choose value Constraints: {x 1 ≠B or x 2 ≠G or x 3 ≠B} G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 There is no more violation, so Agent x 3 communicates its new value to its children Send OK? messages (OK?, x 3 =R) Constraints: {x 1 ≠B or x 2 ≠G or x 3 ≠B} G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 Agent x 4 receives the OK? message and updates its view (OK?, x 3 =R) Update view View: x 1 =B, x 2 =G, x 3 =R G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 Agent x 4 checks its view against its constraints and sees the violation has not been resolved… View: x 1 =B, x 2 =G, x 3 =R check view Constraints: x 4 ≠x 3 , x 4 ≠x 2 , x 4 ≠x 1 G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 Agent x 4 tries to change its value, but this is impossible View: x 1 =B, x 2 =G, x 3 =R Try to choose value Constraints: x 4 ≠x 3 , x 4 ≠x 2 , x 4 ≠x 1 G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 View: x 1 =B, x 2 =G, x 3 =R Agent x 4 extracts and records the conflicts Extract & record conflicts Conflicts: {x 1 =B, x 2 =G, x 3 =B} Constraints: x 4 ≠x 3 , x 4 ≠x 2 , x 4 ≠x 1 {x 1 =B, x 2 =G, x 3 =R} G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 {} is not among the new conflicts, so Agent x 4 sends BACKTRACK messages Send BACKTRACK messages (BACKTRACK, {x 1 =B, x 2 =G, x 3 =R}) View: x 1 =B, x 2 =G, x 3 =R Conflicts: {x 1 =B, x 2 =G, x 3 =B} Constraints: x 4 ≠x 3 , x 4 ≠x 2 , x 4 ≠x 1 {x 1 =B, x 2 =G, x 3 =R} G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 (BACKTRACK, {x 1 =B, x 2 =G, x 3 =R}) match? Agent x 3 receives the message and checks the conflict against its view View: x 1 =B, x 2 =G G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 (BACKTRACK, {x 1 =B, x 2 =G, x 3 =R}) View: x 1 =B, x 2 =G Agent x 3 records the conflict as a new constraint Constraints: {x 1 ≠B or x 2 ≠G or x 3 ≠B} {x 1 ≠B or x 2 ≠G or x 3 ≠R} Record new constraint G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 Agent x 3 needs no new link to enforce it need link? Constraints: {x 1 ≠B or x 2 ≠G or x 3 ≠B} {x 1 ≠B or x 2 ≠G or x 3 ≠R} G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 check view Agent x 3 checks its view, and discovers that one constraint (the new one) is violated View: x 1 =B, x 2 =G Constraints: {x 1 ≠B or x 2 ≠G or x 3 ≠B} {x 1 ≠B or x 2 ≠G or x 3 ≠R} G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 Agent x 3 tries to change its value, but no value satisfies all the constraints Try to choose value View: x 1 =B, x 2 =G Constraints: {x 1 ≠B or x 2 ≠G or x 3 ≠B} {x 1 ≠B or x 2 ≠G or x 3 ≠R} G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 Agent x 3 extracts and records new conflicts Extract & record conflicts Conflicts: View: x 1 =B, x 2 =G {x 1 =B, x 2 =G} G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 {} is not a new conflict, so Agent x 3 sends BACKTRACK messages Send BACKTRACK messages (BACKTRACK, {x 1 =B, x 2 =G}) Conflicts: {x 1 =B, x 2 =G} G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 (BACKTRACK, {x 1 =B, x 2 =G}) match? Agent x 2 receives the message and checks the conflict against its view View: x 1 =B G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 View: x 1 =B Agent x 2 records the conflict as a new constraint (BACKTRACK, {x 1 =B, x 2 =G}) Constraints: x 2 ≠x 1 {x 1 ≠B or x 2 ≠G} Record new constraint G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 View: x 1 =B Agent x 3 checks its view, and discovers that one constraint (the new one) is violated check view Constraints: x 2 ≠x 1 {x 1 ≠B or x 2 ≠G} G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 View: x 1 =B Agent x 2 tries to change its value to B, but it would violate the first constraint Try to choose value Constraints: x 2 ≠x 1 {x 1 ≠B or x 2 ≠G} G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 View: x 1 =B Agent x 2 tries to change its value to R Try to choose value Constraints: x 2 ≠x 1 {x 1 ≠B or x 2 ≠G} G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 View: x 1 =B The constraint is no longer violated, so Agent x 2 chooses value R and communicates it to its children Send OK? messages (OK?, x 2 =R) Constraints: x 2 ≠x 1 {x 1 ≠B or x 2 ≠G} G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example ( O K ? , x 2 = R ) B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 (OK?, x 2 =R) View: x 1 =B, x 2 =R, x 3 =R Agent x 3 and Agent x 4 receive the messages and update their views Update view View: x 1 =B, x 2 =R G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example ( O K ? , x 2 = R ) B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 View: x 1 =B, x 2 =R, x 3 =R View: x 1 =B, x 2 =R Agent x 3 and Agent x 4 check their view against their constraints, and no violation is discovered check view SOLVED! Constraints: {x 1 ≠B or x 2 ≠G or x 3 ≠B} {x 1 ≠B or x 2 ≠G or x 3 ≠R} Constraints: x 4 ≠x 3 , x 4 ≠x 2 , x 4 ≠x 1 G, B, R 2 2. Asynchronous Backtracking: The Graph Coloring Example Weaknesses of the Asynchronous Backtracking Algorithm ? →Use a heuristic to make better choices ? reaches a stable state within a finite number of steps, BUT it still lacks a termination procedure →Use a “Distributed Snapshot” external procedure Distributed Snapshots: Determining Global States of Distributed Systems, ACM Transactions on Computer Systems, 1985 Weaknesses of the Asynchronous Backtracking Algorithm (cont.) ? the agents →Do it beforehand? (might be difficult + need of a centralizing agent…) →Dynamic priority ordering: let the agents come encounter conflicts How to better choose the assignments? The authors prove the algorithm always K. M. Chandy and L. Lamport, Need of a judicious priority ordering among up with a judicious ordering themselves, as they Weaknesses of the Asynchronous Backtracking Algorithm (cont.) ? How to extract conflicts? →Open to all conflict extraction policies →There is a trade off between taking the time to extract minimal conflicts, and trying to speed up the algorithm by using the agent’s view as a super-conflict but wasting time by backtracking more often Try to choose value Change value Extract & record conflicts Send OK? messages {}? Send BACKTRACK IF NEW Wait Wait Send NEW_CONST messages check view Update view possible impossible yes no OK? message BACKTRACK message good violation! Broadcast NO_SOLUTION and terminate Terminate NO_SOLUTION match? yes no Record constraint and neighbor NEW_CONST Send OK? Record new constraint Promotion 3. The Asynchronous Weak- Commitment Search Algorithm 3. The Asynchronous Weak- Commitment Search Algorithm ? the choices of assignments ? every time the search needs to backtrack 3. The Asynchronous Weak- Commitment Search Algorithm (cont.) ? – by step by extending it to variables with lower priority – partial assignment because the partial assignment is abandoned as soon as the algorithm needs to backtrack – with the constraints “promotes itself” (i.e. it changes its priority value to locally become the agent with the highest priority) Use a local min-conflict heuristic to guide Judiciously change the priority ordering “Weak-Commitment” Search: A partial assignment to the variables is constructed step The group of agents “weakly commits” itself to the The priority ordering is then modified so that the agent which failed to find a value to its variable consistent 3. The Asynchronous Weak- Commitment Search Algorithm (cont.) ? – view, it will abandon the partial solution – obsolete, it will abandon the partial assignment too early and perform an unnecessary change in its priority value – records the conflicts it has already sent, and it will temporarily ignore a conflict if it has already sent it before Try to choose value Extract & record conflicts Send OK? messages {}? need link? NEW_LINK view Update view possible yes no yes no good violation! NO_SOLUTION NO_SOLUTION yes no Add child NEW_LINK Send OK? Send priority along with the assignment Send the message to the parents too Record new constraint 3. Weak-Commitment Search ATTENTION! Tricky point: Every time an agent discovers a known conflict in its However, if, due to message delays, the agent’s view is To avoid reacting to such unstable situations, the agent Change value Send BACKTRACK messages Wait Wait check impossible BACKTRACK message Broadcast and terminate Terminate match? 3. Weak-Commitment Search Try to choose value Extract & record conflicts Send OK? messages {}? need link? NEW_LINK view Update view possible yes no OK? message BACKTRACK message yes no good violation! NO_SOLUTION NO_SOLUTION yes no Add child NEW_LINK Send OK? Include the priority of the neighbors in the agent’s view Record new constraint Try to choose value Extract & record conflicts Send OK? messages {}? Send BACKTRACK IF NEW need link? NEW_LINK view Update view possible yes no yes no good violation! NO_SOLUTION NO_SOLUTION yes no Add child NEW_LINK Send OK? Record new constraint Only backtrack if the conflict has never been sent before 3. Weak-Commitment Search Change value Send BACKTRACK messages Wait Wait check impossible Broadcast and terminate Terminate match? Change value Wait Wait check impossible OK? message BACKTRA ssage Broadcast and terminate match? Try to choose value Extract & record conflicts Send OK? messages {}? need link? NEW_LINK view Update view possible yes no OK? message BACKTRACK message yes no good violation! NO_SOLUTION NO_SOLUTION yes no Add child NEW_LINK Send OK? Compute the maximum priority of all neighbors and set current priority to an even higher value (only for NEW conflicts) Communicate the new priority value to all neighbors (only for NEW conflicts) Record new constraint 3. Weak-Commitment Search Try to choose value Extract & record conflicts Send OK? messages {}? need link? NEW_LINK view Update view possible yes no yes no good violation! NO_SOLUTION NO_SOLUTION yes no Add child NEW_LINK Send OK? Record new constraint NOTE: agents must now be aware of ALL constraints involving their variable (OMISSION?!) Guide the choice by minimizing the number of constraint violations with lower priority agents 3. Weak-Commitment Search Change value Send BACKTRACK IF NEW Wait Wait check and terminate Terminate match? Promotion Wait Wait check impossible OK? message BACKTRACK message Terminate match? Try to choose value Extract & record conflicts Send OK? messages {}? view Update view possible yes no OK? message BACKTRACK message need link? NEW_LINK yes no good violation! NO_SOLUTION NO_SOLUTION yes no Add child NEW_LINK Send OK? Record new constraint 3. Weak-Commitment Search Try to choose value Extract & record conflicts Send OK? messages {}? Send view Update view possible yes no good violation! NO_SOLUTION NO_SOLUTION yes no Record new constraintAdd child NEW_LINK Send OK? Every time a new constraint is created, inform all involved agents through NEW_CONST messages 3. Weak-Commitment Search Change value Send BACKTRACK IF NEW Wait Wait check impossible Broadcast and terminate Terminate match? Promotion Change value Wait Wait NEW_CONST messages check impossible OK? message Broadcast Terminate Try to choose value Extract & record conflicts Send OK? messages {}? Send view Update view possible yes no OK? message BACKTRACK message good violation! NO_SOLUTION NO_SOLUTION yes no Record constraint and neighbor Send OK? Record new constraint Upon reception of a NEW_CONST message, record new constraint and new neighbor (if a new link is needed) Every time a new constraint is created, inform all involved agents through NEW_CONST messages 3. Weak-Commitment Search Try to choose value Extract & record conflicts Send OK? messages {}? Send view Update view possible yes no good violation! NO_SOLUTION NO_SOLUTION yes no Record constraint and neighbor Send OK? Record new constraint 3. Weak-Commitment Search Wait Wait NEW_CONST messages check impossible Broadcast Terminate NEW_CONST Change value Send BACKTRACK IF NEW Wait Wait NEW_CONST messages check impossible OK? message BACKTRACK message Broadcast and terminate Terminate match? NEW_CONST Promotion B, R x 1 G, B, R x 2 G x 4 B, R x 3 ≠ ≠ ≠ ≠ 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 G, B, R x 2 G x 4 B, R x 3 Constraints: x 4 ≠x 3 , x 4 ≠x 2 , x 4 ≠x 1 Constraints: x 2 ≠x 1 , x 2 ≠x 4 ≠ ≠ ≠ ≠ Constraints: x 1 ≠x 2 , x 1 ≠x 4 Constraints: x 3 ≠x 4 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 G, B, R x 2 G x 4 B, R x 3 Initial priority values are all set to 0. Two agents with identical priorities are ordered with respect to their index 0 0 0 0 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 B, R 1 G, B, R 2 G 4 B, R 3 Each agent chooses an assignment to its variable (at the first time step, we cannot use the heuristic because agents still have empty views) Try to choose value 0 0 0 0 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 Each agent sends OK? messages to ALL of its neighbors Send OK? messages (OK?, x 1 =(B , 0)) (OK?, x 1 =(B, 0)) ( O K ? , x 2 = ( G , 0 ) ) (OK?, x 3 =(B, 0)) B, R 1 B, R 3 0 0 0 0 G, B, R 2 (OK?, x 2 =(G, 0)) ( O K ?, x 4 = (G , 0 )) (OK?, x 4 =(G, 0)) (OK?, x 4 =(G, 0)) 3. Weak-Commitment Search: The Graph Coloring Example View: x 1 =(B, 0), x 2 =(G, 0) x 3 =(B, 0) All agents update their view Update view B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 (OK?, x 1 =(B , 0)) (OK?, x 1 =(B, 0)) ( O K ? , x 2 = ( G , 0 ) ) (OK?, x 3 =(B, 0)) B, R 1 B, R 3 0 0 0 0 G, B, R 2 (OK?, x 2 =(G, 0)) ( O K ?, x 4 = (G , 0 )) (OK?, x 4 =(G, 0)) (OK?, x 4 =(G, 0)) View: x 4 =(G, 0) View: x 2 =(G, 0), x 4 =(G, 0) View: x 1 =(B, 0), x 4 =(G, 0) 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 All agents check their view against the constraints they are responsible for, and Agent x 4 discovers a violation check view B, R 1 B, R 3 Constraints: x 4 ≠x 3 , x 4 ≠x 2 , x 4 ≠x 1 Constraints: x 2 ≠x 1 , x 2 ≠x 4 0 0 0 0 G, B, R 2 View: x 1 =(B, 0), x 2 =(G, 0) x 3 =(B, 0) View: x 1 =(B, 0), x 4 =(G, 0) Constraints: x 1 ≠x 2 , x 1 ≠x 4 Constraints: x 3 ≠x 4 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 Constraints: x 4 ≠x 3 , x 4 ≠x 2 , x 4 ≠x 1 0 0 0 0 G, B, R 2 Agent x 4 tries to change its assignment, which is impossible Try to choose value View: x 1 =(B, 0), x 2 =(G, 0) x 3 =(B, 0) 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 0 0 0 0 G, B, R 2 Agent x 4 extracts and records the conflicts Extract & record conflicts Conflicts: {x 1 =B, x 2 =G, x 3 =B} View: x 1 =(B, 0), x 2 =(G, 0) x 3 =(B, 0) 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 0 0 0 0 G, B, R 2 Conflicts: {x 1 =B, x 2 =G, x 3 =B} {} is not among the new conflicts, and no new conflict has already been sent, so Agent x 4 sends BACKTRACK messages Send BACKTRACK messages (BACKTRACK, {x 1 =B, x 2 =G, x 3 =B}) 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 1 0 0 0 G, B, R 2 (BACKTRACK, {x 1 =B, x 2 =G, x 3 =B}) Promotion Agent x 4 promotes itself, changing its priority value from 0 to 1 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 1 0 0 0 G, B, R 2 (BACKTRACK, {x 1 =B, x 2 =G, x 3 =B}) (OK?, x 4 =(G, 1)) ( O K ? , x 4 = ( G , 1 ) ) (OK?, x 4 =(G, 1)) Agent x 4 communicates its new priority value to ALL its neighbors Send OK? messages 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 1 0 0 0 G, B, R 2 (BACKTRACK, {x 1 =B, x 2 =G, x 3 =B}) (OK?, x 4 =(G, 1)) ( O K ? , x 4 = ( G , 1 ) ) (OK?, x 4 =(G, 1)) match? CONCURRENTLY, Agent x 3 receives the BACKTRACK message and checks the conflict against its view View: x 4 =(G, 0) 3. Weak-Commitment Search: The Graph Coloring Example Constraints: x 3 ≠x 4 B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 1 0 0 0 G, B, R 2 (BACKTRACK, {x 1 =B, x 2 =G, x 3 =B}) (OK?, x 4 =(G, 1)) ( O K ? , x 4 = ( G , 1 ) ) (OK?, x 4 =(G, 1)) Agent x 3 records the conflict as a new constraint it will be responsible for Record new constraint {x 1 ≠B or x 2 ≠G or x 3 ≠B} View: x 4 =(G, 0) 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 1 0 0 0 G, B, R 2 (OK?, x 4 =(G, 1)) ( O K ? , x 4 = ( G , 1 ) ) (OK?, x 4 =(G, 1)) CONCURRENTLY, all agents receive the OK? messages and update their view Update view View: x 1 =(B, 0), x 4 =(G, 1) View: x 4 =(G, 1) View: x 2 =(G, 0), x 4 =(G, 1) 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 1 0 0 0 G, B, R 2 View: x 1 =(B, 0), x 4 =(G, 1) (Only the priority changed, so no new violation is discovered) check view View: x 4 =(G, 1) View: x 2 =(G, 0), x 4 =(G, 1) 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 1 0 0 0 G, B, R 2 Send NEW_CONST messages CONCURRENTLY, Agent x 3 sends NEW_CONST messages to all agents involved in the new constraint (NEW_CONST, {x 1 ≠B or x 2 ≠G or x 3 ≠B}) ( N E W _ C O N S T , {x 1 ≠ B or x 2 ≠ G o r x 3 ≠ B } ) Constraints: x 3 ≠x 4 {x 1 ≠B or x 2 ≠G or x 3 ≠B} 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 1 0 0 0 G, B, R 2 Agents x 1 and x 2 receive NEW_CONST messages and record new constraint and new neighbor (NEW_CONST, {x 1 ≠B or x 2 ≠G or x 3 ≠B}) ( N E W _ C O N S T , {x 1 ≠ B or x 2 ≠ G o r x 3 ≠ B } ) Record constraint and neighbor New neighbor: Agent x 3 New neighbor: Agent x 3 Constraints: x 2 ≠x 1 , x 2 ≠x 4 Constraints: x 1 ≠x 2 , x 1 ≠x 4 {x 1 ≠B or x 2 ≠G or x 3 ≠R}{x 1 ≠B or x 2 ≠G or x 3 ≠R} 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 1 0 0 0 G, B, R 2 Agents x 1 and x 2 respond to the NEW_CONST through OK? messages New neighbor: Agent x 3 New neighbor: Agent x 3 Constraints: x 2 ≠x 1 , x 2 ≠x 4 Constraints: x 1 ≠x 2 , x 1 ≠x 4 {x 1 ≠B or x 2 ≠G or x 3 ≠R}{x 1 ≠B or x 2 ≠G or x 3 ≠R} Send OK? messages (OK?, x 2 =(G, 0)) ( O K ? , x 1 = ( B , 0 ) ) 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 1 0 0 0 G, B, R 2 (OK?, x 2 =(G, 0)) ( O K ? , x 1 = ( B , 0 ) ) Agent x 3 receives messages and updates its view Update view View: x 1 =(B, 0), x 2 =(G, 0) x 4 =(G, 1) 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 1 0 0 0 G, B, R 2 View: x 1 =(B, 0), x 2 =(G, 0) x 4 =(G, 1) Agent x 3 checks its view, and discovers that one constraint it is responsible for (the new one) is violated check view Constraints: x 3 ≠x 4 {x 1 ≠B or x 2 ≠G or x 3 ≠B} 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 1 0 0 0 G, B, R 2 View: x 1 =(B, 0), x 2 =(G, 0) x 4 =(G, 1) Agent x 3 tries to change its value to R, deleting all violations of constraints it is responsible for, and minimizing the number of violations of others Try to choose value Constraints: x 3 ≠x 4 {x 1 ≠B or x 2 ≠G or x 3 ≠B} 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 1 0 0 0 G, B, R 2 View: x 1 =(B, 0), x 2 =(G, 0) x 4 =(G, 1) There is no more violations of constraints it is responsible for, so Agent x 3 communicates its new value to ALL neighbors Send OK? messages (OK?, x 3 =(R, 0)) (OK?, x 3 =(R, 0)) Constraints: x 3 ≠x 4 {x 1 ≠B or x 2 ≠G or x 3 ≠B} 3. Weak-Commitment Search: The Graph Coloring Example ( O K ? , x 3 = ( R , 0 ) ) B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 1 0 0 0 G, B, R 2 (OK?, x 3 =(R, 0)) (OK?, x 3 =(R, 0)) All agents receive the OK? messages and update their view Update view View: x 1 =(B, 0), x 2 =(G, 0) x 3 =(R, 0) View: x 3 =(R, 0), x 4 =(G, 1) View: x 1 =(B, 0), x 4 =(G, 0) x 3 =(R, 0) 3. Weak-Commitment Search: The Graph Coloring Example ( O K ? , x 3 = ( R , 0 ) ) B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 1 0 0 0 G, B, R 2 View: x 1 =(B, 0), x 2 =(G, 0) x 3 =(R, 0) View: x 3 =(R, 0), x 4 =(G, 1) View: x 1 =(B, 0), x 4 =(G, 0) x 3 =(R, 0) Agent x 1 , x 2 and x 4 check their view against the constraints they are responsible for, and Agent x 2 discovers a violation check view Constraints: x 1 ≠x 2 , x 1 ≠x 4 {x 1 ≠B or x 2 ≠G or x 3 ≠R} Constraints: x 2 ≠x 1 , x 2 ≠x 4 {x 1 ≠B or x 2 ≠G or x 3 ≠R} Constraints: x 4 ≠x 3 , x 4 ≠x 2 , x 4 ≠x 1 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 1 0 0 0 G, B, R 2 View: x 1 =(B, 0), x 4 =(G, 0) x 3 =(R, 0) {x 1 ≠B or x 2 ≠G or x 3 ≠R} Agents x 2 tries to change its value to R, deleting all violations of constraints it is responsible for, and minimizing the number of violations of others Try to choose value Constraints: x 2 ≠x 1 , x 2 ≠x 4 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 1 0 0 0 G, B, R 2 View: x 1 =(B, 0), x 4 =(G, 0) x 3 =(R, 0) {x 1 ≠B or x 2 ≠G or x 3 ≠R} There is no more violations of constraints it is responsible for, so Agent x 3 communicates its new value to ALL neighbors Send OK? messages (OK?, x 2 =(R, 0)) ( O K ?, x 2 = ( R , 0 ) ) (OK?, x 2 =(R, 0)) Constraints: x 2 ≠x 1 , x 2 ≠x 4 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 1 0 0 0 G, B, R 2 (OK?, x 2 =(R, 0)) ( O K ?, x 2 = ( R , 0 ) ) (OK?, x 2 =(R, 0)) All agents receive the OK? messages and update their view Update view View: x 1 =(B, 0), x 2 =(R, 0) x 3 =(R, 0) View: x 2 =(R, 0), x 3 =(R, 0) x 4 =(G, 1) View: x 1 =(B, 0), x 2 =(R, 0) x 4 =(G, 1) 3. Weak-Commitment Search: The Graph Coloring Example B, R x 1 B, G, R x 2 G x 4 B, R x 3 G 4 B, R 1 B, R 3 1 0 0 0 G, B, R 2 Agents x 1 , x 3 and x 4 check their view against the constraints they are responsible for, and no new violation is discovered check view View: x 1 =(B, 0), x 2 =(R, 0) x 3 =(R, 0) View: x 2 =(R, 0), x 3 =(R, 0) x 4 =(G, 1) View: x 1 =(B, 0), x 2 =(R, 0) x 4 =(G, 1) Constraints: x 1 ≠x 2 , x 1 ≠x 4 Constraints: x 4 ≠x 3 , x 4 ≠x 2 , x 4 ≠x 1 {x 1 ≠B or x 2 ≠G or x 3 ≠R} Constraints: x 3 ≠x 4 {x 1 ≠B or x 2 ≠G or x 3 ≠B} SOLVED! 3. Weak-Commitment Search: The Graph Coloring Example 4. Conclusion ? Perform much better than the trivial algorithms 4. Conclusion M. Yokoo, E. Durfee, T. Ishida and K. Kuwabara, Distributed Constraint Satisfaction Problem: Formalization and Algorithms, IEEE Transactions on Knowledge and Data Engineering, VOL. 10, NO. 5, Sept/Oct 1998. Fig. 7. 4. Conclusion M. Yokoo, E. Durfee, T. Ishida and K. Kuwabara, Distributed Constraint Satisfaction Problem: Formalization and Algorithms, IEEE Transactions on Knowledge and Data Engineering, VOL. 10, NO. 5, Sept/Oct 1998. Table 1. 4. Conclusion ? algorithms Distributed and Dynamic Task Reallocation in Robot Organizations ? Single-variable agents => Task Allocation Problem References ? Distributed Constraint Satisfaction Problem: Formalization and Algorithms, IEEE Transactions on Knowledge and Data Engineering, VOL. 10, NO. 5, Sept/Oct 1998 ? Distributed Constrained Heuristic Search, IEEE Transactions on Systems, Man, and Cybernetics, VOL. 21, NO. 6, Nov/Dec 1991 ? Distributed Snapshots: Determining Global States of Distributed Systems, ACM Transactions on Computer Systems, 1985 ? Distributed and Dynamic Task Reallocation in Robot Organizations Perform much better than the trivial W.-M. Shen and B. Salemi, M. Yokoo, E. Durfee, T. Ishida and K. Kuwabara, K. Sycara, S. Roth, N. Nadeh and M. Fox, K. M. Chandy and L. Lamport, W.-M. Shen and B. Salemi,