Anders Jonsson

NeurIPS Conference 2025 Conference Paper

Distances for Markov chains from sample streams

• Sergio Calo
• Anders Jonsson
• Gergely Neu
• Ludovic Schwartz
• Javier Segovia-Aguas

Bisimulation metrics are powerful tools for measuring similarities between stochastic processes, and specifically Markov chains. Recent advances have uncovered that bisimulation metrics are, in fact, optimal-transport distances, which has enabled the development of fast algorithms for computing such metrics with provable accuracy and runtime guarantees. However, these recent methods, as well as all previously known methods, assume full knowledge of the transition dynamics. This is often an impractical assumption in most real-world scenarios, where typically only sample trajectories are available. In this work, we propose a stochastic optimization method that addresses this limitation and estimates bisimulation metrics based on sample access, without requiring explicit transition models. Our approach is derived from a new linear programming (LP) formulation of bisimulation metrics, which we solve using a stochastic primal-dual optimization method. We provide theoretical guarantees on the sample complexity of the algorithm and validate its effectiveness through a series of empirical evaluations.

EWRL Workshop 2025 Workshop Paper

Distances for Markov chains from sample streams

• Sergio Calo
• Anders Jonsson
• Gergely Neu
• Ludovic Schwartz
• Javier Segovia-Aguas

Bisimulation metrics are powerful tools for measuring similarities between stochastic processes, and specifically Markov chains. Recent advances have uncovered that bisimulation metrics are, in fact, optimal-transport distances, which has enabled the development of fast algorithms for computing such metrics with provable accuracy and runtime guarantees. However, these recent methods, as well as all previously known methods, assume full knowledge of the transition dynamics. This is often an impractical assumption in most real-world scenarios, where typically only sample trajectories are available. In this work, we propose a stochastic optimization method that addresses this limitation and estimates bisimulation metrics based on sample access, without requiring explicit transition models. Our approach is derived from a new linear programming (LP) formulation of bisimulation metrics, which we solve using a stochastic primal-dual optimization method. We provide theoretical guarantees on the sample complexity of the algorithm and validate its effectiveness through a series of empirical evaluations.

EWRL Workshop 2025 Workshop Paper

Learning Compact Regular Decision Processes using Priors and Cascades

• Ahana Deb
• Anders Jonsson
• Alessandro Ronca
• Mohammad Sadegh Talebi

In this work we study offline Reinforcement Learning (RL), and extend the previous work on learning Regular Decision Processes (RDPs), which are a class of non-Markovian environment, where the unknown dependency of future observations and rewards from the past interactions can be captured by some hidden finite-state automaton. We utilise the language metric introduced previously for an offline RL algorithm for RDPs, and introduce a novel algorithm to learn a significantly more compact RDP with cycles, which are crucial for scaling to larger, more complex environments. Key to our results is a novel notion of priors for automaton learning, that allows us to exploit prior domain-related knowledge, used to factor out of the state space any feature that is known a priori. We validate our approach experimentally and provide a Probably Approximately Correct (PAC) analysis of our algorithm, showing it enjoys a sample complexity polynomial in the relevant parameters.

EWRL Workshop 2025 Workshop Paper

Learning the Minimum Action Distance

• Lorenzo Steccanella
• Joshua Benjamin Evans
• Özgür Şimşek
• Anders Jonsson

This paper presents a state representation framework for Markov decision processes (MDPs) that can be learned solely from state trajectories, requiring neither reward signals nor the actions executed by the agent. We propose learning the $\textit{minimum action distance}$ (MAD), defined as the minimum number of actions required to transition between states, as a fundamental metric that captures the underlying structure of an environment. MAD naturally enables critical downstream tasks such as goal-conditioned reinforcement learning and reward shaping by providing a dense, geometrically meaningful measure of progress. Our self-supervised learning approach constructs an embedding space where the distances between embedded state pairs correspond to their MAD, accommodating both symmetric and asymmetric approximations. We evaluate the framework on a comprehensive suite of environments with known MAD values, encompassing both deterministic and stochastic dynamics, as well as discrete and continuous state spaces, and environments with noisy observations. Empirical results demonstrate that the proposed approach not only efficiently learns accurate MAD representations across these diverse settings but also significantly outperforms existing state representation methods in terms of representation quality.

NeurIPS Conference 2024 Conference Paper

Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficiently

• Sergio Calo
• Anders Jonsson
• Gergely Neu
• Ludovic Schwartz
• Javier Segovia-Aguas

