Busca heurística simbólica para planejamento em inteligência artificial

Abstract

Automated planning is a subfield of Artificial Intelligence (AI) that focuses on the development of algorithms capable of generating action plans that allow intelligent agents to achieve their goals. The search for a solution plan can be performed forward, generating successor states from an initial state, or backward, generating predecessor states from goal-satisfying states. This is a P-SPACE problem, and to deal with such complexity, two main approaches have been widely explored in the literature: heuristic search, which uses estimates to guide node expansion, and symbolic search, which employs compact representations of state sets through Binary Decision Diagrams (BDDs). Previous works proposed symbolic heuristic search as a way to combine the strengths of both approaches Silva (2019). However, computing heuristics in large state spaces remains a challenging task. To address this, Kissmann (2012) introduced a time limit during heuristic generation to improve the performance of symbolic search. This work proposes incorporating such a time limit into the symbolic heuristic computation of (Silva, 2019) and evaluating the impact of this modification on the performance of symbolic A* search. The proposed algorithm is evaluated on benchmarks from the International Planning Competition (IPC).