Author name cluster

Thomas Bolander

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.

20 papers

2 author rows

IJCAI Conference 2025 Conference Paper

A Logic of General Attention Using Edge-Conditioned Event Models

Gaia Belardinelli
Thomas Bolander
Sebastian Watzl

In this work, we present the first general logic of attention. Attention is a powerful cognitive ability that allows agents to focus on potentially complex information, such as logically structured propositions, higher-order beliefs, or what other agents pay attention to. This ability is a strength, as it helps to ignore what is irrelevant, but it can also introduce biases when some types of information or agents are systematically ignored. Existing dynamic epistemic logics for attention cannot model such complex attention scenarios, as they only model attention to atomic formulas. Additionally, such logics quickly become cumbersome, as their size grows exponentially in the number of agents and announced literals. Here, we introduce a logic that overcomes both limitations. First, we generalize edge-conditioned event models, which we show to be as expressive as standard event models yet exponentially more succinct (generalizing both standard event models and generalized arrow updates). Second, we extend attention to arbitrary formulas, allowing agents to also attend to other agents' beliefs or attention. Our work treats attention as a modality, like belief or awareness. We introduce attention principles that impose closure properties on that modality and that can be used in its axiomatization. Throughout, we illustrate our framework with examples of AI agents reasoning about human attention, demonstrating how such agents can discover attentional biases.

PDF Details DOI

KR Conference 2025 Conference Paper

Depth-Bounded Epistemic Planning

Thomas Bolander
Alessandro Burigana
Marco Montali

We propose a novel algorithm for epistemic planning based on dynamic epistemic logic (DEL). The novelty is that we limit the depth of reasoning of the planning agent to an upper bound b, meaning that the planning agent can only reason about higher-order knowledge to at most (modal) depth b. We then compute a plan requiring the lowest reasoning depth by iteratively incrementing the value of b. The algorithm relies at its core on a new type of "canonical" b-bisimulation contraction that guarantees unique minimal models by construction. This yields smaller states wrt. standard bisimulation contractions, and enables to efficiently check for visited states. We show soundness and completeness of our planning algorithm, under suitable bounds on reasoning depth, and that, for a bound b, it runs in (b+1)-EXPTIME. We implement the algorithm in a novel epistemic planner, DAEDALUS, and compare it to the EFP 2. 0 planner on several benchmarks from the literature, showing effective performance improvements.

PDF Details DOI

AAMAS Conference 2023 Conference Paper

Attention! Dynamic Epistemic Logic Models of (In)attentive Agents

Gaia Belardinelli
Thomas Bolander

Attention is the crucial cognitive ability that limits and selects what information we observe. Previous work by Bolander et al. (2016) proposes a model of attention based on dynamic epistemic logic (DEL) where agents are either fully attentive or not attentive at all. While introducing the realistic feature that inattentive agents believe nothing happens, the model does not represent the most essential aspect of attention: its selectivity. Here, we propose a generalization that allows for paying attention to subsets of atomic formulas. We introduce the corresponding logic for propositional attention, and show its axiomatization to be sound and complete. We then extend the framework to account for inattentive agents that, instead of assuming nothing happens, may default to a specific truth-value of what they failed to attend to (a sort of prior concerning the unattended atoms). This feature allows for a more cognitively plausible representation of the inattentional blindness phenomenon, where agents end up with false beliefs due to their failure to attend to conspicuous but unexpected events. Both versions of the model define attention-based learning through appropriate DEL event models based on a few and clear edge principles. While the size of such event models grow exponentially both with the number of agents and the number of atoms, we introduce a new logical language for describing event models syntactically and show that using this language our event models can be represented linearly in the number of agents and atoms. Furthermore, representing our event models using this language is achieved by a straightforward formalisation of the aforementioned edge principles.

PDF

AIJ Journal 2023 Journal Article

Epistemic planning: Perspectives on the special issue

Vaishak Belle
Thomas Bolander
Andreas Herzig
Bernhard Nebel

