Consensus-Based Decentralized Task Allocation for Multi-Agent Systems and Simultaneous Multi-Agent Tasks

This letter proposes a novel consensus-based timetable algorithm (CBTA) to solve the decentralized simultaneous multi-agent task allocation problem. Due to the limited capability of each agent, multiple agents may be required to perform a task simultaneously. A key challenge is how to meet the requirements and minimize the average start time of all tasks. The proposed CBTA aims to minimize the start time of each task to minimize the average start time of all tasks indirectly, it iterates between a timetable construction phase and a consensus phase. New tasks are included in the timetable of each agent by comparing the estimated start time of tasks placed by its own and other agents during the timetable construction phase. Then in the consensus phase, agents share their timetables with a communication network, and conflicts among their timetables are eliminated according to a consensus rule. Extensive simulation results show that the average start time of tasks of the proposed CBTA is nearly the same as the consensus-based bundle algorithm (CBBA) when performing single-agent tasks, and it is much less than the consensus-based grouping algorithm (CBGA) when performing multi-agent tasks with various communication network topologies.