ABT WITH ASYNCHRONOUS REORDERING

摘要

Existing Distributed Constraint Satisfaction (DisCSP) frameworks can model problems where a)variables and/or b)constraints are distributed among agents. Asynchronous Backtracking (ABT) is the first asynchronous complete algorithm for solving DisCSPs of type a. The order on variables is well-known as an important issue for constraint satisfaction. Previous polynomial space asynchronous algorithms require for completeness a static order on their variables. We show how agents can asynchronously and concurrently propose reordering in ABT while maintaining the completeness of the algorithm with polynomial space complexity.