Escaping from Dead-Ends

When there exists no value that satisfies constraints:

Sequential backtracking: change the most recent decision

• simple control is inadequate under asynchronous changes

Asynchronous backtracking: resolve/communicate a new constraint (nogood)

• other agents try to satisfy the new constraint; thus the nogood sending agent can escape from the dead-end
• can be done concurrently and asynchronously

{

1

, 2}

бы

бы

{1, 2}

new constraint

x2

x1

x3

(nogood,

{(x1,1), (x2,2)})

Prev

Top

With Graphics