key: cord-0529905-cm4m47sd authors: Flores-Aquino, Gabriel O.; Ortega, Jheison Duvier D'iaz; Arvizu, Ricardo Yahir Almazan; Munoz, Ra'ul L'opez; Gutierrez-Frias, O. Octavio; Vasquez-Gomez, J. Irving title: 2D Grid Map Generation for Deep-Learning-based Navigation Approaches date: 2021-10-25 journal: nan DOI: nan sha: bd082f53c287bb1d7648384608552152ab42faba doc_id: 529905 cord_uid: cm4m47sd In the last decade, autonomous navigation for roboticshas been leveraged by deep learning and other approachesbased on machine learning. These approaches have demon-strated significant advantages in robotics performance. Butthey have the disadvantage that they require a lot of data toinfer knowledge. In this paper, we present an algorithm forbuilding 2D maps with attributes that make them useful fortraining and testing machine-learning-based approaches.The maps are based on dungeons environments where sev-eral random rooms are built and then those rooms are con-nected. In addition, we provide a dataset with 10,000 mapsproduced by the proposed algorithm and a description withextensive information for algorithm evaluation. Such infor-mation includes validation of path existence, the best path,distances, among other attributes. We believe that thesemaps and their related information can be very useful forrobotics enthusiasts and researchers who want to test deeplearning approaches. The dataset is available athttps://github.com/gbriel21/map2D_dataSet.git Our experience in the human world dictates to us that the best way to interact with an environment is by using local and global references. This idea is used in Map-based navigation where the robot knows a priory a representation of the work-space. This representation, denominated map, is usually encoded as an occupancy grid where each grid represented an unoccupied or occupied space [1] . The occupancy grid maps are widely used for probabilistic localization and mapping [10] as well for planning algorithms as Rapidly Random Trees (RRT) [7] , RRT* [?] or Probabilistic Road Maps (PRM) [5] to name a few classic examples. The occupancy maps are also necessary for new approaches. For example, in [11] , where the input of a neural network is a dungeon map. In [9] , the authors describe a neuronal planner for solving motion problems. This approach required a large amount of data including, maps or environments useful for testing and training. Another recent use for maps is to infer a latent representation of the work-space, a good example is exposed in [4] . Other recent works explore the uses of reinforcement learning or deep reinforcement learning, such as [2] , where combines sampling-based planning with reinforcement learning. In this work, planning is tested in large spaces represented as an occupancy grid, but the training process is built with small environments. Other works The illustration shows three random rooms that are connected by corridors as well as the paths than connect those rooms. Free cells are drawn in black. Occupied cells are drawn in white. In green dotted lines, breath-first search path is drawn. In solid light blue line A* computed path is drawn. use other learning approaches such as supervised learning techniques. An example of this approach is presented in [6] , where a neural network improves the sampling in difficult passages using as input a map. Recent and unexpected changes in the world such as those caused by the Covid 19 pandemic have accelerated the trend of using service robots for tasks in home and workspaces as hospitals or offices to guarantee safety measures. For these reasons, the proposed maps are intended to represent indoor spaces, similar to dungeons maps used in a large number of computer games [8] , composed of square areas like rooms in a house or office spaces and connected by hallways. In this paper, we propose an algorithm to generate random bi-dimensional maps. The algorithm can be customized, by modifying simple parameters, for example, the size of the output image or the number of rooms. Besides, to increase the diversity and complexity of the maps, the proposed algorithm has several random variables that allow created maps with different sizes for rooms and hallways and maps fully connected as maps with inaccessible regions. Together with this algorithm, we also provide an associated dataset with 10,000 images complemented with a CSV file with information about the parameters that char-acterize the maps and paths founded with the algorithms, Breadth-first search [12] and A* search [3] (see Figure 1 ) and a connectivity matrix that provides information about connection between rooms. We believe that the dataset and associated information can be useful in machine learning approaches, especially for indoor navigation. The document is organized as follows. In section 2, we present the algorithm to generate maps. In section 3, we describe the maps obtained, and in section 4, we explain the characterization for maps. Finally, in section 5, we provide our conclusions and future work. In this section, we present the pseudo-code for building k bi-dimensional maps (see Algorithm 1) . Where each map is conformed as a set of square rooms connected with square passages. The input is the number of maps required and the output is a set of maps with the characteristics described in the parameters. These parameters are map size in pixels; number of rooms with a minimum of two rooms, minimum and maximum limits for the room (room width limit, room length limit), and tunnel width limit for the amplitude of the passages. In line 2, we define a matrix of size (x, y); we consider 1 as an occupied space and 0 as free space, in line 3 we define and array to store the seed points of each room and in line 4 we choose randomly a value for the width of the tunnel. In the first part, we free up the space of the rooms (lines 5 to 11). In line 5 for p = {1, 2, ......, n} where n is the number of rooms, we randomly created n seeds or origin points (line 6) and save them in the array R. Subsequently, in lines 9 and 10 we get randomly, the width and length for the n-th element. For the second part, we need to connect each pair of rooms. To add complexity in line 13, we add the option of not connecting a couple of rooms in the ten percent of cases. In lines 15 and 16, we select progressively a pair of rooms denoted as A and B to connect in one of two ways when A is a horizontal passage and, consequently, B is a vertical passage, lines 19 and 20. When A is vertical and B horizontal, lines 22 and 23. This commutation is again to win a complex and diverse dataset . In this section, we present a brief description of the generated maps. The dataset attached, contains 10,000 square maps of 64 pixels for 64 pixels. Each pixel is represented by a value of 1 for occupied space and 0 for free space as shown in Figure 2 . The origin is (0, 0) and takes place in the upper-left corner and the final pixel position (63, 63) is in the opposite corner. In Figure 2 , we show some examples of the maps by the parameters in Table 1 . The reader can see in sub-figure 2a an example where one room is not connected, this case has the objective to represent the situation where a robot can not access certain spaces. In sub-figure 2f, we show an example of a map with the maximum number of rooms. Below we show and describe the parameters for the algorithm. Also, these parameters are saved and provided together with the dataset. • Item: The number of maps. • Label: A name assigned to identify each map. • Resolution: A relative value to guide the approximate dimension of the map in the real world. • Passages size: The randomly selected dimension from the lower and upper limits in the Tunnel width limit. • Seed rows: A matrix of one row and n columns with the randomly selected position for rows. • Seed columns: A matrix of one row and n columns with the randomly selected position for columns. • Size rows: A matrix of one row and n columns with the randomly selected size length for rooms in pixels. • Size columns: A matrix of one row and n columns with the randomly selected size width for rooms in pixels. • Direction for passages: A matrix of one row and 2(n − 1) columns with the sequence of values that indicate the direction of the tunnel. • Connected: Line matrix with n − 1 elements. It is a sequence composed of True or False that indicates if room A connects with B (see line 13 1). In addition to the set of maps represented as binary images, we included in the dataset an associated document Parameters for dataset item value maps 10,000 maps size 64x64 px item lower limit upper limit rooms 2 9 rooms size row 14 px 33 px room size column 14 px 33 px passages size 7 px 15 px characterization. In each map, we calculated the path with two classic algorithms breadth-first search and A* and we provide in a row and column the coordinates of a path that goes through all the seed points of each room, see Figure 1 for an example, and a connection matrix that show information about the cost or distance in pixels of connecting two rooms. • Row path for breadth-first search: Line matrix with the row coordinate for the path founded. • Column path for breadth-first search: Line matrix with the columns coordinate for the path founded. • Iterations for breadth-first search: The number of iterations required to found a path. • Connection matrix for breadth-first search: Contain information about the path in pixel between all the points. • Row path for A*: Line matrix with the row coordinate for the path founded. • Column path for A*: Line matrix with the columns coordinate for the path founded. • Iterations for A*: The number of iterations required to found a path. • Connection matrix for A*: Contain information about the path in pixel between all the points. The path found is the route that connects all the seed points in the original sequences. That means room 1, room 2 until room n, see Figure 3 . This is not the optimal path but ensures traffic between all rooms. This path was founded after computing Breadth-first search, one of the simplest and archetype algorithms for finding routes in graphs [12] . The connection matrix is a representation where an element c i,j with i = {1, 2, 3.., ..., n} and j = {1, 2, 3.., ..., n} represents the distance in pixels for the i th and j th room. See Figure 4 for some examples. The value of -1 is a convention to indicate "no connection". The value of 0 appears when it is the same point and the rest values are the path distance or cost in pixels. We have presented an algorithm for building random 2D grid maps. This algorithm allows building maps of multiple sizes and degrees of complexity by modifying and selecting randomly simple parameters. Along with the algorithm, it is presented a database with 10,000 2D maps using the proposed method. We include together with the dataset, a CSV file with the configuration parameters for each map and their characterization in terms of calculated paths, computed with two classic algorithms. Overall, this information can be useful to train and test machine learning approaches for map-based navigation. Robotics, Vision and Control Prm-rl: Long-range robotic navigation tasks by combining reinforcement learning and sampling-based planning A formal basis for the heuristic determination of minimum cost paths Robot motion planning in learned latent spaces Probabilistic roadmaps for path planning in high-dimensional configuration spaces Lego: Leveraging experience in roadmap generation for sampling-based planning Rapidly-exploring random trees: A new tool for path planning Constructive generation methods for dungeons and levels Motion planning networks: Bridging the gap between learningbased and classical motion planners Probabilistic robotics Toward autonomous mapping and exploration for mobile robots through deep supervised learning Introduction to Algorithms The authors are grateful for the support provided by CONACYT and the IPN. In addition this work is funded by the SIP-IPN, with registration number 20210268. Jheison Duvier Diaz Ortega is grateful for the support granted in the call for technological development or innovation projects for students of the IPN 2021.