3.1. Definition of Voronoi Cell

Assuming that there are $N$ agents (robots, cars, drones, etc.) in a 2-dimensional plane, conventional Voronoi Cell [Reference Okabe, Boots, Sugihara and Chiu26] of the $i$ th agent can be defined as

(1) \begin{equation}\mathcal{V}_{i}=\left\{\textbf{p}\in \mathbb{R}^{2}|\left\| \textbf{p}-\textbf{p}_{i} \right\| \leq \left\| \textbf{p}-\textbf{p}_{j}\right\|,\forall j\neq i\right\},\end{equation}

which can be rewritten as

(2) \begin{equation}\mathcal{V}_{i}=\left\{\textbf{p}\in \mathbb{R}^{2}|\left(\textbf{p}-\frac{\textbf{p}_{i}+\textbf{p}_{j}}{2}\right)^{\textrm{T}}(\textbf{p}_{j}-\textbf{p}_{i})\leq 0,\forall j\neq i\right\}.\end{equation}

Where $\mathcal{V}_{i}$ denotes the Voronoi Cell of the ith agent, $\textbf{p}$ denotes the position of an agent, $\mathbb{R}^{2}$ denotes the 2-dimensional Euclidean space, $\textbf{p}_{i}$ and $\textbf{p}_{j}$ denote the position of the $i$ th and $j$ th agent, respectively. $\parallel \cdot \parallel$ denotes the Euclidean distance and $i,j\in \{1,2,\cdots,N\}$ .

Geometrically, Voronoi Cells (also known as Voronoi diagram) can be visualized as in Fig. 6(a), where each agent is plotted as a point, and the borderlines between Voronoi Cells are exactly the perpendicular bisectors between each pair of points. Note that all perpendicular bisectors are trimmed properly so that there are no crossed lines.

Figure 6. Illustration of Voronoi Cell and Buffered Voronoi Cell (BVC). (a) Voronoi Cell. (b) Buffered Voronoi Cell.

3.2. Definition of BVC

Based on the definition of Voronoi Cell, BVC [Reference Zhou, Wang, Bandyopadhyay and Schwager18] additionally introduces the concept of safety distance $d$ that satisfies

(3) \begin{equation}\left\| \textbf{p}_{i}-\textbf{p}_{j}\right\| \geq 2d,\forall i,j\in \{1,2,\cdots,N\},i\neq j.\end{equation}

BVC also can be simply illustrated as in Fig. 6(b), where blue lines parallel to each borderline in gray are added in comparison with Fig. 6(a), with their distance ( $d$ ) to the corresponding borderlines being all identical. The area surrounded by blue lines is called “buffer,” where all agents are not allowed to enter.

Regarding the implementation of collision avoidance, buffer in BVC is significant because while in Voronoi Cell “cores” have no size, but in reality each agent has its actual size, and there exists a certain “safety distance” between each two agent to avoid collision. Apparently, the value of $d$ can be set freely according to the size of each agent as well as other factors that may cause collision. As a result, the BVC of the $i$ th agent can thus be defined as

(4) \begin{equation}\overline{\mathcal{V}}_{i}=\left\{\textbf{p}\in \mathbb{R}^{2}\left|\left(\textbf{p}-\frac{\textbf{p}_{i}+\textbf{p}_{j}}{2}\right)^{\textrm{T}}\right.(\textbf{p}_{j}-\textbf{p}_{i})+d\left\| \textbf{p}_{j}-\textbf{p}_{i}\right\| \leq 0,\forall j\neq i\right\},\end{equation}

which is also the expansion of Eq. (2). From the definition of buffer and BVC as well as its property shown in Eq. (3), it is not difficult to find that BVC always keeps the distance between each pair of cell core longer than 2 $d$ .

3.3. Collision avoidance by BVC

This part explains how BVC works in trajectory planning to avoid collision. BVC itself is no more than an extension of Voronoi cell that can divide a space into multiple parts. However, things would be different if BVC keeps updating while the agents are moving toward their corresponding goals, and the updated BVC determines where each agent should be going at the same time. In another word, collision avoidance of BVC is just like a video, and in each frame, the expected position of each agent in the next frame is given according to the current and goal potion of each agent.

