SHACL (SHape Constraint Language) is a W3C recommendation for validating graph-based data against a set of constraints (called shapes). Importantly, SHACL allows to define recursive shapes, i.e. a shape may refer to i...
详细信息
ISBN:
(纸本)9781450370233
SHACL (SHape Constraint Language) is a W3C recommendation for validating graph-based data against a set of constraints (called shapes). Importantly, SHACL allows to define recursive shapes, i.e. a shape may refer to itself, directly of indirectly. The recommendation left open the semantics of recursive shapes, but proposals have emerged recently to extend the official semantics to support recursion. These proposals are based on the principle of possibility (or non-contradiction): a graph is considered valid against a schema if one can assign shapes to nodes in such a way that all constraints are satisfied. This semantics is not constructive, as it does not provide guidelines about how to obtain such an assignment, and it may lead to unfounded assignments, where the only reason to assign a shape to a node is that it allows validating the graph. In contrast, we propose in this paper a stricter, more constructive semantics for SHACL, based on stable models, which are well-known in answer set programming (ASP). This semantics additionally requires a shape assignment to be properly justified by the input constraints. We further exploit the connection to logic programming, and show that SHACL constraints can be naturally represented as logic programs, and that the validation problem for a graph and a SHACL schema can be encoded as an ASP reasoning task. The proposed semantics also enjoys computationally tractable validation in the presence of constraints with stratified negation (as opposed to the previous semantics). We also extend our semantics to 3-valued stable models, which yields a more relaxed notion of validation, tolerant to certain faults in the schema or data. By exploiting a connection between 3-valued stable model semantics and the well-founded semantics for logic programs, we can use our translation into ASP to show another tractability result. Finally, we provide a preliminary evaluation of the approach, which leverages an ASP solver to perform graph valida
In multi-agent systems, multi-agent planning and diagnosis are two key subfields - multi-agent planning approaches identify plans for the agents to execute in order to reach their goals, and multiagent diagnosis appro...
详细信息
ISBN:
(纸本)9798400708480
In multi-agent systems, multi-agent planning and diagnosis are two key subfields - multi-agent planning approaches identify plans for the agents to execute in order to reach their goals, and multiagent diagnosis approaches identify root causes for faults when they occur, typically by using information from the multi-agent planning model as well as the resulting multi-agent plan. However, when a plan fails during execution, the cause can often be related to some commonsense information that is neither explicitly encoded in the planning nor diagnosis problems. As such existing diagnosis approaches fail to accurately identify the root causes in such situations. To remedy this limitation, we extend the Multi-Agent STRIPS problem (a common multi-agent planning framework) to a Commonsense Multi-Agent STRIPS model, which includes commonsense fluents and axioms that may affect the classical planning problem. We show that a solution to a (classical) Multi-Agent STRIPS problem is also a solution to the commonsense variant of the same problem. Then, we propose a decentralized multi-agent diagnosis algorithm, which uses the commonsense information to diagnose faults when they occur during execution. Finally, we demonstrate the feasibility and promise of this approach on several key multiagent planning benchmarks.
This paper proposes a declarative approach to the problem of contrast pattern mining. The approach is based on encodings of the data and the problem with answer set programming (ASP), and evaluated in a novel AI appli...
详细信息
ISBN:
(数字)9783031271816
ISBN:
(纸本)9783031271809;9783031271816
This paper proposes a declarative approach to the problem of contrast pattern mining. The approach is based on encodings of the data and the problem with answer set programming (ASP), and evaluated in a novel AI application in the field of Digital Forensics.
The amount and variety of data that we produce every day pose a constant challenge for meaningful information processing. While knowledge graphs have gained a considerable attention in the recent years, due to their f...
详细信息
ISBN:
(纸本)9789897584749
The amount and variety of data that we produce every day pose a constant challenge for meaningful information processing. While knowledge graphs have gained a considerable attention in the recent years, due to their flexible and universal knowledge representation, they lack the mechanisms facilitating knowledge processing. In this paper, we propose an information system called extended knowledge graphs (EKG) that augments the concept of knowledge graphs with procedural attachments. We put forward the requirements and assumption of the EKG structure and present a categorisation of supported reasoning tasks.
answer set programming with Quantifiers ASP(Q) is a recent extension of answer set programming (ASP) that allows one to model problems from the entire polynomial hierarchy. Earlier work focused on demonstrating modeli...
详细信息
ISBN:
(纸本)9783031157073;9783031157066
answer set programming with Quantifiers ASP(Q) is a recent extension of answer set programming (ASP) that allows one to model problems from the entire polynomial hierarchy. Earlier work focused on demonstrating modeling capabilities of ASP(Q). In this paper, we propose a modular ASP(Q) solver that translates a quantified ASP program together with a given data instance into a Quantified Boolean Formula (QBF) to be solved by any QBF solver. We evaluate the performance of our solver on several instances and with different back-end QBF solvers, demonstrating the efficacy of ASP(Q) as a tool for rapid modeling and solving of complex combinatorial problems. The benchmark problems we use include two new ones, Argumentation Coherence and Para-coherent ASP, for which we develop elegant ASP(Q) encodings.
Heuristics such as the Occam Razor's principle have played a significant role in reducing the search for solutions of a learning task, by giving preference to most compressed hypotheses. For some application domai...
详细信息
ISBN:
(数字)9783319237084
ISBN:
(纸本)9783319237084;9783319237077
Heuristics such as the Occam Razor's principle have played a significant role in reducing the search for solutions of a learning task, by giving preference to most compressed hypotheses. For some application domains, however, these heuristics may become too weak and lead to solutions that are irrelevant or inapplicable. This is particularly the case when hypotheses ought to conform, within the scope of a given language bias, to precise domain-dependent structures. In this paper we introduce a notion of inductive learning through constraint-driven bias that addresses this problem. Specifically, we propose a notion of learning task in which the hypothesis space, induced by its mode declaration, is further constrained by domain-specific denials, and acceptable hypotheses are (brave inductive) solutions that conform with the given domain-specific constraints. We provide an implementation of this new learning task by extending the ASPAL learning approach and leveraging on its meta-level representation of hypothesis space to compute acceptable hypotheses. We demonstrate the usefulness of this new notion of learning by applying it to two class of problems - automated revision of software system goals models and learning of stratified normal programs.
In view of the increasing importance of hardware parallelism, a natural extension of per-instance algorithm selection is to select a set of algorithms to be run in parallel on a given problem instance, based on featur...
详细信息
ISBN:
(数字)9783319190846
ISBN:
(纸本)9783319190846;9783319190839
In view of the increasing importance of hardware parallelism, a natural extension of per-instance algorithm selection is to select a set of algorithms to be run in parallel on a given problem instance, based on features of that instance. Here, we explore how existing algorithm selection techniques can be effectively parallelized. To this end, we leverage the machine learning models used by existing sequential algorithm selectors, such as 3S, ISAC, SATzilla and ME-ASP, and modify their selection procedures to produce a ranking of the given candidate algorithms;we then select the top n algorithms under this ranking to be run in parallel on n processing units. Furthermore, we adapt the pre-solving schedules obtained by aspeed to be effective in a parallel setting with different time budgets for each processing unit. Our empirical results demonstrate that, using 4 processing units, the best of our methods achieves a 12-fold average speedup over the best single solver on a broad set of challenging scenarios from the algorithm selection library.
We present a domain model that formalises the human-land relations in the Maasai nomadic pastoralist society in Kenya, referred to as MSKDM, and its integration with the prominent Land Administration Domain Model (LAD...
详细信息
We present a domain model that formalises the human-land relations in the Maasai nomadic pastoralist society in Kenya, referred to as MSKDM, and its integration with the prominent Land Administration Domain Model (LADM). Our long-term aim is to facilitate a land administration system that can accurately capture and express salient Maasai concepts of land use, ownership, communal tenure, and to assist in transparency during land transactions. We use an extensive corpus of existing research literature, and input from our own on-site workshops, as source material for our domain model. We use real sketch maps drawn by Maasai community members that we collected during our field studies for validation, and to demonstrate how our model can be operationalised.
We introduce dlv2, a new answer set programming (ASP) system. dlv2 combines I-dlv, a fully-compliant ASP-Core-2 grounder, with the well-assessed solver wasp. Input programs may be enriched by annotations and directive...
详细信息
ISBN:
(纸本)9783319616605;9783319616599
We introduce dlv2, a new answer set programming (ASP) system. dlv2 combines I-dlv, a fully-compliant ASP-Core-2 grounder, with the well-assessed solver wasp. Input programs may be enriched by annotations and directives that customize heuristics of the system and extend its solving capabilities. An empirical analysis conducted on benchmarks from past ASP competitions shows that dlv2 outperforms the old dlv system and is close to the state-of-the-art ASP system CLINGO.
Dealing with domains involving substantial quantitative information in answer set programming (ASP) often results in cumbersome and inefficient encodings. Hybrid "CASP" languages combining ASP and Constraint...
详细信息
Dealing with domains involving substantial quantitative information in answer set programming (ASP) often results in cumbersome and inefficient encodings. Hybrid "CASP" languages combining ASP and Constraint programming aim to overcome this limitation, but also impose inconvenient constraints - first and foremost that quantitative information must be encoded by means of total functions. This goes against central knowledge representation principles that contribute to the power of ASP, and makes the formalization of certain domains difficult. ASP{f} is being developed with the ultimate goal of providing scientists and practitioners with an alternative to CASP languages that allows for the efficient representation of qualitative and quantitative information in ASP without restricting one's ability to deal with incompleteness or uncertainty. In this paper we present the latest outcome of such research: versions of the language and of the supporting system that allow for practical, industrial-size use and scalability. The applicability of ASP{f} is demonstrated by a case study on an actual industrial application.
暂无评论