Asynchronous Backtracking (Yokoo, et al. 92)
Characteristics:
- Each agent acts asynchronously and concurrently without any global control.
- Each agent communicates the tentative value assignment to related agents, then negotiates if constraint violations exist.
- The completeness of the algorithm is guaranteed.
Assumptions for the simplicity:
- Each agent has exactly one variable
- All constraints are binary.