| Título: | Optimisation of SAT-based planning via hybrid and prioritised asynchronous binary search strategies: an extension of madagascar planner |
| Autor(es): | Ribeiro, Bruno Campos
Penha, Igor e Silva |
| Orientador(es): | Ribas, Bruno César |
| Assunto: | Planejamento como satisfatibilidade (Inteligência Artificial)
Inteligência artificial
Planejamento automatizado
Algoritmos de busca |
| Data de apresentação: | 18-Dez-2025 |
| Data de publicação: | 4-Ago-2026 |
| Referência: | RIBEIRO, Bruno Campos; PENHA, Igor e Silva. Optimisation of SAT-based planning via hybrid and prioritised asynchronous binary search strategies: an extension of madagascar planner. 2025. 72 f., il. Trabalho de Conclusão de Curso (Bacharelado em Engenharia de Software) — Universidade de Brasília, Brasília, 2025. |
| Abstract: | This undergraduate dissertation investigates the Planning as Satisfiability (SAT) paradigm,
a prominent approach in automated planning in which classical planning problems are
translated into propositional logic formulae and solved by SAT solvers. A comprehensive
review of the theoretical foundations of automated planning and propositional satisfiabil ity is presented, followed by an in-depth analysis of major SAT-based planners, including
the SATPLAN family, Blackbox and Madagascar. Emphasis is placed on the evolution
of encoding strategies, the use of planning graphs, and the impact of mutex propagation
on solver performance. Based on this theoretical framework, the present work introduces
the design, implementation, and evaluation of a set of search algorithms integrated into
the Madagascar planning system. These algorithms encompass sequential, heuristic, ex ponential, backward, and asynchronous parallel strategies for determining the optimal
planning horizon under the SAT-based formulation. The primary objective is to reduce
both the number of calls to the SAT solver and the time required to obtain the smallest
feasible planning horizon. An extensive experimental evaluation demonstrates that the
implemented strategies improve the efficiency of SAT-based planning. |
| Informações adicionais: | Trabalho de Conclusão de Curso (graduação) — Universidade de Brasília, Faculdade de Ciências e Tecnologia em Engenharia, Engenharia de Software, 2025. |
| Licença: | A concessão da licença deste item refere-se ao termo de autorização impresso assinado pelo autor que autoriza a Biblioteca Digital da Produção Intelectual Discente da Universidade de Brasília (BDM) a disponibilizar o trabalho de conclusão de curso por meio do sítio bdm.unb.br, com as seguintes condições: disponível sob Licença Creative Commons 4.0 International, que permite copiar, distribuir e transmitir o trabalho, desde que seja citado o autor e licenciante. Não permite o uso para fins comerciais nem a adaptação desta. |
| Aparece na Coleção: | Engenharia de Software
|
Todos os itens na BDM estão protegidos por copyright. Todos os direitos reservados.
