检索结果-内蒙古大学图书馆

Range-only SLAM with indistinguishable landmarks;a constraint programming approach

constraintS 2016年第4期21卷 557-576页

作者： Jaulin, Luc OSM IHSEV LabSTICC 2 Rue Francois Verny F-29806 Brest France

This paper deals with the simultaneous localization and mapping problem (SLAM) for a robot. The robot has to build a map of its environment while localizing itself using a partially built map. It is assumed that (i) the map is made of point landmarks, (ii) the landmarks are indistinguishable, (iii) the only exteroceptive measurements correspond to the distance between the robot and the landmarks. This paper shows that SLAM can be cast into a constraint network the variables of which being trajectories, digraphs and subsets of Then, we show how constraint propagation can be extended to deal with such generalized constraint networks. As a result, due to the redundancy of measurements of SLAM, we demonstrate that a constraint-based approach provides an efficient backtrack-free algorithm able to solve our SLAM problem in a guaranteed way.

关键词： constraint programming Interval analysis Localization Robotics Simultaneous localization and mapping

来源：评论

学校读者我要写书评

暂无评论

Time windows and constraint programming to deal with strong restriction in the due date of productive systems

引用

ANNUAL REVIEWS IN CONTROL 2014年第1期38卷 134-146页

作者： Pessoa, Marcosiris A. O. Estombelo Montesco, Richard A. Junqueira, Fabricio dos Santos Filho, Diolino Jose Miyagi, Paulo E. Univ Sao Paulo Sao Paulo Brazil Univ Fed Sergipe Sergipe Brazil

The APS (Advanced Planning and Scheduling) systems are widely used by companies;however, the traditional APS systems cannot deal with problems whose the due date is a strong restriction. The problem derives from the way companies use their scheduling heuristics. This paper addresses this problem by using the concept of time windows with the constraint programming mechanism. A procedure is shown to generate the time windows and how they can be used for the APS systems. The APS heuristic approach that uses the concepts of time windows with constraint programming is introduced to solve problems for which the due date is a strong restriction. These heuristics, with tasks allocation either at the beginning or at the end of the task time window, eliminate the need for a priority scheme. To illustrate the advantage of the proposal, some examples are presented. (C) 2014 Elsevier Ltd. All rights reserved.

关键词： constraint programming

来源：评论

学校读者我要写书评

暂无评论

Mining Time-constrained Sequential Patterns with constraint programming

引用

constraintS 2017年第4期22卷 548-570页

作者： Aoga, John O. R. Guns, Tias Schaus, Pierre Univ Catholique Louvain UCLouvain Inst Informat & Commun Technol Elect & Appl Math Louvain Belgium UAC Ecole Doctorale Sci Ingn ED SDI Calavi Benin Vrije Univ Brussel Brussels Belgium Katholieke Univ Leuven Leuven Belgium

constraint programming (CP) has proven to be an effective platform for constraint based sequence mining. Previous work has focused on standard frequent sequence mining, as well as frequent sequence mining with a maximum 'gap' between two matching events in a sequence. The main challenge in the latter is that this constraint can not be imposed independently of the omnipresent frequency constraint. Indeed, the gap constraint changes whether a subsequence is included in a sequence, and hence its frequency. In this work, we go beyond that and investigate the integration of timed events and constraining the minimum/maximum gap as well as minimum/maximum span. The latter constrains the allowed time between the first and last matching event of a pattern. We show how the three are interrelated, and what the required changes to the frequency constraint are. Key in our approach is the concept of an extension window defined by gap/span and we develop techniques to avoid scanning the sequences needlessly, as well as using a backtracking-aware data structure. Experiments demonstrate that the proposed approach outperforms both specialized and CP-based approaches in almost all cases and that the advantage increases as the minimum frequency threshold decreases. This paper is an extension of the original manuscript presented at CPAIOR'17 [5].

关键词： Data mining Sequential pattern mining constraint programming Global constraint Gap constraint Span constraint Time constraint

来源：评论

学校读者我要写书评

暂无评论

Itemset mining: A constraint programming perspective

引用

ARTIFICIAL INTELLIGENCE 2011年第12-13期175卷 1951-1983页

作者： Guns, Tias Nijssen, Siegfried De Raedt, Luc Katholieke Univ Leuven B-3001 Louvain Belgium

The field of data mining has become accustomed to specifying constraints on patterns of interest. A large number of systems and techniques has been developed for solving such constraint-based mining problems, especially for mining itemsets. The approach taken in the field of data mining contrasts with the constraint programming principles developed within the artificial intelligence community. While most data mining research focuses on algorithmic issues and aims at developing highly optimized and scalable implementations that are tailored towards specific tasks, constraint programming employs a more declarative approach. The emphasis lies on developing high-level modeling languages and general solvers that specify what the problem is, rather than outlining how a solution should be computed, yet are powerful enough to be used across a wide variety of applications and application domains. This paper contributes a declarative constraint programming approach to data mining. More specifically, we show that it is possible to employ off-the-shelf constraint programming techniques for modeling and solving a wide variety of constraint-based itemset mining tasks, such as frequent, closed, discriminative, and cost-based itemset mining. In particular, we develop a basic constraint programming model for specifying frequent itemsets and show that this model can easily be extended to realize the other settings. This contrasts with typical procedural data mining systems where the underlying procedures need to be modified in order to accommodate new types of constraint, or novel combinations thereof. Even though the performance of state-of-the-art data mining systems outperforms that of the constraint programming approach on some standard tasks, we also show that there exist problems where the constraint programming approach leads to significant performance improvements over state-of-the-art methods in data mining and as well as to new insights into the underlying data mining probl