We propose a new framework for formulating optimal transport distances between Markov chains. Previously known formulations studied couplings between the entire joint distribution induced by the chains, and derived solutions via a reduction to dynamic programming (DP) in an appropriately defined Markov decision process. This formulation has, however, not led to particularly efficient algorithms so far, since computing the associated DP operators requires fully solving a static optimal transport problem, and these operators need to be applied numerous times during the overall optimization process. In this work, we develop an alternative perspective by considering couplings between a ``flattened'' version of the joint distributions that we call discounted occupancy couplings, and show that calculating optimal transport distances in the full space of joint distributions can be equivalently formulated as solving a linear program (LP) in this reduced space. This LP formulation formulation allows us to port several algorithmic ideas from other areas of optimal transport theory. In particular, our formulation makes it possible to introduce an appropriate notion of entropy regularization into the optimization problem, which in turn enables us to directly calculate optimal transport distances via a Sinkhorn-like method we call Sinkhorn Value Iteration (SVI). We show both theoretically and empirically that this method converges quickly to an optimal coupling, essentially at the same computational cost of running vanilla Sinkhorn in each pair of states. Along the way, we point out that our optimal transport distance exactly matches the common notion of bisimulation metrics between Markov chains, and thus our results also apply to computing such metrics, and in fact our algorithm turns out to be significantly more efficient than the best known methods developed so far for this purpose.

EWRL Workshop 2024 Workshop Paper

Bisimulation Metrics are Optimal Transport Distances, and Can be Computed Efficiently

• Sergio Calo
• Anders Jonsson
• Gergely Neu
• Ludovic Schwartz
• Javier Segovia-Aguas

We propose a new framework for formulating optimal transport distances between Markov chains. Previously known formulations studied couplings between the entire joint distribution induced by the chains, and derived solutions via a reduction to dynamic programming (DP) in an appropriately defined Markov decision process. This formulation has, however, not led to particularly efficient algorithms so far, since computing the associated DP operators requires fully solving a static optimal transport problem, and these operators need to be applied numerous times during the overall optimization process. In this work, we develop an alternative perspective by considering couplings between a “flattened” version of the joint distributions that we call discounted occupancy couplings, and show that calculating optimal transport distances in the full space of joint distributions can be equivalently formulated as solving a linear program (LP) in this reduced space. This LP formulation allows us to port several algorithmic ideas from other areas of optimal transport theory. In particular, our formulation makes it possible to introduce an appropriate notion of entropy regularization into the optimization problem, which in turn enables us to directly calculate optimal transport distances via a Sinkhorn- like method we call Sinkhorn Value Iteration (SVI). We show both theoretically and empirically that this method converges quickly to an optimal coupling, essentially at the same computational cost of running vanilla Sinkhorn in each pair of states. Along the way, we point out that our optimal transport distance exactly matches the common notion of bisimulation metrics between Markov chains, and thus our results also apply to computing such metrics, and in fact our algorithm turns out to be significantly more efficient than the best known methods developed so far for this purpose.

EWRL Workshop 2024 Workshop Paper

Distributed Constrained Multi-Agent Reinforcement Learning with Consensus and Networked Communication

• Santiago Amaya-Corredor
• Miguel Calvo-Fullana
• Anders Jonsson

Our research addresses scalability and coordination challenges inherent to distributed multi-agent systems (MAS) executing under operation constraints. We introduce a novel Constrained Multi-Agent Reinforcement Learning (CMARL) algorithm that integrates a consensus mechanism to ensure agent coordination. Our decentralized approach allows each agent to independently optimize its local rewards while adhering to global constraints evaluated via secondary rewards. These secondary rewards act as a coupling mechanism, penalizing non-cooperative behaviors. Agents operate within a communication network modeled as an undirected graph, exchanging information solely with immediate neighbors to dynamically update dual variables. Our algorithm is validated through its application to the economic dispatch problem within smart grid management, demonstrating its scalability and practical utility in optimizing energy distribution under operational constraints. Experimental results show that our method effectively balances the global and local objectives, proving its robustness in real-world, distributed settings. Key contributions of this work include: (i) the development of a CMARL algorithm that achieves long-term constraint satisfaction and agent consensus, (ii) an enhanced scalability of policy training through problem factorization based on observed state distributions, and (iii) the successful application of our algorithm in a smart grid management use case, highlighting its practical applicability and effectiveness in managing distributed energy resources.

AIJ Journal 2024 Journal Article

Generalized planning as heuristic search: A new planning search-space that leverages pointers over objects

• Javier Segovia-Aguas
• Sergio Jiménez
• Anders Jonsson

