# Centralized Task Allocation and Alignment Based on Constraint Table and Alignment Rules
## 2 Preliminaries
### Consensus-Based Bundle Algorithm (Cbba)  
CBBA is a multi-agent task allocation algorithm based on auction concept. CBBA is organized into two phases, bundle construction phase and consensus phase. In bundle construction phase, each agent makes its own ordered sequence of tasks and bundle by calculating the rewards of each task. The rewards are obtained by arriving or completing tasks so the sequence of tasks for each agent is changed according to reward function to obtain maximum global reward. Algorithm of the bundle construction phase is as below [12; 17]:  
In lines 1-4 of Algorithm 1, vectors about agent \(i\) for bundle construction are initialized to previous iteration results, where \(t\) is number of iteration, \(\mathbf{y}_{i}\) is winning bids list that the agent \(i\) knows, \(\mathbf{z}_{i}\) is winning agent list that the agent \(i\) knows, \(\mathbf{b}_{i}\) is bundle of the agent \(i\), and \(\mathbf{p}_{i}\) is sequence of tasks for agent \(i\). Then, the bundle and the sequence of tasks are constructed until the size of the bundle is same with \(L_{t}\) in lines 5-14 of Algorithm 1. In line 6 of Algorithm 1, it founds agent \(i\)'s maximum reward when a task is added to a previous sequence of tasks of agent \(i\), where \(S_{i}^{p_{i}}\) is reward of agent \(i\) along \(\mathbf{p}_{i}\) and \(\mathbf{p}_{i}(+)_{n}\{j\}\) means that task \(j\) is added after \(n\)th component of \(\mathbf{p}_{i}\). The rewards are then multiplied to the flag whether the reward is higher than winning bid or not. Finally, the task and the sequence that maximize the agent \(i\)'s reward are found in lines 8-9 of Algorithm 1 and the task is added to iteration results in lines 10-13 of Algorithm 1.  
```
1:\(\mathbf{y}_{i}(t)=\mathbf{y}_{i}(t-1)\)
2:\(\mathbf{z}_{i}(t)=\mathbf{z}_{i}(t-1)\)
3:\(\mathbf{b}_{i}(t)=\mathbf{b}_{i}(t-1)\)
4:\(\mathbf{p}_{i}(t)=\mathbf{p}_{i}(t-1)\)
5:while\(|\mathbf{b}_{i}|<L_{t}\),do
6:\(c_{ij}=max_{x\in[\mathbf{p}_{i}]}S_{i}^{p_{i}(+)_{n}\{j\}}-S_{i}^{p_{i}},\ \forall j\in J\backslash b_{i}\)
7:\(h_{ij}=II\big{(}c_{ij}>y_{ij}\big{)},\ \forall j\in J\)
8:\(J_{i}=argmax_{i}c_{ij}h_{ij}\)
9:\(n_{i,J_{i}}=argmax_{n}\ S_{i}^{p_{i}(+)_{n}\{J_{i}\}}\)
10:\(\mathbf{b}_{i}=\mathbf{b}_{i}(+)_{end}\{J\}_{i}\)
11:\(\mathbf{p}_{i}=\mathbf{p}_{i}(+)_{n_{i}J_{i}}\{J\}_{i}\)
12:\(y_{i,J_{i}}(t)=c_{i,J_{i}}\)
13:\(z_{i,J_{i}J_{i}}(t)=i\)
14:endwhile
```  
**Algorithm 1** CBBA Phase 1: Bundle construction  
In the consensus phase, agents confirm tasks to perform based on the bundles made in the bundle construction phase. In the decentralized system, the agents have to communicate data with each other for deciding the winning agent. However, in a centralized system, the agents send data only to the central computer. In the central computer, the data from the agents are collected and the consensus algorithm is processed with the data. The general centralized consensus algorithm is Sequential Greedy Algorithm (SGA) as shown in Algorithm 2[12]. In lines 1-3 of Algorithm 2, variables for SGA are initialized, where \(I\) and \(J\) are groups of agents and tasks, respectively, \(\eta_{i}\) is number of confirmed tasks for agent \(i\), and \(c_{ij}\Big{[}\mathbf{b}_{i}^{(n)}\Big{]}\) is a reward that is obtained by finishing task \(j\) by agent \(i\) based on the bundle of agent \(i\), \(\mathbf{b}_{i}^{(n)}\). Superscript means the number of iterations. In lines 4-18 of Algorithm 2, agent \(i_{n}^{*}\) and task \(j_{n}^{*}\), which are row and column of maximum value of \(c^{n}\), respectively, are found, and the agent \(i_{n}^{*}\) is confirmed to do the task \(j_{n}^{*}\). For the next iteration, the task \(j_{n}^{*}\) is excluded from the group of tasks \(J\) because of the assumption 'one task is allocated to only one agent' in Equation (2). If the number of confirmed tasks \(\eta_{i_{n}^{*}}\) for the agent \(i_{n}^{*}\) is equal