关键词： Data mining Itemset mining constraint programming

来源：评论

学校读者我要写书评

暂无评论

Large neighborhood search with constraint programming for a vehicle routing problem with synchronization constraints

引用

COMPUTERS & OPERATIONS RESEARCH 2018年 92卷 87-97页

作者： Hojabri, Hossein Gendreau, Michel Potvin, Jean-Yves Rousseau, Louis-Martin Univ Montreal Dept Informat & Rech Operat CP 6128Succ Ctr Ville Montreal PQ H3C 3J7 Canada Ecole Polytech Montreal Dept Math & Genie Ind CP 6079Succ Ctr Ville Montreal PQ H3C 3A7 Canada Univ Montreal Ctr Interuniv Rech Reseaux Entreprise Logist & Tr CP 6128Succ Ctr Ville Montreal PQ H3C 3J7 Canada

This paper considers an extension of the vehicle routing problem with time windows, where the arrival of two vehicles at different customer locations must be synchronized. That is, one vehicle has to deliver some product to a customer, like a home theater system, while the crew on another vehicle must install it. This type of problem is often encountered in practice and is very challenging due to the interdependency among the vehicle routes, but has received little attention in the literature. A constraint programming-based adaptive large neighborhood search is proposed to solve this problem. The search abilities of the large neighborhood search and the constraint propagation abilities of constraint programming are combined to determine the feasibility of any proposed modification to the current solution. Numerical results are reported on instances derived from benchmark instances for the vehicle routing problem with time windows with up to 200 customers. (C) 2017 Elsevier Ltd. All rights reserved.

关键词： Vehicle routing Synchronization Large neighborhood search constraint programming

来源：评论

学校读者我要写书评

暂无评论

Practical minimization of pairwise-covering test configurations using constraint programming

引用

INFORMATION AND SOFTWARE TECHNOLOGY 2016年 71卷 129-146页

作者： Hervieu, Aymeric Marijan, Dusica Gotlieb, Arnaud Baudry, Benoit INRIA Rennes Bretagne Atlantique Rennes France Simula Res Lab Fornebu Norway

Context: Testing highly-configurable software systems is challenging due to a large number of test configurations that have to be carefully selected in order to reduce the testing effort as much as possible, while maintaining high software quality. Finding the smallest set of valid test configurations that ensure sufficient coverage of the system's feature interactions is thus the objective of validation engineers, especially when the execution of test configurations is costly or time-consuming. However, this problem is NP-hard in general and approximation algorithms have often been used to address it in practice. Objective: In this paper, we explore an alternative exact approach based on constraint programming that will allow engineers to increase the effectiveness of configuration testing while keeping the number of configurations as low as possible. Method: Our approach consists in using a (time-aware) minimization algorithm based on constraint programming. Given the amount of time, our solution generates a minimized set of valid test configurations that ensure coverage of all pairs of feature values (a.k.a. pairwise coverage). The approach has been implemented in a tool called PACOGEN. Results: PACOGEN was evaluated on 224 feature models in comparison with the two existing tools that are based on a greedy algorithm. For 79% of 224 feature models, PACOGEN generated up to 60% fewer test configurations than the competitor tools. We further evaluated PACOGEN in the case study of an industrial video conferencing product line with a feature model of 169 features, and found 60% fewer configurations compared with the manual approach followed by test engineers. The set of test configurations generated by PACOGEN decreased the time required by test engineers in manual test configuration by 85%, increasing the feature-pairs coverage at the same time. Conclusion: Our experimental evaluation concluded that optimal time-aware minimization of pairwise-covering test configurati

关键词： Variability testing Highly-configurable software systems constraint programming

来源：评论

学校读者我要写书评

暂无评论

Network configuration distributed production scheduling problem: A constraint programming approach

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2024年 188卷

作者： Ziadlou, Ghazal Emami, Saeed Asadi-Gangraj, Ebrahim Babol Noshiravani Univ Technol Dept Ind Engn Babol *** Iran

