Skip to main content

COMPORTAMIENTO AUTONOMO BASADO EN MODELOS: ALGORITMOS ROBUSTOS

TIN2009-10232

•
Funding agency name Ministerio de Ciencia e Innovación
Funding agency acronym MICINN
Program Programa Nacional de Proyectos de Investigación Fundamental
Subprogram Subprograma de Proyectos de Investigación Fundamental no Orientada
Call Proyectos I+D
Call year 2009
State Plan 2008-2011 Plan Nacional de Investigación Científica, Desarrollo e Innovación Tecnológica
Management unit Subdirección General de Proyectos de Investigación
Beneficiary centre UNIVERSITAT POMPEU FABRA CCT

Resultados relacionados

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

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

Action selection for MDPs: anytime AO* vs. UCT

  • Bonet, Blai
  • Geffner, Héctor
Comunicació presentada a: the 26th AAAI Conference on Artificial Intelligence, celebrada a Toronto, Canadà, del 22 al 26 de juliol de 2012, In the presence of non-admissible heuristics, A* and other best-first algorithms can be converted into anytime optimal algorithms over OR graphs, by simply continuing the search after the first solution is found. The same trick, however, does not work for best-first algorithms over AND/OR graphs, that must be able to expand leaf nodes of the explicit graph that are not necessarily part of the best partial solution. Anytime optimal variants of AO* must thus address an exploration-exploitation tradeoff: they cannot just ”exploit”, they must keep exploring as well. In this work, we develop one such variant of AO* and apply it to finite-horizon MDPs. This Anytime AO* algorithm eventually delivers an optimal policy while using non-admissible random heuristics that can be sampled, as when the heuristic is the cost of a base policy that can be sampled with rollouts. We then test Anytime AO* for action selection over large infinite-horizon MDPs that cannot be solved with existing off-line heuristic search and dynamic programming algorithms, and compare it with UCT., H. Geffner is partially supported by grants TIN2009-10232, MICINN, Spain, and EC-7PM SpaceBook.
Repositorio Digital de la UPF
Publication Contribución de congreso (ConferenceOutput)

Width and complexity of belief tracking in non-deterministic conformant and contingent planning

  • Bonet, Blai
  • Geffner, Héctor
Comunicació presentada a: the 26th AAAI Conference on Artificial Intelligence, celebrada a Toronto, Canadà, del 22 al 26 de juliol de 2012, It has been shown recently that the complexity of belief tracking in deterministic conformant and contingent planning is exponential in a width parameter that is often bounded and small. In this work, we introduce a new width notion that applies to non-deterministic conformant and contingent problems as well. We also develop a belief tracking algorithm for non-deterministic problems that is exponential in the problem width, analyze the width of non-deterministic benchmarks, compare the new notion to the previous one over deterministic problems, and present experimental results., H. Geffner is partially supported by grants TIN2009-10232, MICINN, Spain, and EC-7PM SpaceBook.
Repositorio Digital de la UPF
Publication Contribución de congreso (ConferenceOutput)

Searching for plans with carefully designed probes

  • Lipovetzky, Nir
  • Geffner, Héctor
Comunicació presentada a: 21st International Conference on Automated Planning and Scheduling (ICAPS) celebrada de l'11 al 16 de juny de 2011 a Freiburg, Alemanya., We define a probe to be a single action sequence computedgreedily from a given state that either terminates in the goalor fails. We show that by designing these probes carefullyusing a number of existing and new polynomial techniquessuch as helpful actions, landmarks, commitments, and con-sistent subgoals, a single probe from the initial state solvesby itself 683 out of 980 problems from previous IPCs, a num-ber that compares well with the 627 problems solved by FFin EHC mode, with similar times and plan lengths. We alsoshow that by launching one probe from each expanded statein a standard greedy best first search informed by the addi-tive heuristic, the number of problems solved jumps to 900(92%), as opposed to FF that solves 827 problems (84%),and LAMA that solves 879 (89%). The success of probessuggests that many domains can be solved easily once a suit-able serialization of the landmarks is found, an observationthat may open new connections between recent work in plan-ning and more classical work concerning goal serializationand problem decomposition in planning and search., This work is partially supported by grants TIN2009-10232, MICINN, Spain, and EC-7PM-SpaceBook.
Repositorio Digital de la UPF
Publication Contribución de congreso (ConferenceOutput)

