this paper introduces a new velocity tuning approach for autonomous vehicles based on constraintprogramming (CP) over continuous domains. We use CP to compute a safe approximation of configurations where collisions w...
详细信息
ISBN:
(纸本)9783642153952
this paper introduces a new velocity tuning approach for autonomous vehicles based on constraintprogramming (CP) over continuous domains. We use CP to compute a safe approximation of configurations where collisions with obstacles may occur or technological limits may be violated. the use of CP leads to a flexible approach, facilitating the incorporation of new characteristics, e.g., constraints modeling the influence of currents. We illustrate these capabilities offered by CP in the context of UAV missions. Experimental results obtained on actual wind charts are provided.
A new interval constraint propagation algorithm;called MOnotonic Hall Consistency (Mohc), has recently been proposed. Mohc exploits monotonicity of functions to better filter variable domains. Embedded in an interval-...
详细信息
ISBN:
(纸本)9783642153952
A new interval constraint propagation algorithm;called MOnotonic Hall Consistency (Mohc), has recently been proposed. Mohc exploits monotonicity of functions to better filter variable domains. Embedded in an interval-based solver, Mohc shows very high performance for solving systems of numerical constraints (equations or inequalities) over the reals. However, the main drawback is that its revise procedure depends on two user-defined parameters. this paper reports a rigourous empirical study resulting in a variant of Mohc that avoids a manual tuning of the parameters. In particular, we propose a policy to adjust in an auto-adaptive way;during the search, the parameter sensitive to the monotonicity of the revised function.
Personalisation and context-awareness are fundamental concerns in Telephony. this paper introduces a rule-based system - 4CRULES - which enables context-sensitive call control by the means of feature configuration rul...
详细信息
ISBN:
(纸本)9783642153952
Personalisation and context-awareness are fundamental concerns in Telephony. this paper introduces a rule-based system - 4CRULES - which enables context-sensitive call control by the means of feature configuration rules. 4CRULES is interoperable with standard context services and compositional feature architectures. It has been designed to resolve feature interactions, manage conflicting preferences, and mitigate the uncertainty affecting context data. this is achieved through a constraint optimisation model that maximises adherence to user requirements and domain constraints. Experiments on a suite of instances confirm the practicality of the approach and highlight performance- and adherence-critical factors.
In this paper we propose off-line and on-line extensions to the Resource Constrained Project Scheduling Problem. the off-line extension is a variant of RCPSP with time lags and uncertain, bounded activity durations. I...
详细信息
ISBN:
(纸本)9783642153952
In this paper we propose off-line and on-line extensions to the Resource Constrained Project Scheduling Problem. the off-line extension is a variant of RCPSP with time lags and uncertain, bounded activity durations. In this context we improve over our previous work presented in [12] by proposing an incremental flow computation for finding minimal conflict sets and a set of filtering rules for cumulative constraint propagation. the on-line extension is based instead on considering an on-line semantics such as the Self-Timed Execution and take it into account in the scheduling process. Adding the on-line aspect to the problem makes the CSP framework no longer suitable. We have extended the CSP framework to take into account general search decisions and auxiliary unbound variables. An extensive set of experimental results show an improvement
the automatic tuning of the parameters of algorithms and automatic selection of algorithms has received a lot of attention recently. One possible approach is the use of machine learning techniques to learn classifiers...
详细信息
ISBN:
(纸本)9783642153952
the automatic tuning of the parameters of algorithms and automatic selection of algorithms has received a lot of attention recently. One possible approach is the use of machine learning techniques to learn classifiers which, given the characteristics of a particular problem, make a decision as to which algorithm or what parameters to use. Little research has been done into which machine learning algorithms are suitable and the impact of picking the "right" over the "wrong" technique. this paper investigates the differences in performance of several techniques on different data sets. it furthermore provides evidence that by using a meta-technique which combines several machine learning algorithms, we can avoid the problem of having to pick the "best" one and still achieve good performance.
the propositional satisfiability problem (SAT) is one of the simplest instances of constraintprogramming (CP): variables are bi-valued (can only take values 0 or 1), and all constraints are clauses (disjunctions of l...
详细信息
We introduce a parallelized version of tree-decomposition based dynamic programming for solving difficult weighted CSP instances on many cores. A tree decomposition organizes cost functions in a tree of collection of ...
详细信息
ISBN:
(纸本)9783642153952
We introduce a parallelized version of tree-decomposition based dynamic programming for solving difficult weighted CSP instances on many cores. A tree decomposition organizes cost functions in a tree of collection of functions called clusters. By processing the tree from the leaves up to the root, we solve each cluster concurrently, for each assignment of its separator, using a state-of-the-art exact sequential algorithm. the grain of parallelism obtained in tins way is directly related to the tree decomposition used. We use a dedicated strategy for building suitable decompositions. We present preliminary results of our prototype running on a cluster with hundreds of cores on different decomposable real problems. this implementation allowed us to solve the last open CELAR radio link frequency assignment instance to optimality.
In this paper we show that the power of using k-consistency techniques in a constraint problem is precisely captured by using a particular inference rule, which we call positive-hyper-resolution, on the direct Boolean...
详细信息
ISBN:
(纸本)9783642153952
In this paper we show that the power of using k-consistency techniques in a constraint problem is precisely captured by using a particular inference rule, which we call positive-hyper-resolution, on the direct Boolean encoding of the CSP instance. We also show that current clause-learning SAT-solvers will deduce any positive-hyper-resolvent of a fixed size from a given set of clauses in polynomial expected time. We combine these two results to show that, without being explicitly designed to do so, current clause-learning SAT-solvers efficiently simulate k-consistency techniques, for all values of k. We then give some experimental results to show that this feature allows clause-learning SAT-solvers to efficiently solve certain families of CSP instances which are challenging for conventional CP solvers.
In this paper we describe the design and implementation of CP-VIZ, a generic visualization platform for constraintprogramming. It provides multiple views to show the search tree, and the state of constraints and vari...
详细信息
ISBN:
(纸本)9783642153952
In this paper we describe the design and implementation of CP-VIZ, a generic visualization platform for constraintprogramming. It provides multiple views to show the search tree, and the state of constraints and variables for a postmortem analysis of a constraint program. Different to most previous visualization tools, it is system independent, using a light-weight, intermediate XML format to exchange information between solvers and the visualization tools. CP-VIZ is available under an open-source licence, and has already been interfaced to four different constraint systems.
Forbidden patterns problems are a generalisation of (finite) constraint satisfaction problems which are definable in Feder and Vardi's logic MMSNP [1]. in fact, they are examples of infinite constraint satisfactio...
详细信息
ISBN:
(纸本)9783642153952
Forbidden patterns problems are a generalisation of (finite) constraint satisfaction problems which are definable in Feder and Vardi's logic MMSNP [1]. in fact, they are examples of infinite constraint satisfaction problems with nice model theoretic properties introduced by Bodirsky [2]. In previous work [3], we introduced a normal form for these forbidden patterns problems which allowed us to provide an effective characterisation of when a problem is a finite or infinite constraint satisfaction problem. One of the central concepts of this normal form is that of a recolouring. In the presence of a recolouring from a forbidden patterns problem Omega(1) to another forbidden patterns problem Omega(2), containment of Omega(1) in Omega(2) follows. the converse does not hold in general and it remained open whether it did in the case of problems being given in our normal form. In this paper, we prove that this is indeed the case. We also show that the recolouring problem is Pi(p)(2)-harpd and in Sigma(p)(3).
暂无评论