Multi-Robot Connected Fermat Spiral Coverage

• URL: http://arxiv.org/abs/2403.13311v3
• Date: Tue, 16 Apr 2024 15:35:50 GMT
• Title: Multi-Robot Connected Fermat Spiral Coverage
• Authors: Jingtao Tang, Hang Ma,
• Abstract summary: We introduce the Multi-Robot Connected Fermat Spiral (MCFS), a novel algorithmic framework for Multi-Robot Coverage Path Planning (MCPP) MCFS adapts from the computer graphics community to multi-robot coordination for the first time. Our research marks a significant step in MCPP, showcasing the fusion of computer graphics and automated planning principles to advance the capabilities of multi-robot systems in complex environments.
• Score: 2.8750175877666653
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce the Multi-Robot Connected Fermat Spiral (MCFS), a novel algorithmic framework for Multi-Robot Coverage Path Planning (MCPP) that adapts Connected Fermat Spiral (CFS) from the computer graphics community to multi-robot coordination for the first time. MCFS uniquely enables the orchestration of multiple robots to generate coverage paths that contour around arbitrarily shaped obstacles, a feature that is notably lacking in traditional methods. Our framework not only enhances area coverage and optimizes task performance, particularly in terms of makespan, for workspaces rich in irregular obstacles but also addresses the challenges of path continuity and curvature critical for non-holonomic robots by generating smooth paths without decomposing the workspace. MCFS solves MCPP by constructing a graph of isolines and transforming MCPP into a combinatorial optimization problem, aiming to minimize the makespan while covering all vertices. Our contributions include developing a unified CFS version for scalable and adaptable MCPP, extending it to MCPP with novel optimization techniques for cost reduction and path continuity and smoothness, and demonstrating through extensive experiments that MCFS outperforms existing MCPP methods in makespan, path curvature, coverage ratio, and overlapping ratio. Our research marks a significant step in MCPP, showcasing the fusion of computer graphics and automated planning principles to advance the capabilities of multi-robot systems in complex environments. Our code is available at https://github.com/reso1/MCFS.

Related papers

• SCoTT: Wireless-Aware Path Planning with Vision Language Models and Strategic Chains-of-Thought [78.53885607559958]
  A novel approach using vision language models (VLMs) is proposed for enabling path planning in complex wireless-aware environments. To this end, insights from a digital twin with real-world wireless ray tracing data are explored. Results show that SCoTT achieves very close average path gains compared to DP-WA* while at the same time yielding consistently shorter path lengths.
  arXiv  Detail & Related papers  (2024-11-27T10:45:49Z)
• Large-Scale Multi-Robot Coverage Path Planning on Grids with Path Deconfliction [2.5580729045474015]
  We study Multi-Robot Coverage Path Planning (MCPP) on a 4-neighbor 2D grid G, which aims to compute paths for multiple robots to cover all cells of G. We reformulate the problem directly on G, revolutionizing grid-based MCPP solving and establishing new NP-hardness results. We show that our approach significantly improves solution quality and efficiency, managing up to 100 robots on grids as large as 256x256 within minutes of runtime.
  arXiv  Detail & Related papers  (2024-11-03T22:37:56Z)
• Robust Incremental Structure-from-Motion with Hybrid Features [73.55745864762703]
  We introduce an incremental Structure-from-Motion (SfM) system that leverages lines and their structured geometric relations. Our system is consistently more robust and accurate compared to the widely used point-based state of the art in SfM.
  arXiv  Detail & Related papers  (2024-09-29T22:20:32Z)
• A Meta-Engine Framework for Interleaved Task and Motion Planning using Topological Refinements [51.54559117314768]
  Task And Motion Planning (TAMP) is the problem of finding a solution to an automated planning problem. We propose a general and open-source framework for modeling and benchmarking TAMP problems. We introduce an innovative meta-technique to solve TAMP problems involving moving agents and multiple task-state-dependent obstacles.
  arXiv  Detail & Related papers  (2024-08-11T14:57:57Z)
• SOMTP: Self-Supervised Learning-Based Optimizer for MPC-Based Safe Trajectory Planning Problems in Robotics [13.129654942805846]
  Model Predictive Control (MP)-based trajectory planning has been widely used in, and Control Barrier (CBF) can improve its constraints. In this paper, we propose a self-supervised learning algorithm for CBF-MPC trajectory planning.
  arXiv  Detail & Related papers  (2024-05-15T09:38:52Z)
• Deep Reinforcement Learning for Traveling Purchaser Problems [63.37136587778153]
  The traveling purchaser problem (TPP) is an important optimization problem with broad applications. We propose a novel approach based on deep reinforcement learning (DRL), which addresses route construction and purchase planning separately. By introducing a meta-learning strategy, the policy network can be trained stably on large-sized TPP instances.
  arXiv  Detail & Related papers  (2024-04-03T05:32:10Z)
• The Parameterized Complexity of Coordinated Motion Planning [28.39902924923273]
  In Coordinated Motion Planning (CMP), $k$ robots occupy $k$ distinct starting gridpoints and need to reach $k$ distinct destination gridpoints. The goal is to compute a schedule for moving the $k$ robots to their destinations which minimizes a certain objective target. In this paper, we settle the parameterized complexity of CMP-M and CMP-L with respect to their two most fundamental parameters.
  arXiv  Detail & Related papers  (2023-12-12T10:26:01Z)
• CiFHER: A Chiplet-Based FHE Accelerator with a Resizable Structure [5.0817812294893]
  Homomorphic encryption (FHE) is a definitive solution for privacy, but the high computational overhead of FHE poses a challenge to its practical adoption. We propose CiFHER, a chiplet-based FHE accelerator with a resizable structure. This study demonstrates that a CiFHER package composed of a number of compact chiplets provides performance comparable to state-of-the-art monolithic ASIC accelerators.
  arXiv  Detail & Related papers  (2023-08-09T11:41:56Z)
• Simultaneous Contact-Rich Grasping and Locomotion via Distributed Optimization Enabling Free-Climbing for Multi-Limbed Robots [60.06216976204385]
  We present an efficient motion planning framework for simultaneously solving locomotion, grasping, and contact problems. We demonstrate our proposed framework in the hardware experiments, showing that the multi-limbed robot is able to realize various motions including free-climbing at a slope angle 45deg with a much shorter planning time.
  arXiv  Detail & Related papers  (2022-07-04T13:52:10Z)
• Collaborative Intelligent Reflecting Surface Networks with Multi-Agent Reinforcement Learning [63.83425382922157]
  Intelligent reflecting surface (IRS) is envisioned to be widely applied in future wireless networks. In this paper, we investigate a multi-user communication system assisted by cooperative IRS devices with the capability of energy harvesting.
  arXiv  Detail & Related papers  (2022-03-26T20:37:14Z)

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.