Printer Friendly

Environment Mapping Algorithm Using Semantic Description and Constrained Delaunay Triangulation.

I. Introduction

Continuous development of automated systems, including mobile robotics, encourages scientists to develop sophisticated solutions [1]. Ultimately, this will allow robots to serve as a personal aid in everyday tasks. A basic requirement, however, is the robot's ability to reason like humans [2], including the ability to move in their environment. This, in turn, is associated with problems of navigation and path planning, which depend on the environment that either has already been discovered or is just being explored [3]. In recent years, scientists have developed various solutions that can be divided into three main areas that define the scope of current research.

The first area is related to the acquisition of semantic information from sensory data. Problems encountered in this area often belong to the signal domain, i.e., processing, analysis, and segmentation. As a result, an abstract representation of the measurement space is expected. For example, in [4], the authors use the AdaBoost method to generate a space classifier for geometric features obtained by a laser scanner. In [5], an algorithm for acquiring a three-dimensional semantic model from a point cloud is developed. The use of convolution networks for recognition of semantics from camera images is proposed in [6].

The second area is focused on the application of semantics acquisition techniques in the process of simultaneous localization of a mobile robot in the environment and mapping of this space (SLAM). The robot's movement causes sensory data to be collected from different positions. This means that there is a problem of combining the gathered information into a coherent map of the explored environment. For example, in [7], the authors improve the FastSLAM 2.0 algorithm with an extractor of regional features. The article [8] presents a comprehensive solution that builds a 3D map based on a multistage analysis of a point cloud. The authors in [9] develop a hybrid method of mapping relative spatial correlations and Bayesian inference about self-localization. In [10], the authors propose introduction of semantic information into the optimization process of an environmental map based on the highest probability function.

The third focus discusses the use of acquired semantic models in decision-making processes for planning task realization. This issue often utilizes artificial intelligence techniques to solve the problem. The solution presented in [11] shows a model consisting of a spatial and conceptual part, and the methodology of using it in planning processes. In [12], the use of an environmental map with a defined probabilistic distribution of objects to determine the probable location of a sought object of a known type is discussed. The work [13] discusses the interpretation of natural language commands in the robot's workspace.

The following paper focuses on the aspect of an efficient environment mapping with an abstract layer. As a solution to this problem, an algorithm developed by the authors is proposed to generate a metric-semantic model of space explored by a mobile robot. The Delaunay triangulation algorithm [14] and its variant with constraints [15] are used in this method. Similarly, to [16], the Delaunay triangulation is used as a backbone of an environment map, which is explored by the robot. However, in contrast to the beforementioned article, the issue of path planning is not considered--the path is predetermined and focus is put entirely on the semantic analysis of the environment.

The article is organised as follows. In Section II, a description of the problem is given, as well as the details of the proposed method of the environmental mapping. Section III lists the simulation assumptions and presents research results. Finally, conclusions and a plan for further work are presented in Section IV.

II. Method Description

A. Problem Formulation

A mobile robot located in the two-dimensional Cartesian space of the world map Mw has the task of mapping its surroundings by moving along the given path points Pd, creating its own representation of the robot map Mr. This problem is shown in Fig. 1.

The map [mathematical expression not reproducible] is a set of n semantic zones zw. Each zone zw is a tuple [z.sub.w] = ([P.sub.w], s) and has a semantic descriptor 5 from the set [S.sub.t] = {[s.sub.1], [s.sub.2], ..., [s.sub.g]} and a set [P.sub.w] = {[p.sub.1], [p.sub.h]}that contains two points describing a rectangular area. The semantic set St has a defined number g types of space. The use of such description simplifies the sensory aspect to reading information from the explored environment without the need to implement segmentation of this data.

B. Proposed Solution

In the proposed method, the mobile robot is treated as a discrete system. This means that it measures the environment at given Pd points, and the obtained information Us is quantised. These data points are used to determine correlations between them and the existing sets zr of the Mr map. This is used to extend borders of the areas already explored or to discover unknown regions of the environment. The overall concept is presented in Fig. 2. The constructed map [mathematical expression not reproducible] consists of m discovered areas zr, which are semantically consistent with the definition of the world Mw. This map is characterized by the existence of transition areas between the adjacent zones.

