Author name cluster

Alexandre Niveau

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

11 papers

2 author rows

ECAI Conference 2025 Conference Paper

Post-Hoc Interpretation of POMDP Policies

Geoffrey Laforest
Olivier Buffet
Alexandre Niveau
Bruno Zanuttini

Policies for partially observable Markov decision processes are rich objects, prescribing actions to take depending on the whole history of observations and actions. Typical representations of such policies are by hyperplanes in the space of belief states, or by finite-state controllers, which are arguably not easy to interpret. We propose to redescribe policies into mappings defined on features of the current belief state, built in a systematic manner from state features. Such a mapping can in turn be represented by an intelligible object, like a decision tree, thereby providing an interpretable representation of the policy as a whole. We moreover show how our approach allows to explain the decision taken by an agent at each step of an interaction with the environment. This provides an end-to-end process, starting from a policy computed by any solver, and ending with an explanation of each decision made at execution time. We formally define our approach, investigate related computational problems, and report on experiments on several families of problems.

Details

AAMAS Conference 2022 Conference Paper

A Symbolic Representation for Probabilistic Dynamic Epistemic Logic

Sébastien Gamblin
Alexandre Niveau
Maroua Bouzid

Probabilistic Dynamic Epistemic Logic (PDEL) is a formalism for reasoning about the higher-order probabilistic knowledge of agents, and about how this knowledge changes when events occur. While PDEL has been studied for its theoretical appeal, it was only ever applied to toy examples: the combinatorial explosion of probabilistic Kripke structures makes the PDEL framework impractical for realistic applications, such as card games. This paper is a first step towards the use of PDEL in more practical settings: in line with recent work applying ideas from symbolic model checking to (non-probabilistic) DEL, we propose a “symbolic” representation of probabilistic Kripke structures as pseudo-Boolean functions, which can be represented with several data structures of the decision diagram family, in particular Algebraic Decision Diagrams (ADDs). We show that ADDs scale much better than explicit Kripke structures, and that they allow for efficient symbolic model checking, even on the realistic example of the Hanabi card game, thus paving the way towards the practical application of epistemic planning techniques.

PDF

ICAPS Conference 2021 Conference Paper

Knowledge Compilation for Nondeterministic Action Languages

Sergej Scheck
Alexandre Niveau
Bruno Zanuttini

We study different languages for representing nondeterministic actions in planning from the point of view of knowledge compilation. Precisely, we consider succintness issues (how succinct is the description of an action in each language?) and complexity issues (tractability or hardness of several queries which arise naturally in planning and belief tracking). We study an abstract, nondeterministic version of PDDL, nondeterministic conditional STRIPS, the language NNFAT of NNF action theories, and the language NPDDLseq obtained by adding a sequence operator to nondeterministic PDDL. We show that these languages have different succinctness and different complexity even for the most natural queries.

Details

IJCAI Conference 2019 Conference Paper

Hintikka's World: Scalable Higher-order Knowledge

Tristan Charrier
Sébastien Gamblin
Alexandre Niveau
François Schwarzentruber

Hintikka's World is a graphical and pedagogical tool that shows how artificial agents can reason about higher-order knowledge. In this demonstration paper, we present the implementation of symbolic models in Hintikka's World. They enable the tool to scale, by helping it to face the state explosion, which makes it possible to provide examples featuring real card games, such as Hanabi.

PDF Details

AAAI Conference 2017 Conference Paper

Checking the Consistency of Combined Qualitative Constraint Networks

Quentin Cohen-Solal
Maroua Bouzid
Alexandre Niveau

We study the problem of consistency checking for constraint networks over combined qualitative formalisms. We propose a framework which encompasses loose integrations and a form of spatio-temporal reasoning. In particular, we identify sufﬁcient conditions ensuring the polynomiality of consistency checking, and we use them to ﬁnd tractable subclasses.

PDF Details

IJCAI Conference 2017 Conference Paper

Temporal Sequences of Qualitative Information: Reasoning about the Topology of Constant-Size Moving Regions

Quentin Cohen-Solal
Maroua Bouzid
Alexandre Niveau

