Heuristics, Answer Set Programming and Markov Decision Process for Solving a Set of Spatial Puzzles*

Página do item simplificado
dc.contributor.authorDOS SANTOS, T. F.
dc.contributor.authorSANTOS, P. E.
dc.contributor.authorFERREIRA, L. A
dc.contributor.authorReinaldo Bianchi
dc.contributor.authorCABALAR, P.
dc.contributor.authorOrcidhttps://orcid.org/0000-0001-9097-827X
dc.date.accessioned2022-01-12T21:54:19Z
dc.date.available2022-01-12T21:54:19Z
dc.date.issued2022-03-05
dc.description.abstract© 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.
dc.identifier.citationDOS 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.
dc.identifier.doi10.1007/s10489-021-02423-1
dc.identifier.issn1573-7497
dc.identifier.urihttps://repositorio.fei.edu.br/handle/FEI/3593
dc.relation.ispartofApplied Intelligence
dc.rightsAcesso Restrito
dc.subject.otherlanguageAnswer set programming
dc.subject.otherlanguageHeuristic
dc.subject.otherlanguageMarkov decision process
dc.subject.otherlanguageReinforcement learning
dc.subject.otherlanguageSpatial puzzles
dc.titleHeuristics, Answer Set Programming and Markov Decision Process for Solving a Set of Spatial Puzzles*
dc.typeArtigo
fei.scopus.citations0
fei.scopus.eid2-s2.0-85111102328
fei.scopus.subjectAnswer set programming
fei.scopus.subjectAutomated solutions
fei.scopus.subjectChanging environment
fei.scopus.subjectLearning process
fei.scopus.subjectMarkov Decision Processes
fei.scopus.subjectRigid objects
fei.scopus.subjectSpatial entities
fei.scopus.subjectState-of-the-art methods
fei.scopus.updated2024-07-01
fei.scopus.urlhttps://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=85111102328&origin=inward
Arquivos
Coleções
Artigos