Welcome to the UPF Digital Repository

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

Show simple item record

dc.contributor.author Bonet, Blai
dc.contributor.author Geffner, Héctor
dc.date.accessioned 2019-01-25T08:13:38Z
dc.date.available 2019-01-25T08:13:38Z
dc.date.issued 2008
dc.identifier.citation Bonet B, Geffner H. Heuristics for planning with penalties and rewards formulated in logic and computed through circuits. Artif Intell. 2008 Aug;172(12-13):1579-604. DOI: 10.1016/j.artint.2008.03.004
dc.identifier.issn 0004-3702
dc.identifier.uri http://hdl.handle.net/10230/36436
dc.description.abstract 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.
dc.description.sponsorship 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.
dc.format.mimetype application/pdf
dc.language.iso eng
dc.publisher Elsevier
dc.relation.ispartof Artificial Intelligence. 2008 Aug;172(12-13):1579-604.
dc.rights © Elsevier http://dx.doi.org/10.1016/j.artint.2008.03.004
dc.title Heuristics for planning with penalties and rewards formulated in logic and computed through circuits
dc.type info:eu-repo/semantics/article
dc.identifier.doi http://dx.doi.org/10.1016/j.artint.2008.03.004
dc.subject.keyword Planning
dc.subject.keyword Planning heuristics
dc.subject.keyword Planning with rewards
dc.subject.keyword Knowledge compilation
dc.relation.projectID info:eu-repo/grantAgreement/ES/2PN/TIN2006-15387-C03-03
dc.rights.accessRights info:eu-repo/semantics/openAccess
dc.type.version info:eu-repo/semantics/acceptedVersion

This item appears in the following Collection(s)

Show simple item record

Search DSpace

Advanced Search


My Account


Compliant to Partaking