## 2 Literature Review on Robot Path Planning  
Various papers exist on the path planning of robots. 3D path planning was introduced in [34], so that a robot can arrive at its goal as fast as possible, while not colliding with 3D obstacles in the environments. Many path-planning planning algorithms, such as RRT-star or RRT-star-smart [35; 36; 37], used random sampling to generate a path in environments without grid cells. Three-dimensional path planning is distinct from path planning in a building structure with elevators, which is handled in our paper. In the literature on robotics, the A-star algorithm, Theta-star algorithm, Dijkstra algorithm, and Voronoi graph were widely used for path planning of various robots [38; 39; 40; 41]. The A-star algorithm shows better performance than the Dijkstra algorithm by utilizing heuristics to guide its search towards its goal. The Theta-star algorithm in [38; 42] is a variant of the A-star algorithm, propagating information along grid edges without constraining the paths to the grid edges. A-star, Theta-star, or Dijkstra algorithms [39; 40; 41] require that the workspace is composed of multiple grid cells. In order to generate a Voronoi graph in grid maps, one can apply brushfire algorithms [43], which build the distance map at each grid cell. However, as the workspace size increases, the number of grid cells required increases. As the building size increases, the required grid map size increases as well. Therefore, computing a path utilizing A-star, Theta-star, and brushfire algorithms, or Dijkstra algorithms in a large building with many floors, may not be feasible due to the large computational load. Therefore, we argue that grid maps are not desirable in the case where one needs to build a path in a large building with many floors. This inspired us to build a Voronoi graph for representing a large building with many floors. In Robotics, a Voronoi graph has been used as a topological map of a workspace [14; 15; 16; 17; 18; 19; 20]. In [44], multiple robots generate a Voronoi graph as a topological map of the environment, while dropping indexed markers at Voronoi vertices. The references [45; 46; 47] presented robot localization solutions as a robot explores a 2D environment by moving along Voronoi edges. In [45; 46; 47], a Voronoi graph is generated by a robot, which moves along Voronoi edges based on range sensor measurements. However, due to sensing errors or obstacles in the environment, the robot with range sensors may have difficulty in generating an accurate Voronoi graph of the environment. In our paper, the building Voronoi graph is built based on a large building map (e.g., grid map), which is assumed to be known a priori. Hence, our Voronoi graph is robust to sensing errors or obstacles in the environment. This distinguishes our paper from other papers [45; 46; 47] on Voronoi graphs. Voronoi path planning based on two steps was introduced in [48]. In the first step, the safest areas in the environment are extracted by means of a Voronoi graph. In the second step, a fast marching approach was applied to the Voronoi extracted areas in order to obtain the shortest path. In [49], the authors introduced an algorithm based on a Voronoi graph in order to compute an optimal path between a start and a goal in the presence of simple disjoint polygonal obstacles. However, in practice, obstacles can have various shapes, other than simple polygonal shapes. Our paper addresses the building Voronoi graph which is generated based on a large building map with arbitrary shapes. In practice, the robot needs to use an elevator which yields the shortest path to the goal. Moreover, the robot needs to spend some time while staying inside an elevator. We thus set the weight of a Voronoi edge based on the travel time in an elevator and the traversal time of a passage. We address path planning based on the building Voronoi graph, which represents a building structure with elevators.