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