Heuristic search for generalized stochastic shortest path MDPs

  • Kolobov, Andrey
  • Mausam
  • Weld, Daniel S.
  • Geffner, Héctor
Comunicació presentada a: ICAPS 2011 celebrat de l'11 al 16 de juny de 2011 a Freiburg, Alemanya., Research in efficient methods for solving infinite-horizon MDPs has so far concentrated primarily on discounted MDPs and the more general stochastic shortest path problems (SSPs). These are MDPs with 1) an optimal value function V ∗ that is the unique solution of Bellman equation and 2) optimal policies that are the greedy policies w.r.t. V ∗ . This paper’s main contribution is the description of a new class of MDPs, that have well-defined optimal solutions that do not comply with either 1 or 2 above. We call our new class Generalized Stochastic Shortest Path (GSSP) problems. GSSP allows more general reward structure than SSP and subsumes several established MDP types including SSP, positive-bounded, negative, and discounted-reward models. While existing efficient heuristic search algorithms like LAO∗ and LRTDP are not guaranteed to converge to the optimal value function for GSSPs, we present a new heuristic-search-based family of algorithms, FRET (Find, Revise, Eliminate Traps). A preliminary empirical evaluation shows that FRET solves GSSPs much more efficiently than Value Iteration., This work was supported by WRF/TJ Cable Professorship and the following grants: ONR N000140910051, NSF IIS-1016465, TIN2009-10232 (MICINN, Spain).
Repositorio Digital de la UPF
Publication Contribución de congreso (ConferenceOutput)

Width and serialization of classical planning problems

  • Geffner, Héctor
  • Lipovetzky, Nir
We introduce a width parameter that bounds the complexity of classical planning problems and domains, along with a simple but effective blind-search procedure that runs in time that is exponential in the problem width. We show that many benchmark domains have a bounded and small width provided thatgoals are restricted to single atoms, and hence that such problems are provably solvable in low polynomial time. We then focus on the practical value of these ideas over the existing benchmarks which feature conjunctive goals. We show that the blind-search procedure can be used for both serializing the goal into subgoals and for solving the resulting problems, resulting in a ‘blind’ planner that competes well with a best-first search planner guided by state-of-the-art heuristics. In addition, ideas like helpful actions and landmarks can be integrated as well, producing a planner with state-of-the-art performance., H. Geffner is partially supported by grants TIN2009-10232,MICINN, Spain, and EC-7PM-SpaceBook.
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Action selection for MDPs: anytime AO* vs. UCT

  • Bonet, Blai
  • Geffner, Héctor
Comunicació presentada a: the 26th AAAI Conference on Artificial Intelligence, celebrada a Toronto, Canadà, del 22 al 26 de juliol de 2012, In the presence of non-admissible heuristics, A* and other best-first algorithms can be converted into anytime optimal algorithms over OR graphs, by simply continuing the search after the first solution is found. The same trick, however, does not work for best-first algorithms over AND/OR graphs, that must be able to expand leaf nodes of the explicit graph that are not necessarily part of the best partial solution. Anytime optimal variants of AO* must thus address an exploration-exploitation tradeoff: they cannot just ”exploit”, they must keep exploring as well. In this work, we develop one such variant of AO* and apply it to finite-horizon MDPs. This Anytime AO* algorithm eventually delivers an optimal policy while using non-admissible random heuristics that can be sampled, as when the heuristic is the cost of a base policy that can be sampled with rollouts. We then test Anytime AO* for action selection over large infinite-horizon MDPs that cannot be solved with existing off-line heuristic search and dynamic programming algorithms, and compare it with UCT., H. Geffner is partially supported by grants TIN2009-10232, MICINN, Spain, and EC-7PM SpaceBook.
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Width and complexity of belief tracking in non-deterministic conformant and contingent planning

  • Bonet, Blai
  • Geffner, Héctor