Planning as heuristic search is one of the most successful approaches to classical planning but unfortunately, it does not trivially extend to Generalized Planning (GP); GP aims to compute algorithmic solutions that are valid for a set of classical planning instances from a given domain, even if these instances differ in their number of objects, the initial and goal configuration of these objects and hence, in the number (and possible values) of the state variables. State-space search, as it is implemented by heuristic planners, becomes then impractical for GP. In this paper we adapt the planning as heuristic search paradigm to the generalization requirements of GP, and present the first native heuristic search approach to GP. First, the paper introduces a new pointer-based solution space for GP that is independent of the number of classical planning instances in a GP problem and the size of those instances (i. e. the number of objects, state variables and their domain sizes). Second, the paper defines an upgraded version of our GP algorithm, called Best-First Generalized Planning (BFGP), that implements a best-first search in our pointer-based solution space for GP. Lastly, the paper defines a set of evaluation and heuristic functions for BFGP that assess the structural complexity of the candidate GP solutions, as well as their fitness to a given input set of classical planning instances. The computation of these evaluation and heuristic functions does not require grounding states or actions in advance. Therefore our GP as heuristic search approach can handle large sets of state variables with large numerical domains, e. g. integers.

EAAI Journal 2024 Journal Article

Spatial air quality prediction in urban areas via message passing

• Sergio Calo
• Filippo Bistaffa
• Anders Jonsson
• Vicenç Gómez
• Mar Viana

Air pollution in urban areas poses a significant and pressing challenge for modern society. Unfortunately, the existing network of pollution detectors in many cities is limited in scope and fails to adequately cover the entire geographical area. Consequently, the implementation of spatial prediction algorithms becomes essential to generate high-resolution data. In this paper, we introduce two significant contributions: 1) We formalize the air pollution prediction problem as a Maximum A Posteriori (MAP) estimate within the framework of a Markov Random Field and 2) we propose a message-passing algorithm, which stands out as an efficient solution that surpasses the current state of the art. The experimental procedure has been carried out using the case study of the city of Barcelona, based on a dataset extracted from the BCN Open Data portal.

EWRL Workshop 2024 Workshop Paper

Tractable Offline Learning of Regular Decision Processes

• Ahana Deb
• Roberto Cipollone
• Anders Jonsson
• Alessandro Ronca
• Mohammad Sadegh Talebi

This work studies offline Reinforcement Learning (RL) in a class of non-Markovian environments called Regular Decision Processes (RDPs). In RDPs, the unknown dependency of future observations and rewards from the past interactions can be captured by some hidden finite-state automaton. For this reason, many RDP algorithms first reconstruct this unknown dependency using automata learning techniques. In this paper, we show that it is possible to overcome two strong limitations of previous offline RL algorithms for RDPs, notably RegORL. This can be accomplished via the introduction of two original techniques: the development of a new pseudometric based on formal languages, which removes a problematic dependency on $L_\infty^\mathsf{p}$ distinguishability parameters, and the adoption of Count-Min-Sketch (CMS), instead of naive counting. The former reduces the number of samples required in environments that are characterized by a low complexity in language-theoretic terms. The latter alleviates the memory requirements for long planning horizons. We derive the PAC sample complexity bounds associated to each of these techniques, and we validate the approach experimentally.

EWRL Workshop 2024 Workshop Paper

Using a Learned Policy Basis to Optimally Solve Reward Machines

• Guillermo Infante
• David Kuric
• Vicenç Gómez
• Anders Jonsson
• Herke van Hoof

Conventional reinforcement learning (RL) methods can successfully solve a wide range of sequential decision problems. However, learning policies that can generalize predictably across multiple tasks in a setting with non-Markovian reward specifications is a challenging problem. We propose to use successor features (SF) to learn a policy basis so that each (sub)policy in it solves a well-defined subproblem. In a task described by a reward machine (RM) that involves the same set of subproblems, the combination of these (sub)policies can then be used to generate an optimal solution without additional learning. In contrast to other methods that combine (sub)policies via planning, our method asymptotically attains global optimality, even in stochastic environments.

EWRL Workshop 2023 Workshop Paper

Beyond Markovian RL: Efficient Offline RL in Regular Decision Processes

• Roberto Cipollone
• Anders Jonsson
• Alessandro Ronca
• Mohammad Sadegh Talebi

This paper deals with offline (or batch) Reinforcement Learning (RL) in episodic Regular Decision Processes (RDPs). RDPs are the subclass of Non-Markov Decision Processes where the dependency on the history of past events can be captured by a finite-state automaton. We consider a setting where the automaton that underlies the RDP is unknown, and a learner strives to learn a near-optimal policy using pre-collected data, in the form of non-Markov sequences of observations, without further exploration. We present RegORL, an algorithm that suitably combines automata learning techniques and state-of-the-art algorithms for offline RL in MDPs. RegORL has a modular design allowing one to use any off-the-shelf offline RL algorithm in MDPs. We report a non-asymptotic high-probability sample complexity bound for RegORL to yield an $\varepsilon$-optimal policy, which makes appear a notion of concentrability relevant for RDPs. Furthermore, we present a sample complexity lower bound for offline RL in RDPs. To our best knowledge, this is the first work presenting a provably efficient algorithm for offline learning in RDPs.

