Large-Scale Multi-Robot Coverage Path Planning via Local Search
- URL: http://arxiv.org/abs/2312.10797v2
- Date: Wed, 28 Feb 2024 04:08:21 GMT
- Title: Large-Scale Multi-Robot Coverage Path Planning via Local Search
- Authors: Jingtao Tang, Hang Ma
- Abstract summary: We study graph-based Multi-Robot Coverage Path Planning (MCPP) that aims to compute coverage paths for multiple robots.
We introduce a new algorithmic framework, called LS-MCPP, which leverages a local search to operate directly on $D$.
Our experiments demonstrate the effectiveness of LS-MCPP, consistently improving the initial solution.
- Score: 3.396452421780085
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study graph-based Multi-Robot Coverage Path Planning (MCPP) that aims to
compute coverage paths for multiple robots to cover all vertices of a given 2D
grid terrain graph $G$. Existing graph-based MCPP algorithms first compute a
tree cover on $G$ -- a forest of multiple trees that cover all vertices -- and
then employ the Spanning Tree Coverage (STC) paradigm to generate coverage
paths on the decomposed graph $D$ of the terrain graph $G$ by circumnavigating
the edges of the computed trees, aiming to optimize the makespan (i.e., the
maximum coverage path cost among all robots). In this paper, we take a
different approach by exploring how to systematically search for good coverage
paths directly on $D$. We introduce a new algorithmic framework, called
LS-MCPP, which leverages a local search to operate directly on $D$. We propose
a novel standalone paradigm, Extended-STC (ESTC), that extends STC to achieve
complete coverage for MCPP on any decomposed graphs, even those resulting from
incomplete terrain graphs. Furthermore, we demonstrate how to integrate ESTC
with three novel types of neighborhood operators into our framework to
effectively guide its search process. Our extensive experiments demonstrate the
effectiveness of LS-MCPP, consistently improving the initial solution returned
by two state-of-the-art baseline algorithms that compute suboptimal tree covers
on $G$, with a notable reduction in makespan by up to 35.7\% and 30.3\%,
respectively. Moreover, LS-MCPP consistently matches or surpasses the results
of optimal tree cover computation, achieving these outcomes with orders of
magnitude faster runtime, thereby showcasing its significant benefits for
large-scale real-world coverage tasks.
Related papers
- LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget.
Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
arXiv Detail & Related papers (2024-06-29T05:14:04Z) - Graph Sparsification via Mixture of Graphs [67.40204130771967]
We introduce Mixture-of-Graphs (MoG) to dynamically select tailored pruning solutions for each node.
MoG incorporates multiple sparsifier experts, each characterized by unique sparsity levels and pruning criteria, and selects the appropriate experts for each node.
Experiments on four large-scale OGB datasets and two superpixel datasets, equipped with five GNNs, demonstrate that MoG identifies subgraphs at higher sparsity levels.
arXiv Detail & Related papers (2024-05-23T07:40:21Z) - Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs [7.616556723260849]
This paper presents two efficient hierarchical clustering (HC) algorithms with respect to Dasgupta's cost function.
For any input graph $G$ with a clear cluster-structure, our designed algorithms run in nearly-linear time in the input size of $G$.
We show that our designed algorithm produces comparable or better HC trees with much lower running time.
arXiv Detail & Related papers (2023-06-16T16:31:46Z) - Efficient Graph Field Integrators Meet Point Clouds [59.27295475120132]
We present two new classes of algorithms for efficient field integration on graphs encoding point clouds.
The first class, SeparatorFactorization(SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations for point clouds.
arXiv Detail & Related papers (2023-02-02T08:33:36Z) - SoftTreeMax: Policy Gradient with Tree Search [72.9513807133171]
We introduce SoftTreeMax, the first approach that integrates tree-search into policy gradient.
On Atari, SoftTreeMax demonstrates up to 5x better performance in faster run-time compared with distributed PPO.
arXiv Detail & Related papers (2022-09-28T09:55:47Z) - Enhanced Multi-Objective A* Using Balanced Binary Search Trees [35.63053398687847]
Multi-objective A* (MOA*) like algorithms maintain a "frontier" set at any node during the search to keep track of the non-dominated paths that reach that node.
We introduce a new method to efficiently maintain these frontiers for multiple objectives by leveraging balanced binary search trees.
arXiv Detail & Related papers (2022-02-18T02:54:58Z) - Large-Scale Network Embedding in Apache Spark [1.3769786711365102]
We propose an efficient and effective distributed algorithm for network embedding on large graphs using Apache Spark.
We demonstrate in various experiments that our proposed approach is able to handle graphs with billions of edges within a few hours and is at least 4 times faster than the state-of-the-art approaches.
arXiv Detail & Related papers (2021-06-20T04:42:24Z) - Waypoint Planning Networks [66.72790309889432]
We propose a hybrid algorithm based on LSTMs with a local kernel - a classic algorithm such as A*, and a global kernel using a learned algorithm.
We compare WPN against A*, as well as related works including motion planning networks (MPNet) and value networks (VIN)
It is shown that WPN's search space is considerably less than A*, while being able to generate near optimal results.
arXiv Detail & Related papers (2021-05-01T18:02:01Z) - Nearly Minimax Optimal Reward-free Reinforcement Learning [88.75843804630772]
We study the reward-free reinforcement learning framework, which is particularly suitable for batch reinforcement learning and scenarios where one needs policies for multiple reward functions.
We give a new efficient algorithm, textbfStaged textbfSampling + textbfTruncated textbfPlanning (algoname), which interacts with the environment at most $Oleft( fracS2Aepsilon2textpolylogleft(fracSAHepsilon2
arXiv Detail & Related papers (2020-10-12T17:51:19Z)
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.