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

Train scheduling with hybrid answer set programming

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Julian Jordi, Dirk Abels Ostrowski, Max Schaub, Torsten Toletti, Ambra Wanko, Philipp SBB Switzerland Potassco Solutions Germany Potassco Solutions Germany University of Potsdam Germany

We present a solution to real-world train scheduling problems, involving routing, scheduling, and optimization, based on Answer Set programming (ASP). To this end, we pursue a hybrid approach that extends ASP with difference constraints to account for a fine-grained timing. More precisely, we exemplarily show how the hybrid ASP system clingo[DL] can be used to tackle demanding planning-and-scheduling problems. In particular, we investigate how to boost performance by combining distinct ASP solving techniques, such as approximations and heuristics, with preprocessing and encoding techniques for tackling large-scale, real-world train scheduling instances. Copyright © 2020, The Authors. All rights reserved.

关键词： logic programming

A general framework for stable roommates problems using answer set programming

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Erdem, Esra Fidan, Muge Manlove, David Prosser, Patrick Faculty of Engineering and Natural Sciences Sabanci University Istanbul Turkey School of Computing Science University of Glasgow Glasgow United Kingdom

The Stable Roommates problem (SR) is characterized by the preferences of agents over other agents as roommates: each agent ranks all others in strict order of preference. A solution to SR is then a partition of the agents into pairs so that each pair shares a room, and there is no pair of agents that would block this matching (i.e., who prefers the other to their roommate in the matching). There are interesting variations of SR that are motivated by applications (e.g., the preference lists may be incomplete (SRI) and involve ties (SRTI)), and that try to find a more fair solution (e.g., Egalitarian SR). Unlike the Stable Marriage problem, every SR instance is not guaranteed to have a solution. For that reason, there are also variations of SR that try to find a good-enough solution (e.g., Almost SR). Most of these variations are NP-hard. We introduce a formal framework, called SRTI-ASP, utilizing the logic programming paradigm Answer Set programming, that is provable and general enough to solve many of such variations of SR. Our empirical analysis shows that SRTI-ASP is also promising for applications. This paper is under consideration for acceptance in TPLP. Copyright © 2020, The Authors. All rights reserved.

关键词： logic programming

Dynamic multi-agent path finding based on conflict resolution using answer set programming

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Atiq, Basem Patoglu, Volkan Erdem, Esra Faculty of Engineering and Natural Sciences Sabanci University Istanbul Turkey

We study a dynamic version of multi-agent path finding problem (called D-MAPF) where existing agents may leave and new agents may join the team at different times. We introduce a new method to solve D-MAPF based on conflict-resolution. The idea is, when a set of new agents joins the team and there are conflicts, instead of replanning for the whole team, to replan only for a minimal subset of agents whose plans conflict with each other. We utilize answer set programming as part of our method for planning, replanning and identifying minimal set of conflicts. Copyright © 2020, The Authors. All rights reserved.

关键词： logic programming

Concolic Testing in CLP

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Mesnard, Fred Payet, Étienne Vidal, Germán LIM - Université de la Réunion France MiST VRAIN Universitat Politècnica de València Spain

Concolic testing is a popular software verification technique based on a combination of concrete and symbolic execution. Its main focus is finding bugs and generating test cases with the aim of maximizing code coverage. A previous approach to concolic testing in logic programming was not sound because it only dealt with positive constraints (by means of substitutions) but could not represent negative constraints. In this paper, we present a novel framework for concolic testing of CLP programs that generalizes the previous technique. In the CLP setting, one can represent both positive and negative constraints in a natural way, thus giving rise to a sound and (potentially) more efficient technique. Defining verification and testing techniques for CLP programs is increasingly relevant since this framework is becoming popular as an intermediate representation to analyze programs written in other programming paradigms. Copyright © 2020, The Authors. All rights reserved.

关键词： logic programming

Context Delegation for Context-Based Access Control

学校读者我要写书评

暂无评论

Context Delegation for Context-Based Access Control

European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases, ECML PKDD 2018

