A Conflict-Aware Optimal Goal Assignment Algorithm for Multi-Robot Systems

• URL: http://arxiv.org/abs/2402.13292v1
• Date: Mon, 19 Feb 2024 19:04:19 GMT
• Title: A Conflict-Aware Optimal Goal Assignment Algorithm for Multi-Robot Systems
• Authors: Aakash and Indranil Saha
• Abstract summary: A multi-robot application aims to assign a unique goal to each robot while ensuring collision-free paths. We propose an efficient conflict-guided method to compute the next best assignment. We extensively evaluate our algorithm for up to a hundred robots on several benchmark workspaces.
• Score: 6.853165736531941
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The fundamental goal assignment problem for a multi-robot application aims to assign a unique goal to each robot while ensuring collision-free paths, minimizing the total movement cost. A plausible algorithmic solution to this NP-hard problem involves an iterative process that integrates a task planner to compute the goal assignment while ignoring the collision possibilities among the robots and a multi-agent path-finding algorithm to find the collision-free trajectories for a given assignment. This procedure involves a method for computing the next best assignment given the current best assignment. A naive way of computing the next best assignment, as done in the state-of-the-art solutions, becomes a roadblock to achieving scalability in solving the overall problem. To obviate this bottleneck, we propose an efficient conflict-guided method to compute the next best assignment. Additionally, we introduce two more optimizations to the algorithm -- first for avoiding the unconstrained path computations between robot-goal pairs wherever possible, and the second to prevent duplicate constrained path computations for multiple robot-goal pairs. We extensively evaluate our algorithm for up to a hundred robots on several benchmark workspaces. The results demonstrate that the proposed algorithm achieves nearly an order of magnitude speedup over the state-of-the-art algorithm, showcasing its efficacy in real-world scenarios.

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)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• Multi-Robot Active Mapping via Neural Bipartite Graph Matching [49.72892929603187]
  We study the problem of multi-robot active mapping, which aims for complete scene map construction in minimum time steps. The key to this problem lies in the goal position estimation to enable more efficient robot movements. We propose a novel algorithm, namely NeuralCoMapping, which takes advantage of both approaches.
  arXiv  Detail & Related papers  (2022-03-30T14:03:17Z)
• A distributed, plug-n-play algorithm for multi-robot applications with a priori non-computable objective functions [2.2452191187045383]
  In multi-robot applications, the user-defined objectives of the mission can be cast as a general optimization problem. Standard gradient-descent-like algorithms are not applicable to these problems. We introduce a new algorithm that carefully designs each robot's subcost function, the optimization of which can accomplish the overall team objective.
  arXiv  Detail & Related papers  (2021-11-14T20:40:00Z)
• Distributed Allocation and Scheduling of Tasks with Cross-Schedule Dependencies for Heterogeneous Multi-Robot Teams [2.294915015129229]
  We present a distributed task allocation and scheduling algorithm for missions where the tasks of different robots are tightly coupled with temporal and precedence constraints. An application of the planning procedure to a practical use case of a greenhouse maintained by a multi-robot system is given.
  arXiv  Detail & Related papers  (2021-09-07T13:44:28Z)
• Distributed Swarm Collision Avoidance Based on Angular Calculations [0.0]
  In this paper, a distributed and real-time algorithm for dense and complex 2D and 3D environments is proposed. It uses angular calculations to select the optimal direction for the movement of each robot. The proposed method is shown to enable fully autonomous navigation of a swarm of crazyflies.
  arXiv  Detail & Related papers  (2021-08-29T23:12:38Z)
• Prioritized SIPP for Multi-Agent Path Finding With Kinematic Constraints [0.0]
  Multi-Agent Path Finding (MAPF) is a long-standing problem in Robotics and Artificial Intelligence. We present a method that mitigates this issue to a certain extent.
  arXiv  Detail & Related papers  (2021-08-11T10:42:11Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together. The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively. Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
  arXiv  Detail & Related papers  (2021-03-10T03:16:12Z)
• Sparsification for Fast Optimal Multi-Robot Path Planning in Lazy Compilation Schemes [7.766921168069532]
  Path planning for multiple robots (MRPP) represents a task of finding non-colliding paths for robots through which they can navigate from their initial positions to specified goal positions. In this paper, we enhance existing SAT-based algorithm for MRPP via spartification of the set of candidate paths for each robot from which target Boolean encoding is derived.
  arXiv  Detail & Related papers  (2021-03-08T00:57:42Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  This paper investigates the classical integer least-squares problem which estimates signals integer from linear models. The problem is NP-hard and often arises in diverse applications such as signal processing, bioinformatics, communications and machine learning. We propose a general hyper-accelerated tree search (HATS) algorithm by employing a deep neural network to estimate the optimal estimation for the underlying simplified memory-bounded A* algorithm.
  arXiv  Detail & Related papers  (2021-01-07T08:00:02Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  We present a multi-robot allocation algorithm that decouples the key computational challenges of sequential decision-making under uncertainty and multi-agent coordination. We validate our results over a wide range of simulations on two distinct domains: multi-arm conveyor belt pick-and-place and multi-drone delivery dispatch in a city.
  arXiv  Detail & Related papers  (2020-05-27T01:10:41Z)

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.