We have started a systematic study of global constraints on set and multiset variables. We consider here disjoint, partition, and intersection constraints in conjunction with cardinality constraints. these global cons...
详细信息
ISBN:
(纸本)3540232419
We have started a systematic study of global constraints on set and multiset variables. We consider here disjoint, partition, and intersection constraints in conjunction with cardinality constraints. these global constraints fall into one of three classes. In the first class, we show that we can decompose the constraint without hindering bound consistency. No new algorithms therefore need be developed for such constraints. In the second class, we show that decomposition hinders bound consistency but we can present efficient polynomial algorithms for enforcing bound consistency. Many of these algorithms exploit a dual viewpoint, and call upon existing global constraints for finite-domain variables like the global cardinality constraint. In the third class, we show that enforcing bound consistency is NP-hard. We have little choice therefore but to enforce a lesser level of local consistency when the size of such constraints grows.
Many propagation and search algorithms have been developed for constraint satisfaction problems (CSPs). In a standard CSP all variables are existentially quantified. the CSP formalism can be extended to allow universa...
详细信息
ISBN:
(纸本)3540232419
Many propagation and search algorithms have been developed for constraint satisfaction problems (CSPs). In a standard CSP all variables are existentially quantified. the CSP formalism can be extended to allow universally quantified variables, in which case the complexity of the basic reasoning tasks rises from NP-complete to PSPACE-complete. Such problems have, so far, been studied mainly in the context of quantified Boolean formulae. Little work has been done on problems with discrete non-Boolean domains. We attempt to fill this gap by extending propagation and search algorithms from standard CSPs to the quantified case. We also show how the notion of value interchangeability can be exploited to break symmetries and speed up search by orders of magnitude. Finally, we test experimentally the algorithms and methods proposed.
We study here a CSP decomposition method introduced in [9] and called Cyclic-Clustering. While [9] only presents the principles of the method, this paper explains how this method can be made operational by exploiting ...
详细信息
ISBN:
(纸本)076952236X
We study here a CSP decomposition method introduced in [9] and called Cyclic-Clustering. While [9] only presents the principles of the method, this paper explains how this method can be made operational by exploiting good properties of triangulated induced subgraphs. After we give formal results which show that Cyclic-Clustering proposes a time-space trade-off wrt. theoretical complexities. Finally, we present some preliminary experiments which show that Cyclic-Clustering may be efficient in practice.
Controlling an autonomous camera in three-dimensional (3D) virtual environments is a difficult task which manifests itself in many interactive computer graphics applications. Computer games [2] and guided exploration ...
ISBN:
(纸本)3540232419
Controlling an autonomous camera in three-dimensional (3D) virtual environments is a difficult task which manifests itself in many interactive computer graphics applications. Computer games [2] and guided exploration [1] are examples where autonomous cameras are required to provide suitable views of the scene as the user interacts withthe environment. the camera system is expected to consistently provide a suitable view of the target object(s) for the user. the camera control problem is often over-constrained. We successfully applied local search strategies to generate solutions to the problem in real-time. A cost is associated with each constraint (current constraints are: distance, height, occlusion, frame coherence rotation, and frame coherence distance), making some constraints more likely to be satisfied than others. A 3D game engine was developed to evaluate the cameras real-time performance. Preliminary comparisons with related works indicate significant performance benefits from the use of local search.
Answer Set programming has become a host for expressing knowledge representation problems, which reinforces the interest in efficient methods for computing answer sets of a logic program. While for propositional progr...
详细信息
the constraint satisfaction problem (CSP) can be formulated as the problem of deciding, given a pair (A, B) of relational structures, whether or not there is a homomorphism from A to B. Although the CSP is in general ...
详细信息
ISBN:
(纸本)3540232419
the constraint satisfaction problem (CSP) can be formulated as the problem of deciding, given a pair (A, B) of relational structures, whether or not there is a homomorphism from A to B. Although the CSP is in general intractable, it may be restricted by requiring the "target structure" B to be fixed;denote this restriction by CSP(B). In recent years, much effort has been directed towards classifying the complexity of all problems CSP(B). the acquisition of CSP(B) tractability results has generally proceeded by isolating a class of relational structures B believed to be tractable, and then demonstrating a polynomial-time algorithm for the class. In this paper, we introduce a new approach to obtaining CSP(B) tractability results: instead of starting with a class of structures, we start with an algorithm called look-ahead arc consistency, and give an algebraic characterization of the structures solvable by our algorithm. this characterization is used both to identify new tractable structures and to give new proofs of known tractable structures.
In CP literature combinatorial design problems such as sport scheduling, Steiner systems, error-correcting codes and more, are typically solved using Finite Domain (FD) models despite often being more naturally expres...
详细信息
ISBN:
(纸本)3540232419
In CP literature combinatorial design problems such as sport scheduling, Steiner systems, error-correcting codes and more, are typically solved using Finite Domain (FD) models despite often being more naturally expressed as Finite Set (FS) models. Existing FS solvers have difficulty with such problems as they do not make strong use of the ubiquitous set cardinality information. We investigate a new approach to strengthen the propagation of FS constraints in a tractable way: extending the domain representation to more closely approximate the true domain of a set variable. We show how this approach allows us to reach a stronger level of consistency, compared to standard FS solvers, for arbitrary constraints as well as providing a mechanism for implementing certain symmetry breaking constraints. By experiments on Steiner Systems and error correcting codes, we demonstrate that our approach is not only an improvement over standard FS solvers but also an improvement on recently published results using FD 0/1 matrix models as well.
Great progress has been made on DPLL based SAT solvers operating on CNF encoded SAT theories. However, for most problems CNF is not a very natural representation. Typically these problems are more easily expressed usi...
详细信息
ISBN:
(纸本)3540232419
Great progress has been made on DPLL based SAT solvers operating on CNF encoded SAT theories. However, for most problems CNF is not a very natural representation. Typically these problems are more easily expressed using unrestricted propositional formulae and hence must be converted to CNF before modem SAT solvers can be applied. this conversion entails a considerable loss of information about the problem's structure. In this work we demonstrate that conversion to CNF is both unnecessary and undesirable. In particular, we demonstrate that a SAT solver which operates directly on a propositional formula can achieve the same efficiency as a highly optimized modern CNF solver. Furthermore, since the original formula remains intact, such a solver can exploit the original problem structure to improve over CNF solvers. We present empirical evidence showing that exploiting the original structure can yield considerable benefits.
this work shows the implementation of ntcc-lman [1], a framework for ntcc [2], a non deterministic timed concurrent constraint process calculus. this calculus provides a formal model in which concepts proper to roboti...
ISBN:
(纸本)3540232419
this work shows the implementation of ntcc-lman [1], a framework for ntcc [2], a non deterministic timed concurrent constraint process calculus. this calculus provides a formal model in which concepts proper to robotic control can be conveniently represented. the ntcc-lman framework includes a ntcc based kernel language, a compiler, a constraint system, a formal abstract machine based on ntcc reduction rules and a virtual machine. We show how the framework can be used to program typical robotic tasks to control LEGO robots in real time using timed ccp technology. To our knowledge, this is the first timed ccp framework for programming robotic devices.
Until recently, planning research focused on solving problems of feasibility using models consisting of causal rules. Propositional logic is sufficient for representing such rules. However, many planning problems also...
ISBN:
(纸本)3540232419
Until recently, planning research focused on solving problems of feasibility using models consisting of causal rules. Propositional logic is sufficient for representing such rules. However, many planning problems also contain time and resource constraints. It is often impractical to represent such planning domains with propositions. Large time horizons and possible resource states lead to enormous domain representations. Propositional representations can often obscure information that is useful during search. Finally, propositional representations can make it difficult for human modelers to express the domain in a convenient and natural way. the constraint-based Planning paradigm employs constraints as the building blocks of both planning domain rules and plans. the building blocks of such plans are intervals of time over which some state holds or an action occurs in a plan. Each interval is represented by variables describing its properties (e.g. start, end, duration). At each step of the planning process, a mapping is maintained between the plan under construction and an underlying constraint network. As actions are added to the plan, constraints are posted on variables representing the action, its preconditions and its effects (a generalization of causal links). the domain rules contain directives for adding new intervals and for posting constraints over the variables on those intervals as plans are modified. Employing constraints in rules makes it easy to represent disjunctive preconditions, conditional effects, and mutual exclusions directly. the semantics of this mapping ensure that logical inference (e.g. propagation) on the constraint network can be used directly by search engines operating on plans.
暂无评论