## 4 Path Planner Utilizing a Building Voronoi Graph
Figure 4: The enlarged figure of Figure 3.  
Figure 3: MapPoints are marked with yellow points. Blue curve segments in this figure show the trimmed Voronoi graph, which is obtained after removing vertices that are too close to mapPoints. Figure 2: In this figure, the left three mapPoints are generated from the boundary of an obstacle, say \(A\). Furthermore, the right two mapPoints are generated from the boundary of another obstacle, say \(B\). At the center of three mapPoints on the left side, we have a Voronoi vertex. A Voronoi edge leading to this vertex cannot be utilized as a path for a robot, since this vertex exists on obstacle boundary. One thus removes Voronoi vertices which are too close to mapPoints. Red bold curve segments indicate the remaining Voronoi edges, after removing Voronoi vertices which are too close to mapPoints. Trimming additional edges consumes the additional computational load. Considering computational load, we only removed a Voronoi vertex, whose distance from a mapPoint is less than \(\Delta\). It is acknowledged that a Voronoi graph does not provide the shortest path between two points. This article uses the Voronoi graph as the robot's path, since it provides the safest path for the robot. Any Voronoi edge in the workspace can be used as the robot's path segment. At the \(i\)-th floor (\(\forall i\in\{1,2,\ldots,L\}\)), we generate a trimmed Voronoi graph and set it as the topological map \(G_{i}^{\pi}\). Each edge in the trimmed Voronoi graph is weighted using its edge length and its associated passage width. Consider the trimmed Voronoi graph on the \(i\)-th floor. Suppose that a Voronoi edge connects between two vertices, say \(V_{m}\) and \(V_{n}\). We next present how to set the weight of this edge. Let \(\mathbf{V}_{m}\in\mathcal{R}^{2}\) and \(\mathbf{V}_{n}\in\mathcal{R}^{2}\) define the positions of \(V_{m}\) and \(V_{n}\), respectively. The length of this edge is \(\|\mathbf{V}_{m}-\mathbf{V}_{n}\|\). The traversal time of this edge is conjectured as \(\frac{\|\mathbf{V}_{m}-\mathbf{V}_{n}\|}{s_{max}}\). Recall that the robot's maximum speed is \(s_{max}\), i.e., \(\|\mathbf{v}(k)\|\leq s_{max}\) for all \(k\). Therefore, the weight of an edge \(e=(V_{m},V_{n})\) is set as  
\[weight(e)=\frac{\|\mathbf{V}_{m}-\mathbf{V}_{n}\|}{s_{max}}. \tag{4}\]  
See that this weight is set considering the time required to traverse the edge, as the robot moves with its maximum speed \(s_{max}\). We further generate a link edge connecting between distinct floors. Recall that a robot can move from one floor to another utilizing elevators. We generate a Voronoi vertex at a workspace position where an elevator exists. Recall that a Voronoi edge \((i,j)\in E(G)\) is a _link_ if \(\pi(i)\
eq\pi(j)\). The weight of a link is set considering the travel time inside the associated elevator. Suppose that a link is \((i,j)\in E(G_{l})\). Then, we set the weight of this link as \(\delta*\|i-j\|\). Here, \(\delta>0\) is a constant. The weight of a link is set, considering the fact that as the floor difference between two floors increases, it takes more time to make the elevator move between the two floors. Once we obtain all weighted edges in the building Voronoi graph, we then generate the adjacency graph based on the weighted edges. We search for a vertex which is closest to the robot's initial position, and set the vertex as \(V_{s}\). In addition, we search for a vertex which is closest to the goal point, and set the vertex as \(V_{t}\). We obtain the shortest path from \(V_{s}\) to \(V_{t}\) utilizing the adjacency graph. For finding the shortest path in a graph, [PERSON]'s algorithms [55] can be used. The building Voronoi graph is generated considering the entire building, including all elevators. Thus, \(V_{s}\) and \(V_{t}\) can exist on distinct floors. If necessary, the robot uses an elevator, which can lead to the goal as fast as possible. Let \(P_{V}=(V^{1},V^{2},..V^{Q})\) define the sequence of Voronoi vertices along the shortest path from \(V_{s}\) to \(V_{t}\).