Accelerated Reinforcement Learning for Temporal Logic Control Objectives

Yiannis Kantaros

Abstract

This paper addresses the problem of learning control policies for mobile robots, modeled as unknown Markov Decision Processes (MDPs), that are tasked with temporal logic missions, such as sequencing, coverage, or surveillance. The control objective is to synthesize a control policy that maximizes the probability of accomplishing a high-level task, specified as a Linear Temporal Logic (LTL) formula. We propose a novel accelerated model-based reinforcement learning (RL) algorithm for LTL control objectives that is capable of learning control policies significantly faster than related approaches. Its sample-efficiency relies on biasing exploration towards directions that may contribute to task satisfaction by leveraging an automaton representation of the LTL task and a continuously learned MDP model. Comparative experiments demonstrate the sample efficiency of the proposed method against recent RL methods.

Introduction

Reinforcement learning (RL) is a powerful framework for robot control, but it faces significant challenges when rewards are sparse. This sparsity is particularly acute for missions defined by Linear Temporal Logic (LTL), which allows for complex, multi-stage instructions (e.g., "visit A then B, avoiding C"). In such scenarios, a robot exploring randomly may never encounter a reward signal, leading to extremely slow convergence. This paper introduces a model-based RL algorithm that leverages the logical structure of the task to guide exploration, effectively "priming" the agent to discover successful trajectories in large state spaces.

Methodology: Logic-Based Exploration

The core innovation lies in the integration of formal methods with reinforcement learning. The proposed approach follows several key steps:

  1. Automaton Representation: The LTL task is converted into a Deterministic Rabin Automaton (DRA), which serves as a logical map of the mission.
  2. Product MDP Construction: The robot's physical environment (an unknown MDP) is combined with the DRA to form a Product MDP. This allows the agent to track both its physical location and its progress through the logical states of the mission.
  3. Biased Exploration: Instead of standard random exploration, the algorithm uses a $(\epsilon, \delta)$-greedy strategy. While $\epsilon$ controls standard random exploration, $\delta$ introduces a biased exploration component. This bias directs the robot toward actions that, according to the current learned model of the environment, are more likely to advance the logical state of the mission toward completion.

Experimental Evaluation

The algorithm was tested in a 10x10 discrete grid world across three distinct tasks: Reach-Avoid Task I (minimal obstacles), Reach-Avoid Task II (17 obstacle cells), and a Surveillance Task requiring infinite patrolling of six locations. Performance was compared against standard RL baselines, including $\epsilon$-greedy, Boltzmann (softmax) exploration, and the Upper Confidence Bound (UCB1) algorithm.

Comparison of Algorithm 1 against standard RL baselines in Reach-Avoid Task I.

Key Results and Insights

The experimental results highlight the significant sample efficiency gains of the proposed method. In Reach-Avoid Task I, Algorithm 1 converged much faster than all baselines. The advantage became even more pronounced as task complexity increased.

In the Surveillance Task, standard baselines like UCB1 and $\epsilon$-greedy failed to collect any rewards even after 1,000 episodes. This "zero reward plateau" occurs because the probability of completing a complex surveillance cycle through random exploration is negligible. In contrast, the proposed biased exploration allowed the agent to start learning and accumulating rewards within the first few dozen episodes.

Performance in Reach-Avoid Task II (a) and Surveillance Task (b), demonstrating the ability to overcome sparse rewards.

The "aha moment" of this research is the realization that while the environment's transitions may be unknown, the mission's logic is fully known. By using the DRA as a guide, the agent can avoid aimless wandering and focus its exploration on logically productive actions.

Conclusion and Future Work

The proposed accelerated model-based RL algorithm significantly improves sample efficiency for LTL-specified tasks by exploiting the known logical structure of the mission. While currently focused on discrete state spaces, future work will explore scaling these techniques to continuous environments using deep RL and function approximation. This research paves the way for more efficient deployment of autonomous robots in complex, real-world missions where reward signals are naturally sparse.

Summary updated

Abstract

This paper addresses the problem of learning control policies for mobile robots, modeled as unknown Markov Decision Processes (MDPs), that are tasked with temporal logic missions, such as sequencing, coverage, or surveillance. The MDP captures uncertainty in the workspace structure and the outcomes of control decisions. The control objective is to synthesize a control policy that maximizes the probability of accomplishing a high-level task, specified as a Linear Temporal Logic (LTL) formula. To address this problem, we propose a novel accelerated model-based reinforcement learning (RL) algorithm for LTL control objectives that is capable of learning control policies significantly faster than related approaches. Its sample-efficiency relies on biasing exploration towards directions that may contribute to task satisfaction. This is accomplished by leveraging an automaton representation of the LTL task as well as a continuously learned MDP model. Finally, we provide comparative experiments that demonstrate the sample efficiency of the proposed method against recent RL methods for LTL objectives.
BibTeX
@inproceedings{kantaros2022accelerated,
  author = {Yiannis Kantaros},
  title = {{Accelerated Reinforcement Learning for Temporal Logic Control Objectives}},
  booktitle = {IEEE/RSJ International Conference on Intelligent Robots and Systems},
  year = {2022},
  doi = {10.1109/iros47612.2022.9981759},
}
Figure