Distributed constraint Satisfaction problems 2 Asynchronous algorithms Thomas leaute 16.412J-Cognitive Robotics april 7. 2004 Presentation outline Introduction to CSPs and DCSPs 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
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
Introduction to csps and dcsps B,R)≠,B,B G B R 1 Introduction to CSPs and DCSPs Formal definition a Constraint Satisfaction Problem(CSP)is a triple(x,D, c, where XIs a list of variables x,xo...X Dis a list of finite. discrete value domains 1,D2,., D, assigned to the variables Cus a set of constraints C,. C... C. on the variables, a constraint being a predicate D4,×…XD.→>{mve, false} a solution to the problem is an assignment to the variables that satisfies all the constraints
B, R x1 G, B, R x2 G x4 B, R x3 ≠ ≠ ≠ ≠ • Problem (CSP) is a triple (X, D, C), where – X is a list of variables x1, x2, …, xn – D is a list of finite, discrete value domains D1, D2, …, Dn assigned to the variables – C is a set of constraints C1, C2, …, Cn on the variables, a constraint being a predicate: • to the variables that satisfies all the constraints Ck : Dk1 × Dk2 × ...× Dk 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
1 Introduction to CSPs and DCSPs Many ai problems can be formulated as CsPs Example of a multi-agent scheduling problem d Activity A Activity A2 Agent A activity A3→ Activity.→ Activity A agent B activity B Activity B Shared resources R R R s K Sycara, S. Roth, N. Nadeh and M. Fox, Distributed Constrained Heuristic Search IEEE Transactions on Systems, Man, and Cybernetics, VOL 21, NO 6, Nov/Dec 1991 1 Introduction to CSPs and DCSPs Split the problem in coupled sub-problems: distribute the variables and the constraints among the agents d Activity A Agent A Activity A ACtivity A ACtivity a dB Agent B activity B Activity B Shared resources (R, s K Sycara, S. Roth, N. Nadeh and M. Fox, Distributed Constrained Heuristic Search IEEE Transactions on Systems, Man, and Cybernetics, VOL 21, NO 6, Nov/Dec 1991
• • problem*: Distributed Constrained Heuristic Search, tA1 tA2 tA3 tA4 tA5 tB1 tB2 Activity A1 Activity A2 Activity A3 Activity A4 Activity A5 Activity B1 Activity B2 Agent A Agent B R1 R2 R3 Shared resources dA1 dA2 dA5 dA4 dA3 dB1 dB2 • the variables AND the constraints among the agents Distributed Constrained Heuristic Search, tA1 tA2 tA3 tA4 tA5 tB1 tB2 Activity A1 Activity A2 Activity A3 Activity A4 Activity A5 Activity B1 Activity B2 Agent A Agent B R1 R2 R3 Shared resources dA1 dA2 dA3 dA4 dA5 dB1 dB2 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 Agent A Highest Priority 是--奮 agent B Lowest Priorit Sequential = not computationally efficient
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: tA1 Agent A Highest tA2 tA2 Priority … tB1 tB1 tB1 Agent B Lowest … Priority – Sequential => not computationally efficient
possible to choose value 2.T he Asynchronous Backtracking Algorithm Send BACKTRACK messages OK? message Wait BACKTRACK message LINK NO SOLUTION yes Termin hate Record r new constraint Send oK? NEW LINK yes Update view Wa vIew 2. Asynchronous backtracking A ssumptions 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 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
2. Asynchronous Backtracking The agent selects a value for its variable satisfying the constraints whose enforcement it is responsible for asynch Is Backtrack If there is at least one value satisfying the constraints the agent picks one and changes the assignment to its variable
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
2. Asynchronous Backtracking The agent communicates its new assignment to its children through"OK? " messages asynch Is Backtrack Send oK? messages 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 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
2. Asynchronous Backtracking as view BCDEFGH 1?34??? m少 If the agent receives an OK? message from ne of its ts, it updates its view' knowledge of the values of the other variables Update view asynch Is Backtrack A's view Send oK? messages BCDEFGH cm→ ?34??? The agent then checks its view, making sure that the new values do not violate any constraint it is responsible for Update view
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
2. Asynchronous Backtracking ible<to choose as view BCD 1?3 Send oK? messages E 4 F? G? m少 H? If all the constraints it is responsible for are still satisfied, the agent keeps waiting for messages Update view 2. Asynchronous Backtracking as view B|1 C D Send OK? messages E F ?34?? H? If the agent detects violated constraints it tries to change the value of its variable to resolve all the violations Update view
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
2. Asynchronous Backtracking Send oK? messages m少 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) Update view asynch Is Backtrack Extract record inflicts Send OK? messages If one of the conflicts is the empty set, this means any overset of i is a conflict, so that there is no solution to the dscp. the agent broadcasts a NO SOLUTION message and terminates Update view
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
