Effective planning with expressive languages

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.

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.