# Reinforcement Learning-Based Coverage Path Planning with Implicit Cellular Decomposition

arXiv: https://arxiv.org/abs/2110.09018 · HTML: https://mlsanity.com/paper/2110.09018/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 64 references that are in the map.
- First posted on arXiv 18 Oct 2021.

## Builds on (most cited first, 22 of 22)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [Prioritized Experience Replay](https://mlsanity.com/paper/1511.05952/) (2015)
- [Rainbow: Combining Improvements in Deep Reinforcement Learning](https://mlsanity.com/paper/1710.02298/) (2017)
- [Dueling Network Architectures for Deep Reinforcement Learning](https://mlsanity.com/paper/1511.06581/) (2015)
- [Distributional Reinforcement Learning with Quantile Regression](https://mlsanity.com/paper/1710.10044/) (2017)
- [Target-driven Visual Navigation in Indoor Scenes using Deep Reinforcement Learning](https://mlsanity.com/paper/1609.05143/) (2016)
- [Noisy Networks for Exploration](https://mlsanity.com/paper/1706.10295/) (2017)
- [Learning to Navigate in Complex Environments](https://mlsanity.com/paper/1611.03673/) (2016)
- [Learning to Navigate in Cities Without a Map](https://mlsanity.com/paper/1804.00168/) (2018)
- [A Deep Hierarchical Approach to Lifelong Learning in Minecraft](https://mlsanity.com/paper/1604.07255/) (2016)
- [Neural Map: Structured Memory for Deep Reinforcement Learning](https://mlsanity.com/paper/1702.08360/) (2017)
- [Control of Memory, Active Perception, and Action in Minecraft](https://mlsanity.com/paper/1605.09128/) (2016)
- [Stacked What-Where Auto-encoders](https://mlsanity.com/paper/1506.02351/) (2015)
- [Extending the OpenAI Gym for robotics: a toolkit for reinforcement learning using ROS and Gazebo](https://mlsanity.com/paper/1608.05742/) (2016)
- [Active Neural Localization](https://mlsanity.com/paper/1801.08214/) (2018)
- [Towards Cognitive Exploration through Deep Reinforcement Learning for Mobile Robots](https://mlsanity.com/paper/1610.01733/) (2016)
- [Robot Coverage Path Planning for General Surfaces Using Quadratic Differentials](https://mlsanity.com/paper/1701.07549/) (2017)
- [A Sweet Pepper Harvesting Robot for Protected Cropping Environments](https://mlsanity.com/paper/1810.11920/) (2018)
- [A Constant-Factor Approximation Algorithm for Online Coverage Path Planning with Energy Constraint](https://mlsanity.com/paper/1906.11750/) (2019)

## Built on by (most cited first, 6 of 6)

- [Learning Coverage Paths in Unknown Environments with Deep Reinforcement Learning](https://mlsanity.com/paper/2306.16978/) (2023)
- [Learning to Recharge: UAV Coverage Path Planning through Deep Reinforcement Learning](https://mlsanity.com/paper/2309.03157/) (2023)
- [Sim-to-Real Transfer of Deep Reinforcement Learning Agents for Online Coverage Path Planning](https://mlsanity.com/paper/2406.04920/) (2024)
- [Deep Recurrent Q-learning for Energy-constrained Coverage with a Mobile Robot](https://mlsanity.com/paper/2210.00327/) (2022)
- [Efficient Domain Coverage for Vehicles with Second-Order Dynamics via Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2211.05952/) (2022)
- [On-policy Actor-Critic Reinforcement Learning for Multi-UAV Exploration](https://mlsanity.com/paper/2409.11058/) (2024)

## Abstract (arXiv)

Coverage path planning in a generic known environment is shown to be NP-hard. When the environment is unknown, it becomes more challenging as the robot is required to rely on its online map information built during coverage for planning its path. A significant research effort focuses on designing heuristic or approximate algorithms that achieve reasonable performance. Such algorithms have sub-optimal performance in terms of covering the area or the cost of coverage, e.g., coverage time or energy consumption. In this paper, we provide a systematic analysis of the coverage problem and formulate it as an optimal stopping time problem, where the trade-off between coverage performance and its cost is explicitly accounted for. Next, we demonstrate that reinforcement learning (RL) techniques can be leveraged to solve the problem computationally. To this end, we provide some technical and practical considerations to facilitate the application of the RL algorithms and improve the efficiency of the solutions. Finally, through experiments in grid world environments and Gazebo simulator, we show that reinforcement learning-based algorithms efficiently cover realistic unknown indoor environments, and outperform the current state of the art.