EWRL Workshop 2023 Workshop Paper

Optimal Hierarchical Average-Reward Linearly-solvable Markov Decision Processes

• Guillermo Infante Molina
• Anders Jonsson
• Vicenç Gómez

We introduce a novel approach to hierarchical reinforcement learning for Linearly-solvable Markov Decision Processes (LMDPs) in the infinite-horizon average-reward setting. Unlike previous work, our approach allows learning low-level and high-level tasks simultaneously, without imposing limiting restrictions on the low-level tasks. Our method relies on partitions of the state space that create smaller subtasks that are easier to solve, and the equivalence between such partitions to learn more efficiently. We then exploit the compositionality of low-level tasks to exactly represent the value function of the high-level task. Experiments show that our approach can outperform flat average-reward reinforcement learning by one or several orders of magnitude.

NeurIPS Conference 2023 Conference Paper

Provably Efficient Offline Reinforcement Learning in Regular Decision Processes

• Roberto Cipollone
• Anders Jonsson
• Alessandro Ronca
• Mohammad Sadegh Talebi

This paper deals with offline (or batch) Reinforcement Learning (RL) in episodic Regular Decision Processes (RDPs). RDPs are the subclass of Non-Markov Decision Processes where the dependency on the history of past events can be captured by a finite-state automaton. We consider a setting where the automaton that underlies the RDP is unknown, and a learner strives to learn a near-optimal policy using pre-collected data, in the form of non-Markov sequences of observations, without further exploration. We present RegORL, an algorithm that suitably combines automata learning techniques and state-of-the-art algorithms for offline RL in MDPs. RegORL has a modular design allowing one to use any off-the-shelf offline RL algorithm in MDPs. We report a non-asymptotic high-probability sample complexity bound for RegORL to yield an $\varepsilon$-optimal policy, which makes appear a notion of concentrability relevant for RDPs. Furthermore, we present a sample complexity lower bound for offline RL in RDPs. To our best knowledge, this is the first work presenting a provably efficient algorithm for offline learning in RDPs.

IJCAI Conference 2022 Conference Paper

Computing Programs for Generalized Planning as Heuristic Search (Extended Abstract)

• Javier Segovia-Aguas
• Sergio Jiménez Celorrio
• Anders Jonsson

Although heuristic search is one of the most successful approaches to classical planning, this planning paradigm does not apply straightforwardly to Generalized Planning (GP). This paper adapts the planning as heuristic search paradigm to the particularities of GP, and presents the first native heuristic search approach to GP. First, the paper defines a program-based solution space for GP that is independent of the number of planning instances in a GP problem, and the size of these instances. Second, the paper defines the BFGP algorithm for GP, that implements a best-first search in our program-based solution space, and that is guided by different evaluation and heuristic functions.

AAAI Conference 2022 Conference Paper

Globally Optimal Hierarchical Reinforcement Learning for Linearly-Solvable Markov Decision Processes

• Guillermo Infante
• Anders Jonsson
• Vicenç Gómez

We present a novel approach to hierarchical reinforcement learning for linearly-solvable Markov decision processes. Our approach assumes that the state space is partitioned, and defines subtasks for moving between the partitions. We represent value functions on several levels of abstraction, and use the compositionality of subtasks to estimate the optimal values of the states in each partition. The policy is implicitly defined on these optimal value estimates, rather than being decomposed among the subtasks. As a consequence, our approach can learn the globally optimal policy, and does not suffer from non-stationarities induced by high-level decisions. If several partitions have equivalent dynamics, the subtasks of those partitions can be shared. We show that our approach is significantly more sample efficient than that of a flat learner and similar hierarchical approaches when the set of boundary states is smaller than the entire state space.

PRL Workshop 2022 Workshop Paper

State Representation Learning for Goal-Conditioned Reinforcement Learning

• Lorenzo Steccanella
• Anders Jonsson

This paper presents a novel state representation for rewardfree Markov decision processes. The idea is to learn, in a self-supervised manner, an embedding space where distances between pairs of embedded states correspond to the minimum number of actions needed to transition between them. Compared to previous methods, our approach does not require any domain knowledge, learning from offline and unlabeled data. We show how this representation can be leveraged to learn goal-conditioned policies, providing a notion of similarity between states and goals and a useful heuristic distance to guide planning and reinforcement learning algorithms. Finally, we empirically validate our method in classic control domains and multi-goal environments, demonstrating that our method can successfully learn representations in large and/or continuous domains.