作者： Al-Wahah, Mouiad Farkas, Csilla University of South Carolina ColumbiaSC29208 United States

ISBN: (纸本)9783030134525

The capability to delegate access privileges is an essential component of access control policies. We present an ontology-based context delegation approach for context-based access control. Our approach provides a dynamic and adaptive context delegation capability. The delegation does not cause any change to the underlying access control policy. We use Description logic (DL) and logic programming (LP) technologies for modeling contexts, delegation and CBAC privileges. We show how semantic-based techniques can be used to support adaptive and dynamic context delegation for CBAC policies. We provide the formal framework of the approach and show that it is decidable and consistent. © 2019, Springer Nature Switzerland AG.

关键词： logic programming

Human robot collaborative assembly planning: an answer set programming approach

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Rizwan, Momina Patoglu, Volkan Erdem, Esra Faculty of Engineering and Natural Sciences Sabancı University Istanbul Turkey

For planning an assembly of a product from a given set of parts, robots necessitate certain cognitive skills: high-level planning is needed to decide the order of actuation actions, while geometric reasoning is needed to check the feasibility of these actions. For collaborative assembly tasks with humans, robots require further cognitive capabilities, such as commonsense reasoning, sensing, and communication skills, not only to cope with the uncertainty caused by incomplete knowledge about the humans behaviors but also to ensure safer collaborations. We propose a novel method for collaborative assembly planning under uncertainty, that utilizes hybrid conditional planning extended with commonsense reasoning and a rich set of communication actions for collaborative tasks. Our method is based on answer set programming. We show the applicability of our approach in a real-world assembly domain, where a bi-manual Baxter robot collaborates with a human teammate to assemble furniture. This manuscript is under consideration for acceptance in TPLP. Copyright © 2020, The Authors. All rights reserved.

关键词： logic programming

S-semantics – an example

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Drabent, Wlodzimierz Institute of Computer Science Polish Academy of Sciences Department of Computer and Information Science Linköping University

The s-semantics makes it possible to explicitly deal with variables in program answers. So it seems suitable for programs using nonground data structures, like open lists. However it is difficult to find published examples of using the s-semantics to reason about particular programs. Here we apply s-semantics to prove correctness and completeness of Frühwirth’s n queens program. This is compared with a proof, published elsewhere, based on the standard semantics and Herbrand *** Codes 68N17 (Primary) 68N30 (Secondary) Copyright © 2020, The Authors. All rights reserved.

关键词： logic programming

Implementing dynamic answer set programming over finite traces

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Cabalar, Pedro Diéguez, Martín Schaub, Torsten Laferriere, Francois University of Corunna Spain University of Pau France University of Potsdam Germany

We introduce an implementation of an extension of Answer Set programming (ASP) with language constructs from dynamic (and temporal) logic that provides an expressive computational framework for modeling dynamic applications. Starting from logical foundations, provided by dynamic and temporal equilibrium logics over finite linear traces, we develop a translation of dynamic formulas into temporal logic programs. This provides us with a normal form result establishing the strong equivalence of formulas in different logics. Our translation relies on the introduction of auxiliary atoms to guarantee polynomial space complexity and to provide an embedding that is doomed to be impossible over the same language. Finally, the reduction of dynamic formulas to temporal logic programs allows us to extend ASP with both approaches in a uniform way and to implement both extensions via temporal ASP solvers such as telingo. Copyright © 2020, The Authors. All rights reserved.

关键词： logic programming

Reducing incompleteness in the game of Bridge using PLP

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Junkang, L.I. Thépaut, Solène Ventos, Véronique NukkAI Lab Paris France

Bridge is a trick-taking card game requiring the ability to evaluate probabilities since it is a game of incomplete information where each player only sees its cards. In order to choose a strategy, a player needs to gather information about the hidden cards in the other players’ hand. We present a methodology allowing us to model a part of card playing in Bridge using Probabilistic logic programming. Copyright © 2020, The Authors. All rights reserved.

关键词： logic programming