These areas are interpreted as a semantically undefined space. The shape of each zone [z.sub.r] = ([P.sub.r], s)is defined by an associated set of boundary points [P.sub.r] = {[p.sub.1], [p.sub.2], ..., [p.sub.u]} of the varying size u.

In the proposed algorithm we can distinguish the acquisition process of the semantic data Us that is realized for a given position Pd at time k [member of] <1, [absolute value of [P.sub.d]]>. This set consists of elements [u.sub.s] = (p, s), where each is a single environmental measurement and contains the spatial location p = (x, y) of semantic information s.

Another key element of the method is the analysis of correlated combination of the examined space Mr with measurements Us and reduction of excess information. This operation is represented as [direct sum] in the equation below

[M.sub.r](k) = [M.sub.r](k - 1) [direct sum] [U.sub.s] ([P.sub.d] (k)), (1)

where the result is a new representation of the explored environment. The process of merging the Mr and Us datasets is done by using semantic matching and Delaunay triangulation. The first step in the combining process is to analyze the location of sensory data Us in relation to the boundaries of the explored areas. After adding them to the Mr space, the existing boundaries are modified using geometrical relations. A modified set of discovered map points and a newly defined boundary are used to generate a triangulation grid. The resulting mesh of relations between nodes allows defining the updated areas of the Mr map according to their semantic correspondence.

Delaunay triangulation is characterized by the generation of meshes according to the principle of uniform maximization of angles in triangles. This creates zones with largest areas increasing the probability of sensory data inclusion in fewer triangles and accelerates the correlation analysis process. As a convex grid must be generated in each step of triangulation, it is necessary to use an algorithm, in which constraints could be applied. These constraints allow to differentiate between triangles within the explored space and those belonging to the undiscovered one.

Figure 3 shows the triangulation problem; the borders of the discovered areas are marked by a solid black line. Relations between the measurement nodes of the same semantic type are given in light grey. Connections between the zones of differing types are depicted in dark grey. The shape, visible in Fig. 3, is a consequence of the predetermined circular path executed by the mobile robot. Both boundaries (i.e., inner and outer) are a direct result of processing the data acquired during that motion.

The information reduction phase also uses the methodology from the data merging process to eliminate points inside the areas and remove some of the transition points. Internal points are analyzed for semantic correspondence with their neighboring nodes. They are removed when all their connections are of the same type. The selection of transition points is based on the distance to the nearest adjacent transition node. This results in retaining the point in question if it is the closest one among its neighbors, which identical semantic descriptor to a zone of another type.

III. Results

A. Simulation Assumptions

To verify correctness and efficiency of the mapping algorithm the following test conditions were assumed:

--A simulated mobile robot with a virtual sensor moves along the path points in a 2D space, which was set up to represent a single-family home environment [17];

--Sensor placed on the robot returns the semantic information about characteristic points of the robot's environment in eight world directions. Measurement range is limited and analyzing the space behind opaque obstacles, such as walls or fences, is impossible. This is in contrast to windows, which do not block the sensory measurement;

--The simulation process is carried out in a discrete way based on the given path points. Each step of the simulation generates a new map of the explored space based on the sensory data obtained and the already discovered map of the environment;

--The research was carried out in Matlab 2018b, using a computer with the following specification: CPU--Intel Core i5-2430M 2.4 Ghz, RAM--2x4 GB DDR3-1333 CL9, GPU--Nvidia GeForce GT 520MX 1 GB, HD--SSD SATA 2.

B. Experiment

The following scenario of an environmental exploration was assumed in the study. A mobile robot located at the starting point (6, 21) moves clockwise in an octagonal circular motion. In each iteration, it moves by a random distance of <1, 1.1> meters. After every three steps, it changes the movement direction by 45 degrees. Such movement pattern requires 24 iterations of the mapping algorithm to complete the circular shape. The range of the sensor was set to 2 meters with a quantisation of 0.1 meter. The simulation was performed for 100 loops (i.e., path completions), which results in 2400 iterations of the environment mapping algorithm.