Relying on the recently introduced multi-algebras, we present a general approach for reasoning about temporal sequences of qualitative information that is generally more efficient than existing techniques. Applying our approach to the specific case of sequences of topological information about constant-size regions, we show that the resulting formalism has a complete procedure for deciding consistency, and we identify its three maximal tractable subclasses containing all basic relations.

PDF Details

IJCAI Conference 2016 Conference Paper

Efficient Representations for the Modal Logic S5

Alexandre Niveau
Bruno Zanuttini

We investigate efficient representations of subjective formulas in the modal logic of knowledge, S5, and more generally of sets of sets of propositional assignments. One motivation for this study is contingent planning, for which many approaches use operations on such formulas, and can clearly take advantage of efficient representations. We study the language S5-DNF introduced by Bienvenu et al. , and a natural variant of it that uses Binary Decision Diagrams at the propositional level. We also introduce an alternative language, called Epistemic Splitting Diagrams, which provides more compact representations. We compare all three languages from the complexity-theoretic viewpoint of knowledge compilation and also through experiments. Our work sheds light on the pros and cons of each representation in both theory and practice.

PDF Details

IJCAI Conference 2015 Conference Paper

An Algebra of Granular Temporal Relations for Qualitative Reasoning

Quentin Cohen-Solal
Maroua Bouzid
Alexandre Niveau

In this paper, we propose a qualitative formalism for representing and reasoning about time at different scales. It extends the algebra of Euzenat [2001] and overcomes its major limitations, allowing one to reason about relations between points and intervals. Our approach is more expressive than the other algebras of temporal relations: for instance, some relations are more relaxed than those in Allen’s [1983] algebra, while others are stricter. In particular, it enables the modeling of imprecise, gradual, or intuitive relations, such as “just before” or “almost meet”. In addition, we give several results about how a relation changes when considered at different granularities. Finally, we provide an algorithm to compute the algebraic closure of a temporal constraint network in our formalism, which can be used to check its consistency.

PDF Details

AAAI Conference 2014 Conference Paper

A Knowledge Compilation Map for Ordered Real-Valued Decision Diagrams

Hélène Fargier
Pierre Marquis
Alexandre Niveau
Nicolas Schmidt

Valued decision diagrams (VDDs) are data structures that represent functions mapping variable-value assignments to non-negative real numbers. They prove useful to compile cost functions, utility functions, or probability distributions. While the complexity of some queries (notably optimization) and transformations (notably conditioning) on VDD languages has been known for some time, there remain many significant queries and transformations, such as the various kinds of cuts, marginalizations, and combinations, the complexity of which has not been identified so far. This paper contributes to filling this gap and completing previous results about the time and space efficiency of VDD languages, thus leading to a knowledge compilation map for real-valued functions. Our results show that many tasks that are hard on valued CSPs are actually tractable on VDDs.

PDF Details

IJCAI Conference 2013 Conference Paper

Towards a Knowledge Compilation Map for Heterogeneous Representation Languages

Hélène Fargier
Pierre Marquis
Alexandre Niveau

The knowledge compilation map introduced by Darwiche and Marquis takes advantage of a number of concepts (mainly queries, transformations, expressiveness, and succinctness) to compare the relative adequacy of representation languages to some AI problems. However, the framework is limited to the comparison of languages that are interpreted in a homogeneous way (formulæ are interpreted as Boolean functions). This prevents one from comparing, on a formal basis, languages that are close in essence, such as OBDD, MDD, and ADD. To fill the gap, we present a generalized framework into which comparing formally heterogeneous representation languages becomes feasible. In particular, we explain how the key notions of queries and transformations, expressiveness, and succinctness can be lifted to the generalized setting.

PDF Details DOI

ECAI Conference 2010 Conference Paper

Knowledge Compilation Using Interval Automata and Applications to Planning

Alexandre Niveau
Hélène Fargier
Cédric Pralet
Gérard Verfaillie

Knowledge compilation [6, 5, 14, 8] consists in transforming a problem offline into a form which is tractable online. In this paper, we introduce new structures, based on the notion of interval automaton (IA), adapted to the compilation of problems involving both discrete and continuous variables, and especially of decision policies and transition tables, in the purpose of controlling autonomous systems.

Details