Wyniki wyszukiwania - BazTech

Ograniczanie wyników

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: distributed constraint satisfaction

Sortuj według:

Ogranicz wyniki do:

Message delay and Asynchronous DisCSP search

Zivan R., Meisels A.

Archives of Control Sciences

2006

Vol. 16, no. 2

221-242

Distributed constraint satisfaction problems (DisCSPs) are composed of agents, each holding its own variables, that are connected by constraints to variables of other agents. Due to the distributed nature of the problem, message delay can have unexpected effects on the behavior of distributed search algorithms on DisCSPs. This has been shown in experimental studies of asynchronous backtracking algorithms [1, 9]. To evaluate the impact of message delay on the run of DisCSP search algorithms, a model for distributed performance measures is presented. The model counts the number of non concurrent constraints checks, to arrive at a solution, as a non concurrent measure of distributed computation. A simpler version measures distributed computation cost by the number of non-concurrent steps of computation. An algorithm for computing these distributed measures of computational effort is described. The realization of the model for measuring performance of distributed search algorithms is a simulator which includes the cost of message delays. The performance of two asynchronous search algorithms is measured on randomly generated instances of DisCSPs with delayed messages. The Asynchronous Weak Commitment (AWC) algorithm and Asynchronous Backtracking (ABT). The intrinsic reordering process of AWC dictates a need for a more complex count of non-concurrent steps of computation. The improved counting algorithm is also needed for Dynamic ordered ABT. The delay of messages is found to have a strong negative effect on AWC and a smaller effect on dynamically ordered ABT.

A formalization of autonomous dynamic reconfiguration in distributed constraint satisfaction

Hannebauer M.

Fundamenta Informaticae

2000

Vol. 43, Nr 1-4

129-151

Several interesting practical problems in process control, planning and scheduling can be expressed and solved using the model of constraint satisfaction problems. At least four drawbacks of this classical model directly relate to areas of distribution: complexity, scalability, privacy and robustness. Hence, research on distributed constraint satis-faction problems is a new direction in the area of multi-agent systems. A typical engineering task in distributed constraint satisfaction is the design of the distribution itself. A careful look at this task reveals that the design of distribution is critical to the quality and efficiency of the problem solving process and is itself an optimization problem. In this article we formalize different variants of this configuration problem and prove them to be all at least NP-complete. For solving these problems, we present two local operators, agent melting and agent splitting, that can be combined to allow for an autonomous and dynamic reconfiguration of the organizational structure of the problem-solving agents. We prove sequences of these operators to be sufficient for solving any given configuration problem. We also briefly describe what practical steps are necessary to exploit the rather theoretical result of the proof in realistic applications.