Possibilities

Dynamic Epistemic Logic (DEL) provides a framework for epistemic planning that is capable of representing non-deterministic actions, partial observability, higher-order knowledge and both factual and epistemic change. The high expressivity of DEL challenges existing epistemic planners, which typically can handle only restricted fragments of the whole framework. The goal of this work is to push the envelop of practical DEL planning, ultimately aiming for epistemic planners to be able to deal with the full range of features offered by DEL. Towards this goal, we question the traditional semantics of DEL, defined in terms on Kripke models. In particular, we propose an equivalent semantics defined using, as main building block, so-called possibilities: non well-founded objects representing both factual properties of the world, and what agents consider to be possible. We call the resulting framework DELPHIC. We argue that DELPHIC indeed provides a more compact representation of epistemic states. To substantiate this claim, we implement both approaches in ASP and we set up an experimental evaluation to compare DELPHIC with the traditional, Kripke-based approach. The evaluation confirms that DELPHIC outperforms the traditional approach in space and time.

Dynamic Epistemic Logic (DEL) provides a very expressive framework for planning, called epistemic planning. In this paper, we discuss the shortcomings of the traditional DEL semantics, based on Kripke models, and we propose a formulation of epistemic planning based on a different kind of object, called possibility. We argue that the resulting framework, named DELPHIC, constitutes a valid alternative, since it provides a more compact representation of epistemic information and a lighter update mechanism. We conclude by discussing the advantages of DELPHIC, both theoretically and in terms of implementation.

Developing autonomous agents that can reason about the perspective of their (human or artificial) peers is paramount to realistically model a variety of real-world domains. Being aware of the state of mind of others is a key aspect in different fields—e.g., legal reasoning, business negotiations, ethical AI and explainable AI. In particular, in the area of Multi-Agent Epistemic Planning (MEP), agents must reach their goals by taking into account the knowledge and beliefs of other agents. Although the literature offers an ample spectrum of approaches for planning in this scenario, they often come with limitations. This paper expands previous formalization of MEP to enable representing and reasoning in presence of inconsistent beliefs of agents, trust relations and lies. The paper explores the syntax and semantics of the extended MEP framework, along with an implementation of the framework in the solver Epistemic Forward Planner (EFP). The paper reports formal properties about the newly introduced epistemic states update that have been also empirically tested via an actual implementation of the solver.

DELPHIC is a novel semantics for Dynamic Epistemic Logic based on an alternative representation of epistemic states called possibilities. DELPHIC ASP is an Answer Set Programming model of a DEL-based epistemic planner built on top of the DELPHIC semantics. Since the DELPHIC semantics comprises the full range of DEL actions, DELPHIC ASP generalizes the PLATO solver.

Designing agents that reason and act upon the world has always been one of the main objectives of the Artificial Intelligence community. While for planning in “simple” domains the agents can solely rely on facts about the world, in several contexts, e.g., economy, security, justice and politics, the mere knowledge of the world could be insufficient to reach a desired goal. In these scenarios, epistemic reasoning, i.e., reasoning about agents’ beliefs about themselves and about other agents’ beliefs, is essential to design winning strategies. This paper addresses the problem of reasoning in multi-agent epistemic settings exploiting declarative programming techniques. In particular, the paper presents an actual implementation of a multi-shot Answer Set Programming-based planner that can reason in multi-agent epistemic settings, called PLATO (ePistemic muLti-agent Answer seT programming sOlver). The ASP paradigm enables a concise and elegant design of the planner, w.r.t. other imperative implementations, facilitating the development of formal verification of correctness. The paper shows how the planner, exploiting an ad-hoc epistemic state representation and the efficiency of ASP solvers, has competitive performance results on benchmarks collected from the literature.

Multi-agent systems have been employed to model, simulate and explore a variety of real-world scenarios. It is becoming more and more important to investigate formalisms and tools that would allow us to exploit automated reasoning in these domains. An area that has received increasing attention is the use of multi-agent systems which allow an agent to reason about the knowledge and beliefs of other agents. This type of reasoning, i.e., about agents’ perception of the world and also about agents’ knowledge of her and others’ knowledge, is referred to as epistemic reasoning. This paper presents an updated formalization and implementation of a multi-agent epistemic planner, called EFP. In particular, the paper explores the advantages of using alternative state representations that deviate from the commonly used Kripke structures. The paper explores such alternatives in the context of an action language for multi-agent epistemic planning. The paper presents also an actual implementation of a planner that uses the novel ideas, demonstrating concrete performance improvements on benchmarks collected from the literature.

PLATO is an Answer Set Programming (ASP) model implementing an epistemic planner that is built on top a fragment of Dynamic Epistemic Logic called $m\mathcal{A}^*$. The fragment comprises (public and private) ontic actions and (public, private and semi-private) sensing and announcement actions. The planner implements both a Kripke semantics for the fragment and a novel alternative semantics based on objects called possibilities. PLATO is implemented using the clingo solver for ASP programs, which provides some useful APIs that allow for solving problems in an iterative fashion. In this way, we can try to compute plans of increasing length, akin to a BFS visit. The goal of PLATO is to investigate the practical usability of ASP in the implementation of epistemic planners.

EFP 2.0 is an epistemic planner that is built on top a fragment of Dynamic Epistemic Logic called $m\mathcal{A}^*$. The fragment comprises (public and private) ontic actions and (public, private and semi-private) sensing and announcement actions. The planner implements both a Kripke semantics for the fragment and a novel alternative semantics based on objects called possibilities.