JAIR Journal 2021 Journal Article

Induction and Exploitation of Subgoal Automata for Reinforcement Learning

• Daniel Furelos-Blanco
• Mark Law
• Anders Jonsson
• Krysia Broda
• Alessandra Russo

In this paper we present ISA, an approach for learning and exploiting subgoals in episodic reinforcement learning (RL) tasks. ISA interleaves reinforcement learning with the induction of a subgoal automaton, an automaton whose edges are labeled by the task’s subgoals expressed as propositional logic formulas over a set of high-level events. A subgoal automaton also consists of two special states: a state indicating the successful completion of the task, and a state indicating that the task has finished without succeeding. A state-of-the-art inductive logic programming system is used to learn a subgoal automaton that covers the traces of high-level events observed by the RL agent. When the currently exploited automaton does not correctly recognize a trace, the automaton learner induces a new automaton that covers that trace. The interleaving process guarantees the induction of automata with the minimum number of states, and applies a symmetry breaking mechanism to shrink the search space whilst remaining complete. We evaluate ISA in several gridworld and continuous state space problems using different RL algorithms that leverage the automaton structures. We provide an in-depth empirical analysis of the automaton learning performance in terms of the traces, the symmetry breaking and specific restrictions imposed on the final learnable automaton. For each class of RL problem, we show that the learned automata can be successfully exploited to learn policies that reach the goal, achieving an average reward comparable to the case where automata are not learned but handcrafted and given beforehand.

AAAI Conference 2020 Conference Paper

Generalized Planning with Positive and Negative Examples

• Javier Segovia-Aguas
• Sergio Jiménez
• Anders Jonsson

Generalized planning aims at computing an algorithm-like structure (generalized plan) that solves a set of multiple planning instances. In this paper we define negative examples for generalized planning as planning instances that must not be solved by a generalized plan. With this regard the paper extends the notion of validation of a generalized plan as the problem of verifying that a given generalized plan solves the set of input positives instances while it fails to solve a given input set of negative examples. This notion of plan validation allows us to define quantitative metrics to asses the generalization capacity of generalized plans. The paper also shows how to incorporate this new notion of plan validation into a compilation for plan synthesis that takes both positive and negative instances as input. Experiments show that incorporating negative examples can accelerate plan synthesis in several domains and leverage quantitative metrics to evaluate the generalization capacity of the synthesized plans.

AAAI Conference 2020 Conference Paper

Induction of Subgoal Automata for Reinforcement Learning

• Daniel Furelos-Blanco
• Mark Law
• Alessandra Russo
• Krysia Broda
• Anders Jonsson

In this work we present ISA, a novel approach for learning and exploiting subgoals in reinforcement learning (RL). Our method relies on inducing an automaton whose transitions are subgoals expressed as propositional formulas over a set of observable events. A state-of-the-art inductive logic programming system is used to learn the automaton from observation traces perceived by the RL agent. The reinforcement learning and automaton learning processes are interleaved: a new re- fined automaton is learned whenever the RL agent generates a trace not recognized by the current automaton. We evaluate ISA in several gridworld problems and show that it performs similarly to a method for which automata are given in advance. We also show that the learned automata can be exploited to speed up convergence through reward shaping and transfer learning across multiple tasks. Finally, we analyze the running time and the number of traces that ISA needs to learn an automata, and the impact that the number of observable events have on the learner’s performance.

NeurIPS Conference 2020 Conference Paper

Planning in Markov Decision Processes with Gap-Dependent Sample Complexity

• Anders Jonsson
• Emilie Kaufmann
• Pierre Menard
• Omar Darwiche Domingues
• Edouard Leurent
• Michal Valko

We propose MDP-GapE, a new trajectory-based Monte-Carlo Tree Search algorithm for planning in a Markov Decision Process in which transitions have a finite support. We prove an upper bound on the number of sampled trajectories needed for MDP-GapE to identify a near-optimal action with high probability. This problem-dependent result is expressed in terms of the sub-optimality gaps of the state-action pairs that are visited during exploration. Our experiments reveal that MDP-GapE is also effective in practice, in contrast with other algorithms with sample complexity guarantees in the fixed-confidence setting, that are mostly theoretical.

KER Journal 2019 Journal Article

A review of generalized planning

• Sergio Jiménez
• Javier Segovia-Aguas
• Anders Jonsson

Abstract Generalized planning studies the representation, computation and evaluation of solutions that are valid for multiple planning instances. These are topics studied since the early days of AI. However, in recent years, we are experiencing the appearance of novel formalisms to compactly represent generalized planning tasks, the solutions to these tasks (called generalized plans ) and efficient algorithms to compute generalized plans. The paper reviews recent advances in generalized planning and relates them to existing planning formalisms, such as planning with domain control knowledge and approaches for planning under uncertainty, that also aim at generality.

