Effective planning with expressive languages

Autor/a

Francès, Guillem

Director/a

Geffner, Héctor

Fecha de defensa

2017-10-26

Páginas

145 p.



Departamento/Instituto

Universitat Pompeu Fabra. Departament de Tecnologies de la Informació i les Comunicacions

Programa de doctorado

Programa de doctorat en Tecnologies de la Informació i les Comunicacions

Resumen

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.


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.

Palabras clave

Classical planning; Heuristic planning; First-order modeling languages; Modeling and computation; Expressiveness and tractability; Functional STRIPS; Constraint satisfaction; Planificació clàssica; Planificació heurística; Llenguatges de modelatge de primer ordre; Modelatge i computació; Expressivitat i tractabilitat; Satisfacció de restriccions

Materias

62 - Ingeniería. Tecnología

Documentos

tgf.pdf

1.118Mb

 

Derechos

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/
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/

Este ítem aparece en la(s) siguiente(s) colección(ones)