# Centralized Task Allocation and Alignment Based on Constraint Table and Alignment Rules
## 1 Introduction  
Automation techniques of systems are among some highly interesting research themes currently. According to this trend, concepts of swarming with a lot of the Unmanned Vehicles (UxVs) or teaming with manned and unmanned vehicles occur to overcome hard tasks with manned or single vehicle using the UxVs. To coordinate several tasks with the UxVs as described above, the sequence of tasks for each UxV has to be issued to them based on their situations and capabilities. In addition, the purpose of task allocation, for example minimizing total mission time, minimizing fuel consumption, etc., and spatial or temporal constraints have to be considered for successful task allocation and alignment. Hence, management techniques for multi-agent systems have been widely studied with various approaches and algorithms [1; 2; 3; 4; 5; 6; 7; 8; 9; 10; 11]. One of them is developed to recommend tasks to MOD drivers by analyzing and modeling the Mobility-on-Demand Vehicular Crowdsensing (MOD-CS) and MOD-Human-Crowdsensing (MOMAN-CS) market [10]. It is for manned vehicles, so they have freedom to refuse the recommendation. Another is developed for an urban delivery drone system considering energy consumption [11]. Previous research supposed that the energy consumption of robots, especially drones, is proportional to their moving distance but it did not match for delivery drone. Therefore, the weight of the drone including the consignment is also considered when calculating energy consumption. One of the general task allocation algorithms is Consensus-Based Bundle Algorithm (CBBA), which is based on the auction process [12]. Several agents calculate the taskrewards or costs which differ by the purpose, and the task is allocated to the agent that has the highest reward in CBBA. To calculate task rewards, the time-discounted reward scheme, one of the general scoring themes in score-based task allocation algorithm, is used in CBBA. This scheme calculates scores as decreasing time-invariant maximum rewards as time passes. This algorithm is fast to obtain the local optimum solution but CBBA cannot consider the constraints as depicted above. Therefore, Coupled-constraint CBBA (CCBBA), further improved CBBA, is developed [13; 14]. In CCBBA, some spatial and temporal constraints can be considered in the task allocation and alignment. Each agent decides the bidding strategy for each task before bidding. According to the decided strategy, task rewards for each agent are calculated for task allocation. For task alignment, 'number of iterations in constraint violation', and some counts are considered. In the optimistic strategy, if the agent violates some constraints when performing a task, the number of iterations in constraint violation increases but the task can be aligned to the agent if it is lower than some thresholds. CCBBA has the ability to handle most multi-agent management problems, but there is a problem concerning the convergence of solution in certain scenarios. Additionally, there is a minor problem in setting temporal constraints; the user must set the maximum permitted time for each task unless they cannot predict it exactly. CBBA and CCBBA are fast task allocation and alignment algorithms, but computational cost rapidly increases as the number of agents and tasks increases. The reason in CBBA is in the bundle construction phase. When creating a bundle for each agent, the score is calculated not only after the last task of the agent but also before and after all allocated tasks of the agent. For example, an agent has been allocated tasks 1 and 2, and there is an unallocated task 3. Then, scores about sequence of tasks (3-1-2), (1-3-2), and (1-2-3) are calculated to allocate the task 3. Note that task allocation and alignment with coupled constraints are NP-hard problems, and the solution of CBBA is just the local optimum solution. It is a time-consuming process to obtain this kind of solution. The reason in CCBBA is the process about whether an agent can bid to tasks or not.