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

DEPS: a model- and property-based language for system synthesis problems

SOFTWARE AND SYSTEMS MODELING 2024年第4期23卷 973-1002页

作者： Yvars, Pierre-Alain Zimmer, Laurent Inst Super Mecan Paris ISAE Supmeca QUARTZ EA 7393 St Ouen France Dassault Aviat Direct Prospect St Cloud France

DEPS (design problem specification) is a new modeling language designed to pose and solve system design problems. DEPS addresses problems of sizing, configuration, resource allocation and of architecture generation for systems. Unlike system modeling languages, which are dedicated to the representation of a defined system for evaluation or analysis, we propose a problem modeling language for representing the design problem with a view to its automatic resolution. Compared with other declarative problem modeling languages, DEPS is a declarative structured and property-based language that combines structural modeling features specific to object-oriented languages with problem specification features from constraint programming. The mathematical nature of the problems is described by formal properties encapsulated in models organized according to the architecture of the studied system. The main features of the language are presented in details and are illustrated with examples in different domains. An integrated modeling and solving environment called DEPS Studio allows the designer to express its models in DEPS, to compile the models and to compute automatically the solutions. The validation of the approach is done through two case studies. Finally, we will conclude with the studies and developments in progress which will be integrated into the next version of DEPS Studio.

关键词： Model-based system synthesis Specification Design problem modeling language Problem solving constraint programming

来源：评论

学校读者我要写书评

暂无评论

Heuristic for Railway Crew Scheduling With Connectivity of Schedules

引用

TRANSPORTATION RESEARCH RECORD 2024年第8期2678卷 873-887页

作者： Bansal, Akshat Anoop, Kezhe Perumpadappu Rangaraj, Narayan Indian Inst Technol Bombay IITB Mumbai Maharashtra India

This paper addresses the crew scheduling for long-distance passenger train services. A heuristic with bin packing features is developed to generate repeatable crew schedules that satisfy the operational and crew allocation rules. By ensuring the connectivity of crew duties that can be repeated over periodic train schedules, a better estimate of the crew requirement in a region is also obtained. Further, the heuristic ensures a fair division of the total workload and creates long duty cycles, which also makes the process of cyclic rostering easier. The paper also presents an exact approach for crew scheduling using a combination of constraint programming and set covering formulations. The exact approach is not computationally viable for practical scale problem instances, but the heuristic generates good quality solutions (often very close to optimal) even on large data sets. We illustrate the approach on data from the Mumbai Division in Indian Railways and the computational results show that there is potential to reduce the total number of crew duties in the region by around 12%. The heuristic approach provides an efficient way to generate improved crew schedules every time there is a change in the train timetable.

关键词： railway crew scheduling Indian railways constraint programming bin packing Heuristic algorithm

来源：评论

学校读者我要写书评

暂无评论

Two-stage stochastic/robust scheduling based on permutable operation groups

引用

ANNALS OF OPERATIONS RESEARCH 2024年第1-3期332卷 645-687页

作者： Riviere, Louis Artigues, Christian Fargier, Helene Univ Toulouse IRIT CNRS UPS Toulouse France Univ Toulouse LAAS CNRS CNRS UPS Toulouse France Univ Toulouse Artificial & Nat Intelligence Toulouse Inst Toulouse France

In this paper we study the performance of a two-stage approach to scheduling under uncertainty making use of sequences of groups of permutable operations. Given a sample set of uncertainty realization scenarios, the goal is to compute a sequence of groups of permutable operations representing a partial scheduling decision in the first-stage, that yields the best possible score in the second-stage, when, for a specific scenario, a full operation sequence is obtained via a second-stage decision policy. This approach is described for a single-machine problem and the jobshop problem with stochastic and robust optimization, as well as several commonly studied objectives. We propose new constraint programming models as well as a genetic algorithm meta-heuristic to compute such two-stage solutions. We also investigate a warm-start scheme to work around the difficult search space of sequences of permutable operations. Experiments are carried out to characterize when this two-stage approach yields better results. We also compare the introduced methods with existing ones. Theoretical extensions of the known methods are also described and evaluated.

关键词： Stochastic and robust 2-stage scheduling Permutable operation groups constraint programming

来源：评论

学校读者我要写书评

暂无评论

Learning cost action planning models with perfect precision via constraint propagation

引用

INFORMATION SCIENCES 2023年第1期628卷 148-176页

作者： Garrido, Antonio Univ Politecn Valencia Valencian Res Inst Artificial Intelligence VRAIN Valencia Spain

Data-driven AI is rapidly gaining importance. In the context of AI planning, a constraint programming formulation for learning action models in a data-driven fashion is proposed. Data comprises plan observations, which are automatically transformed into a set of planning constraints which need to be satisfied. The formulation captures the essence of the action model and unifies functionalities that are individually supported by other learning approaches, such as costs, noise/uncertainty on actions, information on intermediate state observations and mutex *** is a key concern in data-driven learning, but existing approaches usually learn action models that can be imprecise, where imprecision here is an error indicator of learning something incorrect. On the contrary, the proposed approach guarantees reliability in terms of perfect precision by using constraint propagation. This means that what is learned is 100% correct (i.e., error-free), not only for the initial observations, but also for future observations. To our knowledge, this is a novelty in action model learning literature. Although perfect precision might potentially limit the amount of learned information, the exhaustive experiments over 20 planning domains show that such amount is comparable, and even better, to ARMS and FAMA, two state-of-the-art benchmarks in action model learning.

