# A Low Overhead Mapping Scheme for Exploration and Representation in the Unknown Area
## 2 A New Mapping Scheme of Rmap  
### The Framework of Rmap  
In this section, the entire framework of the Rmap and detailed algorithms are introduced. The Rmap consists of several modules, such as the initial map setting, the minimal bounding rectangle (MBR) creation, R1 selection, the map update, exploration, and the map extension check module as shown in Figure 2. This mapping framework works with the localization module of the SLAM algorithm. Figure 1: An example of a grid and topological map. The grid map maintains all the areas on a cell-by-cell basis. The topological map maintains the map through nodes and edges. (**a**) Environment, (**b**) Grid map, (**c**) Topological map. The initial map setting is a step of collecting initial information when the mobile robot is located in an unknown environment, as shown in Figure 3a. At this step, the robot generates an initial map about the given environment through a one-rotation. The white area of Figure 3b shows the initial sensing data obtained by the rotation of the robot. The MBR creation module creates a minimal bounding rectangle (MBR), as shown in the blue dotted box of Figure 3b. The MBR is the smallest rectangle that can contain all the areas acquired in the initial map setting and all the newly sensing data in the exploration. The R1 selection is the next step to obtain R1 from the MBR. R1 is the largest rectangle that can be created in the occupied area of the MBR. This study uses the rectangle tiling algorithm to get R1. The rectangle tiling is a mathematical algorithm for finding configurable rectangles in a grid [17]. For a rectangle with a height of \(m\) x width \(n\), the whole rectangle candidates can be calculated within the created MBR region by the rectangle tiling algorithm, as shown in Equation (1). Figure 3: The Rmap building process in an unknown area. (**a**) The environment and robot (circle); (**b**) The environmental data obtained through sensing is the white area in the initial map setting, the unknown area is gray, the blue dotted box is the minimal bounding rectangle (MBR); (**c**) the new area is the white part obtained by moving along the red line of (**c**), the gray box is the updated R1 on the map, the blue dotted box is the MBR that contains all the information currently held, and the green box is the next R1 to explore; (**d**) Exploration. Figure 2: The framework of the Rmap scheme in which creating of Rmap is processed in mapping part of simultaneous localization and mapping (SLAM) and shares the Rmap to localization. \[N(m,n)=\sum_{i=0}^{m-1}\sum_{j=0}^{n-1}(m-i)(n-j)=\frac{1}{4}m(m+1)n(n+1) \tag{1}\]  
A similar problem to the set covering problem [18] is finding the largest rectangle among these candidates. The set covering problem is one of the representative [PERSON]'s 21 NP-complete problems in the field of computer science [19]. This study uses the greedy method to calculate the size of all the rectangular candidates to obtain R1, R2, R3,..., Rn in size order. Through this method, the largest rectangle R1 can be chosen. An example of the creation of R1 is the green box in Figure 3c. Then, the R1 information is updated to the map. After updating the R1 information, the robot needs to explore the area for getting new information. This study designed the exploration step, and it is performed to plan and move the robot. The primary exploration policy is to follow the updated R1's boundary line, as shown in the red line in Figure 3c. At this time, the robot moves from the current position to the boundary of R1 by the shortest path. When the robot performs the exploration step, it can explore new areas like the increased white area of Figure 3d. The Rmap scheme using this moving policy can plan an exploration path that minimizes a duplicate path in an unknown environment. The map extension check step verifies that the robot has obtained a new area in the exploration step.