Epistemic planning is the enrichment of automated planning with epistemic notions such as knowledge and belief. In general, single-agent epistemic planning considers the following problem: given an agent's current state of knowledge, and a desirable state of knowledge, how does it get from one to the other? In multi-agent epistemic planning, the current and desirable states of knowledge might also refer to the states of knowledge of other agents, including higher-order knowledge like ensuring that agent A doesn't get to know that agent B knows P. Single-agent epistemic planning is of central importance in settings where agents need to be able to reason about their own lack of knowledge and, e. g. , make plans of how to achieve the required knowledge. Multi-agent epistemic planning is essential for coordination and collaboration among multiple agents, where success can only be expected if agents are able to reason about the knowledge, uncertainty and capabilities of other agents. It is a relatively recent area of research involving several sub-areas of artificial intelligence, such as automated planning, decision-theoretic planning, epistemic logic, strategic reasoning and knowledge representation & reasoning. In order to achieve formalisms and systems for epistemic planning that are both expressive and practically efficient, it is necessary to combine state of the art from several such sub-areas of artificial intelligence that have so far been considered mostly in separation. Application areas of epistemic planning include mobile service robots, explaining planning, game playing, human-robot interaction and social robotics. For this special issue of AIJ, we invited papers on theory, applications, and implemented systems of epistemic planning. In this document, we summarize the accepted papers whilst recapping the essentials of epistemic planning.

Details DOI

KR Conference 2021 Conference Paper

DEL-based Epistemic Planning for Human-Robot Collaboration: Theory and Implementation

Thomas Bolander
Lasse Dissing
Nicolai Herrmann

Epistemic planning based on Dynamic Epistemic Logic (DEL) allows agents to reason and plan from the perspective of other agents. The framework of DEL-based epistemic planning thereby has the potential to represent significant aspects of Theory of Mind in autonomous robots, and to provide a foundation for human-robot collaboration in which coordination is achieved implicitly through perspective shifts. In this paper, we build on previous work in epistemic planning with implicit coordination. We introduce a new notion of indistinguishability between epistemic states based on bisimulation, and provide a novel partition refinement algorithm for computing unique representatives of sets of indistinguishable states. We provide an algorithm for computing implicitly coordinated plans using these new constructs, embed it in a perceive-plan-act agent loop, and implement it on a robot. The planning algorithm is benchmarked against an existing epistemic planning algorithm, and the robotic implementation is demonstrated on human-robot collaboration scenarios requiring implicit coordination.

PDF Details DOI

AAAI Conference 2021 Conference Paper

Planning from Pixels in Atari with Learned Symbolic Representations

Andrea Dittadi
Frederik K. Drachmann
Thomas Bolander

Width-based planning methods have been shown to yield state-of-the-art performance in the Atari 2600 domain using pixel input. One successful approach, RolloutIW, represents states with the B-PROST boolean feature set. An augmented version of RolloutIW, π-IW, shows that learned features can be competitive with handcrafted ones for width-based search. In this paper, we leverage variational autoencoders (VAEs) to learn features directly from pixels in a principled manner, and without supervision. The inference model of the trained VAEs extracts boolean features from pixels, and RolloutIW plans with these features. The resulting combination outperforms the original RolloutIW and human professional play on Atari 2600 and drastically reduces the size of the feature set.

PDF Details

AIJ Journal 2020 Journal Article

DEL-based epistemic planning: Decidability and complexity

Thomas Bolander
Tristan Charrier
Sophie Pinchinat
François Schwarzentruber

Epistemic planning can be used for decision making in multi-agent systems with distributed knowledge and capabilities. Dynamic Epistemic Logic (DEL) has been shown to provide a very natural and expressive framework for epistemic planning. In this paper, we present a systematic overview of known complexity and decidability results for epistemic planning based on DEL, as well as provide some new results and improved proofs of existing results based on reductions between the problems.

Details DOI

IJCAI Conference 2020 Conference Paper

Implementing Theory of Mind on a Robot Using Dynamic Epistemic Logic

Lasse Dissing
Thomas Bolander

Previous research has claimed dynamic epistemic logic (DEL) to be a suitable formalism for representing essential aspects of a Theory of Mind (ToM) for an autonomous agent. This includes the ability of the formalism to represent the reasoning involved in false-belief tasks of arbitrary order, and hence for autonomous agents based on the formalism to become able to pass such tests. This paper provides evidence for the claims by documenting the implementation of a DEL-based reasoning system on a humanoid robot. Our implementation allows the robot to perform cognitive perspective-taking, in particular to reason about the first- and higher-order beliefs of other agents. We demonstrate how this allows the robot to pass a quite general class of false-belief tasks involving human agents. Additionally, as is briefly illustrated, it allows the robot to proactively provide human agents with relevant information in situations where a system without ToM-abilities would fail. The symbolic grounding problem of turning robotic sensor input into logical action descriptions in DEL is achieved via a perception system based on deep neural networks.

PDF Details DOI

PRL Workshop 2020 Workshop Paper

Planning from Pixels in Atari with Learned Symbolic Representations

Frederik Drachmann
Andrea Dittadi
Thomas Bolander

