2. Asynchronous Backtracking: The Graph Coloring Example (OK?,x1=B) BR JB (OK? X,=B X2 G B (OK?,x3=B) Send OK? messages Each agent sends OK? messages to its children 2. Asynchronous Backtracking: The Graph Coloring Example View (OK?,x1=B) B B G (OK B) (OK?,X2=G) G B Vie 1=B,x2=G,x3=B (OK?,x3=B) Update view Agent x2 and Agent x4 update their view
B, R x1 B, G, R x2 G x4 B, R x3 G x4 Send OK? messages Each agent sends OK? messages to its children (OK?, x1=B) (OK?, x1=B) (OK?, x2=G) (OK?, x3=B) B, R x1 B, R x3 G, B, R x2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x1 B, G, R x2 G x4 B, R x3 G x4 (OK?, x1=B) (OK?, x1=B) (OK?, x2=G) (OK?, x3=B) View: x1=B, x2=G, x3=B View: x1=B Agent x2 and Agent x4 Update view update their view B, R x1 B, R x3 G, B, R x2 2. Asynchronous Backtracking: The Graph Coloring Example
2. Asynchronous Backtracking: The Graph Coloring Example View X,- =B B JB Constraints Constraints X≠X3,XX2,x4≠X1 G B lew 1=B,x2=G,x3=B Agent x, and Agent x4 check their view against their constraints. and agent x, discovers a violation 2. Asynchronous Backtracking: The Graph Coloring Example B G Constraints. G B lew B x=G X=B choose> Agent x4 tries to change its assignment, which is impossible
B, R x1 B, G, R x2 G x4 B, R x3 G x4 View: x1=B, x2=G, x3=B View: x1=B Agent x2 and Agent x4 check their view against their constraints, and Agent x4 discovers a violation check view B, R x1 B, R x3 Constraints: x4≠x3, x4≠x2, x4≠x1 Constraints: x2≠x1 G, B, R x2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x1 B, G, R x2 G x4 B, R x3 G x4 View: x1=B, x2=G, x3=B Agent x4 tries to change its assignment, which is impossible B, R x1 B, R x3 Try to choose value Constraints: x4≠x3, x4≠x2, x4≠x1 G, B, R x2 2. Asynchronous Backtracking: The Graph Coloring Example
2. Asynchronous Backtracking: The Graph Coloring Example Conflicts B JB (x1B, x=G, X,=B Constraints X≠X3,XX2,x4≠X1 G B lew 1=B,x2=G,x3=B Agent x4 extracts and records the conflicts 2. Asynchronous Backtracking: The Graph Coloring Example Conflicts B G ix=B, x,G,X=B1 Constraints. G B lew =B,X2=G,X3=B (BACKTRACK {x=B,x2=G,x3=B}) s is not among the new conflicts, so nd BACKTRACK messages Agent x4 sends BACKTRACK messages
Conflicts: {x1=B, x2=G, x3=B} B, R x1 B, G, R x2 G x4 B, R x3 G x4 View: x1=B, x2=G, x3=B Agent x4 extracts and records the conflicts B, R x1 B, R x3 Extract & record conflicts Constraints: x4≠x3, x4≠x2, x4≠x1 G, B, R x2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x1 B, G, R x2 G x4 B, R x3 G x4 {} is not among the new conflicts, so Agent x4 sends BACKTRACK messages B, R x1 B, R x3 Send BACKTRACK messages (BACKTRACK, {x1=B, x2=G, x3=B}) G, B, R x2 Conflicts: {x1=B, x2=G, x3=B} View: x1=B, x2=G, x3=B Constraints: x4≠x3, x4≠x2, x4≠x1 2. Asynchronous Backtracking: The Graph Coloring Example
2. Asynchronous Backtracking: The Graph Coloring Example B JB View: G B 4( BACKTRACK {x1=B,x2=G,x=B}) Agent x3 receives the message and checks the conflict against its view 2. Asynchronous Backtracking: The Graph Coloring Example B G View: G B Constraints (BACKTRACK {x=B,x2=G,x3=B}) (x1 *B or x2*G or x3E Agent x3 records the conflict as a new constraint
B, R x1 B, G, R x2 G x4 B, R x3 G x4 B, R x1 B, R x3 match? Agent x3 receives the message and checks the conflict against its view View: {} (BACKTRACK, {x1=B, x2=G, x3=B}) G, B, R x2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x1 B, G, R x2 G x4 B, R x3 G x4 B, R x1 B, R x3 Agent x3 records the conflict as a new constraint Constraints: View: {} {x1≠B or x2≠G or x3≠B} Record new constraint G, B, R x2 (BACKTRACK, {x1=B, x2=G, x3=B}) 2. Asynchronous Backtracking: The Graph Coloring Example
2. Asynchronous Backtracking: The Graph Coloring Example B JB G B X3 Constraints {x≠Borx2≠Gorx3f Agent x, checks if it needs new links to enforce it 2. Asynchronous Backtracking: The Graph Coloring Example B G I(NEW_LINK) G B Constraints (x1 *B or x2*G or x3E NEW⊥NK」 Agent x2 sends neW link requests
B, R x1 B, G, R x2 G x4 B, R x3 G x4 B, R x1 B, R x3 Agent x3 checks if it needs new links to enforce it need link? Constraints: {x1≠B or x2≠G or x3≠B} G, B, R x2 2. Asynchronous Backtracking: The Graph Coloring Example B, R x1 B, G, R x2 G x4 B, R x3 G x4 B, R x1 B, R x3 Agent x3 NEW_LINK sends NEW_LINK requests (NEW_LINK) (NEW _LINK) Constraints: {x1≠B or x2≠G or x3≠B} G, B, R x2 2. Asynchronous Backtracking: The Graph Coloring Example