Arrow Research search

Author name cluster

Andreas Herzig

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.

81 papers
2 author rows

Possible papers

81

AAAI Conference 2025 Conference Paper

Minimal Change in Modal Logic S5

  • Carlos Aguilera-Ventura
  • Jonathan Ben-Naim
  • Andreas Herzig

We extend belief revision theory from propositional logic to the modal logic S5. Our first contribution takes the form of three new postulates (M1-M3) that go beyond the AGM ones and capture the idea of minimal change in the presence of modalities. Concerning the construction of modal revision operations, we work with set pseudo-distances, i.e., distances between sets of points that may violate the triangle-inequality. Our second contribution is the identification of three axioms (A3-A5) that go beyond the standard axioms of metrics. Loosely speaking, our main result states the following: if a pseudo-distance satisfies certain axioms, then the induced revision operation satisfies (M1-M3). We investigate three pseudo-distances from the literature (Dhaus, Dinj, Dsum), and the three induced revision operations (*Haus, *Inj, *Sum). Using our main result, we show that only *Sum satisfies (M1-M3) all together. As a last contribution, we revisit a major criticism of AGM operations, namely that the revisions of (p ∧ q) and (p ∧ (p → q)) are identical. We show that the problem disappears if instead of material implication we use the modal operator of strict implication that can be defined in S5.

PDF Details DOI

NMR Workshop 2025 Conference Paper

On the Logic of Theory Base Change: Reformulation of Belief Bases

  • Eduardo L. Fermé
  • Andreas Herzig
  • Maria Vanina Martinez

In the logic of theory change, the AGM model has acquired the status of a standard model. However, the AGM model does not seem adequate for some contexts and application domains. This inspired many researchers to propose extensions and generalizations to AGM. Among these extensions, one of the most important are belief bases. Belief bases have more expressivity than belief sets, as explicit and implicit beliefs have different statuses. In this paper, we present reformulation, a belief change operation that allows us to reformulate a belief base making some particular sentences explicit without modifying the consequences of the belief base. We provide a constructive method and its axiomatic characterization.

Details

AAAI Conference 2025 Conference Paper

On the Logic of Theory Base Change: Reformulation of Belief Bases

  • Eduardo L. Fermé
  • Andreas Herzig
  • Maria Vanina Martinez

In the logic of theory change, the AGM model has acquired the status of a standard model. However, the AGM model does not seem adequate for some contexts and application domains. This inspired many researchers to propose extensions and generalizations to AGM. Among these extensions, one of the most important are belief bases. Belief bases have more expressivity than belief sets, as explicit and implicit beliefs have different statuses. In this paper, we present reformulation, a belief change operation that allows us to reformulate a belief base making some particular sentences explicit without modifying the consequences of the belief base. We provide a constructive method and its axiomatic characterization.

PDF Details DOI

ECAI Conference 2024 Conference Paper

A Novel View of Analogical Proportion Between Formulas

  • Andreas Herzig
  • Emiliano Lorini
  • Henri Prade

Analogical proportions are statements of the form “α is to β as γ is to δ”, noted α: β: :γ: δ, and can be understood as “α differs from β as γ differs from δ” and conversely “β differs from α as δ differs from γ”. In this paper, α, β, γ, δ are supposed to be propositional logic formulas, which are appropriate for representing concepts. There exists one approach, developed over the last 15 years, where “α differs from β” is understood in terms of the negation of the material implication α → β. The paper investigates another view where “α differs from β” is interpreted in terms of transformations where some variables become false, some variables become true, and some variables become irrelevant. Both approaches satisfy the three basic postulates of analogical proportions (reflexivity, symmetry, and stability under central permutation), as well as other interesting properties such as transitivity and unicity of δ such that α: β: :γ: δ. However, the two approaches depart from each other since they do not validate the same analogical proportions. In particular, when p, q, r are atoms the proportion p: (p∧r): :q: (q∧r) holds in the new approach, while it fails to do so for the other. The new approach exhibits also a good behaviour with respect to integrity constraints. It is advocated that this makes it appropriate for handling analogy between concepts, while the other approach has proved to be fruitful for Boolean features-based representations. The paper provides a thorough analysis of the differences between the two approaches.

Details

AAAI Conference 2024 Conference Paper

Towards Epistemic-Doxastic Planning with Observation and Revision

  • Thorsten Engesser
  • Andreas Herzig
  • Elise Perrotin

Epistemic planning is useful in situations where multiple agents have different knowledge and beliefs about the world, such as in robot-human interaction. One aspect that has been largely neglected in the literature is planning with observations in the presence of false beliefs. This is a particularly challenging problem because it requires belief revision. We introduce a simple specification language for reasoning about actions with knowledge and belief. We demonstrate our approach on well-known false-belief tasks such as the Sally-Anne Task and compare it to other action languages. Our logic leads to an epistemic planning formalism that is expressive enough to model second-order false-belief tasks, yet has the same computational complexity as classical planning.

PDF Details DOI

KR Conference 2023 Conference Paper

Counterfactual Reasoning via Grounded Distance

  • Carlos Aguilera-Ventura
  • Andreas Herzig
  • Xinghan Liu
  • Emiliano Lorini

Conditional logics are usually interpreted in terms of closest world and minimal change. It relies on a measure of distance between worlds which is defined abstractly, i. e. as an element of the model. The typical example of a concrete measure in literature is the Hamming distance. We show that given countably infinite atomic propositions in the language, Hamming distance is not merely an example, but grounded for two arguably most important conditional logics, Lewis' VC and VCU. That means, a formula is satisfied in a VC (resp. VCU) model, if and only if it is satisfied in a VC (resp. VCU) model whose distance between worlds is Hammingian.

PDF Details DOI

IJCAI Conference 2022 Conference Paper

A Computationally Grounded Logic of 'Seeing-to-it-that'

  • Andreas Herzig
  • Emiliano Lorini
  • Elise Perrotin

We introduce a simple model of agency that is based on the concepts of control and attempt. Both relate agents and propositional variables. Moreover, they can be nested: an agent i may control whether another agent j controls a propositional variable p; i may control whether j attempts to change p; i may attempt to change whether j controls p; i may attempt to change whether j attempts to change p; and so on. In this framework we define several modal operators of time and agency: the LTL operators on the one hand, and the Chellas and the deliberative stit operator on the other. While in the standard stit framework the model checking problem is unfeasible because its models are infinite, in our framework models are represented in a finite and compact way: they are grounded on the primitive concepts of control and attempt. This makes model checking practically feasible. We prove its PSPACE-completeness and we show how the concept of social influence can be captured.

PDF Details DOI

KR Conference 2021 Short Paper

A Dynamic Epistemic Logic with Finite Iteration and Parallel Composition

  • Andreas Herzig
  • Frédéric Maris
  • Elise Perrotin