Width-based planning methods have been shown to yield state-of-the-art performance in the Atari 2600 video game playing domain using pixel input. One approach consists in an episodic rollout version of the Iterated Width (IW) algorithm called RolloutIW, and uses the B-PROST boolean feature set to represent states. Another approach, π-IW, augments RolloutIW with a learned policy to improve how actions are picked in the rollouts. This policy is implemented as a neural network, and the feature set is derived from an intermediate representation learned by the policy network. Results suggest that learned features can be competitive with handcrafted ones in the context of width-based search. This paper introduces a new approach, where we leverage variational autoencoders (VAEs) to learn features for the domains in a principled manner, directly from pixels, and without supervision. We use the inference network (or encoder) of the trained VAEs to extract boolean features from screen states, and use them for planning with RolloutIW. The trained model in combination with RolloutIW outperforms the original RolloutIW and human professional play on the Atari 2600 domain and reduces the size of the feature set from 20. 5 million to 4, 500.

PDF Details

JAIR Journal 2019 Journal Article

Implicitly Coordinated Multi-Agent Path Finding under Destination Uncertainty: Success Guarantees and Computational Complexity

Bernhard Nebel
Thomas Bolander
Thorsten Engesser
Robert Mattmüller

In multi-agent path finding (MAPF), it is usually assumed that planning is performed centrally and that the destinations of the agents are common knowledge. We will drop both assumptions and analyze under which conditions it can be guaranteed that the agents reach their respective destinations using implicitly coordinated plans without communication. Furthermore, we will analyze what the computational costs associated with such a coordination regime are. As it turns out, guarantees can be given assuming that the agents are of a certain type. However, the implied computational costs are quite severe. In the distributed setting, we either have to solve a sequence of NP-complete problems or have to tolerate exponentially longer executions. In the setting with destination uncertainty, bounded plan existence becomes PSPACE-complete. This clearly demonstrates the value of communicating about plans before execution starts.

PDF Details DOI

IJCAI Conference 2019 Conference Paper

Implicitly Coordinated Multi-Agent Path Finding under Destination Uncertainty: Success Guarantees and Computational Complexity (Extended Abstract)

Bernhard Nebel
Thomas Bolander
Thorsten Engesser
Robert Mattmüller

In multi-agent path finding, it is usually assumed that planning is performed centrally and that the destinations of the agents are common knowledge. We will drop both assumptions and analyze under which conditions it can be guaranteed that the agents reach their respective destinations using implicitly coordinated plans without communication.

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

KR Conference 2018 Conference Paper

Better Eager Than Lazy? How Agent Types Impact the Successfulness of Implicit Coordination

Thomas Bolander
Thorsten Engesser
Robert Mattmüller
Bernhard Nebel

Epistemic planning can be used for decision making in multiagent situations with distributed knowledge and capabilities. In recent work, we proposed a new notion of strong policies with implicit coordination. With this it is possible to solve planning tasks with joint goals from a single-agent perspective without the agents having to negotiate about and commit to a joint policy at plan time. We study how and under which circumstances the decentralized application of those policies leads to the desired outcome.

IJCAI Conference 2015 Conference Paper

Complexity Results in Epistemic Planning

Thomas Bolander
Martin Holm Jensen
Francois Schwarzentruber

Epistemic planning is a very expressive framework that extends automated planning by the incorporation of dynamic epistemic logic (DEL). We provide complexity results on the plan existence problem for multi-agent planning tasks, focusing on purely epistemic actions with propositional preconditions. We show that moving from epistemic preconditions to propositional preconditions makes it decidable, more precisely in EXPSPACE. The plan existence problem is PSPACE-complete when the underlying graphs are trees and NP-complete when they are chains (including singletons). We also show PSPACE-hardness of the plan verification problem, which strengthens previous results on the complexity of DEL model checking.

PDF Details

LORI Conference 2015 Conference Paper

Learning Actions Models: Qualitative Approach

Thomas Bolander
Nina Gierasimczuk

Abstract In dynamic epistemic logic, actions are described using action models. In this paper we introduce a framework for studying learnability of action models from observations. We present first results concerning propositional action models. First we check two basic learnability criteria: finite identifiability (conclusively inferring the appropriate action model in finite time) and identifiability in the limit (inconclusive convergence to the right action model). We show that deterministic actions are finitely identifiable, while non-deterministic actions require more learning power—they are identifiable in the limit. We then move on to a particular learning method, which proceeds via restriction of a space of events within a learning-specific action model. This way of learning closely resembles the well-known update method from dynamic epistemic logic. We introduce several different learning methods suited for finite identifiability of particular types of deterministic actions.

Details