Nowadays, many massive factories are forced to distribute their products in several manufacturing units. This issue has caused the emergence of a novel category of problems called distributed production scheduling, which is vital in today's growing world. In this paper, the distributed production scheduling problem by considering network configuration with two echelons is addressed. The first and second echelon factories have different job configurations and have a hybrid flow shop and a flexible job shop environment, respectively. For this problem, A bi-objective mixed integer linear programming (MILP) model is presented to minimize the maximum completion time of jobs and transportation costs between the selected factories in two echelons, respectively. Consequently, the epsilon constraint method is used to deal with this bi-objective model. In addition, since distributed scheduling problems are classified as NP-Hard problems, it is very challenging to solve them for largesized instances. For this reason, a constraint programming model (CP) is also proposed. To evaluate the performance of the proposed MILP model and CP model, a total of 180 numerical instances are randomly generated in small, medium, and large sizes. The obtained results demonstrate the significant ability of the constraint programming approach in solving complex distributed scheduling problems even for large-sized instances with 30 jobs, 10 stages/operations for each job, 6 machines for each stage/operation, and 4 factories at each echelon in a reasonable time and proof that the CP model can outperform the MILP model in this problem.

关键词： Distributed scheduling Multi-factory scheduling Network configuration constraint programming Epsilon constraint method

来源：评论

学校读者我要写书评

暂无评论

Schedule control model for linear projects based on linear scheduling method and constraint programming

引用

AUTOMATION IN CONSTRUCTION 2014年 37卷 22-37页

作者： Tang, Yuanjie Liu, Rengkui Sun, Quanxin Beijing jiaotong Univ State Key Lab Rail Traff Control & Safety Beijing 100044 Peoples R China Beijing Jiaotong Univ MOE Key Lab Urban Transportat Complex Syst Theory Beijing 100044 Peoples R China

China Railway is undertaking massive construction and development projects. A reasonable and resource-leveled schedule that allows for adjustments for unforeseen circumstances during construction is critical for managing railway construction projects. Currently, most construction projects use traditional network planning methods or the Gantt schedule for project management. However, these methods have limited applicability to railway construction projects, which are typically linear. This study uses the linear scheduling method and constraint programming techniques for solving schedule control problems faced during railroad construction. The proposal comprises a schedule control model, scheduling model, and schedule control system;the scheduling model is central to the schedule control model. Characteristics such as high flexibility and practicality facilitate multi-objective optimization during scheduling and modification of the linear schedule. The proposed model and algorithm were validated by comparing results with actual data from a highway construction project and the Urumqi-Dzungaria railway construction project. (C) 2013 Elsevier B.V. All rights reserved.

关键词： China railway construction project Linear scheduling method Resource leveling Schedule control constraint programming

来源：评论

学校读者我要写书评

暂无评论

Combining Genetic Algorithms and constraint programming to Support Stress Testing of Task Deadlines

引用

ACM TRANSACTIONS ON SOFTWARE ENGINEERING AND METHODOLOGY 2015年第1期25卷 1–37页

作者： Di Alesio, Stefano Briand, Lionel C. Nejati, Shiva Gotlieb, Arnaud Simula Res Lab Software Engn Dept N-1325 Lysaker Norway Univ Luxembourg SnT Ctr L-2721 Luxembourg Luxembourg

Tasks in real-time embedded systems (RTES) are often subject to hard deadlines that constrain how quickly the system must react to external inputs. These inputs and their timing vary in a large domain depending on the environment state and can never be fully predicted prior to system execution. Therefore, approaches for stress testing must be developed to uncover possible deadline misses of tasks for different input arrival times. In this article, we describe stress-test case generation as a search problem over the space of task arrival times. Specifically, we search for worst-case scenarios maximizing deadline misses, where each scenario characterizes a test case. In order to scale our search to large industrial-size problems, we combine two state-of-the-art search strategies, namely, genetic algorithms (GA) and constraint programming (CP). Our experimental results show that, in comparison with GA and CP in isolation, GA+CP achieves nearly the same effectiveness as CP and the same efficiency and solution diversity as GA, thus combining the advantages of the two strategies. In light of these results, we conclude that a combined GA+CP approach to stress testing is more likely to scale to large and complex systems.

关键词： Experimentation Measurement Performance Reliability Real-time systems stress testing task deadline search-based software testing genetic algorithms constraint programming

来源：评论

学校读者我要写书评

暂无评论

A comparison of integer and constraint programming models for the deficiency problem

引用

COMPUTERS & OPERATIONS RESEARCH 2016年 68卷 89-96页

作者： Altinakar, Sivan Caporossi, Gilles Hertz, Alain Ecole Polytech Dept Math & Genie Ind Montreal PQ H3C 3A7 Canada HEC Serv Enseignement Methodes Quantitat Gest Montreal PQ Canada

An edge-coloring of a graph G = (V, E) is a function c that assigns an integer c(e) (called color) in {0,1,2, ... } to every edge e e E so that adjacent edges are assigned different colors. An edge-coloring is compact if the colors of the edges incident to every vertex form a set of consecutive integers. The deficiency problem is to determine the minimum number of pendant edges that must be added to a graph such that the resulting graph admits a compact edge-coloring. We propose and analyze three integer programming models and one constraint programming model for the deficiency problem. (C) 2015 Elsevier Ltd. All rights reserved.

关键词： Compact edge-colorings Integer linear programming constraint programming

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：