Figure 4 illustrates a fragment of the explored space used for the experiment. The dashed black line marks the averaged path of the robot's movement. Passages, such as stairs and doors, are marked in light grey, while barriers (i.e., walls) are shown in dark grey. The areas between these zones are described by the following semantic descriptors: garden, terrace, living room, and corridor.

Table I shows the results of the simulation experiment.

The first column contains the number of iterations of the environmental mapping, i.e., how many times the proposed algorithm was executed. The second column defines the number of laps driven by the mobile robot, where one cycle takes 24 iterations of the exploration algorithm. The third column contains the average iteration time of the method for a specific loop (second column) and the last column shows the average width of transition zones between different types of map areas.

The resulting representations of the environment map are shown in Fig. 5. Three different phases are presented, which were obtained after: 1, 25, and 100 exploratory loops. The black line marks the boundaries of the discovered areas, and the grey one depicts the path of robot's motion. Small circular markers inside the largest boundary area indicate the transition between different zones. The subfigures show that the gain in precision of the mapped environment is highest in the first iterations of the algorithm. This observation is supported by the data presented in Table I.

IV. Conclusions

The simulation results prove the validity of the proposed method of environment mapping using semantic information and Delaunay triangulation. The presented algorithm was tested experimentally for spatial description of a semantic environment and was proven to be efficient. The obtained results show a tendency of the algorithm to take more time in subsequent iterations, which is caused by the increasing number of transition points. At the same time, the cyclic mapping of the examined space leads to a decrease in the transition zone size.

In the future work, it is planned to further improve the process of information reduction and attempts will be made to adapt the proposed method to the problem of a real-world environment exploration.

Manuscript received 14 March, 2019; accepted 6 August, 2019.

Conflicts of Interest

The authors declare that they have no conflicts of interest.


[1] F. Ingrand and M. Ghallab, "Deliberation for autonomous robots: A survey", Artificial Intelligence, vol. 247, pp. 10-44, Jun. 2017. DOI: 10.1016/j.artint.2014.11.003.

[2] S. Lemaignan, M. Warnier, E. A. Sisbot, A. Clodic, and R. Alami, "Artificial cognition for social human-robot interaction: An implementation", Artificial Intelligence, vol. 247, pp. 45-69, Jun. 2017. DOI: 10.1016/j.artint.2016.07.002.

[3] S. G. Tzafestas, "Mobile robot control and navigation: A global overview", J. Intell. Robot Syst., vol. 91, no. 1, pp. 35-38, Jul. 2018. DOI: 10.1007/s10846-018-0805-9.

[4] O. Martinez Mozos, R. Triebel, P. Jensfelt, A. Rottmann, and W. Burgard, "Supervised semantic labeling of places using information extracted from sensor data", Robotics and Autonomous Systems, vol. 55, no. 5, pp. 391-402, May 2007. DOI: 10.1016/j.robot.2006.12.003.

[5] R. B. Rusu, Z. C. Marton, N. Blodow, A. Holzbach, and M. Beetz, "Model-based and learned semantic object labeling in 3D point cloud maps of kitchen environments", in Proc. of 2009 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2009, pp. 3601-3608. DOI: 10.1109/IROS.2009.5354759.

[6] N. Sunderhauf et al., "Place categorization and semantic mapping on a mobile robot", in Proc. of 2016 IEEE International Conference on Robotics and Automation (ICRA), 2016, pp. 5729-5736. DOI: 10.1109/ICRA.2016.7487796.

[7] J. Oberlander, K. Uhl, J. M. Zollner, and R. Dillmann, "A region-based SLAM algorithm capturing metric, topological, and semantic properties", in Proc. of 2008 IEEE International Conference on Robotics and Automation, 2008, pp. 1886-1891. DOI: 10.1109/ROBOT.2008.4543482.

[8] A. Nuchter and J. Hertzberg, "Towards semantic maps for mobile robots", Robotics and Autonomous Systems, vol. 56, no. 11, pp. 915-926, Nov. 2008. DOI: 10.1016/j.robot.2008.08.001.

