Skip to main content

Resultados relacionados

Resultados totales (Incluyendo duplicados): 8
Encontrada(s) 1 página(s)

Repositorio Digital de la UPF
Publication Contribución de congreso (ConferenceOutput)

Provably efficient offline reinforcement learning in regular decision processes

  • Cipollone, Roberto
  • Ronca, Alessandro
  • Jonsson, Anders
  • Sadegh Talebi, Mohammad
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 ε-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., Roberto Cipollone is partially supported by the EU H2020 project AIPlan4EU (No. 101016442), the ERC-ADG White-Mech (No. 834228), the EU ICT-48 2020 project TAILOR (No. 952215), the PRIN project RIPER (No. 20203FFYLK), and the PNRR MUR project FAIR (No. PE0000013). Anders Jonsson is partially supported by the EU ICT-48 2020 project TAILOR (No. 952215), AGAUR SGR, and the Spanish grant PID2019-108141GB-I00. Alessandro Ronca is partially supported by the ERC project WhiteMech (No. 834228), and the ERC project ARiAT (No. 852769). Mohammad Sadegh Talebi is partially supported by the Independent Research Fund Denmark, grant number 1026-00397B.
Repositorio Digital de la UPF
Publication Artículo científico (JournalArticle)

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

  • Segovia-Aguas, Javier
  • Jiménez, Sergio
  • Jonsson, Anders, 1973-
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., This work has been co-funded by MCIN/AEI /10.13039/501100011033 under the Maria de Maeztu Units of Excellence Programme (CEX2021-001195-M), TAILOR (H2020 #952215) and AIPlan4EU (H2020 #101016442) projects. Javier Segovia-Aguas is also supported by AGAUR SGR and the Spanish grant PID2019-108141 GB-I00. Sergio Jiménez is supported by the Spanish MINECO project PID2021-127647NB-C22. Anders Jonsson is partially supported by Spanish grant PID2019-108141 GB-I00.
Repositorio Digital de la UPF
Publication Contribución de congreso (ConferenceOutput)

Synthesis of procedural models for deterministic transition systems

  • Segovia-Aguas, Javier
  • Ferrer Mestres, Jonathan
  • Sergio, Jiménez
Comunicació presentada a la 26th European Conference on Artificial Intelligence, celebrada del 30 de setembre al 4 d'octubre de 2023 a Kraków, Poland., This paper introduces a general approach for synthesizing procedural models of the state-transitions of a given discrete system. The approach is general in that it accepts different target languages for modeling the state-transitions of a discrete system; different model acquisition tasks with different target languages, such as the synthesis of STRIPS action models, or the update rule of a cellular automaton, fit as particular instances of our general approach. We follow an inductive approach to synthesis meaning that a set of examples of state-transitions, represented as (pre-state, action, post-state) tuples, are given as input. The goal is to synthesize a structured program that, when executed on a given pre-state, outputs its associated post-state. Our synthesis method implements a combinatorial search in the space of well-structured terminating programs that can be built using a Random-Access Machine (RAM), with a minimalist instruction set, and a finite amount of memory. The combinatorial search is guided with functions that asses the complexity of the candidate programs, as well as their fitness to the given input set of examples., This work is supported by the H2020 AIPLAN4EU project #101016442. Javier Segovia-Aguas is funded by TAILOR, AGAUR SGR and the Spanish grant PID2019-108141GB-I00. Jonathan Ferrer-Mestres is supported by the CSIRO MLAI Future Science Platform. Sergio Jiménez is funded by the Spanish MINECO project PID2021-127647NB-C22.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

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

  • Segovia-Aguas, Javier
  • Jonsson, Anders
  • Jiménez-Celorrio, Sergio|||0000-0003-0561-4880
[EN] 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 pointerbased 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., This work has been co-funded by MCIN/AEI/10.13039/501100011033 under the Maria de Maeztu Units of Excellence Programme (CEX2021-001195-M) , TAILOR (H2020 #952215) and AIPLAN4EU (H2020 #101016442) projects. Javier Segovia-Aguas is also supported by AGAUR SGR and the Spanish grant PID2019-108141 GB-I00. Sergio Jimenez is supported by the Spanish MINECO project PID2021-127647NB-C22. Anders Jonsson is partially supported by Spanish grant PID2019-108141 GB-I00.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

A hybrid approach for expressive numeric and temporal planning with control parameters

  • Sapena Vercher, Oscar|||0000-0003-0533-5603
  • Onaindia De La Rivaherrera, Eva|||0000-0001-6931-8293
  • Marzal Calatayud, Eliseo Jorge|||0000-0003-0658-1953
[EN] Since the release of PDDL 2.1, many planners accepted the challenge of addressing more complicated domains and problems, including both temporal and numeric features for scheduling and resources management. However, very few planners can handle a significant subset of the features that the language allows for modeling. To handle a level of expressiveness sufficient to work with more realistic problems, we have designed NextFLAP (Numeric EXpressions in TFLAP). The planner follows a hybrid approach, which combines a forward partial-order planner with a numeric constraint solver/optimizer. Additionally, we include a new feature, the control parameters, which are relevant for direct modeling numerical quantities and physical properties of objects in the actions, such as ¿partially charging of a battery¿ or ¿obtaining a certain amount of resources¿. This feature overcomes a limitation of the PDDL language, which is that the parameters of the actions must be objects (finite domain values) and, in no case, numeric variables. In this paper we illustrate the advantages of using these temporal and numeric modelling features and then describe our planning system, NextFLAP, that can handle these domains. We show that NextFLAP is competitive with other state-of-the-art planners and that it generates good-quality plans., This work is supported by the Spanish AEI PID2021-127647NB-C22 project and EU ICT-48 2020 project TAILOR (No. 952215) and EU-H2020 project AIPlan4EU (101016442).
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Provably efficient offline reinforcement learning in regular decision processes

  • Cipollone, Roberto
  • Ronca, Alessandro
  • Jonsson, Anders
  • Sadegh Talebi, Mohammad
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 ε-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., Roberto Cipollone is partially supported by the EU H2020 project AIPlan4EU (No. 101016442), the ERC-ADG White-Mech (No. 834228), the EU ICT-48 2020 project TAILOR (No. 952215), the PRIN project RIPER (No. 20203FFYLK), and the PNRR MUR project FAIR (No. PE0000013). Anders Jonsson is partially supported by the EU ICT-48 2020 project TAILOR (No. 952215), AGAUR SGR, and the Spanish grant PID2019-108141GB-I00. Alessandro Ronca is partially supported by the ERC project WhiteMech (No. 834228), and the ERC project ARiAT (No. 852769). Mohammad Sadegh Talebi is partially supported by the Independent Research Fund Denmark, grant number 1026-00397B.
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Synthesis of procedural models for deterministic transition systems

  • Segovia-Aguas, Javier
  • Ferrer Mestres, Jonathan
  • Sergio, Jiménez
Comunicació presentada a la 26th European Conference on Artificial Intelligence, celebrada del 30 de setembre al 4 d'octubre de 2023 a Kraków, Poland., This paper introduces a general approach for synthesizing procedural models of the state-transitions of a given discrete system. The approach is general in that it accepts different target languages for modeling the state-transitions of a discrete system; different model acquisition tasks with different target languages, such as the synthesis of STRIPS action models, or the update rule of a cellular automaton, fit as particular instances of our general approach. We follow an inductive approach to synthesis meaning that a set of examples of state-transitions, represented as (pre-state, action, post-state) tuples, are given as input. The goal is to synthesize a structured program that, when executed on a given pre-state, outputs its associated post-state. Our synthesis method implements a combinatorial search in the space of well-structured terminating programs that can be built using a Random-Access Machine (RAM), with a minimalist instruction set, and a finite amount of memory. The combinatorial search is guided with functions that asses the complexity of the candidate programs, as well as their fitness to the given input set of examples., This work is supported by the H2020 AIPLAN4EU project #101016442. Javier Segovia-Aguas is funded by TAILOR, AGAUR SGR and the Spanish grant PID2019-108141GB-I00. Jonathan Ferrer-Mestres is supported by the CSIRO MLAI Future Science Platform. Sergio Jiménez is funded by the Spanish MINECO project PID2021-127647NB-C22.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

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

  • Segovia-Aguas, Javier
  • Jiménez, Sergio
  • Jonsson, Anders, 1973-
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., This work has been co-funded by MCIN/AEI /10.13039/501100011033 under the Maria de Maeztu Units of Excellence Programme (CEX2021-001195-M), TAILOR (H2020 #952215) and AIPlan4EU (H2020 #101016442) projects. Javier Segovia-Aguas is also supported by AGAUR SGR and the Spanish grant PID2019-108141 GB-I00. Sergio Jiménez is supported by the Spanish MINECO project PID2021-127647NB-C22. Anders Jonsson is partially supported by Spanish grant PID2019-108141 GB-I00.