Source-linked AI summary
Heuristics, Answer Set Programming and Markov Decision Process for Solving a Set of Spatial Puzzles
Thiago Freitas dos Santos, Paulo E. Santos, Leonardo A. Ferreira, Reinaldo A. C. Bianchi, Pedro Cabalar
TL;DR
The paper studies how to learn solutions to spatial puzzles with rigid objects, strings, and holes, where actions and their effects are non-trivial. It adds heuristics from relaxed puzzle solutions to an ASP–MDP and Q-Learning approach, and reports that heuristic-accelerated algorithms outperform their non-heuristic counterparts.
Problem
Learning action sequences in spatial domains is challenging because rigid objects, flexible strings, and holes have non-trivial actions and effects, while earlier formal approaches lacked learning and could not handle more complex, non-stationary versions.
Source: §1 · p. 2Method
The approach combines ASP to represent the puzzle as an MDP with Q-Learning to learn policies, using heuristics derived from relaxed puzzle solutions to guide learning.
Source: §2.2 · p. 6, §2.3 · p. 7, §3.1 · p. 12Results
Heuristic-accelerated algorithms always outperform their non-heuristic counterparts, and oASP(MDP) variants explore more valid states with fewer impossible actions than Q-Learning counterparts.
Source: §7 · p. 32Takeaways & Limitations
Relaxed-puzzle solutions provide guidance that accelerates learning across deterministic, non-deterministic, and non-stationary puzzle versions.
Source: §7 · p. 32The MDP representation assumes an ASP program for each state describes the effects of actions and their possible successor states.
Source: §2.2 · p. 6
Abstract
from arXiv · showhide
Spatial puzzles composed of rigid objects, flexible strings and holes offer interesting domains for reasoning about spatial entities that are common in the human daily-life's activities. The goal of this work is to investigate the automated solution of this kind of puzzles adapting an algorithm that combines Answer Set Programming (ASP) with Markov Decision Process (MDP), algorithm oASP(MDP), to use heuristics accelerating the learning process. ASP is applied to represent the domain as an MDP, while a Reinforcement Learning algorithm (Q-Learning) is used to find the optimal policies. In this work, the heuristics were obtained from the solution of relaxed versions of the puzzles. Experiments were performed on deterministic, non-deterministic and non-stationary versions of the puzzles. Results show that the proposed approach can accelerate the learning process, presenting an advantage when compared to the non-heuristic versions of oASP(MDP) and Q-Learning.
1 Introduction
The paper applies oASP(MDP) to spatial puzzles and introduces heuristics derived from simplified puzzles to accelerate learning. It addresses puzzle variants that prior approaches could not handle and reports better performance than non-heuristic oASP(MDP) and Q-Learning.
1 Introduction
- Learning action sequences in spatial domains is challenging because rigid objects, flexible strings, and holes have non-trivial actions and effects.The paper notes these entities also occur in settings such as robot surgery and machine maintenance.Source: §1 · p. 2
- Earlier formal approaches lacked a learning component and could not cope with more complex, non-stationary puzzle versions.Source: §1 · p. 2
- Heuristics derived from simplified puzzles accelerate oASP(MDP) learning across deterministic, non-deterministic, and string-winding puzzle variants.The approach is applied to the Fisherman’s Folly and Rope Ladder puzzles.Source: §1 · p. 2
- The proposed approach outperforms non-heuristic oASP(MDP) and Q-Learning algorithms.Source: §1 · p. 2
2 Background
The background describes the two spatial-puzzle domains and introduces the ASP, reinforcement-learning, and oASP(MDP) components used to model and solve them.
2.1 Domain
- The Fisherman’s Folly and Rope Ladder puzzles involve strings, rigid objects, and holes, with the goal of freeing a Ring through object-manipulation actions.In Fisherman’s Folly, object size and attachment constrain which holes objects can pass through; the Rope Ladder has two Holed Posts and four string crossings. Passing actions omit intermediate states in which an object is only partly through a hole.Source: §2.1 · p. 3
2.2 Answer Set Programming (ASP)
- ASP constraints exclude physically impossible states, actions, and state-action pairs, while choice rules describe possible successor states for each state and action.The MDP representation uses an ASP program for each state to describe action effects and possible next states.Source: §2.2 · pp. 5–6
2.3 Reinforcement Learning (RL)
- Q-Learning learns an action-value function through interaction, while HAQL adds heuristics to guide action selection when the agent has prior task knowledge.The heuristic modifies action selection within the ϵ-greedy strategy.Source: §2.3 · pp. 7–8
2.4 Online Answer Set Programming for Markov Decision Process
- oASP(MDP) combines ASP’s MDP representation and state-space exploration with Q-Learning’s action-value estimates, adding observed transitions as the agent interacts.Unlike Q-Learning, oASP(MDP) can retain and apply learned knowledge when the environment changes; the paper introduces heuristics for this algorithm in the next section.Source: §2.4 · pp. 8–10
3 Heuristic oASP(MDP) (HoASP(MDP))
HoASP(MDP) adds heuristic guidance to oASP(MDP)'s action choice, using policies learned from simplified puzzles to guide learning on the original puzzles. ASP records observed transitions and impossible actions, while Q-Learning updates action values over episodes.
3 Heuristic oASP(MDP) (HoASP(MDP))
- ASP stores observed state transitions and forbidden actions, updates each state's rules as transitions are detected, and uses them to update Q(s, a).At each episode's end, the received reward updates action values; after several episodes the Q-Table contains the optimal policy.Source: §3 · pp. 11–12
- Heuristics guide action choice by mapping a state in the heuristic task to the original task and selecting an action using equation (6).This changes the action-choice step of oASP(MDP).Source: §3 · pp. 10–11
3.1 Heuristic oASP(MDP) to Solve Spatial Puzzles
- Fisherman’s Folly heuristics come from a simplified puzzle solved with oASP(MDP), restricting the String to at most two windings through the Post Hole.The simplification retains the original puzzle's object configuration and relations.Source: §3.1 · p. 12
- For Rope Ladder, the simplified puzzle starts with one String crossing at each Post Hole, and a mapping matches actions leading to corresponding states in the original puzzle.The action sets are the same in the simplified and original puzzles.Source: §3.1 · p. 12
- The agent initially lacks knowledge of which crossings are physically impossible and learns these constraints from rewards, later excluding impossible actions from consideration.Fisherman’s Folly has 20 possible actions and Rope Ladder has 28.Source: §3.1 · p. 13
- Puzzle states are represented by crossing lists for each long object, with list entries naming an object and the hole face toward which it is crossed.Actions manipulate a Crossing Element through a Host Element toward a Hole Face; the same formalization applies across the puzzles considered.Source: §3.1 · p. 13
4 Experiments
The experiments compare four reinforcement-learning algorithms across configurations of Fisherman’s Folly and Rope Ladder, including simplified, non-deterministic, and non-stationary variants. They assess puzzle-solving steps, accumulated returns, visited states, and Q-Table size.
4 Experiments
- Four algorithms—Q-Learning, oASP(MDP), Heuristically Accelerated Q-Learning, and HoASP(MDP)—were compared across puzzle variants.Experiments used 30 trials per setting, with 6,000 episodes per trial and a 500-action episode limit.Source: §4 · pp. 13–14
- The evaluation covered simplified and original Fisherman’s Folly, a non-deterministic version, a non-stationary Disk version, and Rope Ladder configurations.In non-deterministic Fisherman’s Folly, actions succeed as expected with 80% probability, go toward the opposite hole face with 10% probability, or leave the state unchanged with 10% probability.Source: §4 · pp. 14–15
- Heuristic algorithms used Q-Tables from simplified puzzles, while the non-stationary Disk Fisherman’s Folly comparison used oASP(MDP) and Q-Learning without heuristics.The environment changed after episode 2,000, when disks that could initially cross the Ring could no longer do so.Source: §4 · pp. 14–15
- The metrics were steps to solve, accumulated return, states visited, and state/action pairs in the learned Q-Table.Shared settings included discount factor 0.9, learning rate 0.2, and heuristic control value 0.25.Source: §4 · pp. 14–15
5 Results and Discussion
The results compare standard and heuristically accelerated Q-Learning and oASP(MDP) across simplified, original, non-deterministic, non-stationary, and Rope Ladder puzzles. Heuristics generally accelerate learning in the tested configurations, while the non-stationary case exposes a drawback of retaining a previously learned policy.
5.5 Rope Ladder
- Across configurations, exploration can keep average steps above the optimal solution after learning stabilizes when a trial uses all 500 episode actions without reaching the goal.Heuristics were not used in non-stationary cases because the changed domains were too distinct from their initial configurations.Source: §5.5 · p. 19
5.1 Simplified Fisherman’s Folly (SFF)
- In SFF, oASP(MDP) visits more states by removing impossible actions, while Q-Learning retains more state/action pairs; oASP(MDP)’s accumulated return is slightly better early despite similar step curves.Q-Learning keeps impossible actions in its Q-Table and assigns them negative rewards rather than removing them.Source: §5.1 · pp. 15–16, Figure 2 · p. 20, Figure 3 · p. 21
5.2 Original Fisherman’s Folly (OFF)
- In OFF, SFF-derived heuristics accelerate learning from the outset; oASP(MDP) visits around 25,000 states versus around 6,000 in SFF, while Q-Learning has the most state/action pairs.The SFF solution is part of the OFF solution, and the heuristic algorithms explore a smaller portion of the state space.Source: §5.2 · pp. 16–17, Figure 4 · p. 22
5.3 Non-Deterministic Fisherman’s Folly (NDFF)
- In NDFF, heuristic algorithms perform better early, while oASP(MDP) explores around 80,000 states and its early return advantage over Q-Learning declines with more interactions.The early step-curve difference is statistically relevant; heuristic action choice is applied when an action is selected, despite non-deterministic effects.Source: §5.3 · p. 17, Figure 6 · p. 24, Figure 7 · p. 25
5.4 Non-Stationary Disk Fisherman’s Folly (NSFF)
- In NSFF, Q-Learning performs better after the environment changes at interaction 2,000, as oASP(MDP)’s retained Q-Table leads it toward a sub-optimal policy.The step difference is not visible in accumulated returns because each step rewards -1 while reaching the goal rewards +1,000.Source: §5.4 · pp. 17–18, Figure 8 · p. 26
5.5 Rope Ladder
- In Rope Ladder, heuristic algorithms learn the optimal policy faster than non-heuristic versions; HoASP(MDP) briefly outperforms Heuristically Accelerated Q-Learning around 300 interactions.The reported learning-curve difference is statistically relevant.Source: §5.5 · p. 18, Figure 10 · p. 28
- In Rope Ladder, non-heuristic algorithms have higher returns early, but heuristic algorithms later explore more states and receive higher returns; Q-Learning has the most state/action pairs.The early return pattern is linked to non-heuristic algorithms revisiting familiar states more often and executing fewer impossible actions.Source: §5.5 · pp. 18–19, Figure 10 · p. 28, Figure 11 · p. 29
6 Literature Review
The review covers approaches combining logic, planning, and reinforcement learning, alongside work using heuristics to guide learning. It distinguishes oASP(MDP) from related systems by how ASP represents or generates states and actions, and by its handling of changing environments.
Logic and MDP combinations
- oASP(MDP) generates answer sets before action selection and Q-value approximation, unlike QASP, which the paper says cannot handle non-stationary problems (Nickles 2012).The review also contrasts oASP(MDP)'s domain representation with the ASP–POMDP framework of Zhang et al. (2015), which uses a prior planning phase to estimate the POMDP.Source: §6 · p. 30
Related learning frameworks
- DARLING combines ASP-based modeling, planning, and reasoning with RL for adaptation; its office-service-robot tests showed faster task learning and improving performance (Leonetti et al. 2016).Other reviewed approaches combine symbolic plans with hierarchical RL in PEORL (Yang et al. 2018), or connect deep learning and symbolic representations (Garnelo et al. 2016; Zamani et al. 2017).Source: §6 · pp. 30–31
Heuristics in reinforcement learning
- Prior heuristic-accelerated RL work reports early guidance and later diminishing heuristic importance, with HARL outperforming traditional RL in reported experiments (Bianchi et al. 2008; Martins and Bianchi 2014; Morozs et al. 2015).The review links the present paper's heuristics from simpler domains to transfer learning, while noting that exploring this link is future work (Bianchi et al. 2018).Source: §6 · p. 31
7 Conclusion
The paper evaluates heuristic-guided oASP(MDP) on two spatial puzzles across deterministic, non-deterministic, and non-stationary variants. Its relaxed-domain heuristics guide and accelerate learning, while future work proposes extracting reusable domain rules with ASP.
7 Conclusion
- Experiments compare Q-Learning, HAQL, oASP(MDP), and HoASP(MDP) on Fisherman’s Folly and Rope Ladder across deterministic, non-deterministic, and non-stationary domains.Rope Ladder has more objects and more challenging relations than Fisherman’s Folly.Source: §7 · p. 32
- Heuristic-accelerated algorithms always outperform their non-heuristic counterparts, and oASP(MDP) variants explore more valid states while executing fewer impossible actions.The heuristics come from solutions to relaxed versions of the domains.Source: §7 · p. 32
- Future work proposes using ASP to extract general domain rules, such as constraints, for reasoning and potentially guiding learning with reusable knowledge.The paper suggests that a more general state description could support elaboration-tolerant ASP rules.Source: §7 · p. 32