The effect of temporary links in randomly generated networks of constraints

Abstract

Additional communication links between unconnected agents are used in asynchronous searching,
in order to detect obsolete information. A first way to remove obsolete information is to add new communication links, which allow a nogood owner to determine whether this nogood is obsolete or not. The second solution consists in temporarily keeping the links. A new link is maintained until a fixed number of messages have been exchanged through it. This article investigates different values for the number of messages, values that are either statically or dynamically, during the run time, determined. In the case of processing all the messages, we adapt a dynamical solution for determining the number of necessary messages for maintaining a connection. The experiments show a better efficiency in comparison with the standard Asynchronous Backtracking. In this paper we examine the effect of temporary links for the random binary constraints problem. Experiments with asynchronous search techniques are conducted on randomly generated networks of constraints. Experimental results show that the dynamical solution for the temporary links allows obtaining better results for the majority of classes of problems investigated.