Imagen Imagen
Imagen Alejandro Hidalgo-Paniagua & Miguel A. Vega-Rodríguez & Joaquín Ferruz & Nieves Pavón
ahidalgop@unex.es & mavega@unex.es & ferruz@cartuja.us.es & npavon@dti.uhu.es
University of Extremadura & University of Extremadura & University of Sevilla & University of Huelva

Introduction

  In mobile robotics, one of the main problems consists of finding a feasible path to go from a starting point to a target point in a specific environment. This problem is known as the Path Planning (PP) problem or the Motion Planning problem.

  A feasible path refers to a path in which the robot can move to the target point without colliding with environment's objects (path safety). Furthermore, this problem can be addressed by optimizing several objetives in order to get better paths. These possible objectives could be the path length and the path smoothness.

  On the other hand, a novel field inside robotics is the field known as Evolutionary Robotics (ER). ER develops the robot's controllers applying Evolutionary Algorithms (EAs). These EAs can be modified to handle several objectives. These modified EAs are known as MOEAs (Multi-Objetive Evolutionary Algorithms). The PP problem is a good candidate to be solved by using MOEAs.


Datasets

  In order to test the developed algorithms to solve the PP problem, we used two realistic maps of indoor environments. Figures 1 and 2 show these maps.

Figure 1. Map A.
Figure 2. Map B.

  To make a computational representation of these images, we partition the images in several rows and columns and then we process each resulting cell to get a gray level matrix (occupancy matrix). In order to get the gray level (occupancy) of a specific cell, we take into account the pixels' colours inside of it. Thus, the white pixels refer to an empty surrounding area of the environment (occupancy equal to 0%). The green pixels correspond with walls (occupancy equal to 1000%). Finally, the rest of the pixels (neither white nor green) are the ordinary objects of the environment (occupancy equal to 100%). The reason for considering walls as special items is due to they can be very dangerous objects for a robot. If a robot collides with a wall the most probable event is that the robot will be damaged.

  Figure 3 and 4 show an example of map partitioning for the two proposed maps (Map A and B).

Figure 3. Map A partitioning. Grid = (100*100).
Figure 4. Map B partitioning. Grid = (100*100).

  The maps are available as occupancy matrices too. These matrices have a size equal to 100 rows * 100 columns. Each value of a matrix cell corresponds with a gray level percentage. The data files are plain text and each line of the file corresponds with a row of the matrix. All values in a file line are separated by a comma character (',') and they refers to the matrix columns. These data files can be downloaded from the following links:


      

  In order to test our algorithms, we established four scenarios corresponding with the following directions of a map: the main diagonal of the map (MD), the secondary diagonal of the map (SD), the direction corresponding with the vertical axis (VA), and the direction corresponding with the horizontal axis of the map (HA). We suggest you to use these scenarios to test your algorithms and compare with us (see Table 1).


    Map         Direction         Starting point (X,Y)         Target point (X,Y)    
Map A SD (93,6) (23,75)
Map A MD (93,93) (6,11)
Map A VA (83,32) (11,26)
Map A HA (31,8) (35,89)
Map B SD (94,6) (9,90)
Map B MD (94,90) (6,6)
Map B VA (93,48) (6,49)
Map B HA (28,17) (46,91)
Table 1. Scenarios.