Take Fig. 7 as an example. Assume that there are four agents, with their current and goal position given as the inputs of BVC, which are shown in Fig. 7(a). Detailed definitions of marks can be seen in the title of Fig. 7. Just as what is described in Section 3.2, BVC chart can be drawn in Fig. 7(b) according to these inputs and the preset buffer size $d$ . Here comes the essential part of collision avoidance by BVC: calculation of position for each agent in the next frame.

Figure 7. An example of how BVC works in collision avoidance in one frame. Each color corresponds to an agent. Dots, pale dots, stars, and crosses are current position, position of next frame, goal position, and mid-points of each agent, respectively. (a) Position data for inputs. (b) BVC drawn based on inputs. (c) Obtained outputs.

First, similar to buffer size $d$ , the step distance $l$ that each agent moves for each frame can be set freely by the users. The next process would be divided into two cases: (1) The goal is inside the BVC of corresponding agent and (2) The goal is outside the BVC of corresponding agent. In the case of Fig. 7, the agent in green belongs to case (1) and the agents in red, yellow, and purple belong to case (2).

For case (1), the agent would go straight towards its goal for the distance $l$ . For case (2), the agent would go along the line connecting the current position and midpoint of the agent for distance $l$ instead. Here, the midpoint of an agent is defined as the point on the edges of agent’s BVC (inner buffer) that is closest to the goal. Two cases described above are also illustrated in Fig. 7(c).

Steps above explain all steps required for one frame in collision avoidance by BVC. In application, these steps will be repeated with the update of BVC until all agents reach their corresponding goals. Subsequent frames after Fig. 7 are presented in Fig. 8. Here, the frame in Fig. 7 is defined as Frame 1; thus, Fig. 8(a) is Frame 2, Fig. 8(b) is Frame 3, and Fig. 8(c) is the final frame where each agent reaches the corresponding goal. Note that the step distance $l$ that each agent moves in one frame in Figs. 7 and 8 is much longer than the real one so that it is easier to distinguish one frame from another. In this paper, $l$ is set to be 1 mm for smooth trajectory planning and better collision avoidance performance. Flowchart in Fig. 9 sums up the entire flow described above.

Figure 8. Subsequent frames after Fig. 7. (a) Frame 2. (b) Frame 3. (c) Final frame.

Figure 9. Flowchart of collision avoidance by BVC.

4.1. Design of end-effector

As explained in Section 2.2, fingers that extrude horizontally are added to each end-effector for the grasping of soft materials instead of grasping vertically with air grippers. There are mainly two reasons:

1. (1) Taking advantage of the revolute joint at the end of each SCARA. Generally speaking, the revolute joint at the end of a SCARA is used for the twist of tools equipped on it, like drills. However, by adding horizontal fingers each SCARA obtains an additional link that can be considered as a new redundant DoF, enabling more motion options in collision avoidance and improving reachability.

2. (2) Size optimization that considers both the layout of robots and reachability. The layout of Quad-SCARA is illustrated in Fig. 2, which is relatively crowded. If the end-effector extends less, collision avoidance would be easier but its advantage in flexibility and reachability that can be gained from point (1) would be weakened and vice versa. Therefore, the end-effector is optimized to the size in Fig. 4.

4.2. Proposition of static BVC

Through simulation verification and robot experiments, an unexpected issue emerged: there is a risk of self-collision. Specifically, the air grippers and fingers may collide with the inner corners of robot bases in some cases. The normal self-collision of SCARAs between their original arm parts and their bases can be simple avoided by the default setting in terms of movable ranges for each joint and others, but it is not the same case for air grippers and fingers in this paper. This is because the air grippers and fingers are additionally equipped to the robots and work independently from SCARAs, and there is no appropriate default setting available for the robots to utilize.

