## 3 The Navigation Strategy with Path Priority
### Step 1 and Step 2: Giving an Environment Map and Generalized Voronoi Diagram (GVD) Map Division  
Suppose a map with fixed obstacle positions is shown in Figure 1(a). To avoid the robot hitting any obstacle, the gray boundary for each obstacle is dilated from the periphery of the obstacle, as shown in Figure 1(b). The size of the dilatation is based on the radius of the considered robot's body. Let the Voronoi corners [28] for each obstacle be shown as the red dots in Figure 1(c), where the Voronoi corners include the detected corners and some assigned extra corners. In this study, the extra corners on the boundary of the map are equidistantly set with twice the diameter of a robot and those on the edges of the obstacle are equidistantly set with the diameter of a robot. Those extra corners are added on the workspace boundary and the edges of obstacles. Due to adding the extra corners, navigation points will not be easily influenced by a Voronoi corner and there will be more paths to be chosen by the robot. In this paper, the locations of extra corners are set by a designer's experience. The segmented areas divided by blue lines using a Voronoi diagram are shown in Figure 2d, where any intersection point of blue lines is called a navigation point of robots. Those blue lines passing through obstacles are deleted, as shown in Figure 2e, called the generalized Voronoi diagram (GVD) [29]. The moving path of a robot consists of several links, where each link connects two adjacent navigation points. It is known that if there are few extra corners, then there are few blue lines too (see Figure 2f). In this study, the number of each robot is the path-priority order number of the robot. For instance, robot-1 has higher path priority than robot-2 does. Figure 1: Flow chart of multi-robot path planning. Figure 2: (**a**) The input obstacle map; (**b**) safety margins are added; (**c**) Voronoi corners are detected; (**d**) VD division, (**e**) GVD division, and (**f**) GVD division with few extra corners. There are some navigation points in the GVD divided map, as shown in Figure 2e, and each robot can move from any navigation as an initial position to the target point along the blue lines. However, if there are additional fixed or dynamic obstacles in the space, we will immediately update the divisions in Figure 2d depending on the movements of the considered robot. For instance, as shown in Figure 3a,b,e, there are seven obstacles and two robots (represented by green circles) in the space, and these maps are in Figure 3 based on robot-2's viewpoint. Figure 3a,b shows the positions of robot-1 and robot-2 between adjacent time frames. Figure 3c,d are the local enlargements of Figure 3a,b, respectively, and show many feasible paths (the red arrows) to the navigation points around robot-2. It is noted that some feasible paths may be blocked by higher path-priority robots later. To avoid blocking situations happening, let us have an extra assigned Voronoi corner at the center of the lower path-priority robot (robot-2), such that an extra Voronoi cell is created around robot-2 as shown in the yellow areas of Figure 3e,f, respectively. It is seen that the feasible paths of robot-2 in the yellow Voronoi field shown in Figure 3f will not block the higher path-priority robot's moving. From now on, we can set path priorities for all robots depending on the importance of each robot's task such that the robot transit will be more efficient. In other words, the higher path-priority robots can plan a path ahead of the lower path-priority robots, and the lower path-priority robot will regard the higher path-priority robot as a moving obstacle to be avoided. To increase the safety factor, the dilated range of the moving obstacle depends  
Figure 3: (**a**) The divided map from robot-2’s view point without the assigned extra Voronoi corner at \(time=t\). (**b**) The divided map from robot-2’s view point without the assigned extra Voronoi corner at \(time=t+1\).