Graph-Based Multi-Robot Path Finding and Planning
- URL: http://arxiv.org/abs/2206.11319v1
- Date: Wed, 22 Jun 2022 18:47:00 GMT
- Title: Graph-Based Multi-Robot Path Finding and Planning
- Authors: Hang Ma
- Abstract summary: Planning collision-free paths for multiple robots is important for real-world multi-robot systems.
Recent advances have resulted in MAPF algorithms that can compute collision-free paths for hundreds of robots.
- Score: 3.4260993997836753
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Purpose of Review
Planning collision-free paths for multiple robots is important for real-world
multi-robot systems and has been studied as an optimization problem on graphs,
called Multi-Agent Path Finding (MAPF). This review surveys different
categories of classic and state-of-the-art MAPF algorithms and different
research attempts to tackle the challenges of generalizing MAPF techniques to
real-world scenarios.
Recent Findings
Solving MAPF problems optimally is computationally challenging. Recent
advances have resulted in MAPF algorithms that can compute collision-free paths
for hundreds of robots and thousands of navigation tasks in seconds of runtime.
Many variants of MAPF have been formalized to adapt MAPF techniques to
different real-world requirements, such as considerations of robot kinematics,
online optimization for real-time systems, and the integration of task
assignment and path planning.
Summary
Algorithmic techniques for MAPF problems have addressed important aspects of
several multi-robot applications, including automated warehouse fulfillment and
sortation, automated train scheduling, and navigation of non-holonomic robots
and quadcopters. This showcases their potential for real-world applications of
large-scale multi-robot systems.
Related papers
- Algorithm Selection for Optimal Multi-Agent Path Finding via Graph Embedding [9.831879504969224]
Multi-agent path finding (MAPF) is the problem of finding paths for multiple agents such that they do not collide.
Finding optimal solutions to MAPF is NP-Hard, yet modern optimal solvers can scale to hundreds of agents and even thousands in some cases.
We show how this encoding can be effectively joined with existing encodings, resulting in a novel AS method we call MAPF Algorithm selection via Graph embedding.
arXiv Detail & Related papers (2024-06-16T07:41:58Z) - Scalable Mechanism Design for Multi-Agent Path Finding [87.40027406028425]
Multi-Agent Path Finding (MAPF) involves determining paths for multiple agents to travel simultaneously and collision-free through a shared area toward given goal locations.
Finding an optimal solution is often computationally infeasible, making the use of approximate, suboptimal algorithms essential.
We introduce the problem of scalable mechanism design for MAPF and propose three strategyproof mechanisms, two of which even use approximate MAPF algorithms.
arXiv Detail & Related papers (2024-01-30T14:26:04Z) - Multi-Robot Coordination and Layout Design for Automated Warehousing [55.150593161240444]
We show that, even with state-of-the-art MAPF algorithms, commonly used human-designed layouts can lead to congestion for warehouses with large numbers of robots.
We extend existing automatic scenario generation methods to optimize warehouse layouts.
Results show that our optimized warehouse layouts (1) reduce traffic congestion and thus improve throughput, (2) improve the scalability of the automated warehouses by doubling the number of robots in some cases, and (3) are capable of generating layouts with user-specified diversity measures.
arXiv Detail & Related papers (2023-05-10T20:00:06Z) - AutoML-GPT: Automatic Machine Learning with GPT [74.30699827690596]
We propose developing task-oriented prompts and automatically utilizing large language models (LLMs) to automate the training pipeline.
We present the AutoML-GPT, which employs GPT as the bridge to diverse AI models and dynamically trains models with optimized hyper parameters.
This approach achieves remarkable results in computer vision, natural language processing, and other challenging areas.
arXiv Detail & Related papers (2023-05-04T02:09:43Z) - Learning to Coordinate for a Worker-Station Multi-robot System in Planar
Coverage Tasks [16.323122275188354]
We focus on the multi-robot coverage path planning problem in large-scale planar areas with random dynamic interferers.
We introduce a worker-station MRS consisting of multiple workers with limited resources for actual work, and one station with enough resources for resource replenishment.
We propose an end-to-end decentralized online planning method, which simultaneously solves coverage planning for workers and rendezvous planning for station.
arXiv Detail & Related papers (2022-08-05T05:36:42Z) - 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) - Intelligent Trajectory Design for RIS-NOMA aided Multi-robot
Communications [59.34642007625687]
The goal is to maximize the sum-rate of whole trajectories for multi-robot system by jointly optimizing trajectories and NOMA decoding orders of robots.
An integrated machine learning (ML) scheme is proposed, which combines long short-term memory (LSTM)-autoregressive integrated moving average (ARIMA) model and dueling double deep Q-network (D$3$QN) algorithm.
arXiv Detail & Related papers (2022-05-03T17:14:47Z) - Navigational Path-Planning For All-Terrain Autonomous Agricultural Robot [0.0]
This report compares novel algorithms for autonomous navigation of farmlands.
High-resolution grid map representation is taken into consideration specific to Indian environments.
Results proved the applicability of the algorithms for autonomous field navigation and feasibility with robotic path planning.
arXiv Detail & Related papers (2021-09-05T07:29:13Z) - 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) - Compilation-based Solvers for Multi-Agent Path Finding: a Survey,
Discussion, and Future Opportunities [7.766921168069532]
We show the lessons learned from past developments and current trends in the topic and discuss its wider impact.
Two major approaches to optimal MAPF solving include (1) dedicated search-based methods, which solve MAPF directly, and (2) compilation-based methods that reduce a MAPF instance to an instance in a different well established formalism.
arXiv Detail & Related papers (2021-04-23T20:13:12Z)
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.