Existing dynamic epistemic logics combine standard epistemic logic with a restricted version of dynamic logic. Instead, we here combine a restricted epistemic logic with a rich version of dynamic logic. The epistemic logic is based on `knowing-whether' operators and basically disallows disjunctions and conjunctions in their scope; it moreover captures `knowing-what'. The dynamic logic has not only all the standard program operators of Propositional Dynamic Logic, but also parallel composition as well as an operator of inclusive nondeterministic composition; its atomic programs are assignments of propositional variables. We show that the resulting dynamic epistemic logic is powerful enough to capture several kinds of sequential and parallel planning, and so both in the unbounded and in the finite horizon version.

PDF Details DOI

LAMAS&SR Workshop 2021 Workshop Paper

Epistemic Reasoning about Rationality and Bids in Auctions

  • Munyque Mittelmann
  • Andreas Herzig
  • Laurent Perrussel

The goal of this work is to investigate strategic reasoning in the context of auctions. More precisely, we establish an explicit link between the agents’ choice of bidding actions and bounded rationality. To do so, we extend the Auction Description Language with an epistemic operator and a choice operator and use it to represent a classical auction where agents have imperfect information about other bidders’ valuations. We formalize bounded rationality concepts in iterative protocols and show how to use them to reason about the players’ actions. Finally, we provide a model checking algorithm.

PDF Details

JELIA Conference 2021 Conference Paper

Epistemic Reasoning About Rationality and Bids in Auctions

  • Munyque Mittelmann
  • Andreas Herzig
  • Laurent Perrussel

Abstract In this paper, we investigate strategic reasoning in the context of auctions. More precisely, we establish an explicit link between bidding actions and bounded rationality. To do so, we extend the Auction Description Language with an epistemic operator and an action choice operator and use it to represent a classical auction where agents have imperfect information about other agents’ valuations. We formalize bounded rationality concepts in iterative protocols and show how to use them to reason about the players’ actions. Finally, we provide a model checking algorithm.

Details

IJCAI Conference 2021 Conference Paper

Multi-Agent Abstract Argumentation Frameworks With Incomplete Knowledge of Attacks

  • Andreas Herzig
  • Antonio Yuste Ginel

We introduce a multi-agent, dynamic extension of abstract argumentation frameworks (AFs), strongly inspired by epistemic logic, where agents have only partial information about the conflicts between arguments. These frameworks can be used to model a variety of situations. For instance, those in which agents have bounded logical resources and therefore fail to spot some of the actual attacks, or those where some arguments are not explicitly and fully stated (enthymematic argumentation). Moreover, we include second-order knowledge and common knowledge of the attack relation in our structures (where the latter accounts for the state of the debate), so as to reason about different kinds of persuasion and about strategic features. This version of multi-agent AFs, as well as their updates with public announcements of attacks (more concretely, the effects of these updates on the acceptability of an argument) can be described using S5-PAL, a well-known dynamic-epistemic logic. We also discuss how to extend our proposal to capture arbitrary higher-order attitudes and uncertainty.

PDF Details DOI

KR Conference 2021 Short Paper

On the Epistemic Logic of Incomplete Argumentation Frameworks

  • Andreas Herzig
  • Antonio Yuste-Ginel

We study the relation between two existing formalisms: incomplete argumentation frameworks (IAFs) and epistemic logic of visibility (ELV). We show that the set of completions of a given IAF naturally corresponds to a specific equivalence class of possible worlds within the model of visibility. This connection is further strengthened in two directions. First, we show how to reduce argument acceptance problems of IAFs to ELV model-checking problems. Second, we highlight the epistemic assumptions that underlie IAFs by providing a minimal epistemic logic for IAFs.

PDF Details DOI

ECAI Conference 2020 Conference Paper

A Logic of Explicit and Implicit Distributed Belief

  • Andreas Herzig
  • Emiliano Lorini
  • Elise Perrotin
  • Fabián Romero
  • François Schwarzentruber

We present a new logic of explicit and implicit distributed belief with a formal semantics exploiting the notion of belief base. A coalition’s distributed belief of explicit type corresponds to a piece of information contained in the collective belief base of the coalition, which is obtained by pooling together the individual belief bases of its members. A coalition’s distributed belief of implicit type corresponds to a piece of information that is derivable from the collective belief base of the coalition. We study axiomatic aspects of our logic as well as complexity of model checking. As distributed belief can be inconsistent (contrary to distributed knowledge), we also study a consistency-preserving variant of distributed belief inspired by the literature on belief merging.

Details

KR Conference 2020 Conference Paper

Lightweight Parallel Multi-Agent Epistemic Planning

  • Martin Cooper
  • Andreas Herzig
  • Frédéric Maris
  • Elise Perrotin
  • Julien Vianey

We study a simple version of multi-agent epistemic planning where the number of parallel steps has to be minimized. We prove that this extension of classical planning is in PSPACE. We propose an encoding in PDDL and present some experiments providing evidence that this encoding allows us to solve practical problems. The types of problems we can encode include problems in which one agent can teach another agent how to perform a task and communication problems where some information must not be revealed to some agents.

PDF Details DOI

AAAI Conference 2020 Conference Paper

Refining HTN Methods via Task Insertion with Preferences

  • Zhanhao Xiao
  • Hai Wan
  • Hankui Hankz Zhuo
  • Andreas Herzig
  • Laurent Perrussel
  • Peilin Chen

Hierarchical Task Network (HTN) planning is showing its power in real-world planning. Although domain experts have partial hierarchical domain knowledge, it is time-consuming to specify all HTN methods, leaving them incomplete. On the other hand, traditional HTN learning approaches focus only on declarative goals, omitting the hierarchical domain knowledge. In this paper, we propose a novel learning framework to refine HTN methods via task insertion with completely preserving the original methods. As it is difficult to identify incomplete methods without designating declarative goals for compound tasks, we introduce the notion of prioritized preference to capture the incompleteness possibility of methods. Specifically, the framework first computes the preferred completion profile w. r. t. the prioritized preference to refine the incomplete methods. Then it finds the minimal set of refined methods via a method substitution operation. Experimental analysis demonstrates that our approach is effective, especially in solving new HTN planning instances.

PDF Details

IJCAI Conference 2020 Conference Paper

TouIST: a Friendly Language for Propositional Logic and More

  • Jorge Fernandez
  • Olivier Gasquet
  • Andreas Herzig
  • Dominique Longin
  • Emiliano Lorini
  • Frédéric Maris
  • Pierre Régnier

