# Centralized Task Allocation and Alignment Based on Constraint Table and Alignment Rules
## 5 Algorithm
\begin{table}
\begin{tabular}{c c c} \hline
**No.** & **Contents** & **Cannot Be Allocated** \\ \hline
1 & Bidding flags, & (1.1) 0 \\
2 & Condition of task \(p\) & (2.1) After arriving point of task \(p\) \\
3 & Local MUTEX & (3.1) Task \(q\) is allocated to agent A \\  & with task \(q\) & (4.1) Task \(q\) is allocated already \\
4 &
\begin{tabular}{c} With task \(q\) \\ \end{tabular} \\
5 & Simultaneous with task \(q\) & (5.1) Task \(q\) is allocated to agent A \\
6 & After task \(q\) & (6.1) Task \(q\) is not allocated yet \\  & & (7.1) Task \(q\) is not allocated yet or \\  & & (7.2) Task \(q\) is allocated to agent A or \\
7 & Start during task \(q\) & (7.3) Task \(q\) has relationship (except ‘After’) with \\  & & task \(r\), task \(r\) is allocated to agent A and agent A \\  & & cannot arrive point of task \(p\) after finishing task \(r\) \\  & & (8.1) Task \(q\) is not allocated yet or \\  & & (8.2) Task \(q\) is allocated to agent A or \\
8 & End during task \(q\) & (8.3) Task \(q\) has relationship (except ‘After’) with \\  & task \(r\), task \(r\) is allocated to agent A and agent A \\  & & cannot finish task \(p\) after finishing task \(r\) \\  & & (9.1 *) Some tasks in \(q\), called \(q_{sub}\), are allocated \\
9 & Task \(r\) starts simultaneous with tasks \(q\) & and agent A cannot arrive point of task \(r\) after \\  & & finishing task \(p\) \\  & & (10.1 *) Only task \(q\) is allocated and agent A \\
10 & Task \(r\) starts during task \(q\) & cannot start task \(r\) after finishing task \(p\) before \\  & end-time of task \(q\) *** & \\  & & (11.1 *) Only task \(q\) is allocated and agent A \\
11 & Task \(r\) ends during task \(q\) & cannot end task \(r\) after finishing task \(p\) before \\  & & end-time of task \(q\) \\ \hline \end{tabular}  
* There is no task \(p\) in tasks \((q-q_{sub})\). ** The task \(p\) is not equal to task \(r\). *** If the \(T_{min,dur}\) is not 0, the ‘end-time of task \(q^{\prime}\) is changed to ‘(end-time of task \(q\))\(-\)\(T_{min,dur}\)’.  
\end{table} 
Table 11: Conditions for prohibition of allocating task \(p\) to agent A in TACTAR. If 11 conditions in Table 11 are all passed, start-time and end-time of each task are checked by the constraints table. If temporal violation can be solved by delaying these times, time correction proceeds. If not, these times are not corrected and reward(cost) calculation is processed. It is for time correction of already aligned tasks. Note that this procedure is not equal to bundle construction in Algorithm 1 or 3. In bundle construction, the sequence of whole tasks of each agent is made by calculating rewards(costs). However, in line 1 of Algorithm 7, reward(cost) of each task is calculated just for the next step. For example, there is an agent that is assigned task 1 and 2 and there are three remaining tasks. Then the rewards(costs), calculated in line 1 of Algorithm 7, are three rewards(costs) of remaining tasks for three sequences, (1-2-3), (1-2-4), and (1-2-5). The cost based on accumulated distance cost scheme is calculated as described in lines 6-7 of Algorithm 3. The lines 2-22 in Algorithm 7 are repeated until all tasks are allocated. It will find (agent, task) set that has maximum reward(minimum cost) in line 14 of Algorithm 7. The alignment of this set is tried in line 15 of Algorithm 7 as described in Algorithm 8. In line 1 of Algorithm 8, constraints associated with the task in line 14 of Algorithm 7 are found in the constraint table. The lines 4-8 and lines 10-14 of Algorithm 8 are violation checked for start-time and end-time of the task, respectively. Note that only violations for 'before' and'simultaneous' in Table 6 are checked because start-time and end-time are delayed based on the constraint table in line 1 of Algorithm 7 if they violate 'after' in Table 6. In lines 5 and 11 of Algorithm 8, aligned tasks correction proceeds. First, a task which made violated constraints afterwards are removed from tasks of the agent who made violated constraint.