Multi-Agent Path Finding with Real Robot Dynamics and Interdependent Tasks for Automated Warehouses

• URL: http://arxiv.org/abs/2408.14527v1
• Date: Mon, 26 Aug 2024 15:13:38 GMT
• Title: Multi-Agent Path Finding with Real Robot Dynamics and Interdependent Tasks for Automated Warehouses
• Authors: Vassilissa Lehoux-Lebacque, Tomi Silander, Christelle Loiodice, Seungjoon Lee, Albert Wang, Sofia Michel,
• Abstract summary: 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.
• Score: 1.2810395420131764
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-Agent Path Finding (MAPF) is an important optimization problem underlying the deployment of robots in automated warehouses and factories. Despite the large body of work on this topic, most approaches make heavy simplifications, both on the environment and the agents, which make the resulting algorithms impractical for real-life scenarios. In this paper, 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 fulfilling these tasks. To solve this MAPF problem, we propose an extension of the standard Prioritized Planning algorithm to deal with the inter-dependent tasks (Interleaved Prioritized Planning) and a novel Via-Point Star (VP*) algorithm to compute an optimal dynamics-compliant robot trajectory to visit a sequence of goal locations while avoiding moving obstacles. We prove the completeness of our approach and evaluate it in simulation as well as in a real warehouse.

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)
• 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)
• DC-MRTA: Decentralized Multi-Robot Task Allocation and Navigation in Complex Environments [55.204450019073036]
  We present a novel reinforcement learning based task allocation and decentralized navigation algorithm for mobile robots in warehouse environments. We consider the problem of joint decentralized task allocation and navigation and present a two level approach to solve it. We observe improvement up to 14% in terms of task completion time and up-to 40% improvement in terms of computing collision-free trajectories for the robots.
  arXiv  Detail & Related papers  (2022-09-07T00:35:27Z)
• 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)
• Graph-Based Multi-Robot Path Finding and Planning [3.4260993997836753]
  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.
  arXiv  Detail & Related papers  (2022-06-22T18:47:00Z)
• 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)
• 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)
• Optimal Sequential Task Assignment and Path Finding for Multi-Agent Robotic Assembly Planning [42.38068056643171]
  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.
  arXiv  Detail & Related papers  (2020-06-16T00:45:07Z)

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.