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

Thiago Freitas dos Santos, Paulo E. Santos, Leonardo Anjoletto Ferreira, Reinaldo A.C. Bianchi, Pedro Cabalar

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish
Pages (from-to)4488-4510
Number of pages23
JournalApplied Intelligence
Issue number4
Early online date22 Jul 2021
Publication statusPublished - Mar 2022


  • Answer set programming
  • Heuristic
  • Markov decision process
  • Reinforcement learning
  • Spatial puzzles


Dive into the research topics of 'Heuristics, Answer Set Programming and Markov Decision Process for Solving a Set of Spatial Puzzles*'. Together they form a unique fingerprint.

Cite this