Busca heurística simbólica para planejamento determinístico

Abstract

Automated Planning is a subarea of Artificial Intelligence that aims to study the deliberative process of choosing actions so that an intelligent agent can achieve its goals. The solution to a deterministic planning problem is called plan, i.e., a sequence of actions that takes the agent from the initial state to a state that satisfies the goal. The search for a plan can be done in two ways: (i) progressive from the initial state, trying to reach some state that satisfies the goal and; (ii) regressive, from the set of states that satisfy the goal, trying to reach the initial state. However, producing a plane is computationally difficult and the problem of state space explosion often occurs. In the automated planning literature, there are two approaches to circumvent this problem: (i) heuristic search and; (ii) the symbolic search, based on the representation of states and actions as Binary Decision Diagrams. This paper proposes the implementation and evaluation of a symbolic regressive search-based heuristic for the A ∗ symbolic search algorithm in an attempt to produce plans for planning problems in deterministic domains.