关键词： Learning Cost action model Classical planning constraint programming Reliability Precision

来源：评论

学校读者我要写书评

暂无评论

Automatic Demirci-Selcuk Meet-In-The-Middle Attack On SIMON

引用

COMPUTER JOURNAL 2023年第12期66卷 3052-3068页

作者： Lv, Yin Shi, Danping Guo, Yi Chen, Qiu Hu, Lei Guo, Zihui Chinese Acad Sci Inst Informat Engn State Key Lab Informat Secur Beijing 100093 Peoples R China Univ Chinese Acad Sci Sch Cyber Secur Beijing 100093 Peoples R China Chinese Acad Sci Inst Informat Engn Beijing 100093 Peoples R China

Demirci-Selcuk meet-in-the-middle (DS-MITM) attack is an effective method for cryptanalysis. As far as we know, the published automatic results of DS-MITM attack are all for byte-oriented ciphers. In this article, we first propose the automatic analysis method of DS-MITM attack for bit-oriented ciphers based on constraint programming, which is integrated with key-bridging technique. Based on the automatic modeling method, we propose the first result of DS-MITM attack on SIMON, which is a family of lightweight block ciphers proposed by the National Security Agency (NSA) in 2013.

关键词： Demirci-Selcuk meet-in-the-middle attack SIMON constraint programming key-bridging technique

来源：评论

学校读者我要写书评

暂无评论

An efficient relax-and-solve method for the multi-mode resource constrained project scheduling problem

引用

ANNALS OF OPERATIONS RESEARCH 2024年第1期338卷 41-68页

作者： Etminaniesfahani, Alireza Gu, Hanyu Naeni, Leila Moslemi Salehipour, Amir Univ Technol Sydney Sch Math & Phys Sci Broadway Sydney NSW 2007 Australia Univ Technol Sydney Sch Built Environm Broadway Sydney NSW 2007 Australia Univ Sydney Business Sch Darlington NSW 2006 Australia

The multi-mode resource constrained project scheduling problem (MRCPSP) is an NP-hard optimisation problem involving scheduling tasks under resource and precedence constraints, while there are several modes for executing each task. In this paper, we propose a novel matheuristic based on relax-and-solve (R &S) algorithm to solve MRCPSP. In addition, a mathematical programming model, which is the generalisation of the multi-dimensional knapsack problem is developed. That model conducts the mode selection process for the purpose of generating an initial feasible solution. We evaluate the performance of the proposed algorithm by solving benchmark instances that are widely used in the literature. The results demonstrate that the proposed R &S algorithm outperforms the state-of-the-art methods for solving the MRCPSP.

关键词： Relax-and-solve Multi-mode resource constrained project scheduling problem Matheuristic Rolling time window constraint programming

来源：评论

学校读者我要写书评

暂无评论

Tumato 2.0-a constraint-based planning approach for safe and robust robot behavior

引用

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2024年 1-27页

作者： Vermaelen, Jan Holvoet, Tom Katholieke Univ Leuven DistriNet B-3001 Leuven Belgium

Ensuring the safe and effective operation of autonomous systems is a complex undertaking that inherently relies on underlying decision-making processes. To rigorously analyze these processes, formal verification methods, such as model checking, offer a valuable means. However, the non-deterministic nature of realistic environments makes these approaches challenging and often impractical. This work explores the capabilities of a constraint-based planning approach, Tumato, in generating policies that guide the system to predefined goals while adhering to safety constraints. constraint-based planning approaches are inherently able to provide guarantees of soundness and completeness. Our primary contribution lies in extending Tumato's capabilities to accommodate non-deterministic outcomes of actions, enhancing the robustness of the behavior. Originally designed to accommodate only deterministic outcomes, actions can now be modeled to include alternative outcomes to address contingencies explicitly. The adapted solver generates policies that enable reaching the goals in a safe manner, even when such alternative outcomes of actions occur. Additionally, we introduce a purely declarative manner for specifying safety in Tumato to further enhance its expressiveness as well as to reduce the susceptibility to errors during specification. The incorporation of cost or duration values to actions enables the solver to restore safety in the most preferred manner when necessary. Finally, we highlight the overlap of Tumato's safety-related capabilities with a systems-theoretic approach, STPA (Systems-Theoretic Process Analysis). The aim is to emphasize the ability to avoid unsafe control actions without their explicit identification, contributing to a more comprehensive and holistic understanding of safety.

关键词： Autonomous systems Behavior specification Safe and robust planning constraint programming Tumato

来源：评论

学校读者我要写书评

暂无评论

Large neighborhood search for an aeronautical assembly line time-constrained scheduling problem with multiple modes and a resource leveling objective

