Understanding sample generation strategies for learning heuristic functions in classical planning

Abstract

Heuristic functions are essential in guiding search algorithms to solve planning tasks. We study the problem of learning good heuristic functions for classical planning tasks with neural networks based on samples that are states with their cost-to-goal estimates. It is well known that the learned model quality depends on the quality of training data. Our main goal is to better understand the influence of sample generation strategies on the performance of a greedy best-first search guided by a learned heuristic function. In a set of controlled experiments, we find that two main factors determine the quality of the learned heuristic: the distribution of samples in the state space and the quality of the cost-to-goal estimates. These two factors are interdependent: having perfect cost-to-goal estimates is insufficient if the samples are not well distributed across the state space. We study the effects of restricting samples to only include states that could be visited when solving a given task and the effects of adding samples with high-value estimates. Based on our findings, we propose practical strategies to improve the quality of learned heuristics: three strategies that aim to generate more representative states and two strategies that improve the cost-to-goal estimates. Our resulting neural network heuristic has higher coverage than a basic satisficing heuristic. Compared to a baseline learned heuristic, our best neural network heuristic almost doubles the mean coverage and can increase it for some domains by more than six times.

Funções heurísticas são essenciais para guiar algoritmos de busca na resolução de tarefas de planejamento. Nós estudamos o problema de aprender boas funções heurísticas para tarefas de planejamento clássico usando redes neurais baseadas em amostras que são estados acompanhados de suas estimativas de custo-para-objetivo. É conhecido que a qualidade do modelo aprendido depende da qualidade dos dados de treinamento. Nosso objetivo principal é entender melhor a influência das estratégias de geração de amostras no desempenho do greedy best-first search guiado por uma função heurística aprendida. Em um conjunto de experimentos controlados, descobrimos que dois fatores principais determinam a qualidade da heurística aprendida: a distribuição de amostras no espaço de estados e a qualidade das estimativas de custo-para-objetivo. Esses dois fatores são inter dependentes: ter estimativas ótimas de custo-para-objetivo é insuficiente se as amostras não estiverem bem distribuídas ao longo do espaço de estados. Nós estudamos os efeitos de restringir as amostras para incluir apenas estados que poderiam ser visitados ao resolver uma determinada tarefa e os efeitos de adicionar amostras com altos valores de estima tivas. Com base em nossas descobertas, propomos estratégias práticas para melhorar a qualidade das heurísticas aprendidas: três estratégias que visam gerar estados mais repre sentativos e duas estratégias que melhoram as estimativas de custo-para-objetivo. Nossa heurística resultante da rede neural possui uma cobertura maior do que uma heurística de satisficing básica. Em comparação com uma heurística baseline aprendida, nossa melhor heurística de rede neural quase dobra a cobertura média e aumenta para alguns domínios em mais de seis vezes.