Collaborating Authors

Belief Revision

Distributing Collaborative Multi-Robot Planning with Gaussian Belief Propagation


Precise coordinated planning enables safe and highly efficient motion when many robots must work together in tight spaces, but this would normally require centralised control of all devices which is difficult to scale. We demonstrate a new purely distributed technique based on Gaussian Belief Propagation on multi-robot planning problems formulated by a generic factor graph defining dynamics and collision constraints. We show that our method allows extremely high performance collaborative planning in a simulated road traffic scenario, where vehicles are able to cross each other at a busy multi-lane junction while maintaining much higher average speeds than alternative distributed planning techniques. We encourage the reader to view the accompanying video demonstration to this work at

Goal Recognition as Reinforcement Learning Artificial Intelligence

Most approaches for goal recognition rely on specifications of the possible dynamics of the actor in the environment when pursuing a goal. These specifications suffer from two key issues. First, encoding these dynamics requires careful design by a domain expert, which is often not robust to noise at recognition time. Second, existing approaches often need costly real-time computations to reason about the likelihood of each potential goal. In this paper, we develop a framework that combines model-free reinforcement learning and goal recognition to alleviate the need for careful, manual domain design, and the need for costly online executions. This framework consists of two main stages: Offline learning of policies or utility functions for each potential goal, and online inference. We provide a first instance of this framework using tabular Q-learning for the learning stage, as well as three measures that can be used to perform the inference stage. The resulting instantiation achieves state-of-the-art performance against goal recognizers on standard evaluation domains and superior performance in noisy environments.

Inference with System W Satisfies Syntax Splitting Artificial Intelligence

In this paper, we investigate inductive inference with system W from conditional belief bases with respect to syntax splitting. The concept of syntax splitting for inductive inference states that inferences about independent parts of the signature should not affect each other. This was captured in work by Kern-Isberner, Beierle, and Brewka in the form of postulates for inductive inference operators expressing syntax splitting as a combination of relevance and independence; it was also shown that c-inference fulfils syntax splitting, while system P inference and system Z both fail to satisfy it. System W is a recently introduced inference system for nonmonotonic reasoning that captures and properly extends system Z as well as c-inference. We show that system W fulfils the syntax splitting postulates for inductive inference operators by showing that it satisfies the required properties of relevance and independence. This makes system W another inference operator besides c-inference that fully complies with syntax splitting, while in contrast to c-inference, also extending rational closure.


AAAI Conferences

Belief revision studies strategies about how agents revise their belief states when receiving new evidence. Both in classical belief revision and in epistemic revision, a new input is either in the form of a (weighted) propositional formula or a total pre-order (where the total pre-order is considered as a whole). However, in some real-world applications, a new input can be a partial pre-order where each unit that constitutes the partial pre-order is important and should be considered individually. To address this issue, in this paper, we study how a partial pre-order representing the prior epistemic state can be revised by another partial pre-order (the new input) from a different perspective, where the revision is conducted recursively on the individual units of partial pre-orders. We propose different revision operators (rules), dubbed the extension, match, inner and outer revision operators, from different revision points of view. We also analyze several properties for these operators.


AAAI Conferences

Belief merging aims at extracting a coherent and informative view from a set of belief bases. A first requirement for belief merging operators is to obey basic rationality conditions. Another expected property is to preserve as much information as possible from the input bases. In this paper, we show how new merging operators, called compositional operators, can be defined from existing ones. Such operators aim at offering a higher discriminative power than the merging operators on which they are based, without leading to a complexity shift or losing rationality postulates. We identify some sufficient conditions for ensuring that rationality is fully preserved by composition.


AAAI Conferences

An agent will generally have incomplete and possibly inaccurate knowledge about its environment. In addition, such an agent may receive erroneous information, perhaps in being misinformed about the truth of some formula. In this paper we present a general approach to reasoning about action and belief change in such a setting. An agent may carry out actions, but in some cases may inadvertently execute the wrong one (for example, pushing an unintended button). As well, an agent may sense whether a condition holds, and may revise its beliefs after being told that a formula is true. Our approach is based on an epistemic extension to basic action theories expressed in the situation calculus, augmented by a plausibility relation over situations. This plausibility relation can be thought of as characterising the agent's overall belief state; as such it keeps track of not just the formulas that the agent believes to hold, but also the plausibility of formulas that it does not believe to hold. The agent's belief state is updated by suitably modifying the plausibility relation following the execution of an action. We show that our account generalises previous approaches, and fully handles belief revision, sensing, and erroneous actions.


AAAI Conferences

In Belief Revision the new information is generally accepted, following the principle of primacy of update. In some case this behavior can be criticized and one could require that some new pieces of information can be rejected by the agent because, for instance, of insufficient plausibility. This has given rise to several approaches of non-prioritized Belief Revision. In particular (Hansson et al. 2001) defined credibility-limited revision operators, where a revision is accepted only if the new information is a formula that belongs to a set of credible formulas. They provide several representation theorems in the AGM style. In this work we study credibility-limited revision operators when the information is represented in propositional logic, like in the Katsuno and Mendelzon framework. We propose a set of postulates and a representation theorem for credibility-limited revision operators. Then we explore how to generalize these definitions to the Iterated Belief Revision case, using epistemic states in the Darwiche and Pearl style.


AAAI Conferences

Belief change studies how to update knowledge bases used for reasoning. Traditionally belief revision has been based on full propositional logic. However, reasoning with full propositional knowledge bases is computationally hard, whereas reasoning with Horn knowledge bases is fast. In the past several years, there has been considerable work in belief revision theory on developing a theory of belief contraction for knowledge represented in Horn form. Our main focus here is the computational complexity of belief contraction, and, in particular, of various methods and approaches suggested in the literature.


AAAI Conferences

In this paper, we address the problem of applying AGM-style belief revision to non-classical logics. We discuss the idea of minimal change in revision and show that for non-classical logics, some sort of minimality postulate has to be explicitly introduced. We also present two constructions for revision which satisfy the AGM postulates and prove the representation theorems including minimality postulates.


AAAI Conferences

Belief revision is an operation that aims at modifying old beliefs so that they become consistent with new ones. The issue of belief revision has been studied in various formalisms, in particular, in qualitative algebras (QAs) in which the result is a disjunction of belief bases that is not necessarily representable in a QA. This motivates the study of belief revision in formalisms extending QAs, namely, their propositional closures: in such a closure, the result of belief revision belongs to the formalism. Moreover, this makes it possible to define a contraction operator thanks to the Harper identity. Belief revision in the propositional closure of QAs is studied, an algorithm for a family of revision operators is designed, and an open-source implementation is made freely available on the web.