Search

We study the query evaluation problem in probabilistic databases in the presence of probabilistic existential rules. Our focus is on the Datalog± family of languages for which we define the probabilistic counterpart using a flexible and compact encoding of probabilities. This formalism can be viewed as a generalization of probabilistic databases, as it allows to generate new facts from the given ones, using so-called tuple-generating dependencies, or existential rules. We study the computational cost of this additional expressiveness under two different semantics. First, we use a conventional approach and assume that the probabilistic knowledge base is consistent and employ the standard possible world semantics. Thereafter, we introduce a probabilistic inconsistency-tolerant semantics, which we call inconsistency-tolerant possible world semantics. For both of these cases, we provide a thorough complexity analysis relative to different languages, drawing a complete picture of the complexity of probabilistic query answering in this family.

We introduce the formalism of infinite-state reactive modules to reason about the strategic behaviour of autonomous agents in a setting where data are explicitly exhibited in the systems description and in the specification language. Technically, we endow reactive modules with an infinite domain of interpretation for individual variables, and introduce FO-ATL, a first-order version of alternating time temporal logic, for the specification of properties of interest. We show that their verification is decidable for classes of data types of interest. This result is proved by defining a first-order version of alternating bisimulations and finite bisimilar abstractions. We illustrate the formal machinery by applying it to English and sealed bid auctions. In particular, we show that strategic properties of agents in auctions, including manipulability and collusion, can be expressed and verified in this framework.

In the past, research on learning language models mainly used syntactic information during the learning process but in recent years, researchers began to also use semantic information. This paper presents such an approach where the input of our learning algorithm is a dataset of pairs made up of sentences and the contexts in which they are produced. The system we present is based on inductive logic programming techniques that aim to learn a mapping between n-grams and a semantic representation of their associated meaning. Experiments have shown that we can learn such a mapping that made it possible later to generate relevant descriptions of images or learn the meaning of words without any linguistic resource. ispartof: pages:1764-1765 ispartof: Proceedings of the 22nd European Conference on Artificial Intelligence vol:285 pages:1764-1765 ispartof: European Conference on Artificial Intelligence location:The Hague, The Netherlands date:30 Aug - 3 Sep 2016 status: published

We investigate the parameterised model checking problem for specifications expressed in alternating-time temporal logic. We introduce parameterised concurrent game structures representing infinitely many games with different number of agents. We introduce a parametric variant of ATL to express properties of the system irrespectively of the number of agents present in the system. While the parameterised model checking problem is undecidable, we define a special class of systems on which we develop a sound and complete counter abstraction technique. We illustrate the methodology here devised on the prioritised version of the train-gate-controller.

Minimum sum-of-squares clustering (MSSC) is a widely studied task and numerous approximate as well as a number of exact algorithms have been developed for it. Recently the interest of inte- grating prior knowledge in data mining has been shown, and much attention has gone into incorporating user constraints into clustering algorithms in a generic way. Exact methods for MSSC using integer linear programming or constraint programming have been shown to be able to incorporate a wide range of constraints. However, a better performing method for unconstrained exact clustering is the Repetitive Branch-and-Bound Algorithm (RBBA) algorithm. In this paper we show that both ap- proaches can be combined. The key idea is to replace the internal branch-and-bound of RBBA by a constraint programming solver, and use it to compute tight lower and upper bounds. To achieve this, we integrate the computed bounds into the solver using a novel con- straint. Our method combines the best of both worlds, and is generic as well as performing better than other exact constrained meth- ods. Furthermore, we show that our method can be used for multi- objective MSSC clustering, including constrained multi-objective clustering. ispartof: pages:462-470 ispartof: Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI16) vol:285 pages:462-470 ispartof: European Conference on Artificial Intelligence (ECAI16) location:The Hague, The Netherlands date:29 Aug - 2 Sep 2016 status: published

Clustering is an underspecified task: there are no universal criteria for what makes a good clustering. This is especially true for relational data, where similarity can be based on the features of individuals, the relationships between them, or a mix of both. Existing methods for relational clustering have strong and often implicit biases in this respect. In this paper, we introduce a novel similarity measure for relational data. It is the first measure to incorporate a wide variety of types of similarity, including similarity of attributes, similarity of relational context, and proximity in a hypergraph. We experimentally evaluate how using this similarity affects the quality of clustering on very different types of datasets. The experiments demonstrate that (a) using this similarity in standard clustering methods consistently gives good results, whereas other measures work well only on datasets that match their bias; and (b) on most datasets, the novel similarity outperforms even the best among the existing ones. ispartof: pages:1674-1675 ispartof: Frontiers in Artificial Intelligence and Applications vol:285 pages:1674-1675 ispartof: European Conference on Artificial Intelligence location:NETHERLANDS, Hague date:29 Aug - 2 Sep 2016 status: published

Boolean games (BGs) are a strategic framework in which agents' goals are described using propositional logic. Despite the popularity of BGs, the problem of how agents can coordinate with others to (at least partially) achieve their goals has hardly received any attention. However, negotiation protocols that have been developed outside the setting of BGs can be adopted for this purpose, provided that we can formalize (i) how agents can make commitments and (ii) how deals between coalitions of agents can be identified given a set of active commitments. In this paper, we focus on these two aims. First, we show how agents can formulate commitments that are in accordance with their goals, and what it means for the commitments of an agent to be consistent. Second, we formalize deals in terms of coalitions who can achieve their goals without help from others. We show that verifying the consistency of a set of commitments of one agent is Pi(P)(2)-complete while checking the existence of a deal in a set of mutual commitments is Sigma(P)(2)-complete. Finally, we illustrate how the introduced concepts of commitments and deals can be used to achieve game-theoretical properties of the deals and to configure negotiation protocols.

We present MUREA (MUlti-Resolution Evidence Accumulation): a mobile robot localization method for known 2D environments. It is an evidence accumulation method where the complexity is reduced by means of a multi-resolution scheme. The added value of the contribution, in the authors opinion, are 1) the method per sé; 2) the capability of the system to accept both raw sensor data as well as independently generated localization estimates; 3) the capability of the system to give out a (less) accurate estimate whenever asked to do so (e.g. before its regular completion), which could be called any-time localization. © Springer-Verlag Berlin Heidelberg 2003.