# Centralized Task Allocation and Alignment Based on Constraint Table and Alignment Rules
## 4 Scheduling Scheme  
After task allocation, task alignment should be processed to meet temporal constraints. Assume that every agent has a speed limit and moves to target task points as soon as possible. Additionally, the duration time of each task is not changed by scheduling, such as shrinking or stretching; it is changed only by agents. Then, four basic rules can be made as in Table 5. If the task B is aligned, temporal constraints about the task B are generated. These constraints have to be considered for the next alignment of tasks, the task A in Table 5. If the task B is dropped by rules in Table 5, these constraints cannot be considered any more. Therefore, a constraint table is used in centralized TACTAR to manage generated constraints by aligned tasks. This table has number-of-constraints rows and six columns that contain that shown in Table 6.  
For example, task 2 must start after task 1 ends and task 2 is aligned to agent 3. Then, a row of the constraint table is created. Column 1 of row 1 would be 1 which means task 1. Columns 2 and 3 would be 3 and 2 which mean agent 3 and task 2, respectively. Note that columns 2 and 3 are needed for deleting constraints when tasks are dropped. Column 4 would be 1 which means end-time of task 1. Columns 5 and 6 would be start-time of tasks 2 and 0, respectively. The zero in column 6 means that task 1 should end before the time in column 5. If temporal constraints on task 2 are more than one, other rows of the constraint table will be made. Following the rules in Table 5, one of the temporal constraints 'Not During' in Table 2 cannot be applied because it cannot decide which rule should be applied when violating the constraint. For example, if task A must either end before task B starts or start after task B ends but task A starts after task B starts and task A ends before task B ends, it corresponds to rule 2 and 4. In this situation, task A cannot be aligned without changing the duration time of task A. Additionally, the temporal constraint 'Between' in Table 2 can be separated to 'Before' and 'After', so 'Between' is no longer needed in temporal constraints. The temporal constraint 'Before' can be replaced to 'After'. For example, 'Task A must end before task B starts' can be 'Task B must start after task A ends'. The spatial constraint 'Mutual exclusive' in Table 1 means that only either task A or B can be allocated to all agents at each time. For example, if task A is allocated to agent 1, task B cannot be allocated to all agents. However, it needs to allocate task B to agents \begin{table}
\begin{tabular}{c l} \hline \hline
**Column** & **Description** \\ \hline
1 & Target task ID \\
2 & Allocated agent of task that makes constraint \\
3 & ID of task that makes constraint \\
4 & Target time(0: start-time, 1: end-time) \\
5 & Constraint time \\
6 & Constraint type(0: before, 1: after, 2: simultaneous) \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Contents of constraint table. \begin{table}
\begin{tabular}{c l} \hline \hline
**No.** & **Description \({}^{*}\)** \\ \hline
1 & If task A should start at or after \(t\) and start-time of task A is before \(t\), \\  & start-time of task A is set to \(t\) and recalculate rewards/costs of candidate tasks. \\
2 & If task A should start at or before \(t\) and start-time of task A is after \(t\), \\  & task B and tasks aligned after task B are dropped and re-alignment proceeds. \\
3 & If task A should end at or after \(t\) and end-time of task A is before \(t\), \\  & end-time of task A is set to t and recalculate rewards/costs of candidate tasks. \\
4 & If task A should end at or before \(t\) and end-time of task A is after \(t\), \\  & task B and tasks aligned after task B are dropped and re-alignment proceeds. \\ \hline \hline \end{tabular} \({}^{*}\)Task A is a candidate task of alignment and task B is an aligned task already. Additionally, temporal constraint at time \(t\) is made by task B.  
\end{table} 
Table 5: Basic rules for scheduling. except agent 1.