Optimal Sequential Task Assignment and Path Finding for Multi-Agent Robotic Assembly Planning

• URL: http://arxiv.org/abs/2006.08845v1
• Date: Tue, 16 Jun 2020 00:45:07 GMT
• Title: Optimal Sequential Task Assignment and Path Finding for Multi-Agent Robotic Assembly Planning
• Authors: Kyle Brown, Oriana Peltzer, Martin A. Sehr, Mac Schwager, Mykel J. Kochenderfer
• Abstract summary: We study the problem of sequential task assignment and collision-free routing for large teams of robots in applications with inter-task precedence constraints. We propose a hierarchical algorithm for computing makespan-optimal solutions to the problem.
• Score: 42.38068056643171
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of sequential task assignment and collision-free routing for large teams of robots in applications with inter-task precedence constraints (e.g., task $A$ and task $B$ must both be completed before task $C$ may begin). Such problems commonly occur in assembly planning for robotic manufacturing applications, in which sub-assemblies must be completed before they can be combined to form the final product. We propose a hierarchical algorithm for computing makespan-optimal solutions to the problem. The algorithm is evaluated on a set of randomly generated problem instances where robots must transport objects between stations in a "factory "grid world environment. In addition, we demonstrate in high-fidelity simulation that the output of our algorithm can be used to generate collision-free trajectories for non-holonomic differential-drive robots.

Related papers

• COHERENT: Collaboration of Heterogeneous Multi-Robot System with Large Language Models [49.24666980374751]
  COHERENT is a novel LLM-based task planning framework for collaboration of heterogeneous multi-robot systems. A Proposal-Execution-Feedback-Adjustment mechanism is designed to decompose and assign actions for individual robots. The experimental results show that our work surpasses the previous methods by a large margin in terms of success rate and execution efficiency.
  arXiv  Detail & Related papers  (2024-09-23T15:53:41Z)
• 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)
• Multi-Agent Path Finding with Real Robot Dynamics and Interdependent Tasks for Automated Warehouses [1.2810395420131764]
  Multi-Agent Path Finding (MAPF) is an important optimization problem underlying the deployment of robots in automated warehouses and factories. We consider a realistic problem of online order delivery in a warehouse, where a fleet of robots bring the products belonging to each order from shelves to workstations. This creates a stream of inter-dependent pickup and delivery tasks and the associated MAPF problem consists of computing realistic collision-free robot trajectories.
  arXiv  Detail & Related papers  (2024-08-26T15:13:38Z)
• 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)
• Optimal Integrated Task and Path Planning and Its Application to Multi-Robot Pickup and Delivery [10.530860023128406]
  We propose a generic multi-robot planning mechanism that combines an optimal task planner and an optimal path planner. The Integrated planner, through the interaction of the task planner and the path planner, produces optimal collision-free trajectories for the robots.
  arXiv  Detail & Related papers  (2024-03-02T17:48:40Z)
• A Conflict-Aware Optimal Goal Assignment Algorithm for Multi-Robot Systems [6.853165736531941]
  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.
  arXiv  Detail & Related papers  (2024-02-19T19:04:19Z)
• Contribution \`a l'Optimisation d'un Comportement Collectif pour un Groupe de Robots Autonomes [0.0]
  This thesis studies the domain of collective robotics, and more particularly the optimization problems of multirobot systems. The first contribution is the use of the Butterfly Algorithm Optimization (BOA) to solve the Unknown Area Exploration problem. The second contribution is the development of a new simulation framework for benchmarking dynamic incremental problems in robotics.
  arXiv  Detail & Related papers  (2023-06-10T21:49:08Z)
• Towards Practical Multi-Robot Hybrid Tasks Allocation for Autonomous Cleaning [40.715435411065336]
  We formulate multi-robot hybrid-task allocation under the uncertain cleaning environment as a robust optimization problem. We establish a dataset of emph100 instances made from floor plans, each of which has 2D manually-labeled images and a 3D model. We provide comprehensive results on the collected dataset using three traditional optimization approaches and a deep reinforcement learning-based solver.
  arXiv  Detail & Related papers  (2023-03-12T01:15:08Z)
• 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)
• 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.