## 2 Problem Description
### Optimization Constraints
#### 2.3.2 Kinematic Constraint  
Due to the use of a robot in a controlled environment, kinematic constraints are generated. The constraints are affected by the configuration of the robot, predefined tasks, and the locations where the tasks are performed. Those components are not changed unless the configuration of robot or environment is not changed. Therefore, once the constraints are calculated before solving the problem, it does not need to be calculated while solving the optimization problem.  
To minimize makespan, it is important that both robotic arms are performing tasks concurrently as much as possible. Using kinematic information, it is possible to calculate whether robotic arms can perform two specific tasks simultaneously, and it can be represented as a hashtable-like matrix called a Relation Matrix.  
**Definition 2**.: _A Relation Matrix \(M_{R}\) is a binary matrix where the rows represent one arm's capability to execute tasks and the columns represent the other arm's capability to execute tasks. If there exists a nonzero element in \(M_{R}(i,j)\), then one arm can perform \(\mathcal{T}_{i}\) while the other arm can also conduct \(\mathcal{T}_{j}\). If there are \(n\) tasks in \(\mathbb{T}\), the size of \(M_{R}\) is \(n\times n\) in the case where two robotic arms are used. When the number of robots is \(m\), \(M_{R}\) has a dimension of \(n\times n\times m_{C}2\)._  
An example of the case with three machines (robotic arm) describing the Relation Matrix is shown in Figure 1. A simple _taskset_\(\mathbb{T}\) is defined in Figure 1d, and examples of obtaining the components of \(M_{R}\) are presented in (a)-(c). In this example, \(M_{R}\) has (3 \(\times\) 3 \(\times_{3}C_{2}\)) dimension, because the number of tasks are 3, and robots are 3. To check whether the robot \(i\) and robot \(j\) can perform specific tasks simultaneously, we define \(\textsc{CheckPossible}(\mathcal{T}_{i},\mathcal{T}_{j})\), and it returns the value 1 when possible and 0 when not. \(\mathcal{T}_{i}\), \(\mathcal{T}_{j}\) is the task conducted by robot \(i\) and \(j\), respectively. The function \(\textsc{CheckPossible}(\mathcal{T}_{i},\mathcal{T}_{j})\) checks two components: reachability and collision between two robots. Reachability can be calculated by discretizing the Cartesian space into smaller cubes and by verifying if all points on a surface of a sphere inside the cube can be reached [46]. However, in our environment, cooking materials, appliances, and tools are placed at specific locations, so it does not need to consider the entire Cartesian space. Figure 1b shows the case where the right arm cannot perform \(\mathcal{T}_{3}\) because it cannot reach the location. In this case, the value of \(\textsc{CheckPossible}(\mathcal{T}_{2},\mathcal{T}_{3})\) becomes 0 and so does \(M_{R}(2,3,1)\).  
The second thing checked by \(\textsc{CheckPossible}(\mathcal{T}_{i},\mathcal{T}_{j})\) is the collision between two arms, which is affected by kinematic constraints such as the configuration of the robot. Finding out the collisions between manipulator is one of the research fields in robotics, but it is not the main scope of our work. In more detail, the state-of-the-art method [47] can be applied. Figure 1c shows the case in which the two arms collide with each other. In this case, the value of \(M_{R}(2,1,1)\) become 0 because \(\textsc{CheckPossible}(\mathcal{T}_{2},\mathcal{T}_{1})\) is 0. Figure 1a shows that this case is possible, so the value \(M_{R}(1,2,1)\) is 1. \(M_{R}(i,k,2)\), \(M_{R}(j,k,3)\) also can be obtained using the method above. Following the method described above, \(M_{R}\) can be found before the start of the optimization process. In the next section, the method describing how to apply the information from \(M_{R}\) to the optimization problem will be presented.