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)

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)

Probabilistic activity recognition in navigation

  • Font Sola, Octavi
  • Francès, Guillem
  • Jonsson, Anders, 1973-
  • Bartie, Phil
  • Mackaness, William
Comunicació presentada al 11th Workshop on Positioning, Navigation and Communication (WPNC), celebrat els dies 12 i 13 de març de 2014 a Dresden, Alemanya., In this paper we present a novel probabilistic approach to activity recognition. Our approach is to estimate posterior probabilities of different activities using Bayes' rule. The approach can handle any type of activities as long as it is possible to estimate the conditional probabilities of potential observations, and easily scales to large numbers of activities. We test our approach empirically in an environment where observations are GPS signals of users moving around in a city., The authors are grateful for the funding provided by European FP7 grant #270019 (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.
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)

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)

Probabilistic activity recognition in navigation

  • Font Sola, Octavi
  • Francès, Guillem
  • Jonsson, Anders, 1973-
  • Bartie, Phil
  • Mackaness, William
Comunicació presentada al 11th Workshop on Positioning, Navigation and Communication (WPNC), celebrat els dies 12 i 13 de març de 2014 a Dresden, Alemanya., In this paper we present a novel probabilistic approach to activity recognition. Our approach is to estimate posterior probabilities of different activities using Bayes' rule. The approach can handle any type of activities as long as it is possible to estimate the conditional probabilities of potential observations, and easily scales to large numbers of activities. We test our approach empirically in an environment where observations are GPS signals of users moving around in a city., The authors are grateful for the funding provided by European FP7 grant #270019 (SpaceBook).