New perspectives on landmark generation for HTN planning

Abstract

Landmarks underpin a very important class of heuristics in classical and Hierarchical Task Network (HTN) planning. They appear in nearly every state-of-the-art planning system and have become a standard component of modern planners. A landmark is a necessary feature of a planning problem that must be true (or selected) at some point in every valid solution. In heuristic search, landmarks help measure progress by tracking unfulfilled landmarks at each search node. While the problem of detecting landmarks has been extensively studied in classical planning, relatively few approaches have addressed it in the HTN setting. Existing landmark generation techniques for HTN planning rely on the Delete and Ordering Free (DOF) relaxation. However, they are incomplete due to an additional relaxation known as Task Insertion, which limits the number of detectable landmarks. This work introduces new perspectives on landmark generation for HTN planning through three contributions: (1) We revisit landmark generation with AND/OR graph and introduce two new approaches that identify additional landmarks for the problem, detecting landmarks missed due to the limitations of the original graph encoding. These new methods discover substantially more landmarks while retaining polynomial-time complexity. However, they are all incomplete under DOF. (2) We transform the only fully DOF-aware model in the literature into a decision procedure to find landmarks. This method lets us quantify the gap in landmark detection between DOF-complete and DOFincomplete approaches. (3) We extend the LM-cut algorithm to generate disjunctive landmarks for HTN planning by introducing a new model that incorporates precomputed landmarks as additional goals in the landmark extraction process. This makes LM-cut identify many more disjunctive landmarks with a notably positive impact on search performance. Experiments on International Planning Competition (IPC) benchmarks demonstrate the effectiveness of our new approaches, which significantly improve on the number of landmark detected and the overall search performance compared to the existent state-of-the-art landmark generation strategies.

Landmarks fazer parte de uma classe muito importante de heurísticas no planejamento clássico e no planejamento hierárquico baseado em redes de tarefas (Hierarchical Task Network — HTN). Eles estão presentes em praticamente todos os sistemas de planejamento de ponta e se tornaram um componente padrão dos planejadores modernos. Um landmark é uma característica necessária de um problema de planejamento que deve ser verdadeira (ou selecionada) em algum momento de toda solução válida. Na busca heurística, landmarks ajudam a medir o progresso acompanhando quais landmarks ainda não foram alcançados em cada nó da busca. Embora o problema de detecção de landmarks tenha sido amplamente estudado no planejamento clássico, relativamente poucas abordagens o investigaram no contexto HTN. As técnicas existentes de geração de landmarks para planejamento HTN baseiam-se na relaxação Delete and Ordering Free (DOF). No entanto, essas abordagens são incompletas devido a uma relaxação adicional conhecida como Task Insertion, que limita a quantidade de landmarks detectáveis. Este trabalho introduz novas perspectivas sobre a geração de landmarks em planejamento HTN por meio de três contribuições: (1) Revisitamos o modelo existente baseado em grafos AND/OR para geração de landmarks e propomos duas novas abordagens que identificam landmarks adicionais, cobrindo landmarks não identifados pelas limitações da codificação original. Esses novos métodos descobrem substancialmente mais landmarks, mantendo complexidade polinomial. No entanto, todos permanecem incompletos sob a relaxação DOF. (2) Transformamos o único modelo totalmente compatível com DOF existente na literatura em um procedimento de decisão para identificar landmarks. Essa abordagem nos permite quantificar a diferença na detecção de landmarks entre métodos completos e incompletos em relação à relaxação DOF. (3) Nós estendemos o algorítmo LM-cut para gerar landmarks disjunctivos para planejamento HTN introduzindo um novo modelo que incorpora landmarks pré-computados como novos objetivos na extração de novos landmarks. Isto faz que o LM-cut identifique muito mais landmarks disjunctivos com um impacto positivo notável na performance de busca. Experimentos com benchmarks da International Planning Competition (IPC) demonstram a eficácia das novas abordagens, que melhoram significativamente tanto a quantidade delandmarks detectados quanto o desempenho da busca, em comparação com as estratégias de geração de landmarks do estado da arte.