27 March 2007
Ismel Brito

Many problems in Multi-Agent Systems (MAS) can be formalized as Distributed Constraint Satisfaction problems (DisCSPs). A DisCSP is a CSP in which variables, domains and constraints are distributed among agents. A solution is an assignment that satisfies all constraints. The simplest method to solve a DisCSP is to centralize all the information into a single agent and then apply a classical CSP algorithm. However, this method is often unsuitable for different reasons (i.e. costs of translation, privacy or security issues). In these cases, a distributed solving algorithm is needed. It exchanges messages among agents, until finding a solution. The reference algorithm in an asynchronous setting is ABT (asynchronous backtracking). In this seminar, we will present our extensions to ABT. In particular, we will describe ABTnot and ABThyb. ABTnot is the first asynchronous algorithm that does not add communication links between agents that do not share constraints. This property makes ABTnot suitable for DisCSPs where the connection topology must not change during resolution. In the ABT context, we identify a case of inefficiency provoked by the parallelism on agents' work. ABThyb resolves this inefficiency situation by adding some synchronization points. Both algorithms are complete, correct and terminate.