1,721,244 research outputs found
Complexity of Inconsistency-Tolerant Query Answering in Datalog+/- under Cardinality-Based Repairs
Get PDFQuerying inconsistent ontological knowledge bases is an important problem in practice, for which
several inconsistency-tolerant semantics have been proposed. In these semantics, the input database is
erroneous, and a repair is a maximally consistent database subset. Different notions of maximality (such
as subset and cardinality maximality) have been considered. In this paper, we give a precise picture of
the computational complexity of inconsistency-tolerant query answering in a wide range of Datalog+/–
languages under the cardinality-based versions of three prominent repair semantic
Introducing Ontological CP-Nets
No full textPreference representation and reasoning is a key issue in many real-world
scenarios. Currently, there are many approaches allowing preferences to be assessed in a
qualitative or quantitative way. The most prominent qualitative approach for representing
preferences are CP-nets. Their clear graphical structure unifies an easy representation of
user desires with nice computational properties when computing the best outcome. Here,
we introduce ontological CP-nets, which allow the representation of preferences using a
CP-net over an ontological domain, i.e., variable values are logical formulas constrained
relative to a background domain ontology
Game−Theoretic Agent Programming in Golog
Get PDFWe present the agent programming language GTGolog, which integrates explicit agent programming in Golog with game-theoretic multi-agent planning in Markov games. It is a generalization of DTGolog to a multi-agent setting, where we have two competing single agents or two competing teams of agents. The language allows for specifying a control program for a single agent or a team of agents in a high-level logical language. The control program is then completed by an interpreter in an optimal way against another single agent or another team of agents, by viewing it as a generalization of a Markov game, and computing a Nash strategy. We illustrate the usefulness of this approach along a robotic soccer example
Game−Theoretic Reasoning About Actions in Nonmonotonic Causal Theories
No full textWe present the action language GC+ for reasoning about actions in multi-agent systems under probabilistic uncertainty and partial observability, which is an extension of the action language C+ that is inspired by partially observable stochastic games (POSGs). We provide a finite-horizon value iteration for this framework and show that it characterizes finite-horizon Nash equilibria. We also describe how the framework can be implemented on top of nonmonotonic causal theories. We then present acyclic action descriptions in GC+ as a special case where transitions are computable in polynomial time. We also give an example that shows the usefulness of our approach in practice
Structure-Based Causes and Explanations in the Independent Choice Logic
No full textThis paper is directed towards combining Pearl's structural-model approach to causal reasoning with high-level formalisms for reasoning about actions. More precisely, we present a combination of Pearl's structural-model approach with Poole's independent choice logic. We show how probabilistic theories in the independent choice logic can be mapped to probabilistic causal models. This mapping provides the independent choice logic with appealing concepts of causality and explanation from the structural-model approach. We illustrate this along Halpern and Pearl's sophisticated notions of actual cause, explanation, and partial explanation. This mapping also adds first-order modeling capabilities and explicit actions to the structural-model approach
Adaptive Multi−Agent Programming in GTGolog
Get PDFWe present a novel approach to adaptive multi-agent programming, which is based on an integration of the agent programming language GTGolog with adaptive dynamic programming techniques. GTGolog combines explicit agent programming in Golog with game-theoretic multi-agent planning in stochastic games. In GTGolog, the transition probabilities and reward values of the domain must be provided with the model. The adaptive generalization of GTGolog proposed here is directed towards letting the agents themselves explore and adapt these data. We use high-level programs for the generation of both abstract states and optimal policies
Game-theoretic agent programming in Golog under partial observability
No full textIn this paper, we present the agent programming language POGTGolog, which is a combination of explicit agent programming in Golog with game-theoretic multi-agent planning in a special kind of partially observable stochastic games (POSGs). It is a generalization of the agent programming language GTGolog by partial observability. The approach allows for partially specifying a high-level control program for a system of multiple agents, and for optimally filling in missing details by viewing it as a generalization of a special POSG and computing a Nash equilibrium. We illustrate this approach along a robotic rugby example.
Relational Markov games
No full textAbstract. Towards a compact and elaboration-tolerant first-order representation of Markov games, we introduce relational Markov games, which combine standard Markov games with first-order action descriptions in a stochastic variant of the situation calculus. We focus on the zero-sum two-agent case, where we have two agents with diametrically opposed goals. We also present a symbolic value iteration algorithm for computing Nash policy pairs in this framework.
GAME-THEORETIC GOLOG UNDER Partial Observability
No full textIn this paper, we present the agent programming language POGTGolog (Partially Observable Game-Theoretic Golog), which integrates explicit agent programming in Golog with gametheoretic multi-agent planning in partially observable stochastic games. In this framework, we assume one team of cooperative agents acting under partial observability, where the agents may also have different initial belief states and not necessarily the same rewards. POGTGolog allows for specifying a partial control program in a high-level logical language, which is then completed by an interpreter in an optimal way. To this end, we define a formal semantics of POGTGolog programs in terms of Nash equilibria, and we then specify a POGTGolog interpreter that computes one of these Nash equilibria
- …
