# Finding Optimal Manipulator Arm Shapes to Avoid Collisions in a Static Environment
## 4 Optimization Algorithms
### Method 1--Iterative Algorithm with Collision Analysis
#### 4.1.2 Collision Events  
In addition to the collision type, the algorithm also analyzes the required direction of the bend \"out of the collision zone.\" To achieve this, collisions of the spheres of the upper and lower arms are stored as collision events. A collision event is a continuous intersection of a particular sphere and a particular workspace box. During each event, the direction vector \(\vec{p}(t_{i})\) from the center of the box (node) \(B\) to the center of the sphere \(C(t_{i})\) is recorded in each time step \(t_{i}\) (see Figure 7) as  
\[\vec{p}(t_{i})=C(t_{i})-B. \tag{26}\]  
Afterward, the vectors \(\vec{p}(t_{i})\) are averaged throughout the event, which gives an imaginary spring force that will later be used to bend the arm:  
\[\vec{p}_{\text{avg}}=\frac{1}{n}\sum_{i=0}^{n}\vec{p}(t_{i}), \tag{27}\]  
where \(t_{0}\) denotes the start of the particular collision event (not the start of the simulation) and \(n\) represents the length of the collision event measured in time steps of the simulation. If the intersection ends and starts again later during the trajectory, a new event is created. Figure 8 shows the result of a simple testing trajectory verification. Green points of the trajectory represent sections that the robot was able to reach with no collisions and yellow points mean that a collision occurred. The arm bounding spheres rendered yellow mean that there exists at least one collision event for the sphere. A red arrow is drawn for each collision event of a sphere; it represents the vector \(\vec{p}_{\text{avg}}\) or the imaginary force pushing the sphere out of the collision. Multiple arrows originating from the same sphere mean that the sphere had several collision events during the trajectory. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline
**Possibly Fixable by** & **C1** & **C2** & **C3** & **C4** & **C5** \\ \hline Modify trajectory & no & yes & yes & yes & yes \\ Change robot position & yes & yes & yes & yes & no \\ Modify arms lengths & no & yes * & yes * & yes * & no \\ Modify arms shapes & no & yes * & no & yes * & no \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Overview of five categories of collisions with possible ways of removing them; only cases marked by an asterisk (*) are considered in this research. The collision data, including the collision events, are used as input for the robot adaptation algorithm. The algorithm starts by finding the smallest possible arm lengths that can reach all points of the trajectory without taking collisions into account. This can easily be done by finding the largest value of \(p\) from (14) and then choosing  
\[a_{2}=k\cdot p, \tag{28}\] \[d_{4}=p-a_{2}, \tag{29}\]  
where \(k\in(0;1)\) is a coefficient describing the constant ratio between \(a_{2}\) and \(d_{4}\) (typically \(k\geq 0.5\) for \(a_{2}\geq d_{4}\)). Note that for simplicity, the lengths of the lower and upper arms are tied together; however, their bending is individual. The whole algorithm can be described by the following sequence of operations:  
1. Start with straight arms of the smallest theoretically possible length. 2. Run the simulation for every point of the trajectory. 3. If no collision occurred \(\Rightarrow\) solution found, end. 4. If at least one C1 or C5 collision occurred \(\Rightarrow\) impossible to solve, end. 5. If at least one C3 collision occurred \(\Rightarrow\) remove any existing arm bending, make the lower and upper arms longer by a chosen value, and go to step 8. Figure 8: Simple result of a simulation showing colliding bounding spheres with collision events (red arrows). Figure 7: Example of a collision event of one arm bounding sphere and one workplace bounding box; the sphere is drawn in five simulation time steps: \(t_{-1},\ t_{0},\ \dots,\ t_{3}\). The event begins at \(t_{0}\). If some C2 or C4 collisions exist \(\Rightarrow\) use the force vectors \(\vec{p}_{\text{avg}}\) calculated from collision events to bend the arm by a chosen amount (the bending is added to any already existing bending).