To address this issue, a new approach of BVC implementation called “static BVC” is proposed. Specifically, besides treating each robot end-effector (one gripper and two fingers) as a BVC for collision avoidance, each inner corner of the robot base is additionally treated as a fixed BVC to avoid the self-collision described above. Figure 10 illustrates the image of this proposition. During the trajectory planning and collision avoidance of SCARAs, four normal cells in orange keep moving and avoiding the collision with all types of cells, including static cells in red that stay still. Simulation and experiment results prove that this proposition is effective, which will be presented in detail in Section 5.

Figure 10. Static and normal BVC. Sizes of each cell may vary from real ones. Each cell core is plotted as a dot and a circle with the diameter of safe distance d. Circles in orange are normal cells, and circles in red are static cells.

Since static BVC is verified to be effective for static obstacles with their size known, it is expected that this idea can also be utilized in other collision avoidance situations besides the original BVC.

4.3. Optimization of buffer size

Theoretically, larger buffer size means safer collision avoidance where agents are farther from each other. However, the total workspace of Quad-SCARA is limited. This means that there may be no solution for BVC if the buffer is too large, and the collision avoidance may not be guaranteed if the buffer is too small. Empirical results and data from simulation validation reveal that a buffer of 20 mm is too small for collision avoidance, and a buffer more than 30 mm may cause no solution.

Taking the concerns explained above into consideration, the authors newly introduce the index of “shortest distance” between each pair of end-effector for the optimization of buffer size and evaluation of collision avoidance. Specifically, the simulator calculates all distances between each point and lines that form the contours of end-effectors, and the least one among them is defined as the shortest distance. With the reference of shortest distance, the buffer size is optimized to 25 mm in this paper.

5.1. Grasping of a handkerchief

Figure 11 shows the process of an end-effector grasping and moving a handkerchief with the size of 250 mm^*250 mm. The height of end-effector is controlled manually. The end-effector approaches the handkerchief in the second picture, succeeds in grasping in the third picture, and lifts the handkerchief up in the fourth. Then, the end-effector moves horizontally while keeping the handkerchief in the fifth picture and releases it in the last. Similar experiments have been performed for 10 times and are all successful, proving its graspability with the condition of a correct input height.

Figure 11. Grasping test of a handkerchief.

5.2. Collision avoidance

To validate and evaluate the overall performance of collision avoidance system on Quad-SCARA, an experiment was made with the results depicted in Figs. 12, 13, and 14 and conditions listed in Table III. The experiment starts with the state that all four corners of the target cloth are grasped. The goal positions of all SCARAs for folding motion are given, and after the folding motion, all robots return to their corresponding initial positions, thus completing the spreading motion. In Fig. 13, the calculated shortest distances are displayed, with their corresponding locations marked in pink dotted lines.

Table III. Conditions of the experiments in Fig. 12.

Figure 12. Snapshots of the experiments. The upper row is the motion for folding a handkerchief, and the lower row is the motion for spreading.

Figure 13. Snapshots for simulation results. Numbers correspond to those in Fig. 12. The shortest distances are displayed on the left upper corner and are magnified at the bottom of each picture.

Figure 14. BVC charts for collision avoidance. Numbers correspond to those in Fig. 12. BVCs in light green, dark green, deep blue, and pink are static BVCs.

5.3. Discussions

The proposed collision avoidance system for Quad-SCARA in multi-point grasping state is successful throughout the whole process of both folding and spreading motion, not only in avoiding the collision between robot end-effectors but also in avoiding self-collision with the proposition of static BVC.

Figure 15 shows the minimal value of shortest distance detected in simulation throughout the experiment described in Section 5.2, which is 1.99 mm. Note that its value in reality would be approximately 2 mm longer than that in simulation, which is about 4 mm. This is because the contours of the robots and end-effectors in simulator are slightly bigger (1 mm for each) than real ones, just as what is explained in Section 2.3. Therefore, although in simulator it seems to be very close to collision, but in reality there is a sufficient clearance to avoid collision. This result also verifies that the optimization for both end-effector size and BVC buffer size is appropriate and viable.

Figure 15. Shortest distance.