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

2019-02-16 · Thiago Freitas dos Santos, Paulo E. Santos, Leonardo A. Ferreira, Reinaldo A. C. Bianchi, Pedro Cabalar

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.

📄 PDF Abstract BibTeX arXiv:1903.03411

Code (1)

https://bitbucket.org/thiagomestrado/journalarticle 공식 구현

Tasks

Q-LearningReinforcement Learning Reinforcement Learning (RL)

Methods 이 논문이 사용한 방법론

Q-Learning Q-Learning is an off-policy temporal difference control algorithm: $$Q\left(S\_{t}, A\_{t}\right) \leftarrow Q\left(S\_{t}, A\_{t}\right) + \alpha\left[R_{t+1} +…

Answer Set Programming for Non-Stationary Markov Decision Processes

2017-05-03 · Leonardo A. Ferreira, Reinaldo A. C. Bianchi, Paulo E. Santos, Ramon Lopez de Mantaras

Non-stationary domains, where unforeseen changes happen, present a challenge for agents to find an optimal policy for a sequential decision making problem. This work investigates a solution to this problem that combines …

Decision Making reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)+1

Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach

2024-02-29 · Daniele Meli, Alberto Castellini, Alessandro Farinelli

Partially Observable Markov Decision Processes (POMDPs) are a powerful framework for planning under uncertainty. They allow to model state uncertainty as a belief probability distribution. Approximate solvers based on Mo…

Inductive logic programming

A method for the online construction of the set of states of a Markov Decision Process using Answer Set Programming

2017-06-05 · Leonardo A. Ferreira, Reinaldo A. C. Bianchi, Paulo E. Santos, Ramon Lopez de Mantaras

Non-stationary domains, that change in unpredicted ways, are a challenge for agents searching for optimal policies in sequential decision-making problems. This paper presents a combination of Markov Decision Processes (M…

Decision Making Reinforcement Learning Reinforcement Learning (RL)Sequential Decision Making

Elaboration Tolerant Representation of Markov Decision Process via Decision-Theoretic Extension of Probabilistic Action Language pBC+

2019-04-01 · Yi Wang, Joohyung Lee

We extend probabilistic action language pBC+ with the notion of utility as in decision theory. The semantics of the extended pBC+ can be defined as a shorthand notation for a decision-theoretic extension of the probabili…

A Markov Decision Process for Variable Selection in Branch & Bound

2025-10-22 · Paul Strang, Zacharie Alès, Côme Bissuel, Olivier Juan 외 arxiv

Mixed-Integer Linear Programming (MILP) is a powerful framework used to address a wide range of NP-hard combinatorial optimization problems, often solved by Branch and Bound (B&B). A key factor influencing the performanc…

Reinforcement Learning