This work deals with logical formalization and problem solving using automated solvers. We present the automatic translator TouIST that provides a simple language to generate logical formulas from a problem description. Our tool allows us to model many static or dynamic combinatorial problems and to benefit from the regular improvements of SAT, QBF or SMT solvers in order to solve these problems efficiently. In particular, we show how to use TouIST to solve different classes of planning tasks in Artificial Intelligence.

PDF Details DOI

IJCAI Conference 2019 Conference Paper

Dynamic logic of parallel propositional assignments and its applications to planning

  • Andreas Herzig
  • Frédéric Maris
  • Julien Vianey

We introduce a dynamic logic with parallel composition and two kinds of nondeterministic composition, exclusive and inclusive. We show PSPACE completeness of both the model checking and the satisfiability problem and apply our logic to sequential and parallel classical planning where actions have conditional effects.

PDF Details

IJCAI Conference 2019 Conference Paper

Stratified Evidence Logics

  • Philippe Balbiani
  • David Fernández-Duque
  • Andreas Herzig
  • Emiliano Lorini

Evidence logics model agents' belief revision process as they incorporate and aggregate information obtained from multiple sources. This information is captured using neighbourhood structures, where individual neighbourhoods represent pieces of evidence. In this paper we propose an extended framework which allows one to explicitly quantify either the number of evidence sets, or effort, needed to justify a given proposition, provide a complete deductive calculus and a proof of decidability, and show how existing frameworks can be embedded into ours.

PDF Details

JELIA Conference 2019 Conference Paper

The Dynamic Logic of Policies and Contingent Planning

  • Thomas Bolander
  • Thorsten Engesser
  • Andreas Herzig
  • Robert Mattmüller
  • Bernhard Nebel

Abstract In classical deterministic planning, solutions to planning tasks are simply sequences of actions, but that is not sufficient for contingent plans in non-deterministic environments. Contingent plans are often expressed through policies that map states to actions. An alternative is to specify contingent plans as programs, e. g. in the syntax of Propositional Dynamic Logic (PDL). PDL is a logic for reasoning about programs with sequential composition, test and non-deterministic choice. However, as we show in the paper, none of the existing PDL modalities directly captures the notion of a solution to a planning task under non-determinism. We add a new modality to star-free PDL correctly capturing this notion. We prove the appropriateness of the new modality by showing how to translate back and forth between policies and PDL programs under the new modality. More precisely, we show how a policy solution to a planning task gives rise to a program solution expressed via the new modality, and vice versa. We also provide an axiomatisation of our PDL extension through reduction axioms into standard star-free PDL.

Details

EUMAS Conference 2018 Conference Paper

Temporal Epistemic Gossip Problems

  • Martin C. Cooper
  • Andreas Herzig
  • Frederic Maris
  • Julien Vianey

Abstract Gossip problems are planning problems where several agents have to share information (‘secrets’) by means of phone calls between two agents. In epistemic gossip problems the goal can be to achieve higher-order knowledge, i. e. , knowledge about other agents’ knowledge; to that end, in a call agents communicate not only secrets, but also agents’ knowledge of secrets, agents’ knowledge about other agents’ knowledge about secrets, etc. Temporal epistemic gossip problems moreover impose constraints on the times of calls. These constraints are of two kinds: either they stipulate that a call between two agents must necessarily be made at some time point, or they stipulate that a call can be made within some possible (set of) interval(s). In the non-temporal version, calls between two agents are either always possible or always impossible. We investigate the complexity of the plan existence problem in this general setting. Concerning the upper bound, we prove that it is in NP in the general case, and that it is in P when the problem is non-temporal and the goal is a positive epistemic formula. As for the lower bound, we prove NP-completeness for two fragments: problems with possibly negative goals even in the non-temporal case, and problems with temporal constraints even if the goal is a set of positive atoms.

Details

IJCAI Conference 2017 Conference Paper

Dynamic Logic for Data-aware Systems: Decidability Results

  • Francesco Belardinelli
  • Andreas Herzig

We introduce a first-order extension of dynamic logic (FO-DL), suitable to represent and reason about the behaviour of Data-aware Systems (DaS), which are systems whose data content is explicitly exhibited in the system’s description. We illustrate the expressivity of the formal framework by modelling English auctions as DaS, and by specifying relevant properties in FO-DL. Most importantly, we develop an abstraction-based verification procedure, thus proving that the model checking problem for DaS against FO-DL is actually decidable, provided some mild assumptions on the interpretationdomain.

PDF Details

IJCAI Conference 2017 Conference Paper

Hierarchical Task Network Planning with Task Insertion and State Constraints

  • Zhanhao Xiao
  • Andreas Herzig
  • Laurent Perrussel
  • Hai Wan
  • Xiaoheng Su

We extend hierarchical task network planning with task insertion (TIHTN) by introducing state constraints, called TIHTNS. We show that just as for TIHTN planning, all solutions of the TIHTNS planning problem can be obtained by acyclic decomposition and task insertion, entailing that its plan-existence problem is decidable without any restriction on decomposition methods. We also prove that the extension by state constraints does not increase the complexity of the plan-existence problem, which stays 2-NEXPTIME-complete, based on an acyclic progression operator. In addition, we show that TIHTNS planning covers not only the original TIHTN planning but also hierarchy-relaxed hierarchical goal network planning.

PDF Details

IJCAI Conference 2017 Conference Paper

Non-Determinism and the Dynamics of Knowledge

  • Davide Grossi
  • Andreas Herzig
  • Wiebe van der Hoek
  • Christos Moyzes

In this paper we attempt to shed light on the concept of an agent’s knowledge after a non-deterministic action is executed. We start by making a comparison between notions of non-deterministic choice, and between notions of sequential composition, of settings with dynamic and/or epistemic character; namely Propositional Dynamic Logic (PDL), Dynamic Epistemic Logic (DEL), and the more recent logic of Semi-Public Environments (SPE). These logics represent two different approaches for defining the aforementioned actions, and in order to provide unified frameworks that encompass both, we define the logics DELVO (DEL+Vision+Ontic change) and PDLVE (PDL+Vision+Epistemic operators). DELVO is given a sound and complete axiomatisation.

PDF Details

TARK Conference 2017 Conference Paper

Relaxing Exclusive Control in Boolean Games

  • Francesco Belardinelli
  • Umberto Grandi
  • Andreas Herzig
  • Dominique Longin
  • Emiliano Lorini
  • Arianna Novaro
  • Laurent Perrussel

In the typical framework for boolean games (BG) each player can change the truth value of some propositional atoms, while attempting to make her goal true. In standard BG goals are propositional formulas, whereas in iterated BG goals are formulas of Linear Temporal Logic. Both notions of BG are characterised by the fact that agents have exclusive control over their set of atoms, meaning that no two agents can control the same atom. In the present contribution we drop the exclusivity assumption and explore structures where an atom can be controlled by multiple agents. We introduce Concurrent Game Structures with Shared Propositional Control (CGS-SPC) and show that they ac- count for several classes of repeated games, including iterated boolean games, influence games, and aggregation games. Our main result shows that, as far as verification is concerned, CGS-SPC can be reduced to concurrent game structures with exclusive control. This result provides a polynomial reduction for the model checking problem of specifications in Alternating-time Temporal Logic on CGS-SPC.

