Pasar al contenido principal

Resultados relacionados

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

Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Heuristics for planning with penalties and rewards formulated in logic and computed through circuits

  • Bonet, Blai
  • Geffner, Héctor
The automatic derivation of heuristic functions for guiding the search for plans is a fundamental technique in planning. The type of heuristics that have been considered so far, however, deal only with simple planning models where costs are associated with actions but not with states. In this work we address this limitation by formulating a more expressive planning model and a corresponding heuristic where preferences in the form of penalties and rewards are associated with fluents as well. The heuristic, that is a generalization of the well-known delete-relaxation heuristic, is admissible, informative, but intractable. Exploiting a correspondence between heuristics and preferred models, and a property of formulas compiled in d-DNNF, we show however that if a suitable relaxation of the domain, expressed as the strong completion of a logic program with no time indices or horizon is compiled into d-DNNF, the heuristic can be computed for any search state in time that is linear in the size of the compiled representation. This representation defines an evaluation network or circuit that maps states into heuristic values in linear-time. While this circuit may have exponential size in the worst case, as for OBDDs, this is not necessarily so. We report empirical results, discuss the application of the framework in settings where there are no goals but just preferences, and illustrate the versatility of the account by developing a new heuristic that overcomes limitations of delete-based relaxations through the use of valid but implicit plan constraints. In particular, for the Traveling Salesman Problem, the new heuristic captures the exact cost while the delete-relaxation heuristic, which is also exponential in the worst case, captures only the Minimum Spanning Tree lower bound., H. Geffner is partially supported by grant TIN2006-15387-C03-03 from MEC/Spain and B. Bonet by a grant from DID/USB/Venezuela. Our planner was built upon a planner by Patrik Haslum. Preliminary experiments were run on the Hermes Computing Resource at the Aragon Institute of Engineering Research (I3A), University of Zaragoza.
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

Retractions onto series-parallel posets

  • Dalmau, Víctor
  • Krokhin, Andrei
  • Larose, Benoit
The poset retraction problem for a poset P is whether a given poset Q containing P as a subposet admits a retraction onto P, that is, whether there is a homomorphism from Q onto P which fixes every element of P. We study this problem for finite series-parallel posets . We present equivalent combinatorial, algebraic, and topological charaterisations of posets for which the problem is tractable, and, for such a poset P , we describe posets admitting a retraction onto P., Financial help of NSERC Canada is gratefully acknowledged. Víctor Dalmau is partially supported by the MEC under the program “Ramon y Cajal”, Grants TIN 2006-15387-C03-03, TIN 2004-04343, the EU PASCAL Network of Excellence IST-2002-506778, and the MODNET Marie Curie Research Training Network MRTN-CT-2004-512234. Andrei Krokhin is partially supported by the UK EPSRC Grants EP/C543831/1 and EP/C54384X/1. Benoit Larose is partially supported by NSERC, FQRNT, and CRM.
Repositorio Digital de la UPF
Publicación Artículo científico (JournalArticle)

CSP duality and trees of bounded pathwidth

  • Carvalho, Catarina
  • Dalmau, Víctor
  • Krokhin, Andrei
We study non-uniform constraint satisfaction problems definable in monadic Datalog stratified by the use of non-linearity. We show how such problems can be described in terms of homomorphism dualities involving trees of bounded pathwidth and in algebraic terms. For this, we introduce a new parameter for trees that closely approximates pathwidth and can be characterised via a hypergraph searching game., The first author is supported by FCT grant SFRH/BPD/26216/2006 and also by FCT and FEDER within the project ISFL-1-143 of the Centre for Algebra of the University of Lisbon. The second author is supported by grants TIN2006-15387-C03-03 and TIN2007-68005-C04 funded by the MCyT. The third author is supported by the UK EPSRC grants EP/G011001/1 and EP/C543831/1.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

CSP duality and trees of bounded pathwidth

  • Carvalho, Catarina
  • Dalmau, Víctor
  • Krokhin, Andrei
We study non-uniform constraint satisfaction problems definable in monadic Datalog stratified by the use of non-linearity. We show how such problems can be described in terms of homomorphism dualities involving trees of bounded pathwidth and in algebraic terms. For this, we introduce a new parameter for trees that closely approximates pathwidth and can be characterised via a hypergraph searching game., The first author is supported by FCT grant SFRH/BPD/26216/2006 and also by FCT and FEDER within the project ISFL-1-143 of the Centre for Algebra of the University of Lisbon. The second author is supported by grants TIN2006-15387-C03-03 and TIN2007-68005-C04 funded by the MCyT. The third author is supported by the UK EPSRC grants EP/G011001/1 and EP/C543831/1.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Retractions onto series-parallel posets

  • Dalmau, Víctor
  • Krokhin, Andrei
  • Larose, Benoit
The poset retraction problem for a poset P is whether a given poset Q containing P as a subposet admits a retraction onto P, that is, whether there is a homomorphism from Q onto P which fixes every element of P. We study this problem for finite series-parallel posets . We present equivalent combinatorial, algebraic, and topological charaterisations of posets for which the problem is tractable, and, for such a poset P , we describe posets admitting a retraction onto P., Financial help of NSERC Canada is gratefully acknowledged. Víctor Dalmau is partially supported by the MEC under the program “Ramon y Cajal”, Grants TIN 2006-15387-C03-03, TIN 2004-04343, the EU PASCAL Network of Excellence IST-2002-506778, and the MODNET Marie Curie Research Training Network MRTN-CT-2004-512234. Andrei Krokhin is partially supported by the UK EPSRC Grants EP/C543831/1 and EP/C54384X/1. Benoit Larose is partially supported by NSERC, FQRNT, and CRM.
Recercat. Dipósit de la Recerca de Catalunya
Publicación Artículo científico (JournalArticle)

Heuristics for planning with penalties and rewards formulated in logic and computed through circuits

  • Bonet, Blai
  • Geffner, Héctor
The automatic derivation of heuristic functions for guiding the search for plans is a fundamental technique in planning. The type of heuristics that have been considered so far, however, deal only with simple planning models where costs are associated with actions but not with states. In this work we address this limitation by formulating a more expressive planning model and a corresponding heuristic where preferences in the form of penalties and rewards are associated with fluents as well. The heuristic, that is a generalization of the well-known delete-relaxation heuristic, is admissible, informative, but intractable. Exploiting a correspondence between heuristics and preferred models, and a property of formulas compiled in d-DNNF, we show however that if a suitable relaxation of the domain, expressed as the strong completion of a logic program with no time indices or horizon is compiled into d-DNNF, the heuristic can be computed for any search state in time that is linear in the size of the compiled representation. This representation defines an evaluation network or circuit that maps states into heuristic values in linear-time. While this circuit may have exponential size in the worst case, as for OBDDs, this is not necessarily so. We report empirical results, discuss the application of the framework in settings where there are no goals but just preferences, and illustrate the versatility of the account by developing a new heuristic that overcomes limitations of delete-based relaxations through the use of valid but implicit plan constraints. In particular, for the Traveling Salesman Problem, the new heuristic captures the exact cost while the delete-relaxation heuristic, which is also exponential in the worst case, captures only the Minimum Spanning Tree lower bound., H. Geffner is partially supported by grant TIN2006-15387-C03-03 from MEC/Spain and B. Bonet by a grant from DID/USB/Venezuela. Our planner was built upon a planner by Patrik Haslum. Preliminary experiments were run on the Hermes Computing Resource at the Aragon Institute of Engineering Research (I3A), University of Zaragoza.