## 4 Path Planner Utilizing a Building Voronoi Graph  
This section presents the path planner utilizing a building Voronoi graph. First, one presents how to generate \(G_{i}^{\pi}\) for all \(i\in\{1,2,\ldots,L\}\). Each floor is represented as a plane with obstacles. Let _mapPoints_ denote the 2D points associated with static obstacle boundaries in a known 2D map. Since the robot is localized in a known map, it can derive the relative position of a mapPoint while it moves. The robot needs to avoid colliding with mapPoints while it moves. Moreover, the robot needs to avoid colliding with objects, such as humans, in the building environment. At every floor, map boundaries are represented as mapPoints in the workspace. For instance, in a grid map, a mapPoint can be a grid cell presenting the map. MapPoints can be obtained utilizing the map of each floor in the building. It is assumed that mapPoints are known a priori. Using mapPoints at the \(i\)-th floor (\(i\in\{1,2,\ldots,L\}\)), we generate \(G_{i}^{\pi}\). Suppose that \(N^{i}\) mapPoints exist at the \(i\)-th floor (\(i\in\{1,2,\ldots,L\}\)). Let \(\mathbf{O}_{n}^{i}\) define the position of \(n\)-th mapPoint at the \(i\)-th floor. Here, \(n\in\{1,2,\ldots,N^{i}\}\). Suppose that one can access the map of every floor, representing mapPoints on the associated plane. At the \(i\)-th floor, one generates a Voronoi graph \(G_{i}^{\pi}\) as follows. In MATLAB, the _voronoi_ function returns the set of Voronoi edges associated with a given seed points (mapPoints in this paper). The Voronoi edges are all points in the plane, which are equidistant to the two nearest seed points (mapPoints in this paper). A Voronoi vertex is a point where more than two Voronoi edges meet. In the case where mapPoints are generated from the sensing measurements of a robot, the mapPoints may form a cluster. In the case where mapPoints are clustered, one may generate a Voronoi vertex which exists inside the clustered mapPoints. See Figure 2 for an illustration. Five mapPoints exist in total. 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\). In Figure 2, a curve segment indicates the Voronoi edge generated utilizing mapPoints. Furthermore, a circle indicates a Voronoi vertex. At the center of three mapPoints on the left side, there exists a Voronoi vertex. A Voronoi edge leading to this vertex cannot be utilized as a path for a robot, since this vertex exists on an obstacle boundary. One thus removes Voronoi vertices which are too close to mapPoints. Then, Voronoi edges leading to the removed vertices also disappear. In Figure 2, red bold curve segments indicate the remaining Voronoi edges, after removing Voronoi vertices which are too close to mapPoints. For instance, we depict a map which is composed of mapPoints. In Figure 3, mapPoints are plotted with yellow points. Blue curve segments in this figure indicate the trimmed Voronoi graph, which is obtained after removing vertices that are too close to mapPoints. Figure 4 is the enlarged figure of Figure 3. See that mapPoints are clustered around map boundaries. In simulations, we removed a Voronoi vertex, whose distance from a mapPoint is less than a certain distance, say \(\Delta\) (5 m in MATLAB simulations). Figure 3 shows that we still have Voronoi edges which are not necessary for robot path planning. In fact, we can trim a Voronoi edge which crosses the workspace boundary. In addition, we can trim a Voronoi vertex which exists outside the workspace. Furthermore, we can remove Voronoi edges which lead to workspace corners [54]. The authors of [54] considered the case where the robot builds a Voronoi diagram using range sensor measurements. In this case, edges leading to workspace corners can be easily detected using on-board sensors on the robot. However, in our paper, the Voronoi graph is built using the building map, not using range sensor measurements.