[9] D. W. Ko, C. Yi, and I. H. Suh, "Semantic mapping and navigation: A Bayesian approach", in Proc. of 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2013, pp. 2630-2636. DOI: 10.1109/IROS.2013.6696727.

[10] S. L. Bowman, N. Atanasov, K. Daniilidis, and G. J. Pappas, "Probabilistic data association for semantic SLAM", in Proc. of 2017 IEEE International Conference on Robotics and Automation (ICRA), 2017, pp. 1722-1729. DOI: 10.1109/ICRA.2017.7989203.

[11] C. Galindo, J.-A. Fernandez-Madrigal, J. Gonzalez, and A. Saffiotti, "Robot task planning using semantic maps", Robotics and Autonomous Systems, vol. 56, no. 11, pp. 955-966, Nov. 2008. DOI: 10.1016/j.robot.2008.08.007.

[12] T. Kollar and N. Roy, "Utilizing object-object and object-scene context when planning to find things", in Proc. of 2009 IEEE International Conference on Robotics and Automation, 2009, pp. 2168-2173. DOI: 10.1109/ROBOT.2009.5152831.

[13] F. Duvallet et al., "Inferring Maps and Behaviors from Natural Language Instructions", in Experimental Robotics, Springer, Cham, 2016, pp. 373-388. DOI: 10.1007/978-3-319-23778-7_25.

[14] D. T. Lee and B. J. Schachter, "Two algorithms for constructing a Delaunay triangulation", International Journal of Computer and Information Sciences, vol. 9, no. 3, pp. 219-242, Jun. 1980. DOI: 10.1007/BF00977785.

[15] J. R. Shewchuk, "General-dimensional constrained Delaunay and constrained regular triangulations, I: Combinatorial properties", Discrete Comput. Geom., vol. 39, no. 1, pp. 580-637, Mar. 2008. DOI: 10.1007/s00454-008-9060-3.

[16] P. Wang, Y. Liu, T. Jin, and M. Huang, "Real-Time Map Generation Using Constraint Delaunay Triangulation", in Convergence and Hybrid Information Technology, 2011, pp. 530-537. DOI: 10.1007/978-3-642-24082-9_65.

[17] D. Figurowski and A. Jain, "Hybrid path planning for mobile robot using known environment model with semantic layer", in Proc. of AIP Conference, vol. 2029, no. 1, p. 020014, Oct. 2018. DOI: 10.1063/1.5066476.

Daniel Figurowski *, Pawel Dworak

Department of Control Engineering and Robotics, Faculty of Electrical Engineering, West Pomeranian University of Technology, 26 Kwietnia 10, 71-126 Szczecin, Poland

Caption: Fig. 1. The problem of environment mapping by a mobile robot.

Caption: Fig. 2. The idea of the proposed mapping algorithm.

Caption: Fig. 3. Convex triangulation problem and semantic correlation.

Caption: Fig. 4. Simulation environment context.

Caption: Fig. 5. Environment maps generated by the proposed algorithm: (a) after 24 iterations; (b) after 600 iterations; (c) after 2400 iterations.

Algorithm    Loop    Loop's iterations    Transition zone
iterations   Index       mean time           mean width

24             1          0.4140 s            0.2969 m
48             2          0.6104 s            0.2173 m
120            5          0.8492 s            0.1703 m
240           10          1.0930 s            0.1246 m
600           25          1.7021 s            0.0889 m
1200          50          3.1697 s            0.0683 m
2400          100         3.5932 s            0.0504 m
COPYRIGHT 2019 Kaunas University of Technology, Faculty of Telecommunications and Electronics
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2019 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Figurowski, Daniel; Dworak, Pawel
Publication:Elektronika ir Elektrotechnika
Date:Dec 1, 2019
Previous Article:Development of Cyber-Physical Security Testbed Based on IEC 61850 Architecture.
Next Article:MSSB to Prevent Cable Termination Faults for Long High Voltage Underground Cable Lines.

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters