Scalable Multi-robot Motion Planning for Congested Environments With Topological Guidance

• URL: http://arxiv.org/abs/2210.07141v2
• Date: Thu, 25 May 2023 18:19:21 GMT
• Title: Scalable Multi-robot Motion Planning for Congested Environments With Topological Guidance
• Authors: Courtney McBeth, James Motes, Diane Uwacu, Marco Morales, Nancy M. Amato
• Abstract summary: Multi-robot motion planning (MRMP) is the problem of finding collision-free paths for a set of robots in a continuous state space. We extend an existing single-robot motion planning method to leverage the improved efficiency provided by topological guidance. We demonstrate our method's ability to efficiently plan paths in complex environments with many narrow passages, scaling to robot teams of size up to 25 times larger than existing methods.
• Score: 2.846144602096543
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multi-robot motion planning (MRMP) is the problem of finding collision-free paths for a set of robots in a continuous state space. The difficulty of MRMP increases with the number of robots and is exacerbated in environments with narrow passages that robots must pass through, like warehouse aisles where coordination between robots is required. In single-robot settings, topology-guided motion planning methods have shown improved performance in these constricted environments. In this work, we extend an existing topology-guided single-robot motion planning method to the multi-robot domain to leverage the improved efficiency provided by topological guidance. We demonstrate our method's ability to efficiently plan paths in complex environments with many narrow passages, scaling to robot teams of size up to 25 times larger than existing methods in this class of problems. By leveraging knowledge of the topology of the environment, we also find higher-quality solutions than other methods.

Related papers

• Robotic warehousing operations: a learn-then-optimize approach to large-scale neighborhood search [84.39855372157616]
  This paper supports robotic parts-to-picker operations in warehousing by optimizing order-workstation assignments, item-pod assignments and the schedule of order fulfillment at workstations. We solve it via large-scale neighborhood search, with a novel learn-then-optimize approach to subproblem generation. In collaboration with Amazon Robotics, we show that our model and algorithm generate much stronger solutions for practical problems than state-of-the-art approaches.
  arXiv  Detail & Related papers  (2024-08-29T20:22:22Z)
• 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)
• Leveraging Hyperbolic Embeddings for Coarse-to-Fine Robot Design [40.01142267374432]
  Multi-cellular robot design aims to create robots comprised of numerous cells that can be efficiently controlled to perform diverse tasks. Previous research has demonstrated the ability to generate robots for various tasks, but these approaches often optimize robots directly in the vast design space. This paper presents a novel coarse-to-fine method for designing multi-cellular robots.
  arXiv  Detail & Related papers  (2023-11-01T11:56:32Z)
• Minimizing Turns in Watchman Robot Navigation: Strategies and Solutions [1.6749379740049928]
  This paper introduces an efficient linear-time algorithm for solving the Orthogonal Watchman Route Problem (OWRP) The findings of this study contribute to the progress of robotic systems by enabling the design of more streamlined patrol robots.
  arXiv  Detail & Related papers  (2023-08-19T18:53:53Z)
• 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)
• REvolveR: Continuous Evolutionary Models for Robot-to-robot Policy Transfer [57.045140028275036]
  We consider the problem of transferring a policy across two different robots with significantly different parameters such as kinematics and morphology. Existing approaches that train a new policy by matching the action or state transition distribution, including imitation learning methods, fail due to optimal action and/or state distribution being mismatched in different robots. We propose a novel method named $REvolveR$ of using continuous evolutionary models for robotic policy transfer implemented in a physics simulator.
  arXiv  Detail & Related papers  (2022-02-10T18:50:25Z)
• 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)
• Large Scale Distributed Collaborative Unlabeled Motion Planning with Graph Policy Gradients [122.85280150421175]
  We present a learning method to solve the unlabelled motion problem with motion constraints and space constraints in 2D space for a large number of robots. We employ a graph neural network (GNN) to parameterize policies for the robots.
  arXiv  Detail & Related papers  (2021-02-11T21:57:43Z)
• Mobile Robot Path Planning in Dynamic Environments through Globally Guided Reinforcement Learning [12.813442161633116]
  We introduce a globally guided learning reinforcement approach (G2RL) to solve the multi-robot planning problem. G2RL incorporates a novel path reward structure that generalizes to arbitrary environments. We evaluate our method across different map types, obstacle densities and the number of robots.
  arXiv  Detail & Related papers  (2020-05-11T20:42:29Z)

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.