This file is raw output from pdftotext and may not be ideal for distribution. If you are a maintainer for Hackipedia, please sit down when you have time and clean this text version up. Source PDF: /mnt/fw-js/docs/Hardware/Electronics/Robotics/A 3D laser range finder for autonomous mobile robots.pdf Like all conversions the text below should be fully readable as UTF-8 unicode text. --------------------------------------------------------------- Proceedings of the 32nd ISR(International Symposium on Robotics), pp. 153 - 158, 19-21 April 2001 A 3D laser range finder for autonomous mobile robots Hartmut Surmann, Kai Lingemann, Andreas N¨ chter and Joachim Hertzberg u GMD - German National Research Center for Information Technology, AiS - Institute for Autonomous intelligent Systems 53754 Sankt Augustin, Germany   E-mail: surmann,lingemann,nuechter,hertzberg @gmd.de. ¡ Abstract This paper presents a high quality, low cost 3D laser range finder designed for autonomous mobile systems. The 3D laser is built on the base of a 2D range finder by the exten- sion with a standard servo. The servo is controlled by a com- puter running RT-Linux. The scan resolution ( 5 cm) for a ¢ complete 3D scan of an area of 150 (h) 90 (v) degree is £ up to 115000 points and can be grabbed in 12 seconds. Stan- dard resolutions e.g. 150 (h) £ 90 (v) degree with 22500 points are grabbed in 4 seconds. While scanning, different online algorithms for line and surface detection are applied to the data. Object segmentation and detection are done off- line after the scan. The implemented software modules de- Figure 1: The mobile robot equipped with 3D laser range finder. tect overhanging objects blocking the path of the robot. With the proposed approach a cheap, precise, reliable and real-time A few number of groups build 3D laser range finders capable 3D sensor for autonomous mobile robots is available and/or special algorithms on the basis of 2D laser range find- and the robot navigation and recognition in real-time is im- ers to overcome the drawback of only 2D proximity informa- proved. tion that may cause problems with overhanging objects (e.g. chairs, tables or stairways) [9, 10, 11]. Furthermore, the map 1. Introduction building and navigation process [12] is improved since ob- Prognoses at the beginning of the nineties claimed for the jects blocking the path are detected and classified. new millennium a number of about 50.000 independently op- Thrun et al. use two laser range finders, one shifted by erating autonomous service robots in different areas of pro- 90 degrees [9]. The 3D information is generated while the duction and service sectors [1]. The reality is different. In robot is moving. The accuracy of the acquired data depends industrial environments guided vehicles, i.e. vehicles guided on the accuracy of the robot pose. Object detection without by a magnetic or optical track are standard [2]. Autonomous moving the robot is not possible. Waltheim et al. [11] and mobile service systems, i.e. systems not restricted by a track, Kristensen et. al. [10] use an amtec rotation module [13] are used extremely rarely although many research groups are with high accuracy at high costs ( $3500). ¢ working on this since several years – particularly with mobile Our approach extends a standard 2D laser range finder by a systems for transportation tasks, e.g. [3, 4, 5, 6]. One of sev- low cost rotation module based on a servo motor. Combining eral reasons for the gap between prognoses and reality is the such an extension with a set of fast algorithms has resulted in lack of good, cheap and fast sensors that allow the robots to good object detection and obstacle avoiding system. sense the environment in real-time and to act on the basis of 2. Constructing a 3D laser range finder the acquired data. This paper presents a 3D laser range finder designed for The presented 3D laser range finder is built on the basis of autonomous mobile systems (fig. 1). A large number of to- a 2D range finder by extension with a mount and a servomo- day’s autonomous robots use 2D laser range finders as a prox- tor. The 2D laser range finder is attached to the mount so that imity sensor. They are very fast (processing time 30 ms), ¢ it can be rotated. The rotation axis is horizontal. A standard precise ( 1 cm, ¢ ¨¨¦¤ © § ¥ ) and becoming cheaper ( $3000)¢ servo ( $75) is connected on the left side (fig. 2). Anno- ¢ since there are at least two competing products [7, 8]. tation: An alternative approach is to rotate the range finder around the vertical axis. Throughout this paper we will only 3. Real time control and online algorithms discuss the approach based on a horizontal rotation, but all presented algorithms can be used in the same way. The differ- The servo of the new 3D laser range finder is controlled ences between both approaches are the orientation of the apex by a computer running RT-Linux, a real-time operating sys- angle and the effects of dynamic objects moving through the tem which runs LINUX as a task with lowest priority. The scene, e.g. persons. Using vertical scanning, a perturbation servomotor expects a signal every 20 ms, the length of the either appears with low probability within a few scans making signal determines the position of the motor (1 ms = leftmost them useless for further data processing, or does not appear at position, 1.5 ms = middle position, 2 ms = rightmost posi- all. The first approach on the other hand shows perturbations tion). This very time critical job has to be done by a real time throughout the whole scene, but these data can still be used operating system since a latency of about 10 s corresponds  for robot navigation and object detection (see also fig. 9). to a deviation of . Real time Linux has an average la- ¢ © ¤ tency of about 5 s (PII-333) and thus the rotation can be  realized with an average deviation of . $#"§ © ! While scanning, different online algorithms for line and surface detection are applied to the data, thus no extra time is needed. Two different kinds of line detection algorithms have been tested. The first algorithm is a simple straightforward match- ing algorithm running in , ( is the number of points) 1)'% 0 (& ( with small constants. The algorithm implements a simple length comparison. The data of the laser range finder (points @54 ¦8! 7"5¨¨2 9 2 ! ! 4 6 2 4 3 ) is ordered anticlockwise so that one com- parison per point is sufficient. We assume that the points $B4 8¦! 52 C 2 ! ! 4 Aare already on a line. For we have to check if E5$2 6 D C F E5$5G@2 F 6 D C 2 4 A Figure 2: The 3D laser range finder. The servo is mounted at the left side. A camera on top is used to get texture images for the realistic H W@V& TRF ED I 54 I 2 F )IC ! 0 U S Q 6 2 P (1) A appearances of a 3D scene. To obtain better results this algorithm runs on preprocessed The given setup determines an intrinsic order of the ac- data. Data points located close together are joined so the dis- quired data. The data coming from the 2D laser range finder tance from one point to the next point is almost the same. is ordered anticlockwise. In addition the 2D scans (scanned This process minimizes the fluctuations within the data and planes) are ordered due to the rotation. A digital camera for reduces the points to be processed. Hence this algorithm runs texture mapping is mounted on top of the 3D laser range very fast, but the quality of the lines is limited. finder. While rotating, serveral photos are taken so that the The second line detection algorithm implemented is the texture mapping can be applied to a larger area. well known Hough-Transform [14]. A ( ) parametrisation Y G4 X The 3D laser range finder uses only standard interfaces of the space of lines is used, where is the angle of the normal Y of a computer. The servomotor is directly connected to the to the line and the distance along this normal from the line X parallel port, the 2D laser range finder to the serial port and to the origin of the image. Using this parametrisation, all the camera is connected to an USB port. Nowadays, every points of a line fulfill the following equation: computer (esp. laptops) does have these interfaces and the built 3D laser range finder can therefore easily be used on u0 Y tV5qp10 Y ¦WecaX ! & sr g i h & g f d b ` (2) mobile platforms. The mount and the servo are inexpensive and no special Solving this equation for every point , that is calculat- 0 "i 4 )& b Y electronic devices are used, so the price of the whole system ing for every angle , results in a histogram (see fig. 3). X mainly depends on the used 2D laser range finder. The maximum of the histogram corresponds to a line and the The maximal scan resolution for a complete 3D scan of number of points belonging to this line is maximal. an area of (h) ¤ © §  ¨¨£ © § (v) is up to 115000 points and The iteration of the following three steps returns all line can be grabbed in 12 seconds. Standard resolutions e.g. segments. (h) ¤ © §  (v) with 22500 points are grabbed in 4 seconds. ¨¨£ © §  The grabbing speed can be increased by a factor of using  ¢ 1. find maximum = find straight line and calculate the line equation ` vi xThwbR£ 2 a RS-422 instead of a RS-232 which is the standard inter- face of the laser range finder. The scan resolution is basically 2. tag all points belonging to this line determined by the resolution of the laser range finder and is ¢ 5 cm [8]. It can be increased to 1 cm with other laser ¢ 3. remove these points from the histogram and make line range finders [7]. segments. Iteration: 18 Iteration: 17 Based on the detected lines, the following algorithm tries to detect surfaces in the 3-dimensional scene. 70 70 60 50 40 60 50 40 Scanning a plane surface, the line detection algorithm will 30 20 10 30 20 10 return a sequence of lines in successive 2D scans approxi- 0 0 200 250 200 250 mate the shape of this surface. The task is to recognize such 150 150 0 50 100 150 200 50 100 0 50 100 150 200 50 100 structures within the 3D data input and to concatenate these 250 0 250 0 independent lines to one single surface. The surface detection Iteration: 16 Iteration: 01 algorithm proceeds the following steps: 70 60 70 60 0. The first set of lines – coming from the very first 2D 50 50 40 30 20 40 30 20 scan – is stored. 10 10 0 0 0 150 200 250 0 150 200 250 1. Every other line is being checked with the set of stored 50 100 150 200 250 0 50 100 50 100 150 200 250 0 50 100 lines. If a matching line is found, these two lines are transformed into a surface. Figure 3: Histogram of the Hough transformation with 1, 3, 5 and y 2. If no such matching line exists, the line may be an ex- points tension of an already found surface. In this case, the new line is matching with the top line of a surface. This top line is being replaced by the new The final step uses the intrinsic order of the data as it comes line, resulting in an enlarged surface (fig. 5). from the laser range finder. Due to the intrinsic order of the data on a line only one check is necessary to determine 3. Otherwise the line is stored as a stand-alone line in the whether a point belongs to a line segment. An advantage of set mentioned above. the Hough transformation is that it computes the general line equation and all of the belonging line segments in one step To achieve real time capabilities, the algorithm makes use which is helpfull in further processing steps (fig. 4). of the characteristics of the data as it comes from the range finder, i.e. it is the order by the scanned planes. Therefore the Scan Punkte lines are sorted throughout the whole scene (with regard to 400 Gefunden Linien their location within the virtual scene) due to their inherited order. Thus an efficient local search can be realized. Two criteria have to be fulfilled in order to match lines: On one hand the endpoints of the matching line must be within 200 an -area around the corresponding points of the given line S (fig. 5). On the other hand the angle between the two lines has to be smaller than a given value . The second constraint ƒ is necessary for correct classification of short lines, since they fulfill the distance criterion very easily. 0 To illustrate this aspect, the reader may imagine the 3D scan of a complex object, a chair, for example. The specific -200 0 200 400 structure of this object will yield in a set of small, differently Figure 4: Lines found by the Hough transformation (one horizontal oriented lines, approximating the many small surfaces of the plane of 3D image of figure 9) chair (fig. 11). Because of the closeness of these lines they would be transformed into some fewer, lager surfaces. The Hough-Transformation runs in ), where is the VE'% (‚ €& € e distance to the furthest data point. This maximum distance is  2 currently limited to 10 m, so that the transformation can be †… „ done in real-time. For indoor environments this limitation is – • ” ‘’“ ˆ sufficient. After line detection the transformation of the 2D coordi- nates into 3D coordinates is done. All following data process- ‰ ing steps operate on the three dimensional data. 3.1. The third dimension ‡ All algorithms described so far run on 2 dimensional data. Figure 5: Expansion of a surface by a new line After line detection is done the data is converted into 3D. This step, merely a joining of lines found in former scans, This procedure can be generalized to handle other kinds of can be done online, too, since no data from future scans is elements as well, since lines are represented by 2 points and necessary. This means that the robot or a user gets much in- surfaces by 2 lines. formation about objects in the scenery right during the scan. 5. Results 4. Offline algorithms To visualize the data, different viewer programs based on Offline algorithms are used to create a 3D map of the O PEN GL and JAVA 3D were implemented. The task of these room and to enable a safe navigation of the robot. Despite programs is the projection of the 3D scene to the image plate, of the prior algorithms, this step requires information about i.e. the monitor. A graphical user interface developed with the whole scene and has to be done after the scan process is JAVA (fig. 7) enables a simple and easy way to use the scanner finished. application and the external viewers. Object segmentation is done by sequentially merging con- glomerations of points, lines and surfaces into one object: 1. Start with one arbitrary element, e.g. a surface. This element is already treated as a “real” object in this state of the algorithm. 2. Iterate over the previously found elements and check whether there are any elements “near enough” to this object. 3. If such an element is found, the object is enlarged until it encloses this element. 4. Repeat until no more elements fit the given object. During this process, all elements belonging to the object are marked. The object segmentation algorithm starts again, un- til no more conglomerations of elements exists, i.e. until no more objects can be found within the scanned scene. Figure 7: The JAVA user interface The first example (fig. 8) shows a man sitting on a chair in a corridor. Durring the 12 seconds scan, a person is crossing the scene two times (at the right side). Figure 9 shows the 115000 scan points as they come from the scanner. The two pertubation can be seen as white stripes at the right side. Figure 6: Representation of an object The objects are characterized by bounding boxes (cubes) (fig. 6). A bounding box is given by 3 orthogonal lines, cor- responding to the axes of the virtual world coordinate system. In addition, each object is surrounded by a sphere which en- closes the whole bounding box. This sphere is used to check very fast whether a single point is near enough to this object to be examined as part of the bounding box. The algorithm first checks if the point is inside the sphere. Figure 8: The third author sitting on a chair This can be done by a test of the euclidian distance. If the element passes this test, the algorithm has to determine Based on figure 9 the implemented algorithms compute a whether the point is near enough to the actual bounding box. line view as shown in figure 10. This picture demonstrates In this case, the lines defining the bounding box have to be clearly that the line detection is done in 2D planes coming re-adjusted to enclose this new point, the sphere likewise. from the scanner. Figure 9: Scanned points Figure 12: Detected surfaces and objects in fig. 11 Figure 11 shows the detected surfaces derived from the lines of figure 10. On the left side the lines are joined to a large surface representing the wall very well. In contrast the other side consists of several small surfaces, due to the person crossing the scene while scanning (for the dynamic view of the planes see the url [15]. This perturbation did not change the general look of the scene as shown in the previous figures. Figure 12 illustrates the results of the object detection step. The person in the middle consisting of a bunch of surfaces is placed within one single bounding box and clearly marked as an obstacle. The pertubated surfaces on the right side are placed in different boxes. These boxes still can be used for safe navigation of a mobile robot, to derive a path around all obstacles, regardless of the scanning error. The second example shows a stairway without any dy- namic objects during the scanning process (fig 13). It shows Figure 10: Detected lines in fig. 9 that fine structures like the staircase railing can be detected by the system. Surfaces with a similar orientation (that is, with a sufficiently small angle between their normal vectors) get the same color. This labeling enables the algorithm to detect a wall even if it is separated into several smaller surfaces. Fur- thermore it is possible to detect walls as a whole even if they were interrupted by doors, for example. 6. Conclusion This paper has presented a cheap, precise and reliable high quality 3D sensor for autonomous mobile robots. With the proposed approach a real-time capable 3D sensor is available and the robot navigation and recognition in real-time is im- proved. The 3D laser is built on base of an ordinary 2D range finder and uses only standard computer interfaces. The 3D scanner senses the environment contactless without the ne- cessity of setting landmarks. The scan resolution for a com- plete 3D scan of an area of 150 (h) 90 (v) degree is up to £ 115000 points and can be grabbed in 12 seconds. The pre- Figure 11: Detected surfaces in fig. 10 cision is mainly determined by the laser scanner ( 5 cm). ¢ Figure 13: Picture, scan of the stairway in our building, detected lines and surfaces. The picture is assembled of 3 photos. Standard resolutions e.g. 150 (h) 90 (v) degree with 22500 £ [6] Hartmut Surmann and Antonio Morales, “A five layer sen- points are grabbed in 4 seconds. While scanning, different sor architecture for autonomous robots in indoor environ- online algorithms for line and surface detection are applied ments,” in International symposium on robotics and automa- to the data. Object segmentation and detection are done off- tion ISRA’2000, Monterrey, N.L., Mexico, 10-12 Nov. 2000, line after the scan. The implemented software modules detect pp. 533–538. overhanging objects blocking the path of the robot. [7] URL: Sick optic electronic, “PLS: Definition der Telegramme Needless to say much work remains to be done. Future zwischen Benutzerschnittstelle und Sensorsystem uber RS- ¨ work will concentrate on four further aspects. 422 / RS-232,” in http://www.sickoptic.com/laser.htm, 2000. [8] URL: Schmersal EOT, “LSS 300: Telegramm zwischen — Improving object classification while fusing camera in- Benutzerschnittstelle und Sensorsystem V.1.14,” in http:// formation and an object database. www.schmersal.de/d/produkte/n2000/laserlss.html, 2000. — [9] Sebastian Thrun, Dieter Fox, and Wolfram Burgard, “A real- Improving facility management systems by construct- time algorithm for mobile robot mapping with applications to ing and updating digital building models including the multi-robot and 3d mapping,” in IEEE International Confer- inventory (scan matching). ence on Robotics and Automation, San Francisco, 2000. — Increasing the rotation angle of the servo. [10] Steen Kristensen and Patric Jensfelt, “Active global localisa- tion for a mobile robot using multiple hypothesis tracking,” in — Detecting non-flat or quadrangular surfaces. Proceedings of the IJCAI’99 Workshop on Reasoning with Un- certainty in Robot Navigation, Stockholm, Sweden, 1999, pp. References 13–22. [11] Axel Walthelm and Amir Madany Momlouk, “Multisensoric [1] R.D. Schraft and H. Volz, Serviceroboter, Innovative Tech- active spatial exploration and modeling,” in Dynamische Per- nik in Dienstleistung und Versorgung, Springer-Verlag, Berlin, zeption: Workshop der GI-Fachgruppe 1.0.4 Bildverstehen, Heidelberg, 1996. Ulm. 2000, pp. 141–146, AKA Akad. Verl.-Ges., Berlin. [2] PSLT, FTS-Anlagen-Analyse Europa: Technischer Bericht, [12] Hartmut Surmann and Liliane Peters, MORIA - A Robot with PSLT Hannover, 1998. Fuzzy Controlled Behaviour, vol. 61 of Studies in Fuzziness [3] Joseph F. Engelberger, “Health-care robotics goes commer- and Soft Computing, chapter Layer Integration, pp. 343–365, cial: the ‘HelpMate’ experience,” Robotica, vol. 11, pp. 517– Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 2001. 523, March 1993. [13] URL: amtec, “amtec product homepage,” in http://www.- [4] P. Weckesser R. Graf, “Roomservice in a hotel,” in IFAC powercube.de/index products.html, 1999. Symposium on Intelligent Autonomous Vehicle, Madrid, 1998, [14] P. V. C. Hough, “Methods and means for recognising complex pp. 641–647. patterns,” in U.S. Patent 3 069 654, Dec 1962. [5] S. J. Vestli, “Mops - a system for mail distribution in office- [15] URL: GMD-AiS 3D Laserscanner, “Animated gif of a 3d scan type buildings,” Service Robot: An International Journal, vol. (multiple 2d layers),” in http://capehorn.gmd.de:8080/pic- 2, no. 2, pp. 29–35, 1996. tures/demo1.gif, 2001.