Tag Archives: Abstraction

Object oriented paradigm to improve transfer learning in RL, i.e., a sort of symbolic abstraction mechanism

Ofir Marom, Benjamin Rosman, Transferable dynamics models for efficient object-oriented reinforcement learning, Robotics and Autonomous Systems, Volume 174, 2024 DOI: 10.1016/j.artint.2024.104079.

The Reinforcement Learning (RL) framework offers a general paradigm for constructing autonomous agents that can make effective decisions when solving tasks. An important area of study within the field of RL is transfer learning, where an agent utilizes knowledge gained from solving previous tasks to solve a new task more efficiently. While the notion of transfer learning is conceptually appealing, in practice, not all RL representations are amenable to transfer learning. Moreover, much of the research on transfer learning in RL is purely empirical. Previous research has shown that object-oriented representations are suitable for the purposes of transfer learning with theoretical efficiency guarantees. Such representations leverage the notion of object classes to learn lifted rules that apply to grounded object instantiations. In this paper, we extend previous research on object-oriented representations and introduce two formalisms: the first is based on deictic predicates, and is used to learn a transferable transition dynamics model; the second is based on propositions, and is used to learn a transferable reward dynamics model. In addition, we extend previously introduced efficient learning algorithms for object-oriented representations to our proposed formalisms. Our frameworks are then combined into a single efficient algorithm that learns transferable transition and reward dynamics models across a domain of related tasks. We illustrate our proposed algorithm empirically on an extended version of the Taxi domain, as well as the more difficult Sokoban domain, showing the benefits of our approach with regards to efficient learning and transfer.

Abstraction of continuous control problems considered as MDPs

H. G. Tanner and A. Stager, Data-Driven Abstractions for Robots With Stochastic Dynamics, IEEE Transactions on Robotics, vol. 38, no. 3, pp. 1686-1702, June 2022 DOI: 10.1109/TRO.2021.3119209.

This article describes the construction of stochastic, data-based discrete abstractions for uncertain random processes continuous in time and space. Motivated by the fact that modeling processes often introduce errors which interfere with the implementation of control strategies, here the abstraction process proceeds in reverse: the methodology does not abstract models; rather it models abstractions. Specifically, it first formalizes a template for a family of stochastic abstractions, and then fits the parameters of that template to match the dynamics of the underlying process and ground the abstraction. The article also shows how the parameter-fitting approach can be implemented based on a probabilistic model validation approach which draws from randomized algorithms, and results in a discrete abstract model which is approximately simulated by the actual process physics, at a desired confidence level. In this way, the models afford the implementation of symbolic control plans with probabilistic guarantees at a desired level of fidelity.

A general model of abstraction of graphs

Christer Bäckström, Peter Jonsson, A framework for analysing state-abstraction methods, Artificial Intelligence, Volume 302, 2022 DOI: 10.1016/j.artint.2021.103608.

Abstraction has been used in combinatorial search and action planning from the very beginning of AI. Many different methods and formalisms for state abstraction have been proposed in the literature, but they have been designed from various points of view and with varying purposes. Hence, these methods have been notoriously difficult to analyse and compare in a structured way. In order to improve upon this situation, we present a coherent and flexible framework for modelling abstraction (and abstraction-like) methods based on graph transformations. The usefulness of the framework is demonstrated by applying it to problems in both search and planning. We model six different abstraction methods from the planning literature and analyse their intrinsic properties. We show how to capture many search abstraction concepts (such as avoiding backtracking between levels) and how to put them into a broader context. We also use the framework to identify and investigate connections between refinement and heuristics—two concepts that have usually been considered as unrelated in the literature. This provides new insights into various topics, e.g. Valtorta’s theorem and spurious states. We finally extend the framework with composition of transformations to accommodate for abstraction hierarchies, and other multi-level concepts. We demonstrate the latter by modelling and analysing the merge-and-shrink abstraction method.

Using abstraction of dimensions in RRT motion planning

Xanthidis, M., Esposito, J.M., Rekleitis, I. et al., Motion Planning by Sampling in Subspaces of Progressively Increasing Dimension, . J Intell Robot Syst 100, 777–789 (2020) DOI: 10.1007/s10846-020-01217-w.

This paper introduces an enhancement to traditional sampling-based planners, resulting in efficiency increases for high-dimensional holonomic systems such as hyper-redundant manipulators, snake-like robots, and humanoids. Despite the performance advantages of modern sampling-based motion planners, solving high dimensional planning problems in near real-time remains a considerable challenge. The proposed enhancement to popular sampling-based planning algorithms is aimed at circumventing the exponential dependence on dimensionality, by progressively exploring lower dimensional volumes of the configuration space. Extensive experiments comparing the enhanced and traditional version of RRT, RRT-Connect, and Bidirectional T-RRT on both a planar hyper-redundant manipulator and the Baxter humanoid robot show significant acceleration, up to two orders of magnitude, on computing a solution. We also explore important implementation issues in the sampling process and discuss the limitations of this method.

Abstraction of controllers

Stanley W. Smith, Murat Arcak, Majid Zamani, Approximate abstractions of control systems with an application to aggregation, Automatica, 119 (2020) DOI: 10.1016/j.automatica.2020.109065.

Previous approaches to constructing abstractions for control systems rely on geometric conditions or, in the case of an interconnected control system, a condition on the interconnection topology. Since these conditions are not always satisfiable, we relax the restrictions on the choice of abstractions, instead opting to select ones which nearly satisfy such conditions via optimization-based approaches. To quantify the resulting effect on the error between the abstraction and concrete control system, we introduce the notions of practical simulation functions and practical storage functions. We show that our approach facilitates the procedure of aggregation, where one creates an abstraction by partitioning agents into aggregate areas. We demonstrate the results on an application where we regulate the temperature in three separate zones of a building.