# Automatic Optimal Robotic Base Placement for Collaborative Industrial Robotic Car Painting
## 4 Construction of the First Cost Function: Minimizing the Possibility of Collision  
In this section, we construct a cost function that quantifies the notion of collision possibility in the context of multi-robot car painting, which is based on computing the overlap area between planar ellipses. Figure 4: Algorithm 1 generates a 3D point cloud and a minimum volume enclosing ellipsoid (MVEE) for each of the robotic arms. To provide the intuition behind our proposed cost function in this section, let us consider the multi-robot arrangements depicted in Figure 5. The ellipses are the MVEEs that closely fit the reachable workspace of the forearms of the robotic arms. As it can be seen from these arrangement, larger volumes of intersection in-between the ellipsoids amount to a higher possibility of collision in-between the robots while they are painting the vehicle. Additionally, larger volumes of intersection in-between the 3D ellipsoids correspond to larger areas of intersection in-between their projections on the factory floor. Remarkably, the projection of these 3D ellipses on the factory floor results in planar ellipses. Hence, the overlap areas of planar ellipses can quantify the possibility of collision in-between the arms during painting (see Figure 6). Additionally, there are very efficient computational algorithms in the literature for computing the overlap area between ellipses as elaborated in what follows. To formalize this intuition, we first consider each of the ellipsoids \(\text{MVEE}(\mathcal{P}_{i}(\mathbf{0}))\), \(1\leq i\leq M\), which are generated by the pre-processing stage summarized in Algorithm 1. According to Remark 3, each computed ellipsoid \(\text{MVEE}(\mathcal{P}_{i}(\mathbf{0}))\) is obtained based on the assumption that its corresponding robot base position is located at the origin. Considering the variable unknown base position vector \(\mathbf{p}_{i}\) given by (1), it is possible to translate the ellipsoid using this vector. In particular, the ellipsoid associated with the \(i\)th arm with base position \(\mathbf{p}_{i}\), \(1\leq i\leq M\), is given by  
Figure 5: Intuition behind the first cost function formulation. The ellipsoids in the plots are the MVEEs that closely fit the reachable workspace of the robot forearms. The larger the volumes of intersection in-between the ellipsoids, the higher the possibility of robot collision during painting. Larger intersection volumes between the 3D ellipsoids, in turn, correspond to larger overlap areas of their projections on the factory floor. Figure 6: The planar ellipse overlap areas are employed to define the first cost function, which quantifies the possibility of collision in-between the robotic arms during painting. \[\text{MVEE}(\mathcal{P}_{i}(\mathbf{p}_{i}))=\Bigg{\{}(x,\,y,\,z)\Bigg{|}\frac{(x-c _{x,i}-p_{x,i})^{2}}{r_{x,i}^{2}}+\frac{\big{(}y-c_{y,i}-p_{y,i}\big{)}^{2}}{r_{y,i}^{2}}+\frac{(z-c_{z,i})^{2}}{r_{z,i}^{2}}=1\Bigg{\}}. \tag{10}\]  
We project the translated ellipsoids given by (10) onto the floor/ceiling to obtain planar ellipses, which are parameterized by the Cartesian coordinates of the robot base positions. Specifically, we project the ellipsoid \(\text{MVEE}(\mathcal{P}_{i}(\mathbf{p}_{i}))\), \(1\leq i\leq M\), given by (10) to obtain the planar ellipse  
\[\mathcal{E}(\mathcal{P}_{i}(\mathbf{p}_{i})):=\Bigg{\{}(x,\,y)\Bigg{|}\frac{( x-c_{x,i}-p_{x,i})^{2}}{r_{x,i}^{2}}+\frac{\big{(}y-c_{y,i}-p_{y,i}\big{)}^{2}}{r_{y,i}^{2}}=1-\frac{c_{z,i}^{2}}{r_{z,i}^{2}}\Bigg{\}}. \tag{11}\]  
Having obtained the planar ellipses, we denote the overlap area between the \(i\)th ellipse \(\mathcal{E}(\mathcal{P}_{i}(\mathbf{p}_{i}))\) and the \(j\)th ellipse \(\mathcal{E}\left(\mathcal{P}_{j}\Big{(}\mathbf{p}_{j}\Big{)}\right)\), where \(1\leq i<j\leq M\), by \(\mathcal{A}_{i,j}\Big{(}\mathbf{p}_{i},\mathbf{p}_{j}\Big{)}\).