In Distributed CSPs (DisCSPs), agents may want to keep parts of their problem secret but accept to cooperate by exchanging proposals. Asynchronism in solving DisCSPs [1] increases flexibility, parallelism, and robustness. Enumerative algorithms apply for discrete problems with small domains. Our goal is to develop asynchronous algorithms that can deal with numeric constraints. Centralized techniques for CSPs with continuous domains interleave (dichotomous) splitting of the search space with forms of bound consistency. Consecutive numerical values are aggregated into intervals. As a first step towards our goal, we have developed Asynchronous Aggregation Search (AAS) [1] , allowing agents to asynchronously propose subspaces of their search space. Agents propose splits of domains that ensure the feasibility of their subproblem. Then we have proposed DMAC, allowing to maintain bound (or arc) consistency in AAS [1] . Dichotomous splits are generally only partially sound splits since the agent proposing them does not necessarily have its constraints fully satisfied by them. The simplest and most widely used strategy for partially sound splits is the dichotomous one, but the technique we propose next can similarly deal with more complex splitting strategies. We propose a framework called Replicas-based DisCSP (RDisCSP) where each initial agent is represented by a set of abstract agents. Except for the last positioned abstract agent of an initial agent A j (called checking replica), its other abstract agents in a RDisCSP do not intend to satisfy the whole problem of A j , but a relaxation of it or even a totally feasible constraint. For achieving Asynchronous Dichotomous search Maintaining Bound-consistency (ADMB) using DMAC over RDisCSPs, each abstract agent behaves according to complete splitting operators. They propose search spaces that are half of the size of their allowed search space (within a relative tolerance k). Each initial agent A j has constraints over the external variables V j and any x i , x i ∈V j can take values from a domain D i . With ADMB, the upper-bound of the number of abstract agents for A j required to reach solutions with resolution ε is xi∈Vj log 2/(1+k) (|D i |/ε). ADMB can be used for solving RDisCSPs with numerical constraints. All abstract agents of any initial agent can be represented in ADMB by the same physical agent and all messages sent to them are then sent in only one message. The structures of abstract agents required for maintaining consistency at different splitting levels are shared in the physical agent. The consistency nogoods for a level are generated only once for an initial agent (by its checking replica). The checking replica has to ensure that the subproblem it proposes is feasible with the resolution ε. ADMB is the first asynchronous algorithm for dealing with private constraints over mixed and continuous domains.
The Asynchronous Aggregation Search (AAS) family of protocols actually extends ABT to the case where the same variable can be instantiated by several agents (e.g., at different levels of abstraction REF ).
Asynchronous search for numeric DisCSPs
In Proc. of CP’2001
Computer Science