AIJ Journal 2019 Journal Article

Computing programs for generalized planning using a classical planner

• Javier Segovia-Aguas
• Sergio Jiménez
• Anders Jonsson

Generalized planning is the task of generating a single solution (a generalized plan) that is valid for multiple planning instances. In this paper we introduce a novel formalism for representing generalized plans that borrows two mechanisms from structured programming: control flow and procedure calls. On one hand, control flow structures allow to compactly represent generalized plans. On the other hand, procedure calls allow to represent hierarchical and recursive solutions as well as to reuse existing generalized plans. The paper also presents a compilation from generalized planning into classical planning which allows us to compute generalized plans with off-the-shelf planners. The compilation can incorporate prior knowledge in the form of auxiliary procedures which expands the applicability of the approach to more challenging tasks. Experiments show that a classical planner using our compilation can compute generalized plans that solve a wide range of generalized planning tasks, including sorting lists of variable size or DFS traversing variable-size binary trees. Additionally the paper presents an extension of the compilation for computing generalized plans when generalization requires a high-level state representation that is not provided a priori. This extension brings a new landscape of benchmarks to classical planning since classification tasks can naturally be modeled as generalized planning tasks, and hence, as classical planning tasks. Finally the paper shows that the compilation can be extended to compute control knowledge for off-the-shelf planners and solve planning instances that are difficult to solve without such additional knowledge.

AAAI Conference 2019 Conference Paper

Solving Multiagent Planning Problems with Concurrent Conditional Effects

• Daniel Furelos-Blanco
• Anders Jonsson

In this work we present a novel approach to solving concurrent multiagent planning problems in which several agents act in parallel. Our approach relies on a compilation from concurrent multiagent planning to classical planning, allowing us to use an off-the-shelf classical planner to solve the original multiagent problem. The solution can be directly interpreted as a concurrent plan that satisfies a given set of concurrency constraints, while avoiding the exponential blowup associated with concurrent actions. Our planner is the first to handle action effects that are conditional on what other agents are doing. Theoretically, we show that the compilation is sound and complete. Empirically, we show that our compilation can solve challenging multiagent planning problems that require concurrent actions.

AAMAS Conference 2018 Conference Paper

CARPooL: Collective Adaptation using concuRrent PLanning

• Daniel Furelos-Blanco
• Antonio Bucchiarone
• Anders Jonsson

In this paper we present the CARPooL demonstrator, an implementation of a Collective Adaptation Engine (CAE) that addresses the challenge of collective adaptation in the smart mobility domain. CARPooL resolves adaptation issues via concurrent planning techniques. It also allows to interact with the provided solutions by adding new issues or analyzing the actions done by each agent.

AAMAS Conference 2018 Conference Paper

Collective Adaptation through Concurrent Planning: the Case of Sustainable Urban Mobility

• Antonio Bucchiarone
• Daniel Furelos-Blanco
• Anders Jonsson
• Fahmida Khandokar
• Monjur Mourshed

In this paper we address the challenges that impede collective adaptation in smart mobility systems by proposing a notion of ensembles. Ensembles enable systems with collective adaptability to be built as emergent aggregations of autonomous and self-adaptive agents. Adaptation in these systems is triggered by a run-time occurrence, which is known as an issue. The novel aspect of our approach is, it allows agents affected by an issue in the context of a smart mobility scenario to adapt collaboratively with minimal impact on their own preferences through an issue resolution process based on concurrent planning algorithms.

JAIR Journal 2018 Journal Article

Computing Hierarchical Finite State Controllers With Classical Planning

• Javier Segovia-Aguas
• Sergio Jiménez
• Anders Jonsson

Finite State Controllers (FSCs) are an effective way to compactly represent sequential plans. By imposing appropriate conditions on transitions, FSCs can also represent generalized plans (plans that solve a range of planning problems from a given domain). In this paper we introduce the concept of hierarchical FSCs for planning by allowing controllers to call other controllers. This call mechanism allows hierarchical FSCs to represent generalized plans more compactly than individual FSCs, to compute controllers in a modular fashion or even more, to compute recursive controllers. The paper introduces a classical planning compilation for computing hierarchical FSCs that solve challenging generalized planning tasks. The compilation takes as input a finite set of classical planning problems from a given domain. The output of the compilation is a single classical planning problem whose solution induces: (1) a hierarchical FSC and (2), the corresponding validation of that controller on the input classical planning problems.

IJCAI Conference 2017 Conference Paper

Generating Context-Free Grammars using Classical Planning

