Despite their expressive power in representing alternatives or beliefs tainted by incomparabilities, it is often difficult to use generic partial orders. Hence, various structures have been historically studied in the literature, such as weak orders, semiorders or interval orders, each capturing a different fragment of partial orders. In this article, we propose and study in detail a fragment rich enough to represent some highly intuitive patterns involving incomparable elements that cannot be captured by the aforementioned fragments: partitioned linear orders (PLOs). These structures can be viewed as split independent linear orders, each one of them representing a local totally ranked situation. Then, we show how they can be used in Katsuno-Mendelzon-style belief revision. We propose a set of postulates, a representation theorem and a family of concrete operators.

International audience

Rational agents’ decisions are driven by their intentions, in the sense that agents execute actions that most probably lead to situations where their intentions are achieved. Using that insight, this paper proposes a method for ‘intention checking’: let a description of a game, a state and the action executed by the agent at that state be given, the method checks whether the agent acted with the intention to reach a situation where some proposition ‘p’ is true. We use a logic with epistemic and temporal operators to reason about games and extend it with an intention operator ‘IX’. Formulas of the form ‘IX(p)’ are defined to be true in the situations where the intention check method verifies that the agent acts with the intention to achieve ‘p’ in the next state of the game. We show that this operator satisfies the principles of Bratman’s Asymmetry Thesis, and we also compare it to other theories of intention.

International audience

The aim of this paper is to highlight two important issues related to the annotation and querying of Intangible Cultural Heritage video datasets. First, we focus on ontology completion by annotating dance videos. In order to build video training sets and to enrich the proposed ontology, manual video annotation is performed based on background knowledge formalized in an ontology, representing a semantics of a traditional dance. The paper provides a case study on Malaysian Zapin dances. Second, we address the question of how can end-users efficiently query the datasets of annotated videos that are built.

Symmetry detection is a promising approach for reducing the search tree of games. In General Game Playing (GGP), where any game is compactly represented by a set of rules in the Game Description Language (GDL), the state-of-the-art methods for symmetry detection rely on a rule graph associated with the GDL description of the game. Though such rule-based symmetry detection methods can be applied to various tree search algorithms, they cover only a limited number of symmetries which are apparent in the GDL description. In this paper, we develop an alternative approach to symmetry detection in stochastic games that exploits constraint programming techniques. The minimax optimization problem in a GDL game is cast as a stochastic constraint satisfaction problem (SCSP), which can be viewed as a sequence of one-stage SCSPs. Minimax symmetries are inferred according to themicrostructure complement of these one-stage constraint networks. Based on a theoretical analysis of this approach, we experimentally show on various games that the recent stochastic constraint solver MAC-UCB, coupled with constraint-based symmetry detection, significantly outperforms the standard Monte Carlo Tree Search algorithms, coupled with rule-based symmetry detection. This constraint-driven approach is also validated by the excellent results obtained by our player during the last GGP competition.

This paper proposes interval-based possibilistic networks. This extension allows to compactly encode and reason with epistemic uncertainty and imprecise beliefs as well as with multiple expert knowledge. We propose a natural semantics based on compatible possibilistic networks. The paper shows finally that computing uncertainty bounds of an event can be done in interval-based networks without extra computational cost.

Possibilistic logic is a well-known framework for dealing with uncertainty and reasoning under inconsistent knowledge bases. Standard possibilistic logic expressions are propositional logic formulas associated with positive real degrees belonging to [0,1]. However, in practice it may be difficult for an expert to provide exact degrees associated with formulas of a knowledge base. This paper proposes a flexible representation of uncertain information where the weights associated with formulas are in the form of intervals. We first study a framework for reasoning with interval-based possibilistic knowledge bases by extending main concepts of possibilistic logic such as the ones of necessity and possibility measures. We then provide a characterization of an interval-based possibilistic logic base by means of a concept of compatible standard possibilistic logic bases. We show that intervalbased possibilistic logic extends possibilistic logic in the case where all intervals are singletons. Lastly, we provide computational complexity results of deriving plausible conclusions from interval-based possibilistic bases and we show that the flexibility in representing uncertain information is handled without extra computational costs.

In the last decade, several approaches have been proposed for merging multiple and potentially conflicting pieces of information. Egalitarian fusion modes pick solutions that minimize the local dissatisfaction of each source (agent, expert), which is involved in the fusion process. When pieces of information to merge are prioritized, or ranked, most existing approaches assume that these priority degrees are commensurable, namely sources are assumed to share the same meaning of uncertainty scales. This article provides useful strategies for an egalitarian fusion of incommensurable ranked belief bases under constraints. In particular, it focuses on Max-based merging operators, and proposes a merging operator that allows to aggregate a set of ranked belief bases E. This operator is based on the concept of compatible scales. We provide three equivalent characterizations of this operator. The first one shows that Max-based merging of incommensurable belief bases can also be defined in terms of a Pareto-like ordering on possible worlds, denominated SMP ordering. The second one is based on the notion of compatible rankings defined on finite scales. The third one is only based on total pre-orders induced by ranked bases to merge. The last part of the article analyses rational postulates satisfied by our merging operator and compare it with some related works.

Recently, several approaches have been proposed to merge possibly contradictory belief bases. This paper focuses on max-based merging operators applied to incommensurable ranked belief bases. We first propose a characterization of a result of merging using Pareto-like ordering on a set of possible solutions. Then we propose two equivalent ways to recover the result of merging. The first one is based on the notion of compatible rankings defined on finite scales. The second one is only based on total pre-orders induced by ranked bases to merge.

This paper deals with iterated belief change. Epistemic states are suitable to represent an intelligent agent's knowledge. Most of the time, when dealing with geographic information, the agent faces incomplete, uncertain, or inaccurate information and needs a mechanism for either revision, update, or fusion to handle their change in beliefs in the presence of new items of information. After some preliminaries on the representation of epistemic states by means of pre-orders, the paper presents three approaches to belief change: revision, update, and fusion. For each of these approaches, the background, postulates, representation by pre-orders, and semantic and syntactic requirements are given. In each case, the approaches are illustrated by examples.

This paper deals with the extraction of default rules from a database of examples. The proposed approach is based on a special kind of probability distributions, called "big-stepped probabilities", which are known to provide a semantics for non-monotonic reasoning. The rules which are learnt are genuine default rules, which could be used (under some conditions) in a non-monotonic reasoning system and can be encoded in possibilistic logic.