Decentralized Task Assignment with Precedence Constraints Using Approximate Message Passing Algorithm
Open Access
- 5 January 2026
- journal article
- Published by Springer Nature in International Journal of Aeronautical and Space Sciences
- Vol. 27 (4) , 3674-3693
Abstract
This paper proposes a novel decentralized task assignment algorithm, called constrained task assignment and scheduling via approximate message passing (CTAS-AMP), for solving the constrained task assignment with scheduling (CTAS) problem, where tasks must be assigned to agents while respecting precedence constraints. Existing decentralized methods such as consensus-based bundle algorithm (CBBA) and its variants are limited in handling complex temporal dependencies. To address this, we model CTAS as a maximum a posteriori (MAP) estimation problem within a graphical model that includes agent, task, and constraint nodes. Using max-product belief propagation, we derive four types of messages and propose an iterative algorithm that computes, exchanges, and refines these messages under practical approximations. To satisfy constraints, the proposed method incorporates dedicated conflict resolution and refinement steps. Simulation results show that CTAS-AMP consistently generates feasible solutions that fully satisfy all precedence constraints, and demonstrates strong performance and robustness, particularly in scenarios with high variance in task rewards, compared to existing approaches such as coupled constrained CBBA.Keywords
Funding Information
- Defense Acquisition Program Administration (KRIT-CT-22-064-00)
- Gyeonggi-do Regional Research Center (GRRC KAU 2023-B01)
This publication has 30 references indexed in Scilit:
- Approximate message passing algorithm for decentralised task assignment and schedulingInternational Journal of Systems Science, 2025
- Decentralized message passing algorithm for heterogeneous multi-depot vehicle routing problemsOperations Research Perspectives, 2025
- A distributed task allocation approach for multi-UAV persistent monitoring in dynamic environmentsScientific Reports, 2025
- Multi-UAV cooperative system for search and rescue based on YOLOv5International Journal of Disaster Risk Reduction, 2022
- Optimal Task Assignment for UAV Swarm Operations in Hostile EnvironmentsInternational Journal of Aeronautical and Space Sciences, 2020
- Cooperative Task Assignment and Track Planning For Multi-UAV Attack Mobile TargetsJournal of Intelligent & Robotic Systems, 2020
- A Bid-Based Grouping Method for Communication-Efficient Decentralized Multi-UAV Task AllocationInternational Journal of Aeronautical and Space Sciences, 2019
- Constrained multi-objective optimization for multi-UAV planningJournal of Ambient Intelligence and Humanized Computing, 2018
- Low-cost Multi-UAV Technologies for Contour Mapping of Nuclear Radiation FieldJournal of Intelligent & Robotic Systems, 2012
- BAYESIAN INFERENCE1988