Traversing large search spaces can be done more efficiently by exploiting the dead-ends - in formal terms nogoods-discovered during search. If a previously found nogood appears again, the search process can avoid it, ...
详细信息
ISBN:
(纸本)9781614998068;9781614998051
Traversing large search spaces can be done more efficiently by exploiting the dead-ends - in formal terms nogoods-discovered during search. If a previously found nogood appears again, the search process can avoid it, saving some search effort. Storing all found nogoods may require exponential memory, which is unaffordable. However, current memories allow to store a large set of nogoods, to be maintained during the solving process. In many cases, a solution is found before memory is exhausted. In the context of distributed Constraint Satisfaction, the AWC algorithm allows to compute a solution quickly but, to guarantee completeness, it requires storing all found nogoods. Trading space per time, we develop a new iterative version of the algorithm that delays the exponential effects. We present this new version in the context of distributed SAT, where agents hold several Boolean variables. Taking advantage of existing SAT technology, this version perform calls to external MaxSAT solver. Experimentally, we confirm the benefits of the proposed approach on several benchmarks.
The Constraint Satisfaction Problem (csp) formalism is used to represent many combinatorial decision problems instances simply and efficiently. However, many such problems cannot be solved on a single, centralized com...
详细信息
The Constraint Satisfaction Problem (csp) formalism is used to represent many combinatorial decision problems instances simply and efficiently. However, many such problems cannot be solved on a single, centralized computer for various reasons (e.g., their excessive size or privacy). The distributed csp (Discsp) extends the csp model to allow such combinatorial decision problems to be modelled and handled. In this paper, we propose a complete Discsp-solving algorithm, called distributed Backtracking with Sessions (DBS), which can solve Discsp so that each agent encapsulates a whole "complex" problem with many variables and constraints. We prove that the algorithm is sound and complete, and generates promising experimental results.
A distributed constraint satisfaction problem (Discsp) is a csp in which variables and constraints are distributed among multiple automated agents. Many researchers have developed techniques for solving Discsps. They ...
详细信息
A distributed constraint satisfaction problem (Discsp) is a csp in which variables and constraints are distributed among multiple automated agents. Many researchers have developed techniques for solving Discsps. They assume for simplicity that each agent has exactly one variable. For real planning and scheduling problems, these techniques require a large number of messages passing among agents, so these problems are very difficult to solve. In this paper, we present a general distributed model for solving real-life scheduling problems. This distributed model is based on the idea of holonic systems. Furthermore, we propose some guidelines for distributing large-scale problems. Finally, we present two case studies in which two scheduling problems are distributed by using our model. (C) 2008 Elsevier Ltd. All rights reserved.
Many problems of theoretical and practical interest can be formulated as Constraint Satisfaction Problems (csps). Solving a general csp is known to be NP-complete;however, distributed models may take advantage of divi...
详细信息
Many problems of theoretical and practical interest can be formulated as Constraint Satisfaction Problems (csps). Solving a general csp is known to be NP-complete;however, distributed models may take advantage of dividing the problem into a set of simpler inter-connected sub-problems which can be more easily solved. The purpose of this paper is three-fold: first, we present a technique to distribute the constraint network by means of selection of tree structures. Thus, the csp is represented as a meta-tree csp structure that is used as a hierarchy of communication by our distributed algorithm. Then, a distributed and asynchronous search algorithm (DTS) is presented. DTS is committed to solving the meta-tree csp structure in a depth-first search tree. Finally, an intra-agent search algorithm is presented. This algorithm takes into account the Nogood_message to prune the search space. We have focused our research on the railway scheduling problem which can be distributed by tree structures. We show that our distributed algorithm outperforms well-known centralized algorithms. (C) 2008 Elsevier Ltd. All rights reserved.
暂无评论