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