Details DOI

IJCAI Conference 2017 Conference Paper

Strategically knowing how

  • Raul Fervari
  • Andreas Herzig
  • Yanjun Li
  • Yanjing Wang

In this paper, we propose a single-agent logic of goal-directed knowing how extending the standard epistemic logic of knowing that with a new knowing how operator. The semantics of the new operator is based on the idea that knowing how to achieve phi means that there exists a (uniform) strategy such that the agent knows that it can make sure phi. We give an intuitive axiomatisation of our logic and prove the soundness, completeness, and decidability of the logic. The crucial axioms relating knowing that and knowing how illustrate our understanding of knowing how in this setting. This logic can be used in representing and reasoning about knowledge-how.

PDF Details

ECAI Conference 2016 Conference Paper

A Simple Account of Multi-Agent Epistemic Planning

  • Martin C. Cooper
  • Andreas Herzig
  • Faustine Maffre
  • Frederic Maris
  • Pierre Régnier

A realistic model of multi-agent planning must allow us to formalize notions which are absent in classical planning, such as communication and knowledge. We investigate multi-agent planning based on a simple logic of knowledge that is grounded on the visibility of propositional variables. Using such a formal logic allows us to prove the existence of a plan given the description of the individual actions. We present an encoding of multi-agent planning problems expressed in this logic into the standard planning language PDDL. The solvability of a planning task is reduced to a model checking problem in a dynamic extension of our logic, proving its complexity. Feeding the resulting problem into a PDDL planner provides a provably correct plan for the original multi-agent planning problem. We apply our method on several examples such as the gossip problem.

Details

KR Conference 2016 Conference Paper

Building epistemic logic from observationsand public announcements

  • Tristan Charrier
  • Andreas Herzig
  • Emiliano Lorini
  • Faustine Maffre
  • Francois Schwarzentruber

