Centralized Task Allocation and Alignment Based on Constraint Table and Alignment Rules

Abstract

In this paper, we propose a centralized task allocation and an alignment technique based on constraint table and alignment rules. For task allocation, a scoring scheme has to be set. The existing time-discounted scoring scheme has two problems; if the score is calculated based on arrival time, the agent who arrives in a task point first may finish the task late, and if the score is calculated based on end-time of the task, agents who have the same score may appear because of temporal constraints. Therefore, a modified time-discounted reward scheme based on both arrival and end-time is proposed. Additionally, an accumulated distance cost scheme is proposed for minimum fuel consumption. The constraint table made by tasks that are already aligned is also considered in scoring. For centralized task alignment based on the constraint table and alignment rules, a technique based on sequential greedy algorithm is proposed. Resolving conflicts on alignment is described in detail using constraint table and alignment rules, which are composed of four basic principles. We demonstrate simulations about task allocation and alignment for multi-agent with coupled constraints. Simple and complicated cases are used to verify the scoring schemes and the proposed techniques. Additionally, a huge case is used to show computational efficiency. The results are feasibly good when the constraints are properly set.

Keywords

• task allocation
• task alignment
• mission planning
• task planning
• multi-agent systems
• multi-agent planning and scheduling