Heuristics, Answer Set Programming and Markov Decision Process for Solving a Set of Spatial Puzzles*
Nenhuma Miniatura disponível
Citações na Scopus
0
Tipo de produção
Artigo
Data
2022-03-05
Autores
DOS SANTOS, T. F.
SANTOS, P. E.
FERREIRA, L. A
Reinaldo Bianchi
CABALAR, P.
SANTOS, P. E.
FERREIRA, L. A
Reinaldo Bianchi
CABALAR, P.
Orientador
Periódico
Applied Intelligence
Título da Revista
ISSN da Revista
Título de Volume
Citação
DOS SANTOS, T. F.; SANTOS, P. E.; BIANCHI, L. A.; CABALAR, P. Heuristics, Answer Set Programming and Markov Decision Process for Solving a Set of Spatial Puzzles*. Applied Intelligence, March, 2022.
Texto completo (DOI)
Palavras-chave
Resumo
© 2021, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.Spatial puzzles composed of rigid objects, flexible strings and holes offer interesting challenges for reasoning about spatial entities that are common in the human daily-life’s activities. This motivates the use of spatial puzzles as domains of study in this work. The goal of this paper is to investigate the automated solution of this kind of problems by extending an algorithm that combines Answer Set Programming (ASP) with Markov Decision Process (MDP) and Reinforcement Learning (RL), called oASP(MDP). This method is capable of constructing the set of domain states online, i.e., while the agent interacts with a changing environment. The aim of the extension proposed in this work is to add heuristics as a mechanism to accelerate the learning process, resulting in the main contribution of this paper: the Heuristic oASP(MDP) (HoASP(MDP)) algorithm. Experiments were performed on deterministic, non-deterministic and non-stationary versions of the puzzles. Results show that the proposed approach can considerably accelerate the learning process, outperforming other state-of-the-art methods.