• Javier Segovia-Aguas
• Sergio Jiménez
• Anders Jonsson

This paper presents a novel approach for generating Context-Free Grammars (CFGs) from small sets of input strings (a single input string in some cases). Our approach is to compile this task into a classical planning problem whose solutions are sequences of actions that build and validate a CFG compliant with the input strings. In addition, we show that our compilation is suitable for implementing the two canonical tasks for CFGs, string production and string recognition.

IJCAI Conference 2016 Conference Paper

Automatic Generation of High-Level State Features for Generalized Planning

• Damir Lotinac
• Javier Segovia-Aguas
• Sergio Jim
• eacute; nez
• Anders Jonsson

In many domains generalized plans can only be computed if certain high-level state features, i. e. ~features that capture key concepts to accurately distinguish between states and make good decisions, are available. In most applications of generalized planning such features are hand-coded by an expert. This paper presents a novel method to automatically generate high-level state features for solving a generalized planning problem. Our method extends a compilation of generalized planning into classical planning and integrates the computation of generalized plans with the computation of features, in the form of conjunctive queries. Experiments show that we generate features for diverse generalized planning problems and hence, compute generalized plans without providing a prior high-level representation of the states. We also bring a new landscape of challenging benchmarks to classical planning since our compilation naturally models classification tasks as classical planning problems.

IJCAI Conference 2016 Conference Paper

Hierarchical Finite State Controllers for Generalized Planning

• Javier Segovia-Aguas
• Sergio Jim
• eacute; nez
• Anders Jonsson

Finite State Controllers (FSCs) are an effective way to represent sequential plans compactly. By imposing appropriate conditions on transitions, FSCs can also represent generalized plans that solve a range of planning problems from a given domain. In this paper we introduce the concept of hierarchical FSCs for planning by allowing controllers to call other controllers. We show that hierarchical FSCs can represent generalized plans more compactly than individual FSCs. Moreover, our call mechanism makes it possible to generate hierarchical FSCs in a modular fashion, or even to apply recursion. We also introduce a compilation that enables a classical planner to generate hierarchical FSCs that solve challenging generalized planning problems. The compilation takes as input a set of planning problems from a given domain and outputs a single classical planning problem, whose solution corresponds to a hierarchical FSC.

RLDM Conference 2015 Conference Abstract

Automatic Generation of HTNs From PDDL

• Anders Jonsson
• Damir Lotinac

Hierarchical Task Networks, or HTNs, are a popular model in planning for representing tasks or decision processes that are organized in a hierarchy. Although HTNs are known to be at least as expressive as STRIPS planning, being expressive enough to represent highly complex decision processes is not the main reason for their popularity. On the contrary, by imposing ordering constraints on the tasks at each level of the hierarchy, an HTN can significantly simplify the search for an action sequence that achieves a desired goal. In this paper we present a novel algorithm that automatically generates HTNs from PDDL, the standard language for describing planning domains. The HTNs that our algorithmconstructs contain two types of composite tasks that interact to achieve the goal of a planning instance. One type of task achieves fluents by traversing the edges of invariant graphs in which only one fluent can be true at a time. The other type of task traverses a single edge of an invariant graph by applying the associated action, which first involves ensuring that the preconditions of the action hold. The resulting HTNs can be applied to any instance of a planning domain, and are provably sound, such that the solution to an HTN instance can always be translated back to a solution to the original planning instance. In several domains we are able to solve most or all planning instances using HTNs created from a single example instance. Poster T47*: Reinforcement Learning in Decentralized Stochastic Control Systems with Partial History Sharing Jalal Arabneydi*, McGill University; Aditya Mahajan, McGill University In this paper, we are interested in systems with multiple agents that wish to cooperate in order to accomplish a common task while a) agents have different information (decentralized information) and b) agents do not know the complete model of the system i. e. , they may only know the partial model or may not know the model at all. The agents must learn the optimal strategies by interacting with their environment i. e. , by multi-agent Reinforcement Learning (RL). The presence of multiple agents with different informa- tion makes multi-agent (decentralized) reinforcement learning conceptually more difficult than single-agent (centralized) reinforcement learning. We propose a novel multi-agent reinforcement learning algorithm that learns epsilon-team-optimal solution for systems with partial history sharing information structure, which encompasses a large class of multi-agent systems including delayed sharing, control sharing, mean field sharing, etc. Our approach consists of two main steps as follows: 1) the multiagent (decentralized) system is converted to an equivalent single-agent (centralized) POMDP (Partial Observable Markov Decision Process) using the common information approach of Nayyar et al, TAC 2013, and 2) based on the obtained POMDP, an approximate RL algorithm is constructed using a novel methodology. We show that the performance of the RL strategy converges to the optimal performance exponentially fast. We illustrate the proposed ap- proach and verify it numerically by obtaining a multi-agent Q-learning algorithm for two-user Multi Access Broadcast Channel (MABC) which is a benchmark example for multi-agent systems.

