Task Allocation for Autonomous Machines using Computational Intelligence and Deep Reinforcement Learning

Thanh Thi Nguyen, Quoc Viet Hung Nguyen, Jonathan Kua, Imran Razzak, Dung Nguyen, Saeid NahavandiarXiv 2025 · DOI · arXiv

Introduction

Task Allocation (TA) is a fundamental challenge in multi-agent autonomous systems, essentially answering the "who does what" question. In a fleet of agents—such as drones or industrial robots—the objective is to assign a set of tasks to agents while minimizing total costs, which may include time, energy consumption, or operational risk.

While conceptually straightforward, TA is a combinatorial optimization problem that is NP-hard. As the number of agents and tasks increases, the computational complexity grows exponentially. Traditional mathematical models often excel in static, predictable environments but struggle with the dynamic uncertainties of real-world missions, such as emerging tasks, communication latencies, and sensor noise. This survey explores the evolution of TA strategies from classical optimization to modern Deep Reinforcement Learning (RL).

Methodological Framework

The survey categorizes TA methodologies into three primary domains: classical heuristics, decentralized auction-based methods, and deep reinforcement learning.

Taxonomy of Task Allocation (TA) methodologies categorized by the survey.

1. Classical and Heuristic Methods

  • Linear and Integer Programming: These methods provide mathematically optimal solutions but are computationally intensive and typically require a centralized controller, creating a single point of failure.
  • Evolutionary Algorithms: Techniques such as Genetic Algorithms (GA) and Particle Swarm Optimization (PSO) mimic biological processes to find near-optimal solutions rapidly, offering better scalability than exact methods.

2. Decentralized Auction-Based Methods

The Consensus-Based Bundle Algorithm (CBBA) represents the current standard for decentralized allocation. It utilizes an auction mechanism where agents bid on task "bundles" and a consensus protocol to resolve conflicts through local communication with neighbors.

3. Deep Reinforcement Learning (RL)

Cutting-edge research focuses on end-to-end learning where agents develop policies through trial and error. Architectures such as Deep Q-Learning, Proximal Policy Optimization (PPO), and Twin Delayed DDPG are employed to handle continuous action spaces. Notably, the integration of Graph Convolutional Networks (GCNs) allows agents to better model the interdependencies between tasks and heterogeneous robot capabilities.

Summary of surveyed methods across different algorithmic categories.

Experimental Context and Benchmarking

As a survey, the paper reviews diverse experimental setups rather than introducing a new dataset. Common simulation environments include:

  • Gazebo Simulator: Often utilizing TurtleBot 3 models for 2D navigation and task execution benchmarks.
  • Custom Simulations: Bespoke environments for specialized applications like military mission planning, Mobile Edge Computing (MEC) offloading, and UAV-assisted communication networks.

The authors highlight a significant gap in the field: the lack of standardized, cross-methodology benchmarks (an "ImageNet for Task Allocation") to allow for direct comparison between disparate algorithmic approaches.

Analysis and Key Results

  • Optimality vs. Speed: While Integer Programming ensures 100% optimality, PSO and GA are significantly faster for large-scale problems. CBBA is noted for providing a guaranteed 50% optimality in specific multi-task scenarios while remaining conflict-free.
  • Deep RL Performance: In dynamic environments with moving obstacles, Deep RL-based methods (particularly PPO) have shown superior performance over traditional navigation-focused TA in terms of success rates and path efficiency.
  • The Communication Trade-off: Decentralized methods offer robustness but require significant communication bandwidth. In low-bandwidth scenarios, the time required to reach consensus can negate the efficiency gains of the optimized allocation.

Discussion and Future Directions

The field is shifting toward handling heterogeneity, where diverse agents (e.g., a drone and a robotic arm) must coordinate despite different skill sets. While Deep RL offers the promise of discovering non-obvious, efficient strategies directly from raw sensor data, it faces challenges regarding training time and the need for high-fidelity simulators.

Future research is expected to leverage the Internet of Things (IoT), allowing robots to consult environmental sensors (smart cameras, floor sensors) to enhance decision-making. Establishing comprehensive benchmarking environments remains a priority for the research community to objectively measure progress across classical and learning-based methods.

Summary updated

Abstract

Enabling multiple autonomous machines to perform reliably requires the development of efficient cooperative control algorithms. This paper presents a survey of algorithms that have been developed for controlling and coordinating autonomous machines in complex environments. We especially focus on task allocation methods using computational intelligence (CI) and deep reinforcement learning (RL). The advantages and disadvantages of the surveyed methods are analysed thoroughly. We also propose and discuss in detail various future research directions that shed light on how to improve existing algorithms or create new methods to enhance the employability and performance of autonomous machines in real-world applications. The findings indicate that CI and deep RL methods provide viable approaches to addressing complex task allocation problems in dynamic and uncertain environments. The recent development of deep RL has greatly contributed to the literature on controlling and coordinating autonomous machines, and it has become a growing trend in this area. It is envisaged that this paper will provide researchers and engineers with a comprehensive overview of progress in machine learning research related to autonomous machines. It also highlights underexplored areas, identifies emerging methodologies, and suggests new avenues for exploration in future research within this domain.
BibTeX
@misc{nguyen2025task,
  author = {Thanh Thi Nguyen and Quoc Viet Hung Nguyen and Jonathan Kua and Imran Razzak and Dung Nguyen and Saeid Nahavandi},
  title = {{Task Allocation for Autonomous Machines using Computational Intelligence and Deep Reinforcement Learning}},
  year = {2025},
  eprint = {2508.20688},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2508.20688},
}
Figure