Comunicació presentada a: the 26th AAAI Conference on Artificial Intelligence, celebrada a Toronto, Canadà, del 22 al 26 de juliol de 2012, It has been shown recently that the complexity of belief tracking in deterministic conformant and contingent planning is exponential in a width parameter that is often bounded and small. In this work, we introduce a new width notion that applies to non-deterministic conformant and contingent problems as well. We also develop a belief tracking algorithm for non-deterministic problems that is exponential in the problem width, analyze the width of non-deterministic benchmarks, compare the new notion to the previous one over deterministic problems, and present experimental results., H. Geffner is partially supported by grants TIN2009-10232, MICINN, Spain, and EC-7PM SpaceBook.
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Width and serialization of classical planning problems

  • Geffner, Héctor
  • Lipovetzky, Nir
We introduce a width parameter that bounds the complexity of classical planning problems and domains, along with a simple but effective blind-search procedure that runs in time that is exponential in the problem width. We show that many benchmark domains have a bounded and small width provided thatgoals are restricted to single atoms, and hence that such problems are provably solvable in low polynomial time. We then focus on the practical value of these ideas over the existing benchmarks which feature conjunctive goals. We show that the blind-search procedure can be used for both serializing the goal into subgoals and for solving the resulting problems, resulting in a ‘blind’ planner that competes well with a best-first search planner guided by state-of-the-art heuristics. In addition, ideas like helpful actions and landmarks can be integrated as well, producing a planner with state-of-the-art performance., H. Geffner is partially supported by grants TIN2009-10232,MICINN, Spain, and EC-7PM-SpaceBook.
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Searching for plans with carefully designed probes

  • Lipovetzky, Nir
  • Geffner, Héctor
Comunicació presentada a: 21st International Conference on Automated Planning and Scheduling (ICAPS) celebrada de l'11 al 16 de juny de 2011 a Freiburg, Alemanya., We define a probe to be a single action sequence computedgreedily from a given state that either terminates in the goalor fails. We show that by designing these probes carefullyusing a number of existing and new polynomial techniquessuch as helpful actions, landmarks, commitments, and con-sistent subgoals, a single probe from the initial state solvesby itself 683 out of 980 problems from previous IPCs, a num-ber that compares well with the 627 problems solved by FFin EHC mode, with similar times and plan lengths. We alsoshow that by launching one probe from each expanded statein a standard greedy best first search informed by the addi-tive heuristic, the number of problems solved jumps to 900(92%), as opposed to FF that solves 827 problems (84%),and LAMA that solves 879 (89%). The success of probessuggests that many domains can be solved easily once a suit-able serialization of the landmarks is found, an observationthat may open new connections between recent work in plan-ning and more classical work concerning goal serializationand problem decomposition in planning and search., This work is partially supported by grants TIN2009-10232, MICINN, Spain, and EC-7PM-SpaceBook.
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Heuristic search for generalized stochastic shortest path MDPs

  • Kolobov, Andrey
  • Mausam
  • Weld, Daniel S.
  • Geffner, Héctor
Comunicació presentada a: ICAPS 2011 celebrat de l'11 al 16 de juny de 2011 a Freiburg, Alemanya., Research in efficient methods for solving infinite-horizon MDPs has so far concentrated primarily on discounted MDPs and the more general stochastic shortest path problems (SSPs). These are MDPs with 1) an optimal value function V ∗ that is the unique solution of Bellman equation and 2) optimal policies that are the greedy policies w.r.t. V ∗ . This paper’s main contribution is the description of a new class of MDPs, that have well-defined optimal solutions that do not comply with either 1 or 2 above. We call our new class Generalized Stochastic Shortest Path (GSSP) problems. GSSP allows more general reward structure than SSP and subsumes several established MDP types including SSP, positive-bounded, negative, and discounted-reward models. While existing efficient heuristic search algorithms like LAO∗ and LRTDP are not guaranteed to converge to the optimal value function for GSSPs, we present a new heuristic-search-based family of algorithms, FRET (Find, Revise, Eliminate Traps). A preliminary empirical evaluation shows that FRET solves GSSPs much more efficiently than Value Iteration., This work was supported by WRF/TJ Cable Professorship and the following grants: ONR N000140910051, NSF IIS-1016465, TIN2009-10232 (MICINN, Spain).