LPAR Conference 2013 Conference Paper

A Seligman-Style Tableau System

Patrick Blackburn
Thomas Bolander
Torben Braüner
Klaus Frovin Jørgensen

Abstract Proof systems for hybrid logic typically use @-operators to access information hidden behind modalities; this labeling approach lies at the heart of most resolution, natural deduction, and tableau systems for hybrid logic. But there is another, less well-known approach, which we have come to believe is conceptually clearer. We call this Seligman-style inference, as it was first introduced and explored by Jerry Seligman in the setting of natural deduction and sequent calculus in the late 1990s. The purpose of this paper is to introduce a Seligman-style tableau system. The most obvious feature of Seligman-style systems is that they work with arbitrary formulas, not just formulas prefixed by @-operators. To achieve this in a tableau system, we introduce a rule called GoTo which allows us to “jump to a named world” on a tableau branch, thereby creating a local proof context (which we call a block ) on that branch. To the surprise of some of the authors (who have worked extensively on developing the labeling approach) Seligman-style inference is often clearer: not only is the approach more modular, individual proofs can be more direct. We briefly discuss termination and extensions to richer logics, and relate our system to Seligman’s original sequent calculus.

Details

IJCAI Conference 2013 Conference Paper

Undecidability in Epistemic Planning

Guillaume Aucher
Thomas Bolander

Dynamic epistemic logic (DEL) provides a very expressive framework for multi-agent planning that can deal with nondeterminism, partial observability, sensing actions, and arbitrary nesting of beliefs about other agents’ beliefs. However, as we show in this paper, this expressiveness comes at a price. The planning framework is undecidable, even if we allow only purely epistemic actions (actions that change only beliefs, not ontic facts). Undecidability holds already in the S5 setting with at least 2 agents, and even with 1 agent in S4. It shows that multi-agent planning is robustly undecidable if we assume that agents can reason with an arbitrary nesting of beliefs about beliefs. We also prove a corollary showing undecidability of the DEL model checking problem with the star operator on actions (iteration).

PDF Details DOI

JELIA Conference 2012 Conference Paper

Conditional Epistemic Planning

Mikkel Birkegaard Andersen
Thomas Bolander
Martin Holm Jensen

Abstract Recent work has shown that Dynamic Epistemic Logic (DEL) offers a solid foundation for automated planning under partial observability and non-determinism. Under such circumstances, a plan must branch if it is to guarantee achieving the goal under all contingencies (strong planning). Without branching, plans can offer only the possibility of achieving the goal (weak planning). We show how to formulate planning in uncertain domains using DEL and give a language of conditional plans. Translating this language to standard DEL gives verification of both strong and weak plans via model checking. In addition to plan verification, we provide a tableau-inspired algorithm for synthesising plans, and show this algorithm to be terminating, sound and complete.

Details

I&C Journal 2010 Journal Article

Hybrid logical analyses of the ambient calculus

Thomas Bolander
René Rydhof Hansen

In this paper, hybrid logic is used to formulate three control flow analyses for Mobile Ambients, a process calculus designed for modelling mobility. We show that hybrid logic is very well-suited to express the semantic structure of the ambient calculus and how features of hybrid logic can be exploited to reduce the “administrative overhead” of the analysis specification and thus simplify it. Finally, we use HyLoTab, a fully automated theorem prover for hybrid logic, both as a convenient platform for a prototype implementation as well as to formally prove the correctness of the analysis.

Details DOI

IJCAI Conference 2003 Conference Paper

From Logic Programming Semantics to the Consistency of Syntactical Treatments of Knowledge and Belief

Thomas Bolander

This paper concerns formal theories for reasoning about the knowledge and belief of agents. It has seemed attractive to researchers in artificial intelligence to formalise these propositional attitudes as predicates of first-order predicate logic. This allows the agents to express stronger introspective beliefs and engage in stronger meta-rcasoning than in the classical modal operator approach. Results by Montague [1963] and Thomason [1980] show, however, that the predicate approach is prone to inconsistency. More recent results by des Rivieres & Levesque [1988] and Morreau & Kraus [1998] show that we can maintain the predicate approach if we make suitable restrictions to our set of epistemic axioms. Their results are proved by careful translations from corresponding modal formalisms. In the present paper we show that their results fit nicely into the framework of logic programming semantics, in that we show their results to be corollaries of well-known results in this field. This does not only allow us to demonstrate a close connection between consistency problems in the syntactic treatment of propositional attitudes and problems in semantics for logic programs, but it also allows us to strengthen the results of des Rivieres & Levesque [1988] and Morreau & Kraus [1998].

PDF