Multi-agent pathfinding is the problem of finding collision-free paths for a set of agents. Solving this problem optimally is computationally hard, therefore many techniques based on reductions to other formalisms wer...
详细信息
ISBN:
(纸本)9781450392136
Multi-agent pathfinding is the problem of finding collision-free paths for a set of agents. Solving this problem optimally is computationally hard, therefore many techniques based on reductions to other formalisms were developed. In comparison to search-based techniques, the reduction-based techniques fall behind on large maps even for a small number of agents. To combat this phenomenon, we propose several strategies for pruning vertices off large instances that will most likely not be used by agents. First, we introduce these strategies conceptually and prove which of them maintain completeness and optimality. Eventually, we conduct an exhaustive evaluation and show that graph pruning strategies make reduction-based solvers comparable to search-based techniques on large maps while maintaining their advantage on small dense maps.
This paper presents a semantic model to represent topology-based security requirements, recommend measures to address any possible security violations, and thus make the underlying systems compliant with its security ...
详细信息
ISBN:
(纸本)9781450344869
This paper presents a semantic model to represent topology-based security requirements, recommend measures to address any possible security violations, and thus make the underlying systems compliant with its security requirements. The proposed action-based model is capable of adaptively adjusting the topological model of a given system in response to changes in the structure of its operational environment. The proposed framework benefits from non-monotonic reasoning to reason about possible execution paths and hence recommend actions to prevent security requirements violations. The results of our case studies show that using the proposed approach to enforce security measures, not only can we detect possible security violations caused by changes in the structure of operational environment, but also recommend actions to address possible violations.
Epistemic specification (ES for short) is an extension of answer set programming (ASP for short). The extension is built around the introduction of modalities K and M, and then is capable of representing incomplete in...
详细信息
ISBN:
(纸本)9781479929733
Epistemic specification (ES for short) is an extension of answer set programming (ASP for short). The extension is built around the introduction of modalities K and M, and then is capable of representing incomplete information in the presence of multiple belief sets. Although both syntax and semantics of ES are up in the air, the need for this extension has been illustrated with several examples in the literatures. In this paper, we present a new ES version with only modality K and the design of its inference engine ESmodels that aims to be efficient enough to promote the theoretical research and also practical use of ES. We first introduce the syntax and semantics of the new version of ES and show it is succinct but flexible by comparing it with existing ES versions. Then, we focus on the description of the algorithm and optimization approaches of the inference engine. Finally, we conclude with perspectives.
Procedural content generation (PCG) has the potential to create unique artifacts, levels, and gameplay mechanics. However, it remains challenging to generate content that satisfies gameplay constraints: methods to ach...
详细信息
ISBN:
(纸本)9781450314473
Procedural content generation (PCG) has the potential to create unique artifacts, levels, and gameplay mechanics. However, it remains challenging to generate content that satisfies gameplay constraints: methods to achieve this include generate-and-test, search-based generation, and constructive methods. In this paper, we present a prototype, a simple game, which demonstrates the use of an off-the-shelf logic program solver, Clingo, as an easy and expressive way to model these constraint problems, and find solutions that satisfy gameplay constraints. By delegating the difficult search optimization problem to an external program, we were able to quickly prototype PCG in a low-effort way by expressing the desired content as a set of rules and constraints, keeping the focus on the designer's intentions for the generated content, rather than specific methods used to create or find it. The expressiveness and versatility of this approach is demonstrated by applying this technique to two areas of PCG in the game.
Formal verification is essential for circuit correctness. Extending binary logic verification to Multi-Valued Logic (MVL) presents challenges due to encoding challenges. answer set programming (ASP) enables compact MV...
详细信息
ISBN:
(数字)9798350343083
ISBN:
(纸本)9798350343090
Formal verification is essential for circuit correctness. Extending binary logic verification to Multi-Valued Logic (MVL) presents challenges due to encoding challenges. answer set programming (ASP) enables compact MVL circuit encoding. In this paper, we propose a Polynomial Formal Verification (PFV) approach for MVL circuits with a constant cutwidth. It employs a divide-and-conquer algorithm to decompose circuits into subcircuits, each representing an output, where ASP is used to encode and verify the subcircuits. The approach reduces verification complexity to the circuit's cutwidth, independent of input bitwidth, ensuring linear time verification for circuits with constant cutwidth. We validate our approach using adder architectures, as many adder architectures have a constant cutwidth. Empirical experiments involve various adder architectures and different logic levels.
Partially Observable Monte Carlo Planning (POMCP) is an efficient solver for Partially Observable Markov Decision Processes (POMDPs). It allows scaling to large state spaces by computing an approximation of the optima...
详细信息
ISBN:
(纸本)9781450394321
Partially Observable Monte Carlo Planning (POMCP) is an efficient solver for Partially Observable Markov Decision Processes (POMDPs). It allows scaling to large state spaces by computing an approximation of the optimal policy locally and online, using a Monte Carlo Tree Search based strategy. However, POMCP suffers from sparse reward function, namely, rewards achieved only when the final goal is reached, particularly in environments with large state spaces and long horizons. Recently, logic specifications have been integrated into POMCP to guide exploration and to satisfy safety requirements. However, such policy-related rules require manual definition by domain experts, especially in real-world scenarios. In this paper, we use inductive logic programming to learn logic specifications from traces of POMCP executions, i.e., sets of belief-action pairs generated by the planner. Specifically, we learn rules expressed in the paradigm of answer set programming. We then integrate them inside POMCP to provide soft policy bias toward promising actions. In the context of two benchmark scenarios, rocksample and battery, we show that the integration of learned rules from small task instances can improve performance with fewer Monte Carlo simulations and in larger task instances. We make our modified version of POMCP publicly available at https://***/GiuMaz/pomcp_***.
This paper investigates the use of high-level action languages for designing ethical autonomous agents. It proposes a novel and modular logic-based framework for representing and reasoning over a variety of ethical th...
详细信息
ISBN:
(纸本)9781510855076
This paper investigates the use of high-level action languages for designing ethical autonomous agents. It proposes a novel and modular logic-based framework for representing and reasoning over a variety of ethical theories, based on a modified version of the Event Calculus and implemented in answer set programming. The ethical decision-making process is conceived of as a multi-step procedure captured by four types of interdependent models which allow the agent to assess its environment, reason over its accountability and make ethically informed choices The overarching ambition of the presented research is twofold. First, to allow the systematic representation of an unbounded number of ethical reasoning processes, through a framework that is adaptable and extensible by virtue of its designed hierarchisation and standard syntax. Second, to avoid the pitfall of much research in current computational ethics that too readily embed moral information within computational engines, thereby feeding agents with atomic answers that fail to truly represent underlying dynamics. We aim instead to comprehensively displace the burden of moral reasoning from the programmer to the program itself.
RASP is a recent extension to answer set programming (ASP) that permits declarative specification and reasoning on the consumption and production of resources. ASP can be seen as a particular case of RASP. In this pap...
详细信息
In this article, we compare the expressive powers of classes of normal logic programs that are obtained by constraining the number of positive subgoals (n) in the bodies of rules. The comparison is based on the existe...
详细信息
In this article, we compare the expressive powers of classes of normal logic programs that are obtained by constraining the number of positive subgoals (n) in the bodies of rules. The comparison is based on the existence/ nonexistence of polynomial, faithful, and modular (PFM) translation functions between the classes. As a result, we obtain a strict ordering among the classes under consideration. Binary programs (n ≤ 2) are shown to be as expressive as unconstrained programs but strictly more expressive than unary programs (n ≤ 1) which, in turn, are strictly more expressive than atomic programs (n = 0). We also take propositional theories into consideration and prove them to be strictly less expressive than atomic programs. In spite of the gap in expressiveness, we develop a faithful but non-modular translation function from normal programs to propositional theories. We consider this as a breakthrough due to sub-quadratic time complexity (of the order of ||P|| × log 2 |Hb(P)|). Furthermore, we present a prototype implementation of the translation function and demonstrate its promising performance with SAT solvers using three benchmark problems.
暂无评论