We develop an approach called bounded combinatorial reconfiguration for solving combinatorial reconfiguration problems based on answer set programming. The general task is to study the solution spaces of source combin...
详细信息
ISBN:
(纸本)9783031436185;9783031436192
We develop an approach called bounded combinatorial reconfiguration for solving combinatorial reconfiguration problems based on answer set programming. The general task is to study the solution spaces of source combinatorial problems and to decide whether or not there are sequences of feasible solutions that have special properties. The resulting recongo solver covers all metrics of the solver track in the most recent international competition on combinatorial reconfiguration (CoRe Challenge 2022). recongo ranked first in the shortest metric of the single-engine solvers track.
Declarative methods such as answer set programming show potential in cutting down development costs in commercial videogames and real-time applications in general. Many shortcomings, however, prevent their adoption, s...
详细信息
ISBN:
(数字)9781665459891
ISBN:
(纸本)9781665459891
Declarative methods such as answer set programming show potential in cutting down development costs in commercial videogames and real-time applications in general. Many shortcomings, however, prevent their adoption, such as performance and integration gaps. In this work we illustrate our ThinkEngine, a framework in which a tight integration of declarative formalisms within the typical game development workflow is made possible in the context of the Unity game engine. ThinkEngine allows to wire declarative AI modules to the game logic and to move the computational load of reasoning tasks outside the main game loop using an hybrid deliberative/reactive architecture. In this paper, we illustrate the architecture of the ThinkEngine and its role both at design and run-time. Then we show how to program declarative modules in a proof-of-concept game, and report about performance and related work.
We present a novel approach to the creation of smart contracts that takes an existing legal document and allows it to be incrementally elaborated into a tested smart contract by domain experts. Smart contracts are cur...
详细信息
ISBN:
(纸本)9783030975463;9783030975456
We present a novel approach to the creation of smart contracts that takes an existing legal document and allows it to be incrementally elaborated into a tested smart contract by domain experts. Smart contracts are currently built with compiled imperative languages, and suffer from lack of agility, elevated risks from errors and security flaws, and high development costs. This paper describes a smart editor that uses a declarative language (answer set programming (ASP)) to represent the business logic of legal documents. The document is incrementally elaborated in a fixed sequence of steps beginning with an ontology discovery step that identifies the explicit and implicit artefacts and applicable constraints. This information is used to generate ASP representations which provide the foundation required for modelling the legal logic. Furthermore, we have achieved the verbalisation of rules built during modelling, and have developed a method of representing artefacts visually which allows logic modelling, model validation and program verification to be visual. During these steps, the original legal document is enhanced with additional embedded information, which results in a tested executable ASP program which can then be used as a smart contract if modifications are made to the blockchain smart contract infrastructure.
answer set programming (ASP) is a well-established declarative AI formalism for knowledge representation and reasoning. ASP systems were successfully applied to both industrial and academic problems. Nonetheless, thei...
详细信息
ISBN:
(纸本)9783031157073;9783031157066
answer set programming (ASP) is a well-established declarative AI formalism for knowledge representation and reasoning. ASP systems were successfully applied to both industrial and academic problems. Nonetheless, their performance can be improved by embedding domain-specific heuristics into their solving process. However, the development of domain-specific heuristics often requires both a deep knowledge of the domain at hand and a good understanding of the fundamental working principles of the ASP solvers. In this paper, we investigate the use of deep learning techniques to automatically generate domain-specific heuristics for ASP solvers targeting the well-known graph coloring problem. Empirical results show that the idea is promising: the performance of the ASP solver WASP can be improved.
Modal logic S5 is used extensively for representing knowledge that includes statements about necessity and possibility, owing to its simplicity in handling chained modal operators. Significant research effort has been...
详细信息
ISBN:
(纸本)9783031157073;9783031157066
Modal logic S5 is used extensively for representing knowledge that includes statements about necessity and possibility, owing to its simplicity in handling chained modal operators. Significant research effort has been devoted in developing efficient reasoning mechanisms over complex S5 formulas, resulting in various solvers taking advantage of the boolean satisfiability problem (SAT). Among them, the most performant solver implements a heuristic for identifying worlds that can be merged, hence reducing the size of SAT instances to be checked. Recently, answer set programming (ASP) has also been considered, and different ASP encodings were proposed and tested, reaching state-of-the-art performance. In particular, a heuristic for identifying the propositional atoms that are relevant in every world resulted in a performance gain in previous experiments. This work addresses the open question of whether the aforementioned two heuristics can be combined, as well as possibly enabling lazy instantiation of the resulting encodings, and what their potential impact is on the performance of the ASP-based solver. Experiments show that lazy creation of worlds provides some further performance gain to the ASP-based solver on the tested instances.
In this paper we develop a state transition function for partially observable multi-agent epistemic domains and implement it using answer set programming (ASP). The transition function computes the next state upon an ...
详细信息
ISBN:
(纸本)9783031157073;9783031157066
In this paper we develop a state transition function for partially observable multi-agent epistemic domains and implement it using answer set programming (ASP). The transition function computes the next state upon an occurrence of a single action. Thus it can be used as a module in epistemic planners. Our transition function incorporates ontic, sensing and announcement actions and allows for arbitrary nested belief formulae and general common knowledge. A novel feature of our model is that upon an action occurrence, an observing agent corrects his (possibly wrong) initial beliefs about action precondition and his observability. By examples, we show that this step is necessary for robust state transition. We establish some properties of our state transition function regarding its soundness in updating beliefs of agents consistent with their observability.
We present a general approach to planning with incomplete information in answer set programming (ASP). More precisely, we consider the problems of conformant and conditional planning with sensing actions and assumptio...
详细信息
We present a general approach to planning with incomplete information in answer set programming (ASP). More precisely, we consider the problems of conformant and conditional planning with sensing actions and assumptions. We represent planning problems using a simple formalism where logic programs describe the transition function between states, the initial states and the goal states. For solving planning problems, we use Quantified answer set programming (QASP), an extension of ASP with existential and universal quantifiers over atoms that is analogous to Quantified Boolean Formulas (QBFs). We define the language of quantified logic programs and use it to represent the solutions different variants of conformant and conditional planning. On the practical side, we present a translation-based QASP solver that converts quantified logic programs into QBFs and then executes a QBF solver, and we evaluate experimentally the approach on conformant and conditional planning benchmarks.
Multi-agent pathfinding (MAPF) is the problem of finding k non-colliding paths connecting k given initial positions with k given goal positions on a given map. In its sum-of-costs variant, the total number of moves an...
详细信息
Multi-agent pathfinding (MAPF) is the problem of finding k non-colliding paths connecting k given initial positions with k given goal positions on a given map. In its sum-of-costs variant, the total number of moves and wait actions performed by agents before they definitely reach the goal is minimized. Not surprisingly, since MAPF is combinatorial, a number of compilations to Boolean Satisfiability (SAT) and answer set programming (ASP) exist. In this article, we describe in detail the first family of compilations to ASP that solve sum-of-costs MAPF over 4-connected grids. Compared to existing ASP compilations, a distinguishing feature of our compilation is that the number of total clauses (after grounding) grow linearly with the number of agents, while existing compilations grow quadratically. In addition, the optimization objective is such that its size after grounding does not depend on the size of the grid. In our experimental evaluation, we show that our approach outperforms search-based sum-of-costs MAPF solvers when grids are congested with agents. We also show that our approach is competitive with a SAT-based approach when follow conflicts are taken into account. We also explore the potential of our solver when finding makespan-optimal solutions, in which makespan is minimized first and then cost is minimized. Our results show that makespan-optimal solutions are slightly suboptimal in most benchmarks. Moreover, our MAPF solver, when run in that mode, is faster and scales better.
Goal-directed evaluation of answerset Programs is gaining traction thanks to its amenability to create AI systems that can, due to the evaluation mechanism used, generate explanations and justifications. s(CASP) is o...
详细信息
In this paper, we present a system, called xASP, for generating explanations that explain why an atom belongs to (or does not belong to) an answerset of a given program. The system can generate all possible explanati...
详细信息
ISBN:
(纸本)9783031157073;9783031157066
In this paper, we present a system, called xASP, for generating explanations that explain why an atom belongs to (or does not belong to) an answerset of a given program. The system can generate all possible explanations for a query without the need to simplify the program before computing explanations, i.e., it works with non-ground programs. These properties distinguish xASP from existing systems such as xClingo, DiscASP, exp(ASP(c)), and s(CASP), which also generate explanations for queries to logic programs under the answerset semantics but simplify and ground the programs (the three systems xClingo, DiscASP, exp(ASP(c))) or do not always generate all possible explanations (the system s(CASP)). In addition, the output of xASP is insensitive to syntactic variations such as the order conditions and the order of rules, which is also different from the output of s(CASP).
暂无评论