Symmetry Breaking During Search (SBDS) adds conditional symmetry breaking constraints (which are nogoods) dynamically upon backtracking to avoid exploring symmetrically equivalents of visited search space. the constra...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Symmetry Breaking During Search (SBDS) adds conditional symmetry breaking constraints (which are nogoods) dynamically upon backtracking to avoid exploring symmetrically equivalents of visited search space. the constraint store is proliferated with numerous such individual nogoods which are weak in constraint propagation. We introduce the notion of increasing nogoods, and give a global constraint of a sequence of increasing nogoods, incNGs. Reasoning globally with increasing nogoods allows extra prunings. We prove formally that nogoods accumulated for a given symmetry at a search node in SBDS and its variants are increasing. thus we can maintain only one increasing-nogoods global constraint for each given symmetry during search. We give a polynomial time filtering algorithm for incNGs and also an efficient incremental counterpart which is stronger than GAC on each individual nogood. We demonstrate with extensive experimentation how incNGs can increase propagation and speed up search against SBDS, its variants, SBDD and carefully tailored static methods.
In this paper, we consider a problem of management of crisis situations (incidents on nuclear or chemical plants, natural disasters...) that require remote sensing, using a set of ground and aerial robots. In this pro...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
In this paper, we consider a problem of management of crisis situations (incidents on nuclear or chemical plants, natural disasters...) that require remote sensing, using a set of ground and aerial robots. In this problem, sensed data must be transmitted in real-time to an operation center even in case of unavailability of traditional communication infrastructures. this implies that an ad hoc wireless communication network must be deployed, for instance using a fleet of UAVs acting as communication relays. From a technical point of view, we tackle a scheduling problem in which activities of mobile sensing robots and mobile relays must be synchronized both in time and space. Schedules produced must also be flexible and robust to the uncertainty about the duration of robot moves at execution time. the problem is modeled and solved using constraint-based local search, with some calls to graph algorithms that help defining good communication networks.
Determining the appropriate level of local consistency to enforce on a given instance of a constraint Satisfaction Problem (CSP) is not an easy task. However, selecting the right level may determine our ability to sol...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Determining the appropriate level of local consistency to enforce on a given instance of a constraint Satisfaction Problem (CSP) is not an easy task. However, selecting the right level may determine our ability to solve the problem. Adaptive parameterized consistency was recently proposed for binary CSPs as a strategy to dynamically select one of two local consistencies (i. e., AC and maxRPC). In this paper, we propose a similar strategy for non-binary table constraints to select between enforcing GAC and pairwise consistency. While the former strategy approximates the supports by their rank and requires that the variables domains be ordered, our technique removes those limitations. We empirically evaluate our approach on benchmark problems to establish its advantages.
this paper studies how to generalize Lagrangian relaxation to high-level optimization models, including constraint-programming and local search models. It exploits the concepts of constraint violation (typically used ...
详细信息
Siu et al. propose stream CSPs (St-CSPs) as a generalisation of finite domain CSPs to cater for constraints on infinite streams, and a solving algorithm that produces a deterministic Buchi automaton recognising the so...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Siu et al. propose stream CSPs (St-CSPs) as a generalisation of finite domain CSPs to cater for constraints on infinite streams, and a solving algorithm that produces a deterministic Buchi automaton recognising the solution language. As a novel application, we demonstrate how St-CSPs can model mathematically and generate a PID controller for driving a self-balancing tray and an inverted pendulum in real-time. We propose and give formally the correctness of an improvement to the implementation that eliminates numerous unnecessary states in the solution automaton for St-CSPs involving the first temporal operator, thereby reducing solving time. We give two St-CSP examples that can benefit from our new implementation techniques. Our approach always generates a solution automaton not bigger than, but potentially exponentially smaller than, that produced by the original implementation. Experimental results show substantial improvements.
the DCOP model has gained momentum in recent years thanks to its ability to capture problems that are naturally distributed and cannot be realistically addressed in a centralized manner. Dynamic programming based tech...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
the DCOP model has gained momentum in recent years thanks to its ability to capture problems that are naturally distributed and cannot be realistically addressed in a centralized manner. Dynamic programming based techniques have been recognized to be among the most effective techniques for building complete DCOP solvers (e.g., DPOP). Unfortunately, they also suffer from a widely recognized drawback: their messages are exponential in size. Another limitation is that most current DCOP algorithms do not actively exploit hard constraints, which are common in many real problems. this paper addresses these two limitations by introducing an algorithm, called BrC-DPOP, that exploits arc consistency and a form of consistency that applies to paths in pseudo-trees to reduce the size of the messages. Experimental results shows that BrC-DPOP uses messages that are up to one order of magnitude smaller than DPOP, and that it can scale up well, being able to solve problems that its counterpart can not.
Distributed constraint satisfaction (DisCSP) models decision problems where physically distributed agents control different decision variables, but must communicate with each other to agree on a global solution. Most ...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Distributed constraint satisfaction (DisCSP) models decision problems where physically distributed agents control different decision variables, but must communicate with each other to agree on a global solution. Most DisCSP research assumes an abstract communication layer based on a peer-to-peer wired network. However, many practical applications of distributed reasoning require to be implemented over wireless networks, which impose different communication costs, and may affect the performance of DisCSP algorithms. We study the impact of wireless network topology and routing on two leading DisCSP algorithms -ABT and AFC-ng. We introduce a new framework for experiments which models different communication layers. We show that the communication layer has a significant impact on the messaging costs, which can vary by over an order of magnitude. We also show the impact on computation time, where the equivalent non-concurrent constraint checks can vary by a factor of 6. Finally, we show that given a fixed agent ordering, changing the communications topology can increase the number of messages by up to 50%.
Because of the dynamism and uncertainty associated with many real life problems, these problems and their associated constraint Satisfaction Problem (CSP) models may change over time; thus an earlier solution found fo...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
Because of the dynamism and uncertainty associated with many real life problems, these problems and their associated constraint Satisfaction Problem (CSP) models may change over time; thus an earlier solution found for the latter may become invalid. Moreover, many approaches proposed in the literature cannot be applied when the required information about dynamism is unknown ([9], [4], [5], [11], [10], etc.). this fact has motivated us to consider dynamic situations where, in addition, only limited assumptions about changes can be made. Our analysis focuses on CSPs with ordered and discrete domains that model problems for which the order over the elements of the domain is significant. In these cases, a common type of change that problems may undergo is restrictive modifications over the bounds of the solution space. A discussion of these assumptions, their motivation and real life examples can be found in [3]. In this paper, we present an algorithm that meets the goal of combining solution stability (meaning that solutions can often be repaired using other similar values if they undergo a value loss) and robustness (meaning that solutions have a high likelihood of remaining solutions after changes). the desireability of this combination of features was noted in the survey [8]. Furthermore, in this work we have extended both concepts to apply to the type of CSP analyzed. the paper is organized as follows. Section 2 presents the new conceptions of robustness and stability. Section 3 describes our approach for finding solutions that simultaneously meet boththese criteria. In Section 4 we present some experimental results. Section 5 gives conclusions.
One approach to automated constraint modelling is to generate, and then select from, a set of candidate models. this method is used by the automated modelling system CONJURE. To select a preferred model or set of mode...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
One approach to automated constraint modelling is to generate, and then select from, a set of candidate models. this method is used by the automated modelling system CONJURE. To select a preferred model or set of models for a problem class from the candidates CONJURE produces, we use a set of training instances drawn from the target class. It is important that the training instances are discriminating. If all models solve a given instance in a trivial amount of time, or if no models solve it in the time available, then the instance is not useful for model selection. this paper addresses the task of generating small sets of discriminating training instances automatically. the instance space is determined by the parameters of the associated problem class. We develop a number of methods of finding parameter configurations that give discriminating training instances, some of them leveraging existing parameter-tuning techniques. Our experimental results confirm the success of our approach in reducing a large set of input models to a small set that we can expect to perform well for the given problem class.
From a theoretical viewpoint, the (tree-) decomposition methods offer a good approach for solving constraint Satisfaction Problems (CSPs) when their (tree)-width is small. In this case, they have often shown their pra...
详细信息
ISBN:
(纸本)9783319104287;9783319104270
From a theoretical viewpoint, the (tree-) decomposition methods offer a good approach for solving constraint Satisfaction Problems (CSPs) when their (tree)-width is small. In this case, they have often shown their practical interest. So, the literature (coming from Mathematics or AI) has concentrated its efforts on the minimization of a single parameter, the tree-width. Nevertheless, experimental studies have shown that this parameter is not always the most relevant to consider for solving CSPs. In this paper, we experimentally show that the decomposition algorithms of the state of the art produce clusters (a tree-decomposition is a tree of clusters) having several connected components. then we highlight that such clusters create a real problem for the efficiency of solving methods. To avoid this kind of problem, we consider here a new kind of graph decomposition called Bag-Connected Tree-Decomposition, which considers only tree-decompositions such that each cluster is connected. We propose a first polynomial time algorithm to find such decompositions. Finally, we show experimentally that using these bag-connected tree-decompositions improves significantly the solving of CSPs by decomposition methods.
暂无评论