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:
- Automaton Representation: The LTL task is converted into a Deterministic Rabin Automaton (DRA), which serves as a logical map of the mission.
- 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.
- 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.
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.
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