As to the first problem, we adopt the solution of (Herzig, We study an epistemic logic where knowledge is built from what the agents observe (including higher-order visibility) and what the agents learn from public announcements. This fixes two main drawbacks of previous observability-based approaches where who sees what is common knowledge and where the epistemic operators distribute over disjunction. The latter forbids the modeling of most of the classical epistemic problems, starting with the muddy children puzzle. We integrate a dynamic dimension where both facts of the world and the agents’ observability can be modified by assignment programs. We establish that the model checking problem is PS PACE-complete.

IJCAI Conference 2016 Conference Paper

Epistemic Boolean Games Based on a Logic of Visibility and Control

  • Andreas Herzig
  • Emiliano Lorini
  • Faustine Maffre
  • Francois Schwarzentruber

We analyse epistemic boolean games ina computationally grounded dynamic epistemic logic. The agents' knowledge is determined by what they see, including higher-order visibility: agents may observe whether another agent observes an atom or not. The agents' actions consist in modifying the truth values of atoms. We provide an axiomatisation of the logic, establish that the model checking problem is in PSPACE, and show how one can reason about equilibria in epistemic boolean games.

PDF Details

JELIA Conference 2016 Conference Paper

On Hierarchical Task Networks

  • Andreas Herzig
  • Laurent Perrussel
  • Zhanhao Xiao

Abstract In planning based on hierarchical task networks (HTN), plans are generated by refining high-level actions (‘compound tasks’) into lower-level actions, until primitive actions are obtained that can be sent to execution. While a primitive action is defined by its precondition and effects, a high-level action is defined by zero, one or several methods: sets of (high-level or primitive) actions decomposing it together with a constraint. We give a semantics of HTNs in terms of dynamic logic with program inclusion. We propose postulates guaranteeing soundness and completeness of action refinement. We also show that hybrid planning can be analysed in the same dynamic logic framework.

Details

IJCAI Conference 2016 Conference Paper

On Logics of Strategic Ability Based on Propositional Control

  • Francesco Belardinelli
  • Andreas Herzig

Recently logics for strategic ability have gained pre-eminence in the modelisation and analysis of game-theoretic scenarios. In this paper we provide a contribution to the comparison of two popular frameworks: Concurrent Game Structures (CGS) and Coalition Logic of Propositional Control (CLPC). Specifically, we ground the abstract abilities of agents in CGS on Propositional Control, thus obtaining a class of CGS that has the same expressive power as CL-PC. We study the computational properties of this setting. Further, we relax some of the assumptions of CL-PC so as to introduce a wider class of computationally-grounded CGS.

PDF Details

JELIA Conference 2016 Conference Paper

Refinement of Intentions

  • Andreas Herzig
  • Laurent Perrussel
  • Zhanhao Xiao
  • Dongmo Zhang

Abstract According to Bratman, future-directed intentions are high-level plans. We view such plans as high-level actions that can typically not be executed directly: they have to be progressively refined until executable basic actions are obtained. Higher- and lower-level actions are linked by the means-end relation, alias instrumentality relation. In this paper we extend Shoham’s database perspective of Bratman’s theory by the notions of refinement and instrumentality.

Details

ECAI Conference 2016 Conference Paper

Simple Epistemic Planning: Generalised Gossiping

  • Martin C. Cooper
  • Andreas Herzig
  • Faustine Maffre
  • Frederic Maris
  • Pierre Régnier

The gossip problem, in which information (secrets) must be shared among a certain number of agents using the minimum number of calls, is of interest in the conception of communication networks and protocols. We extend the gossip problem to arbitrary epistemic depths. For example, we may require not only that all agents know all secrets but also that all agents know that all agents know all secrets. We give optimal protocols for the generalised gossip problem, in the case of two-way communications, one-way communications and parallel communication. In the presence of negative goals testing the existence of a successful protocol is NP-complete.

Details

LORI Conference 2015 Conference Paper

A Poor Man's Epistemic Logic Based on Propositional Assignment and Higher-Order Observation

  • Andreas Herzig
  • Emiliano Lorini
  • Faustine Maffre

Abstract We introduce a dynamic epistemic logic that is based on what an agent can observe, including joint observation and observation of what other agents observe. This generalizes van der Hoek, Wooldridge and colleague’s logics ECL-PC(PO) and LRC where it is common knowledge which propositional variables each agent observes. In our logic, facts of the world and their observability can both be modified by assignment programs. We show how epistemic operators can be interpreted in this framework and identify the conditions under which the principles of positive and negative introspection are valid. We also provide a sound and complete axiomatization and prove that the satisfiability problem is PSpace -complete. Finally, we show how public and private announcements can be expressed and illustrate the latter by the gossip spreading problem.

Details

IJCAI Conference 2015 Conference Paper

Epistemic Equilibrium Logic

  • Luis Fari
  • ntilde; as del Cerro
  • Andreas Herzig
  • Ezgi Iraz Su

We add epistemic modal operators to the language of here-and-there logic and define epistemic hereand-there models. We then successively define epistemic equilibrium models and autoepistemic equilibrium models. The former are obtained from here-and-there models by the standard minimisation of truth of Pearce’s equilibrium logic; they provide an epistemic extension of that logic. The latter are obtained from the former by maximising the set of epistemic possibilities; they provide a new semantics for Gelfond’s epistemic specifications. For both definitions we characterise strong equivalence by means of logical equivalence in epistemic hereand-there logic.

PDF Details

EUMAS Conference 2015 Conference Paper

How to Share Knowledge by Gossiping

  • Andreas Herzig
  • Faustine Maffre

Abstract Given n agents each of which has a secret (a fact not known to anybody else), the classical version of the gossip problem is to achieve shared knowledge of all secrets in a minimal number of phone calls. There exist protocols achieving shared knowledge in \(2(n{-}2)\) calls: when the protocol terminates everybody knows all the secrets. We generalize that problem and focus on higher-order shared knowledge: how many calls does it take to obtain that everybody knows that everybody knows all secrets? More generally, how many calls does it take to obtain shared knowledge of order k? This requires not only the communication of secrets, but also the communication of knowledge about secrets. We give a protocol that works in \((k{+}1)(n{-}2)\) steps and prove that it is correct: it achieves shared knowledge of level k. The proof is presented in a dynamic epistemic logic that is based on the observability of propositional variables by agents.

Details DOI

KR Conference 2014 Conference Paper

A dynamic logic framework for abstract argumentation

  • Sylvie Doutre
  • Andreas Herzig
  • Laurent Perrussel

the semantics. This is done in an extension of the language of attack variables by variables representing argument acceptance. Based on such a logical representation, several authors have recently investigated the dynamics of the AF, such as (Baumann 2012; Booth et al. 2013; Bisquert et al. 2013; Coste-Marquis et al. 2013). They start by distinguishing several kinds of modification of the AF, such as the addition or the removal of attacks, or the enforcement of the acceptability of an argument a (e. g. such that a is part of at least one extension). All these papers build on previous work in belief change, either referring to AGM theory (Alchourrón, Gärdenfors, and Makinson 1985), such as (Booth et al. 2013; Coste-Marquis et al. 2013), or to KM theory (Katsuno and Mendelzon 1992), such as (Bisquert et al. 2013). They express the modification as a logical formula describing some goal, i. e., a property that AF should satisfy: the task is to revise/update AF so that this formula is true. The above papers do not provide a single framework encompassing at the same time AF, the logical definition of the enforcement constraint and the change operations: there is usually one language for representing AF and another language for representing constraints, plus some definitions in the metalanguage connecting them. This has motivated us to provide a general, unified logical framework for the representation and the update of argumentation frameworks. We make use of a flexible yet simple logic: Dynamic Logic of Propositional Assignments, abbreviated DL-PA (Balbiani, Herzig, and Troquard 2013). DL-PA is a simple instantiation of Propositional Dynamic Logic PDL (Harel 1984; Harel, Kozen, and Tiuryn 2000) whose atomic programs are assignments of propositional variables to either true or false. Complex programs are built then from atomic programs by the standard PDL program operators of sequential composition, nondeterministic composition, and test. We here moreover add a less frequently considered PDL program operator, namely the converse operator. The language of DL-PA has formulas of the form hπiϕ and [π]ϕ, where π is a program and ϕ is a formula. The former expresses that ϕ is true after some possible execution of π, and the latter expresses that ϕ is true after every possible execution of π. It is shown in (Balbiani, Herzig, and Troquard 2013) that every DL-PA formula can be reduced to an equivalent propositional formula. The reduction extends to the converse operator in a straight- We provide a logical analysis of abstract argumentation frameworks and their dynamics. Following previous work, we express attack relation and argument status by means of propositional variables and define acceptability criteria by formulas of propositional logic. We here study the dynamics of argumentation frameworks in terms of basic operations on these propositional variables, viz. change of their truth values. We describe these operations in a uniform way within a well-known variant of Propositional Dynamic Logic PDL: the Dynamic Logic of Propositional Assignments, DL-PA. The atomic programs of DL-PA are assignments of propositional variables to truth values, and complex programs can be built by means of the connectives of sequential and nondeterministic composition and test. We start by showing that in DL-PA, the construction of extensions can be performed by a DL-PA program that is parametrized by the definition of acceptance. We then mainly focus on how the acceptance of one or more arguments can be enforced and show that this can be achieved by changing the truth values of the propositional variables describing the attack relation in a minimal way.

JELIA Conference 2014 Conference Paper

A Dynamic View of Active Integrity Constraints

  • Guillaume Feuillade
  • Andreas Herzig

Abstract Active integrity constraints have been introduced in the database community as a way to restore integrity. We view active integrity constraints as programs of Dynamic Logic of Propositional Assignments DL − PA and show how several semantics of database repair that were proposed in the literature can be characterised by DL − PA formulas. We moreover propose a new definition of repair. For all these definitions we provide DL − PA counterparts of decision problems such as the existence of a repair or the existence of a unique repair.

Details

KR Conference 2014 Conference Paper

Belief change operations: a short history of nearly everything, told in dynamic logic of propositional assignments

  • Andreas Herzig

and Makinson (AGM) studied the properties that ‘good’ revision operations should have (Alchourrón, Gärdenfors, and Makinson 1985). Similarly, Katsuno and Mendelzon (KM) studied the properties ‘good’ update operations should have (Katsuno and Mendelzon 1992). The difference between revision and update can be illustrated by the example of a new edition of a dictionary that is advertised as being ‘updated and revised’: revision corrects information that turned out to be wrong (about a static world), while update takes into account new usages of words, i. e., the dynamics of the world. Dalal’s operation satisfies the AGM postulates for revision, and Winslett’s and Forbus’s operations satisfy the KM postulates for update. This is however not enough to characterise these operations: they validate properties beyond the AGM/KM postulates, such as Parikh’s relevance postulate that is based on language splitting (Parikh 1999; Kourousias and Makinson 2007). Only few papers investigated this issue. Similarly, the related problem of syntactically constructing the new belief base B◦A has only received little attention. Indeed, the above concrete belief change operations were almost exclusively studied from a semantical perspective: instead of viewing B ◦ A as a formula, it is viewed as a set of models of classical propositional logic, alias a set of valuations. Therefore ◦ is not part of the object language but is in the metalanguage. We call ◦ a metalanguage operation, as opposed to object language operator, i. e., a logical connective. If the set of propositional variables P is finite then there is an easy recipe to construct a formula representing B ◦ A: describe each valuation v ∈ B ◦ A by the V  conjunction of V literals Fml(v) = p∈v p ∧ p∈P\v ¬p and take the disjunction of these big conjunctions Fml(v): the set of models W of v∈B◦A Fml(v) equals B ◦ A, and therefore the former is the syntactical counterpart of the latter. Is there a better, syntactic procedure building the new belief base? The answer is positive for WSS, which is the simplest update operation: an update procedure based on variable forgetting is in (Herzig and Rifi 1999) and its generalisation to literal forgetting is in (Herzig, Lang, and Marquis 2013). As to the PMA, there is an axiomatisation in (Herzig 1996) that can be turned into a decision procedure for the belief change consequence problem; it is however based on formulas in disjunctive normal form and is as such very close to the semantics. Finally, there We examine several belief change operations in the light of Dynamic Logic of Propositional Assignments DL-PA. We show that we can encode in a systematic way update operations (such as Winslett’s ‘Possible Models Approach’) and revision operations (such as Dalal’s) as particular DL-PA programs. Every DL-PA formula being equivalent to a boolean formula, we obtain syntactical counterparts for all these belief change operations.

JAAMAS Journal 2014 Journal Article

Logics of knowledge and action: critical analysis and challenges

  • Andreas Herzig

Abstract We overview the most prominent logics of knowledge and action that were proposed and studied in the multiagent systems literature. We classify them according to these two dimensions, knowledge and action, and moreover introduce a distinction between individual knowledge and group knowledge, and between a nonstrategic an a strategic interpretation of action operators. For each of the logics in our classification we highlight problematic properties. They indicate weaknesses in the design of these logics and call into question their suitability to represent knowledge and reason about it. This leads to a list of research challenges.

Details DOI

ECAI Conference 2014 Conference Paper

On the revision of planning tasks

  • Andreas Herzig
  • Maria Viviane de Menezes
  • Leliane Nunes de Barros
  • Renata Wassermann

When a planning task cannot be solved then it can often be made solvable by modifying it a bit: one may change either the set of actions, or the initial state, or the goal description. We show that modification of actions can be reduced to initial state modification. We then apply Katsuno and Mendelzon's distinction between update and revision and show that the modification of the initial state is an update and the modification of the goal description is a revision. We consider variants of Forbus's update and Dalal's revision operation and argue that existing belief change operations do not apply as they stand because their inputs are boolean formulas, while plan task modification involves counterfactual statements. We show that they can be captured in Dynamic Logic of Propositional Assignments DL-PA.

Details

LORI Conference 2013 Conference Paper

Listen to Me! Public Announcements to Agents That Pay Attention - or Not

  • Hans van Ditmarsch
  • Andreas Herzig
  • Emiliano Lorini
  • François Schwarzentruber

Abstract In public announcement logic it is assumed that all agents pay attention (listen to/observe) to the announcement. Weaker observational conditions can be modelled in event (action) model logic. In this work, we propose a version of public announcement logic wherein it is encoded in the states of the epistemic model which agents pay attention to the announcement. This logic is called attention-based announcement logic, abbreviated ABAL. We give an axiomatization and prove that complexity of satisfiability is the same as that of public announcement logic, and therefore lower than that of action model logic [2]. We exploit our logic to formalize the concept of joint attention that has been widely discussed in the philosophical and cognitive science literature. Finally, we extend our logic by integrating attention change.

Details

LORI Conference 2013 Conference Paper

Reasoning about Actions Meets Strategic Logics

  • Andreas Herzig
  • Emiliano Lorini
  • Dirk Walther 0002

Abstract We introduce ATLEA, a novel extension of Alternating-time Temporal Logic with explicit actions in the object language. ATLEA allows to reason about abilities of agents under commitments to play certain actions. Pre- and postconditions as well as availability and unavailability of actions can be expressed. We show that the multiagent extension of Reiter’s solution to the frame problem can be encoded into ATLEA. We also consider an epistemic extension of ATLEA. We demonstrate that the resulting logic is sufficiently expressive to reason about uniform choices of actions. Complexity results for the satisfiability problem of ATLEA and its epistemic extension are given in the paper.

Details

IJCAI Conference 2011 Conference Paper

A Dynamic Logic of Normative Systems

  • Andreas Herzig
  • Emiliano Lorini
  • Fr
  • eacute; d
  • eacute; ric Moisan
  • Nicolas Troquard

We propose a logical framework to represent and reason about agent interactions in normative systems. Our starting point is a dynamic logic of propositional assignments whose satisfiability problem is PSPACE-complete. We show that it embeds Coalition Logic of Propositional Control CL-PC and that various notions of ability and capability can be captured in it. We illustrate it on a water resource management case study. Finally, we show how the logic can be easily extended in order to represent constitutive rules which are also an essential component of the modelling of social reality.

PDF Details DOI

AAMAS Conference 2011 Conference Paper

Agents That Speak: Modelling Communicative Plans and Information Sources in a Logic of Announcements

  • Philippe Balbiani
  • Nadine Guiraud
  • Andreas Herzig
  • Emiliano Lorini

We present a modal logic of belief and announcements in a multi-agent setting. This logic allows to express not only that ψ holds after the announcement of φ as in standard public announcement logic (PAL), but also that the announcement of φ occurs. We use the logic to provide a formal analysis of several concepts that are relevant for multi-agent systems (MAS) theory and applications: the notions of communicative action (an agent informs another agent about something) and communicative intention (an agent has the intention to inform another agent about something), and the notion of information source.

PDF

JELIA Conference 2010 Conference Paper

A Logical Account of Lying

  • Chiaki Sakama
  • Martin Caminada
  • Andreas Herzig

Abstract This paper aims at providing a formal account of lying – a dishonest attitude of human beings. We first formulate lying under propositional modal logic and present basic properties for it. We then investigate why one engages in lying and how one reasons about lying. We distinguish between offensive and defensive lies, or deductive and abductive lies, based on intention behind the act. We also study two weak forms of dishonesty, bullshit and deception, and provide their logical features in contrast to lying. We finally argue dishonesty postulates that agents should try to satisfy for both moral and self-interested reasons.

Details

LORI Conference 2009 Conference Paper

Dynamic Context Logic

  • Guillaume Aucher
  • Davide Grossi
  • Andreas Herzig
  • Emiliano Lorini

Abstract Building on a simple modal logic of context, the paper presents a dynamic logic characterizing operations of contraction and expansion on theories. We investigate the mathematical properties of the logic, and show how it can capture some aspects of the dynamics of normative systems once they are viewed as logical theories.

Details

LORI Conference 2009 Conference Paper

Epistemic Games in Modal Logic: Joint Actions, Knowledge and Preferences All Together

  • Emiliano Lorini
  • François Schwarzentruber
  • Andreas Herzig

Abstract We propose a modal logic called \(\mathcal{EDLA}\) ( Epistemic Dynamic Logic of Agency ) that allows to reason about epistemic games in strategic form. \(\mathcal{EDLA}\) integrates the concepts of joint action, preference and knowledge. In the first part of the paper we introduce \(\mathcal{EDLA}\) and provide soundness, completeness and complexity results. In the second part we study in \(\mathcal{EDLA}\) the epistemic and rationality conditions of some classical solution concepts like Nash equilibrium and iterated strict dominance. In the last part of the paper we combine \(\mathcal{EDLA}\) with Dynamic Epistemic Logic (DEL) in order to model epistemic game dynamics.

Details

LORI Conference 2009 Conference Paper

Intentions and Assignments

  • Emiliano Lorini
  • Mehdi Dastani
  • Hans van Ditmarsch
  • Andreas Herzig
  • John-Jules Ch. Meyer

Abstract The aim of this work is propose a logical approach to intention dynamics based on the notion of assignment [3, 7]. The function of an assignment is to associate the truth value of a certain formula ϕ to a propositional atom p. We combine a static modal logic of belief and choice with three kinds of dynamic modalities and corresponding three kinds of assignments: assignments operating on an agent’s beliefs, assignments operating on the agent’s choices and assignments operating on the objective world. An agent’s intention is defined in our approach as the agent’s choice to perform a given action and two basic operations on intentions called intention generation and intention reconsideration are defined as specific kinds of assignments on choices.

Details

JELIA Conference 2008 Conference Paper

Uniform Interpolation by Resolution in Modal Logic

  • Andreas Herzig
  • Jérôme Mengin

Abstract The problem of computing a uniform interpolant of a given formula on a sublanguage is known in Artificial Intelligence as variable forgetting. In propositional logic, there are well known methods for performing variable forgetting. Variable forgetting is more involved in modal logics, because one must forget a variable not in one world, but in several worlds. It has been shown that modal logic K has the uniform interpolation property, and a method has recently been proposed for forgetting variables in a modal formula (of mu-calculus) given in disjunctive normal form. However, there are cases where information comes naturally in a more conjunctive form. In this paper, we propose a method, based on an extension of resolution to modal logics, to perform variable forgetting for formulae in conjunctive normal form, in the modal logic K.

Details

TARK Conference 2007 Conference Paper

A normal simulation of coalition logic and an epistemic extension

  • Jan M. Broersen
  • Andreas Herzig
  • Nicolas Troquard

In this paper we show how coalition logic can be reduced to the fusion of a normal modal STIT logic for agency and a standard normal temporal logic for discrete time, and how this multi-modal system can be suitably extended with an epistemic modality. Both systems are complete, and we provide a new axiomatization for the STIT-fragment. The epistemic extension enables us to express that agents see to something under uncertainty about the present state or uncertainty about which action is being taken. In accordance with established terminology in the planning community, we call this version of STIT the ‘conformant STIT’. The conformant STIT enables us to express that agents are able to perform a uniform strategy. As a final word of recommendation for this paper we want to point out that its subject is at the junction of four academic fields, viz. modal logic, philosophy, game-theory and AI-planning.

Details

AAMAS Conference 2007 Conference Paper

Delegation and Mental States

  • Emiliano Lorini
  • Nicolas Troquard
  • Andreas Herzig
  • Cristiano Castelfranchi

In the recent literature on multiagent systems there have been several proposals of formal systems for reasoning about delegation. Most of these approaches have dealt with the concept of delegation leaving mental states such as beliefs, goals and intentions out of consideration. The aim of this paper is to develop a formal approach for reasoning about delegation by modeling intentions and beliefs of the delegating agent in an explicit way. We present a logic where it is possible to investigate the relations between the concept of Intention to be and the concept of Delegation.

PDF

TARK Conference 2007 Conference Paper

What can we achieve by arbitrary announcements? : A dynamic take on Fitch's knowability

  • Philippe Balbiani
  • Alexandru Baltag
  • Hans van Ditmarsch
  • Andreas Herzig
  • Tomohiro Hoshi
  • Tiago de Lima

Public announcement logic is an extension of multi-agent epistemic logic with dynamic operators to model the informational consequences of announcements to the entire group of agents. We propose an extension of public announcement logic with a dynamic modal operator that expresses what is true after any announcement: ϕ expresses that ϕ is true after an arbitrary announcement ψ. As this includes the trivial announcement >, one might as well say that ϕ expresses what remains true after any announcement: it therefore corresponds to truth persistence after (definable) relativisation. The dual operation ♦ϕ expresses that there is an announcement after which ϕ. This gives a perspective on Fitch’s knowability issues: for which formulas ϕ does it hold that ϕ → ♦Kϕ? We give various semantic results, and we show completeness for a Hilbert-style axiomatisation of this logic.

Details

JELIA Conference 2006 Conference Paper

A Modularity Approach for a Fragment of ALC

  • Andreas Herzig
  • Ivan Varzinczak

Abstract In this paper we address the principle of modularity of ontologies in description logics. It turns out that with existing accounts of modularity of ontologies we do not completely avoid unforeseen interactions between module components, and modules designed in those ways may be as complex as whole theories. We here give a more fine-grained paradigm for modularizing descriptions. We propose algorithms that check whether a given terminology is modular and that also help the designer making it modular, if needed. Completeness, correctness and termination results are demonstrated for a fragment of \({\mathcal{ALC}}\). We also present the properties that ontologies that are modular in our sense satisfy w. r. t. reasoning services.

Details

ECAI Conference 2006 Conference Paper

A New Semantics for the FIPA Agent Communication Language Based on Social Attitudes

  • Benoît Gaudou
  • Andreas Herzig
  • Dominique Longin
  • Matthias Nickles

One of the most important aspects of the research on agent interaction is the definition of agent communication languages (ACLs), and the specification of a proper formal semantics of such languages is a crucial prerequisite for the usefulness and acceptance of artificial agency. Nevertheless, those ACLs which are still mostly used, especially the standard FIPA-ACL, have a communication act semantics in terms of the participating agents' mental attitudes (viz. beliefs and intentions), which are in general undeterminable from an external point of view due to agent autonomy. In contrast, semantics of ACLs based on commitments are fully verifiable, but not sufficiently formalized and understood yet. In order to overcome this situation, we propose a FIPA-ACL semantics which is fully verifiable, fully formalized, lean and easily applicable. It is based on social attitudes represented using a logic of grounding in straightforward extension of the BDI agent model.

Details

JELIA Conference 2006 Conference Paper

A STIT-Extension of ATL

  • Jan M. Broersen
  • Andreas Herzig
  • Nicolas Troquard

Abstract A problem in many formalisms for reasoning about multi-agent systems, like ATL or PDL, is the inability to express that a certain complex action (as in PDL), choice or strategy (as in ATL) is performed by an agent. However, in so called STIT-logics, this is exactly the main operator: seeing to it that a certain condition is achieved. Here we present an extension of ATL, introducing ideas from STIT-theory, that can express that a group of agents A perform a certain strategy. As a demonstration of the applicability of the formalism, we show how it sheds new light on the problem of modelling ‘uniform strategies’ in epistemic versions of ATL.

Details

ECAI Conference 2006 Conference Paper

Elaborating Domain Descriptions

  • Andreas Herzig
  • Laurent Perrussel
  • Ivan Varzinczak

In this work we address the problem of elaborating domain descriptions (alias action theories), in particular those that are expressed in dynamic logic. We define a general method based on contraction of formulas in a version of propositional dynamic logic with a solution to the frame problem. We present the semantics of our theory change and define syntactical operators for contracting a domain description. We establish soundness and completeness of the operators w. r. t. the semantics for descriptions that satisfy a principle of modularity that we have defined in previous work.

Details

KR Conference 2006 Conference Paper

Grounding and the expression of belief

  • Benoit Gaudou
  • Andreas Herzig
  • Dominique Longin

In this paper we investigate the logic of speech acts and groundedness. A piece of information is grounded for a group of agents if it is publicly expressed and established by all agents of the group. Our concept of groundedness is founded on the expression of the sincerity condition of speech act theory. We formalize groundedness within an extended BDI (Belief, Desire, Intention) logic where belief is viewed as a kind of group belief. We show that our logic permits to reconcile the mentalist approaches on the one hand, and the structural and social approaches on the other, which are the two rival research programs in the formalization of agent interaction. Although groundedness is thus linked to the standard mental attitude of belief, it is immune to the critiques that have been put forward against the mentalist approaches, viz. that they require too strong hypotheses about the agents' mental states such as sincerity and cooperation: just as the structural approaches, groundedness only bears on the public aspect of communication. In our extended BDI logic we study communication between heterogeneous agents. We characterize inform and request speech acts in terms of preconditions and effects. We demonstrate the power of our solution by means of two examples. First, we revisit the well-known FIPA Contract Net Protocol. As a second example, we show how Walton and Krabbe's commitments can be redefined in term of groundedness.

JELIA Conference 2006 Conference Paper

Introducing Attempt in a Modal Logic of Intentional Action

  • Emiliano Lorini
  • Andreas Herzig
  • Cristiano Castelfranchi

Abstract The main objective of this work is to develop a multi-modal logic of Intention and Attempt. We call this logic LIA. All formal results are focused on the notion of attempt. We substitute the dynamic molecular notion action by his atomic constituent attempt and define the former from the latter. The relations between attempts, goals, beliefs and present-directed intentions are studied. A section of the paper is devoted to the analysis of the relations of our modal logic with a situation calculus-style approach.

Details

IJCAI Conference 2005 Conference Paper

Cohesion, coupling and the meta-theory of actions

  • Andreas Herzig
  • Ivan

In this work we recast some design principles commonly used in software engineering and adapt them to the design and analysis of domain descriptions in reasoning about actions. We show how the informal requirements of cohesion and coupling can be turned into consistency tests of several different arrangements of modules. This gives us new criteria for domain description evaluation and clarifies the link between software and knowledge engineering in what concerns the meta-theory of actions.

PDF

KR Conference 2004 Conference Paper

C&L Intention Revisited

  • Andreas Herzig
  • Dominique Longin

The 1990 papers of Cohen and Levesque (C&L) on rational interaction have been most influential. Their approach is based on a logical framework integrating the concepts of belief, action, time, and choice. On top of these they define notions of achievement goal, persistent goal, and intention. We here revisit their approach in a simplified, propositional logic, for which we give complete axiomatization. Within that logic we study the definition of achievement goals, refining C&L’s analysis. Our analysis allows us to identify the conditions under which achievement goals persist. We then discuss the C&L definition of intention as well as a variant that has been proposed by Sadek and Bretier. We argue that both are too strong and propose a weakened version.

NMR Workshop 2004 Conference Paper

Domain descriptions should be modular

  • Andreas Herzig
  • Ivan Varzinczak

We address the problem of what a good domain description for reasoning about actions should look like. We state some metatheoretic postulates concerning this sore spot, which establishes the notion of a modular domain description. We point out the problems that arise when modularity is violated and propose algorithms to overcome them.

Details

NMR Workshop 2002 Conference Paper

It depends on the context! A decidable logic of actions and plans based on a ternary dependence relation

  • Marcos A. Castilho
  • Andreas Herzig
  • Ivan Varzinczak

In this paper we argue for a weak form of causality in terms of a dependence relation involving actions, atoms and formulae in order to deal with the frame and ramification problems. This relation allows the atoms to change their value without forcing or causing it. Once integrated in the framework of the Logic of Actions and Plans LAP, it gives us a simple and powerful formalism to reasoning about actions and a decision procedure in terms of tableau methods. We also show how to deal with scenarios involving indeterminate and indirect effects which no other causal framework can handle.

Details

TARK Conference 1996 Conference Paper

Belief Change and Dependence

  • Luis Fariñas del Cerro
  • Andreas Herzig

It is a very natural requirement for belief change operations that formulas that are independent of a given update should be preserved. Such a proposal has already been made by G£rdenfors (1990). In this perspective we study the links between belief change and the notion of dependence, our aim being to give dependence axioms able to characterize the AGM postulates. Proceeding exactly in the same way as G~irdenfors (1988) did in the case of epistemic entrenchment, we show how a given dependence relation can be used to define a contraction operation, and the other way round we show how an independence relation can be obtained from a given contraction operation. The grande finale is a characterization theorem.

Details

UAI Conference 1994 Conference Paper

An Ordinal View of Independence with Application to Plausible Reasoning

  • Didier Dubois
  • Luis Fariñas del Cerro
  • Andreas Herzig
  • Henri Prade

An ordinal view of independence is studied in the framework of possibility theory. We investigate three possible definitions of dependence, of increasing strength. One of them is the counterpart to the multiplication law in probability theory, and the two others are based on the notion of conditional possibility. These two have enough expressive power to support the whole possibility theory, and a complete axiomatization is provided for the strongest one. Moreover we show that weak independence is well-suited to the problems of belief change and plausible reasoning, especially to address the problem of blocking of property inheritance in exception-tolerant taxonomic reasoning.

Details