Relational Continuous Models (RCMs) represent joint probability densities over attributes of objects, when the attributes have continuous domains. With relational representation, they can model joint probability distributions over large numbers of variables compactly in a natural way. This paper presents the first exact inference algorithm for RCMs at a lifted level, so that it scales up to large models of real world applications. The algorithm applies to relational pairwise models which are (relational) products of potentials of arity 2. Our algorithm is unique in two ways. First, it is an efficient lifted inference algorithm. When Gaussian potentials are used, it takes only linear time while existing methods take cubic time. Second, it is the first exact inference algorithm which handles RCMs in a lifted way. The algorithm is illustrated over an example from Econometrics. Experimental results show that our algorithm outperforms both a ground-level inference algorithm and an algorithm built with previously-known lifted methods

In this paper we study the sequential strategic interactive setting of two-person, two-stage, seller-offers bargaining under uncertainty. We model the epistemology of the problem in a finite interactive decision-theoretic framework and solve it for three types of agents of successively increasing (epistemological) sophistication (or, capacity to represent and reason with higher orders of beliefs). In particular, we remove common knowledge assumptions about the agents' epistemology which, if made, would be sufficient to imply the existence of a, possibly unique, game-theoretic equilibrium solution. In this context, we present a characterization of a monotonic relationship between an agent's optimal behavior and its beliefs under a particular moment-based ordering. Further, based on this characterization, we present the \emph{spread-accumulate} sampling technique -- a method of sampling an agent's higher order belief by generating ``evenly dispersed" beliefs for which we (pre)compute offline solutions. Then, we present a method for approximating higher order prior belief update to arbitrary precision by identifying a (previously solved) belief ``closest" to the true belief. In addition, these methods directly suggest a mechanism for achieving a balance between efficiency and the quality of the approximation -- either by generating a large number of offline solutions or by allowing the agent to search online for a ``closer" belief in the vicinity of best current solution.

We study the problem of achieving cooperation between two self-interested agents that play a sequence of randomly generated normal form games, each game played only once. To achieve cooperation we extend a model used to explain cooperative behavior by humans. We show how a modification of a pre-regularized particle filter can be used to detect the cooperation level of the opponent and play accordingly. We examine how properties of the games affect the ability of an agent to detect cooperation and explore the effects of different environments and different levels of conflict. We present results obtained in simulation on hundreds of randomly generated games.

In this work, we present maximum causal entropy correlated equilibria, a new solution concept that we apply to Markov games. This contribution extends the existing solution concept of maximum entropy correlated equilibria for normal-form games to settings with elements of dynamic interaction with a stochastic environment by employing the recently developed principle of maximum causal entropy. This solution concept is justified for two purposes: as a mechanism for prescribing actions, it reveals the least additional information about the agents' motives possible; and as a predictive estimator of actions for a group of agents assumed to behave according to an unknown correlated equilibrium, it has the fewest additional assumptions and minimizes worst-case action prediction log-loss. Importantly, equilibria for this solution concept are guaranteed to be unique and Markovian, enabling efficient algorithms for finding them.

Informational conflicts in operational policies cause agents to run into situations where responding based on the rules in one policy violates the same or another policy. Static checking of these conflicts is infeasible and impractical in a dynamic environment. This paper discusses a practical approach to handling policy conflicts in real-time domains within the context of a hierarchical military command and control simulated system that consists of a central command, squad leaders and squad members. All the entities in the domain function according to preset communication and action protocols in order to perform successful missions. Each entity in the domain is equipped with an instance of a metacognitive component to provide on-board/on-time analysis of actions and recommendations during the operation of the system. The metacognitive component is the Metacognitive Loop (MCL) which is a general purpose anomaly processor designed to function as a cross-domain plugin system. It continuously monitors expectations and notices when they are violated, assesses the cause of the violation and guides the host system to an appropriate response. MCL makes use of three ontologies—indications, failures and responses—to perform the notice, assess and guide phases when a conflict occurs. Conflicts in the set of rules (within a policy or between policies) manifest as expectation violations in the real world. These expectation violations trigger nodes in the indication ontology which, in turn, activate associated nodes in the failure ontology. The responding failure nodes then activate the appropriate nodes in the response ontology. Depending on which response node gets activated, the actual response may vary from ignoring the conflict to prioritizing, modifying or deleting one or more conflicting rules.

Knowledge compilation is a valuable tool for dealing with the computational intractability of propositional reasoning. In knowledge compilation, a representation in a source language is typically compiled into a target language in order to perform some reasoning task in polynomial time. One particularly popular target language is Deterministic Decomposable Negation Normal Form (d-DNNF). d-DNNF supports efficient reasoning for tasks such as consistency checking and model counting, and as such it has proven a useful representation language for Bayesian inference, conformant planning, and diagnosis. In this paper, we exploit recent advances in #SAT solving in order to produce a new state-of-the-art CNF → d-DNNF compiler. We evaluate the properties and performance of our compiler relative to C2D, the de facto standard for compiling to d-DNNF. Empirical results demonstrate that our compiler is generally one order of magnitude faster than C2D on typical benchmark problems while yielding a d-DNNF representation of comparable size.

Learning useful information when solving SAT or CSP problems to speed up a tree-search approaches, is one of the main explored tracks in various works. Such information are known as goods and nogoods and they aim to forbid to repetitively visit the same parts of the search space. Unfortunately and unlike nogoods, the exploitation of goods is limited to tree-search approaches based on the structural properties of the problem. In this paper, we propose to generalize and reformulate structural goods under SAT. We also propose a learning scheme of general goods and show their integration in a DPLL-like procedure.

To harness modern multicore processors, it is imperative to develop parallel versions of fundamental algorithms. In this paper, we present a general approach to best-first heuristic search in a shared-memory setting. Each thread attempts to expand the most promising nodes. By using abstraction to partition the state space, we detect duplicate states while avoiding lock contention. We allow speculative expansions when necessary to keep threads busy. We identify and fix potential livelock conditions. In an empirical comparison on STRIPS planning, grid pathfinding, and sliding tile puzzle problems using an 8-core machine, we show that A* implemented in our framework yields faster search performance than previous parallel search proposals. We also demonstrate that our approach extends easily to other best-first searches, such as weighted A* and anytime heuristic search.

We present a fractal technique for addressing geometric analogy problems from the Raven's Standard Progressive Matrices test of general intelligence. In this method, an image is represented fractally, capturing its inherent self-similarity. We apply these fractal representations to problems from the Raven's test, and show how these representations afford a new method for solving complex geometric analogy problems. We present results using the fractal algorithm on all 60 problems from the Standard Progressive Matrices version of the Raven's test.

Constraint satisfaction problems are mathematical models of real-world problems. In contrast to randomly generated artificial problems, real-world problems usually have non-random structure. Knowledge about that structure, when identified in advance, can make search to find solutions more effective. This paper introduces DrawCSP, a visualization program that can show both the original and the discovered structure of constraint satisfaction problems. DrawCSP provides insight into both search algorithm design and into the challenges real-world problems present.