Reinforcement Learning-Based Coverage Path Planning with Implicit Cellular Decomposition

• URL: http://arxiv.org/abs/2110.09018v1
• Date: Mon, 18 Oct 2021 05:18:52 GMT
• Title: Reinforcement Learning-Based Coverage Path Planning with Implicit Cellular Decomposition
• Authors: Javad Heydari and Olimpiya Saha and Viswanath Ganapathy
• Abstract summary: This paper provides a systematic analysis of the coverage problem and formulates it as an optimal stopping time problem. We show that reinforcement learning-based algorithms efficiently cover realistic unknown indoor environments.
• Score: 5.2424255020469595
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• LLM-A*: Large Language Model Enhanced Incremental Heuristic Search on Path Planning [91.95362946266577]
  Path planning is a fundamental scientific problem in robotics and autonomous navigation. Traditional algorithms like A* and its variants are capable of ensuring path validity but suffer from significant computational and memory inefficiencies as the state space grows. We propose a new LLM based route planning method that synergistically combines the precise pathfinding capabilities of A* with the global reasoning capability of LLMs. This hybrid approach aims to enhance pathfinding efficiency in terms of time and space complexity while maintaining the integrity of path validity, especially in large-scale scenarios.
  arXiv  Detail & Related papers  (2024-06-20T01:24:30Z)
• Discovering General Reinforcement Learning Algorithms with Adversarial Environment Design [54.39859618450935]
  We show that it is possible to meta-learn update rules, with the hope of discovering algorithms that can perform well on a wide range of RL tasks. Despite impressive initial results from algorithms such as Learned Policy Gradient (LPG), there remains a gap when these algorithms are applied to unseen environments. In this work, we examine how characteristics of the meta-supervised-training distribution impact the performance of these algorithms.
  arXiv  Detail & Related papers  (2023-10-04T12:52:56Z)
• Computation-efficient Deep Learning for Computer Vision: A Survey [121.84121397440337]
  Deep learning models have reached or even exceeded human-level performance in a range of visual perception tasks. Deep learning models usually demand significant computational resources, leading to impractical power consumption, latency, or carbon emissions in real-world scenarios. New research focus is computationally efficient deep learning, which strives to achieve satisfactory performance while minimizing the computational cost during inference.
  arXiv  Detail & Related papers  (2023-08-27T03:55:28Z)
• Learning Coverage Paths in Unknown Environments with Deep Reinforcement Learning [17.69984142788365]
  Coverage path planning ( CPP) is the problem of finding a path that covers the entire free space of a confined area. We investigate how suitable reinforcement learning is for this challenging problem. We propose a computationally feasible egocentric map representation based on frontiers, and a novel reward term based on total variation.
  arXiv  Detail & Related papers  (2023-06-29T14:32:06Z)
• Autonomous search of real-life environments combining dynamical system-based path planning and unsupervised learning [0.0]
  This paper proposes algorithms for obstacle avoidance, chaotic trajectory dispersal, and accurate coverage calculation. The algorithms produce generally smooth chaotic trajectories and provide high scanning coverage of environments. The performance of this application was comparable to that of a conventional optimal path planner.
  arXiv  Detail & Related papers  (2023-05-03T00:09:31Z)
• MARLIN: Soft Actor-Critic based Reinforcement Learning for Congestion Control in Real Networks [63.24965775030673]
  We propose a novel Reinforcement Learning (RL) approach to design generic Congestion Control (CC) algorithms. Our solution, MARLIN, uses the Soft Actor-Critic algorithm to maximize both entropy and return. We trained MARLIN on a real network with varying background traffic patterns to overcome the sim-to-real mismatch.
  arXiv  Detail & Related papers  (2023-02-02T18:27:20Z)
• TransPath: Learning Heuristics For Grid-Based Pathfinding via Transformers [64.88759709443819]
  We suggest learning the instance-dependent proxies that are supposed to notably increase the efficiency of the search. The first proxy we suggest to learn is the correction factor, i.e. the ratio between the instance independent cost-to-go estimate and the perfect one. The second proxy is the path probability, which indicates how likely the grid cell is lying on the shortest path.
  arXiv  Detail & Related papers  (2022-12-22T14:26:11Z)
• Offline Stochastic Shortest Path: Learning, Evaluation and Towards Optimality [57.91411772725183]
  In this paper, we consider the offline shortest path problem when the state space and the action space are finite. We design the simple value-based algorithms for tackling both offline policy evaluation (OPE) and offline policy learning tasks. Our analysis of these simple algorithms yields strong instance-dependent bounds which can imply worst-case bounds that are near-minimax optimal.
  arXiv  Detail & Related papers  (2022-06-10T07:44:56Z)
• Neural Motion Planning for Autonomous Parking [6.1805402105389895]
  This paper presents a hybrid motion planning strategy that combines a deep generative network with a conventional motion planning method. The proposed method effectively learns the representations of a given state, and shows improvement in terms of algorithm performance.
  arXiv  Detail & Related papers  (2021-11-12T14:29:38Z)
• Integrating Deep Reinforcement and Supervised Learning to Expedite Indoor Mapping [0.0]
  We show that combining the two methods can shorten the mapping time, compared to frontier-based motion planning, by up to 75%. One is the use of deep reinforcement learning to train the motion planner. The second is the inclusion of a pre-trained generative deep neural network, acting as a map predictor.
  arXiv  Detail & Related papers  (2021-09-17T12:07:07Z)
• Experience-Based Heuristic Search: Robust Motion Planning with Deep Q-Learning [0.0]
  We show how experiences in the form of a Deep Q-Network can be integrated as optimal policy in a search algorithm. Our method may encourage further investigation of the applicability of reinforcement-learning-based planning in the field of self-driving vehicles.
  arXiv  Detail & Related papers  (2021-02-05T12:08:11Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.