引用

ANNALS OF OPERATIONS RESEARCH 2024年第1期338卷 13-40页

作者： Sanchidrian, Tamara Borreguero Portoleau, Tom Artigues, Christian Sanchez, Alvaro Garcia Mier, Miguel Ortega Lopez, Pierre Airbus Paseo John Lennon S-N Getafe 28906 Spain Univ Toulouse CNRS LAAS 7 Ave Colonel Roche F-31400 Toulouse France Univ Politecn Madrid Ind Engn & Logist Res Grp ETSII Jose Gutierrez Abascal 2 Madrid 28006 Spain

This paper deals with a scheduling problem arising at the tactical decision level in aeronautical assembly line. It has the structure of a challenging multi-mode resource-constrained project scheduling problem with incompatibility constraints, a resource leveling objective and also a large number of tasks. We first present a new event-based mixed-integer linear programming formulation and a standard constraint programming formulation of the problem. A large-neighborhood search approach based on the constraint programming model and tailored to the resource leveling objective is proposed. The approaches are tested and compared using industrial instances, yielding significant improvement compared to the heuristic currently used by the company. Moreover, the large-neighborhood search method significantly improves the method proposed in the literature on a related multi-mode resource investment problem when short CPU times are required.

关键词： Aeronautical assembly line scheduling Multiple modes Resource leveling Mixed-integer linear programming constraint programming Large neighborhood search

来源：评论

学校读者我要写书评

暂无评论

Extension of constraint-procedural logic-generated environments for deep Q-learning agent training and benchmarking

引用

JOURNAL OF LOGIC AND COMPUTATION 2023年第8期33卷 1712-1733页

作者： De Gasperis, Giovanni Costantini, Stefania Rafanelli, Andrea Migliarini, Patrizio Letteri, Ivan Dyoub, Abeer Univ LAquila Dept Informat Engn Comp Sci & Math Via Vetoio I-67100 Laquila Italy Univ Pisa Dept Comp Sci Largo B Pontecorvo I-57127 Pisa Italy

Autonomous robots can be employed in exploring unknown environments and performing many tasks, such as, e.g. detecting areas of interest, collecting target objects, etc. Deep reinforcement learning (RL) is often used to train this kind of robot. However, concerning the artificial environments aimed at testing the robot, there is a lack of available data sets and a long time is needed to create them from scratch. A good data set is in fact usually produced with high effort in terms of cost and human work to satisfy the constraints imposed by the expected results. In the first part of this paper, we focus on the specification of the properties of the solutions needed to build a data set, making the case of environment exploration. In the proposed approach, rather than using imperative programming, we explore the possibility of generating data sets using constraint programming in Prolog. In this phase, geometric predicates describe a virtual environment according to inter-space requirements. The second part of the paper is focused on testing the generated data set in an AI gym via space search techniques. We developed a Neuro-Symbolic agent built from the following: (i) A deep Q-learning component implemented in Python, able to address via RL a search problem in the virtual space;the agent has the goal to explore a generated virtual environment to seek for a target, improving its performance through a RL process. (ii) A symbolic component able to re-address the search when the Q-learning component gets stuck in a part of the virtual environment;these components stimulate the agent to move to and explore other parts of the environment. Wide experimentation has been performed, with promising results, and is reported, to demonstrate the effectiveness of the approach.

关键词： Procedural generation constraint programming deep Q-learning neuro-symbolic intelligent agents computer aided design architecture

来源：评论

学校读者我要写书评

暂无评论

Generic Exact Combinatorial Search at HPC Scale

引用

INTERNATIONAL JOURNAL OF PARALLEL programming 2023年第1期51卷 83-106页

作者： MacGregor, Ruairidh Archibald, Blair Trinder, Phil Univ Glasgow Sch Comp Sci Glasgow Scotland

Exact combinatorial search is essential to a wide range of important applications, and there are many large problems that need to be solved quickly. Searches are extremely challenging to parallelise due to a combination of factors, e.g. searches are non-deterministic, dynamic pruning changes the workload, and search tasks have very different runtimes. YewPar is a C++/HPX framework that generalises parallel search by providing a range of sophisticated search *** paper demonstrates generic high performance combinatorial search, i.e. that a variety of exact combinatorial searches can be easily parallelised for HPC using YewPar. We present a new mechanism for profiling key aspects of YewPar parallel combinatorial search, and demonstrate its value. We exhibit, for the first time, generic exact combinatorial searches at HPC scale. We baseline YewPar against state-of-the-art sequential C++ and C++/OpenMP implementations. We demonstrate that deploying YewPar on an HPC system can dramatically reduce the runtime of large problems, e.g. from days to just 100s. The maximum relative speedups we achieve for an enumeration search are near-linear up to 195(6825) compute-nodes(workers), super-linear for an optimisation search on up to 128(4480) (pruning reduces the workload), and sub-linear for decision searches on up to 64(2240) compute-nodes(workers).

关键词： Combinatorial search Parallel skeletons constraint programming High performance computing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：