DC-MRTA: Decentralized Multi-Robot Task Allocation and Navigation in Complex Environments

• URL: http://arxiv.org/abs/2209.02865v1
• Date: Wed, 7 Sep 2022 00:35:27 GMT
• Title: DC-MRTA: Decentralized Multi-Robot Task Allocation and Navigation in Complex Environments
• Authors: Aakriti Agrawal, Senthil Hariharan, Amrit Singh Bedi, Dinesh Manocha
• Abstract summary: 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.
• Score: 55.204450019073036
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a novel reinforcement learning (RL) based task allocation and decentralized navigation algorithm for mobile robots in warehouse environments. Our approach is designed for scenarios in which multiple robots are used to perform various pick up and delivery tasks. We consider the problem of joint decentralized task allocation and navigation and present a two level approach to solve it. At the higher level, we solve the task allocation by formulating it in terms of Markov Decision Processes and choosing the appropriate rewards to minimize the Total Travel Delay (TTD). At the lower level, we use a decentralized navigation scheme based on ORCA that enables each robot to perform these tasks in an independent manner, and avoid collisions with other robots and dynamic obstacles. We combine these lower and upper levels by defining rewards for the higher level as the feedback from the lower level navigation algorithm. We perform extensive evaluation in complex warehouse layouts with large number of agents and highlight the benefits over state-of-the-art algorithms based on myopic pickup distance minimization and regret-based task selection. 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.

Related papers

• Generalizability of Graph Neural Networks for Decentralized Unlabeled Motion Planning [72.86540018081531]
  Unlabeled motion planning involves assigning a set of robots to target locations while ensuring collision avoidance. This problem forms an essential building block for multi-robot systems in applications such as exploration, surveillance, and transportation. We address this problem in a decentralized setting where each robot knows only the positions of its $k$-nearest robots and $k$-nearest targets.
  arXiv  Detail & Related papers  (2024-09-29T23:57:25Z)
• 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)
• Diffusion-Reinforcement Learning Hierarchical Motion Planning in Adversarial Multi-agent Games [6.532258098619471]
  We focus on a motion planning task for an evasive target in a partially observable multi-agent adversarial pursuit-evasion games (PEG) These pursuit-evasion problems are relevant to various applications, such as search and rescue operations and surveillance robots. We propose a hierarchical architecture that integrates a high-level diffusion model to plan global paths responsive to environment data.
  arXiv  Detail & Related papers  (2024-03-16T03:53:55Z)
• Mission-driven Exploration for Accelerated Deep Reinforcement Learning with Temporal Logic Task Specifications [11.812602599752294]
  We consider robots with unknown dynamics operating in environments with unknown structure. Our goal is to synthesize a control policy that maximizes the probability of satisfying an automaton-encoded task. We propose a novel DRL algorithm, which has the capability to learn control policies at a notably faster rate compared to similar methods.
  arXiv  Detail & Related papers  (2023-11-28T18:59:58Z)
• 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)
• 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)
• ReLMoGen: Leveraging Motion Generation in Reinforcement Learning for Mobile Manipulation [99.2543521972137]
  ReLMoGen is a framework that combines a learned policy to predict subgoals and a motion generator to plan and execute the motion needed to reach these subgoals. Our method is benchmarked on a diverse set of seven robotics tasks in photo-realistic simulation environments. ReLMoGen shows outstanding transferability between different motion generators at test time, indicating a great potential to transfer to real robots.
  arXiv  Detail & Related papers  (2020-08-18T08:05:15Z)

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.