AIJ Journal 2014 Journal Article

Limitations of acyclic causal graphs for planning

• Anders Jonsson
• Peter Jonsson
• Tomas Lööw

Causal graphs are widely used in planning to capture the internal structure of planning instances. Researchers have paid special attention to the subclass of planning instances with acyclic causal graphs, which in the past have been exploited to generate hierarchical plans, to compute heuristics, and to identify classes of planning instances that are easy to solve. This naturally raises the question of whether planning is easier when the causal graph is acyclic. In this article we show that the answer to this question is no, proving that in the worst case, the problem of plan existence is PSPACE -complete even when the causal graph is acyclic. Since the variables of the planning instances in our reduction are propositional, this result applies to Strips planning with negative preconditions. We show that the reduction still holds if we restrict actions to have at most two preconditions. Having established that planning is hard for acyclic causal graphs, we study two subclasses of planning instances with acyclic causal graphs. One such subclass is described by propositional variables that are either irreversible or symmetrically reversible. Another subclass is described by variables with strongly connected domain transition graphs. In both cases, plan existence is bounded away from PSPACE, but in the latter case, the problem of bounded plan existence is hard, implying that optimal planning is significantly harder than satisficing planning for this class.

AIJ Journal 2012 Journal Article

The influence of k-dependence on the complexity of planning

• Omer Giménez
• Anders Jonsson

A planning problem is k-dependent if each action has at most k pre-conditions on variables unaffected by the action. This concept is of interest because k is a constant for all but a few of the current benchmark domains in planning, and is known to have implications for tractability. In this paper, we present an algorithm for solving planning problems in P ( k ), the class of k-dependent planning problems with binary variables and polytree causal graphs. We prove that our algorithm runs in polynomial time when k is a fixed constant. If, in addition, the causal graph has bounded depth, we show that plan generation is linear in the size of the input. Although these contributions are theoretical due to the limited scope of the class P ( k ), suitable reductions from more complex planning problems to P ( k ) could potentially give rise to fast domain-independent heuristics.

IJCAI Conference 2007 Conference Paper

• Anders Jonsson

The complexity of existing planners is bounded by the length of the resulting plan, a fact that limits planning to domains with relatively short solutions. We present a novel planning algorithm that uses the causal graph of a domain to decompose it into subproblems and stores subproblem plans in memory as macros. In many domains, the resulting plan can be expressed using relatively few macros, making it possible to generate exponential length plans in polynomial time. We show that our algorithm is complete, and that there exist special cases for which it is optimal and polynomial. Experimental results demonstrate the potential of using macros to solve planning domains with long solution plans.

JMLR Journal 2006 Journal Article

Causal Graph Based Decomposition of Factored MDPs

• Anders Jonsson
• Andrew Barto

We present Variable Influence Structure Analysis, or VISA, an algorithm that performs hierarchical decomposition of factored Markov decision processes. VISA uses a dynamic Bayesian network model of actions, and constructs a causal graph that captures relationships between state variables. In tasks with sparse causal graphs VISA exploits structure by introducing activities that cause the values of state variables to change. The result is a hierarchy of activities that together represent a solution to the original task. VISA performs state abstraction for each activity by ignoring irrelevant state variables and lower-level activities. In addition, we describe an algorithm for constructing compact models of the activities introduced. State abstraction and compact activity models enable VISA to apply efficient algorithms to solve the stand-alone subtask associated with each activity. Experimental results show that the decomposition introduced by VISA can significantly accelerate construction of an optimal, or near-optimal, policy. [abs] [ pdf ][ bib ] &copy JMLR 2006. ( edit, beta )

NeurIPS Conference 2000 Conference Paper

Automated State Abstraction for Options using the U-Tree Algorithm

• Anders Jonsson
• Andrew Barto

Learning a complex task can be significantly facilitated by defining a hierarchy of subtasks. An agent can learn to choose between various temporally abstract actions, each solving an assigned subtask, to accom(cid: 173) plish the overall task. In this paper, we study hierarchical learning using the framework of options. We argue that to take full advantage of hier(cid: 173) archical structure, one should perform option-specific state abstraction, and that if this is to scale to larger tasks, state abstraction should be au(cid: 173) tomated. We adapt McCallum's U-Tree algorithm to automatically build option-specific representations of the state feature space, and we illus(cid: 173) trate the resulting algorithm using a simple hierarchical task. Results suggest that automated option-specific state abstraction is an attractive approach to making hierarchical learning systems more effective.