One typically proves infeasibility in satisfiability/constraint satisfaction (or optimality in integer programming) by constructing a tree certificate. However, deciding how to branch in the search tree is hard, and impacts search time drastically. We explore the power of a simple paradigm, that of throwing random darts into the assignment space and then using information gathered by that dart to guide what to do next. This method seems to work well when the number of short certificates of infeasibility is moderate, suggesting that the overhead of throwing darts is more than paid for by the information gained by these darts.

Statistical relational learning (SRL) augments probabilistic models with relational representations and facilitates reasoning over sets of objects. When learning the probabilistic parameters for SRL models, however, one often resorts to reasoning over individual objects. To address this challenge, we compile a Markov logic network into a compact and efficient first-order data structure and use weighted first-order model counting to exactly optimize the likelihood of the parameters in a lifted manner. By exploiting the relational structure in the model, it is possible to learn more accurate parameters and dramatically improve the run time of the likelihood calculation. This allows us to calculate the exact likelihood for models where previously only approximate inference was feasible. Results on real-world data sets show that this approach learns more accurate models.

We present a robust framework for complex event recognition that is well-suited for integrating information that varies widely in detail and granularity. Consider the scenario of an agent in an instrumented space performing a complex task while describing what he is doing in a natural manner. The system takes in a variety of information, including objects and gestures recognized by RGB-D and descriptions of events extracted from recognized and parsed speech. The system outputs a complete reconstruction of the agent’s plan, explaining actions in terms of more complex activities and filling in unobserved but necessary events. We show how to use Markov Logic (a probabilistic extension to first order logic) to create a theory in which observations can be partial, noisy, and refer to future or temporally ambiguous events; complex events are composed from simpler events in a manner that exposes their structure for inference and learning; and uncertainty is handled in a sound probabilistic manner. We demonstrate the effectiveness of the approach for tracking cooking plans in the presence of noisy and incomplete observations.

Lifted inference algorithms are able to boost efficiency through  exploiting symmetries and exchangeability of the underling  first-order probabilistic models.  Models with transitive relations  (e.g., if X and Y are friends and so are Y and Z, then X and Z will  likely be friends) are essential in social network analysis. With   n elements in a transitive relation model, the computational  complexity of exact propositional inference is O(2 n ( n -1)/2 ),  making it intractable for large domains. However, no tractable exact  inference on the transitive relations has been reported on the  transitive relations. In this paper, we report a novel deterministic  approximate lifted inference algorithm, which efficiently solves  inference problems on the transitive relations without degenerating  input models. We introduce an alternative graph representation for  first-order probabilistic models with formulas of homogeneous  bivariate predicates. The new representation, which is closely  related to exponential-family random graph models, leads to an  efficient deterministic approximate lifting algorithm by exploiting  the asymptotic properties of the state space. We perform experiments  to verify the effectiveness of the proposed algorithm.

Modal Markov Logic for a single agent has previously been proposed as an extension to propositional Markov logic. While the framework allowed reasoning under the principle of maximum entropy for various modal logics, it is not feasible to apply its counting based inference to reason about the beliefs and knowledge of multiple agents due to magnitude of the numbers involved. We propose a modal extension of propositional Markov logicthat avoids this problem by coarsening the state space.The problem stems from the fact that in the single-agent setting, the state space is only doubly exponential in the number of propositions in the domain, but the state space can potentially become infinite in the multi-agent setting. In addition, the proposed framework adds only the overhead of deciding satisfiability for the chosen modal logic on the top of the complexity of exact inference in propositional Markov logic. The proposed framework allows one to find a distribution that matches probabilities of formulas obtained from training data (or provided by an expert). Finally, we show how one can compute lower and upper bounds on probabilities of arbitrary formulas.

RockIt is a maximum a-posteriori (MAP) query engine for statistical relational models. MAP inference in graphical models is an optimization problem which can be compiled to integer linear programs (ILPs). We describe several advances in translating MAP queries to ILP instances and present the novel meta-algorithm cutting plane aggregation (CPA). CPA exploits local context-specific symmetries and bundles up sets of linear constraints. The resulting counting constraints lead to more compact ILPs and make the symmetry of the ground model more explicit to state-of-the-art ILP solvers. Moreover, RockIt parallelizes most parts of the MAP inference pipeline taking advantage of ubiquitous shared-memory multi-core architectures. We report on extensive experiments with Markov logic network (MLN) benchmarks showing that RockIt outperforms the state-of-the-art systems Alchemy, Markov TheBeast, and Tuffy both in terms of efficiency and quality of results. This paper is a short version of a AAAI publication of the same name.

Relational Markov Decision Processes (RMDPs) offer an elegant formalism that combines probabilistic and relational knowledge representations with the decision-theoretic notions of action and utility. In this paper we motivate RMDPs to address a variety of problems in AI, including open world planning, transfer learning, and relational inference. We describe a symbolic dynamic programming approach via the "template method" which addresses the problem of reasoning about exogenous events. We end with a discussion of the challenges involved and some promising future research directions.

The introduction of Electric Vehicles (EVs) in the existing Energy Grid raises many issues regarding Grid stability and charging behavior. Uncontrolled charging on the customer’s side may increase the already high peaks in the energy demand that lead to respective increase in the energy prices.We propose a novel smart charging algorithm that maximizes individual welfare and reduces the individual energy expenses. We use Reinforcement Learning trained on real world data to learn the individual household consumption behavior and propose a charging algorithm with respect to individual welfare maximization objective. Furthermore, we use statistical customer models to simulate the EV customer behavior. We show that the individual customers, represented by intelligent agents, using the proposed charging algorithm reduce their energy expenses. Additionally, we show that the average energy prices, on an aggregated level, are reduced as a result of smarter use of the energy available. Finally we prove that the presented algorithm achieves significant peak reduction and reshaping of the energy demand curve.

The PowerTAC competition focuses on trading activities in energy markets. One of the important subtasks of designing an effective agent for this scenario is to predict the energy use and generation of the customer agents in the marketplace. These predictions can inform pricing and tariff design questions, as well as decisions to balance power use and generation over time. Similar prediction problems are also important in real world energy markets. Here we present some initial experiments applying machine learning to predict future customer energy usage patterns in the PowerTAC simulation.

Personal communication and relationships within spatially distributed or separated groups can be difficult to establish and maintain. A promising approach investigated with respect to this problem are ambient intelligence and smart environments equipped with perception and communication technology. These technologies require a standardized way to access sensors, actuators, and to develop applications for them to be usable. Furthermore, they have to address concerns like privacy in order to be accepted. We propose a middleware based on a distributed reasoning concept and a qualitative spatial privacy aware representation to address these requirements.