Online Concurrent Multi-Robot Coverage Path Planning

• URL: http://arxiv.org/abs/2403.10460v1
• Date: Fri, 15 Mar 2024 16:51:30 GMT
• Title: Online Concurrent Multi-Robot Coverage Path Planning
• Authors: Ratijit Mitra, Indranil Saha,
• Abstract summary: In a horizon, the path planning and the path execution interleave, meaning when the path planning occurs for robots with no paths, the robots with outstanding paths do not execute. We propose a centralized algorithm that is not horizon-based. It plans paths at any time for a subset of robots with no paths, who have reached their previously assigned goals, while the rest execute their outstanding paths.
• Score: 5.801044612920816
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, centralized receding horizon online multi-robot coverage path planning algorithms have shown remarkable scalability in thoroughly exploring large, complex, unknown workspaces with many robots. In a horizon, the path planning and the path execution interleave, meaning when the path planning occurs for robots with no paths, the robots with outstanding paths do not execute, and subsequently, when the robots with new or outstanding paths execute to reach respective goals, path planning does not occur for those robots yet to get new paths, leading to wastage of both the robotic and the computation resources. As a remedy, we propose a centralized algorithm that is not horizon-based. It plans paths at any time for a subset of robots with no paths, i.e., who have reached their previously assigned goals, while the rest execute their outstanding paths, thereby enabling concurrent planning and execution. We formally prove that the proposed algorithm ensures complete coverage of an unknown workspace and analyze its time complexity. To demonstrate scalability, we evaluate our algorithm to cover eight large $2$D grid benchmark workspaces with up to 512 aerial and ground robots, respectively. A comparison with a state-of-the-art horizon-based algorithm shows its superiority in completing the coverage with up to 1.6x speedup. For validation, we perform ROS + Gazebo simulations in six 2D grid benchmark workspaces with 10 quadcopters and TurtleBots, respectively. We also successfully conducted one outdoor experiment with three quadcopters and one indoor with two TurtleBots.

Related papers

• Multi-Robot Informative Path Planning for Efficient Target Mapping using Deep Reinforcement Learning [11.134855513221359]
  We propose a novel deep reinforcement learning approach for multi-robot informative path planning. We train our reinforcement learning policy via the centralized training and decentralized execution paradigm. Our approach outperforms other state-of-the-art multi-robot target mapping approaches by 33.75% in terms of the number of discovered targets-of-interest.
  arXiv  Detail & Related papers  (2024-09-25T14:27:37Z)
• POA: Passable Obstacles Aware Path-planning Algorithm for Navigation of a Two-wheeled Robot in Highly Cluttered Environments [53.41594627336511]
  Passable Obstacles Aware (POA) planner is a novel navigation method for two-wheeled robots in a cluttered environment. Our algorithm allows two-wheeled robots to find a path through passable obstacles.
  arXiv  Detail & Related papers  (2023-07-16T19:44:27Z)
• DC-MRTA: Decentralized Multi-Robot Task Allocation and Navigation in Complex Environments [55.204450019073036]
  We present a novel reinforcement learning based task allocation and decentralized navigation algorithm for mobile robots in warehouse environments. We consider the problem of joint decentralized task allocation and navigation and present a two level approach to solve it. We observe improvement up to 14% in terms of task completion time and up-to 40% improvement in terms of computing collision-free trajectories for the robots.
  arXiv  Detail & Related papers  (2022-09-07T00:35:27Z)
• Incremental 3D Scene Completion for Safe and Efficient Exploration Mapping and Planning [60.599223456298915]
  We propose a novel way to integrate deep learning into exploration by leveraging 3D scene completion for informed, safe, and interpretable mapping and planning. We show that our method can speed up coverage of an environment by 73% compared to the baselines with only minimal reduction in map accuracy. Even if scene completions are not included in the final map, we show that they can be used to guide the robot to choose more informative paths, speeding up the measurement of the scene with the robot's sensors by 35%.
  arXiv  Detail & Related papers  (2022-08-17T14:19:33Z)
• Hierarchical Path-planning from Speech Instructions with Spatial Concept-based Topometric Semantic Mapping [7.332652485849632]
  This study aims to realize a hierarchical spatial representation using a topometric semantic map and path planning with speech instructions, including waypoints. We conducted experiments in home environments using the Toyota Human Support Robot on the SIGVerse simulator and in a lab-office environment with the real robot, Albert. Navigation experiments using speech instructions with a waypoint demonstrated a performance improvement of SpCoTMHP over the baseline hierarchical path planning method with path costs.
  arXiv  Detail & Related papers  (2022-03-21T09:15:25Z)
• Systematic Comparison of Path Planning Algorithms using PathBench [55.335463666037086]
  Path planning is an essential component of mobile robotics. Development of learning-based path planning algorithms has been experiencing rapid growth. This paper presents PathBench, a platform for developing, visualizing, training, testing, and benchmarking of existing and future path planning algorithms.
  arXiv  Detail & Related papers  (2022-03-07T01:52:57Z)
• SABER: Data-Driven Motion Planner for Autonomously Navigating Heterogeneous Robots [112.2491765424719]
  We present an end-to-end online motion planning framework that uses a data-driven approach to navigate a heterogeneous robot team towards a global goal. We use model predictive control (SMPC) to calculate control inputs that satisfy robot dynamics, and consider uncertainty during obstacle avoidance with chance constraints. recurrent neural networks are used to provide a quick estimate of future state uncertainty considered in the SMPC finite-time horizon solution. A Deep Q-learning agent is employed to serve as a high-level path planner, providing the SMPC with target positions that move the robots towards a desired global goal.
  arXiv  Detail & Related papers  (2021-08-03T02:56:21Z)
• PathBench: A Benchmarking Platform for Classical and Learned Path Planning Algorithms [59.3879573040863]
  Path planning is a key component in mobile robotics. Few attempts have been made to benchmark the algorithms holistically or unify their interface. This paper presents PathBench, a platform for developing, visualizing, training, testing, and benchmarking of existing and future path planning algorithms.
  arXiv  Detail & Related papers  (2021-05-04T21:48:18Z)
• Online search of unknown terrains using a dynamical system-based path planning approach [0.0]
  This study introduces a new scalable technique that helps a robot to steer away from the obstacles and cover the entire space in a short period of time. Using this technique resulted in 49% boost, on average, in the robot's performance compared to the state-of-the-art planners.
  arXiv  Detail & Related papers  (2021-03-22T14:00:04Z)

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.