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

arXiv: https://arxiv.org/abs/2209.02865 · HTML: https://mlsanity.com/paper/2209.02865/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 49 references that are in the map.
- First posted on arXiv 7 Sep 2022.

## Builds on (most cited first, 12 of 12)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Neural Policy Gradient Methods: Global Optimality and Rates of Convergence](https://mlsanity.com/paper/1909.01150/) (2019)
- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks](https://mlsanity.com/paper/1705.10868/) (2017)
- [Integrated Task Assignment and Path Planning for Capacitated Multi-Agent Pickup and Delivery](https://mlsanity.com/paper/2110.14891/) (2021)
- [Multi-agent Motion Planning for Dense and Dynamic Environments via Deep Reinforcement Learning](https://mlsanity.com/paper/2001.06627/) (2020)
- [Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints](https://mlsanity.com/paper/2005.13109/) (2020)
- [Decentralized Task and Path Planning for Multi-Robot Systems](https://mlsanity.com/paper/2011.10034/) (2020)
- [DeepMNavigate: Deep Reinforced Multi-Robot Navigation Unifying Local & Global Collision Avoidance](https://mlsanity.com/paper/1910.09441/) (2019)
- [Decentralized Task Allocation in Multi-Robot Systems via Bipartite Graph Matching Augmented with Fuzzy Clustering](https://mlsanity.com/paper/1807.07957/) (2018)
- [V-RVO: Decentralized Multi-Agent Collision Avoidance using Voronoi Diagrams and Reciprocal Velocity Obstacles](https://mlsanity.com/paper/2102.13281/) (2021)

## Built on by (most cited first, 7 of 7)

- [PIMbot: Policy and Incentive Manipulation for Multi-Robot Reinforcement Learning in Social Dilemmas](https://mlsanity.com/paper/2307.15944/) (2023)
- [Robustness to Multi-Modal Environment Uncertainty in MARL using Curriculum Learning](https://mlsanity.com/paper/2310.08746/) (2023)
- [Together We Rise: Optimizing Real-Time Multi-Robot Task Allocation using Coordinated Heterogeneous Plays](https://mlsanity.com/paper/2502.16079/) (2025)
- [PIMbot: A Self-Adaptive Attack Framework for Adversarial Manipulation of Multi-Robot Reinforcement Learning](https://mlsanity.com/paper/2605.23027/) (2026)
- [Real-World Depth Recovery via Structure Uncertainty Modeling and Inaccurate GT Depth Fitting](https://mlsanity.com/paper/2504.11820/) (2025)
- [Enhancing Lifelong Multi-Agent Path-finding by Using Artificial Potential Fields](https://mlsanity.com/paper/2505.22753/) (2025)
- [Coordination Matters: Evaluation of Cooperative Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2605.06557/) (2026)

## Abstract (arXiv)

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.