Effective planning with expressive languages

dc.contributor
Universitat Pompeu Fabra. Departament de Tecnologies de la Informació i les Comunicacions
dc.contributor.author
Francès, Guillem
dc.date.accessioned
2017-11-14T16:13:55Z
dc.date.available
2017-11-14T16:13:55Z
dc.date.issued
2017-10-26
dc.identifier.uri
http://hdl.handle.net/10803/456319
dc.description.abstract
Classical planning is concerned with finding sequences of actions that achieve a certain goal from an initial state of the world, assuming that actions are deterministic, states are fully known, and both are described in some modeling language. This work develops effective means of dealing with expressive modeling languages for classical planning. First, we show that expressive languages not only allow simpler problem representations, but also capture additional problem structure that can be leveraged by heuristic solution methods. We develop heuristics that support functions and existential quantification in the problem definition, and show empirically that they can be more informed and cost-effective. Second, we develop a novel width-based algorithm that matches state-of-the-art performance without looking at the declarative representation of actions. This is a significant departure from previous research, and advances the use of expressive modeling languages in planning and the scope and effectiveness of classical planners.
en_US
dc.description.abstract
La planificació clàssica consisteix en trobar una seqüència d’accions que meni d’un cert estat inicial fins a un estat desitjat, on les accions són deterministes, els estats perfectament coneguts, i ambdós elements són descrits en algun llenguatge formal. En aquest treball desenvolupem mitjans efectius de tractar amb llenguatges expressius de planificació clàssica. Primer, mostrem que un llenguatge més expressiu no només permet obtenir representacions compactes, sinó que permet capturar també estructura del problema aprofitable mitjançant mètodes heuristics, desenvolupem heurístiques que suporten funcions i quantificació existencial en la definició del problema, i demostrem empíricament que poden ser més informades i efectives. En segon lloc, desenvolupem un nou algorisme que ofereix rendiment similar a l’estat de l’art sense necessitat de cap representació declarativa de les accions. Això suposa una innovació significativa respecte a la recerca anterior, i un avenç en l’ús de llenguatges expressius i en l’abast i efectivitat dels planificadors clàssics.
en_US
dc.format.extent
145 p.
en_US
dc.format.mimetype
application/pdf
dc.language.iso
eng
en_US
dc.publisher
Universitat Pompeu Fabra
dc.rights.license
L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/4.0/
dc.rights.uri
http://creativecommons.org/licenses/by-nc-nd/4.0/
*
dc.source
TDX (Tesis Doctorals en Xarxa)
dc.subject
Classical planning
en_US
dc.subject
Heuristic planning
en_US
dc.subject
First-order modeling languages
en_US
dc.subject
Modeling and computation
en_US
dc.subject
Expressiveness and tractability
en_US
dc.subject
Functional STRIPS
en_US
dc.subject
Constraint satisfaction
en_US
dc.subject
Planificació clàssica
en_US
dc.subject
Planificació heurística
en_US
dc.subject
Llenguatges de modelatge de primer ordre
en_US
dc.subject
Modelatge i computació
en_US
dc.subject
Expressivitat i tractabilitat
en_US
dc.subject
Satisfacció de restriccions
en_US
dc.title
Effective planning with expressive languages
en_US
dc.type
info:eu-repo/semantics/doctoralThesis
dc.type
info:eu-repo/semantics/publishedVersion
dc.subject.udc
62
en_US
dc.contributor.authoremail
guillem.frances@upf.edu
en_US
dc.contributor.director
Geffner, Héctor
dc.embargo.terms
cap
en_US
dc.rights.accessLevel
info:eu-repo/semantics/openAccess
dc.description.degree
Programa de doctorat en Tecnologies de la Informació i les Comunicacions


Documents

tgf.pdf

1.118Mb PDF

Aquest element apareix en la col·lecció o col·leccions següent(s)