A new technique for processing ultrasonic arc maps is proposed and compared to six existing techniques for map-building purposes. These techniques are simple point marking along the line-of-sight, voting and thresholding, morphological processing, Bayesian update scheme for occupancy grids, arc-transversal median algorithm, and triangulation-based fusion. The directional maximum technique, newly proposed in this paper, employs directional processing to extract the map of the environment from ultrasonic arc maps. It aims at overcoming the intrinsic angular uncertainty of ultrasonic sensors in map building, as well as eliminating noise and cross-talk related misreadings. The compared techniques are implemented with a wall-following motion-planning scheme for ground coverage. The comparison is based on experimental data and three complementary error criteria: mean absolute error, correct detection rate for full and empty regions, and computational cost in terms of CPU time. The directional maximum technique offers a very good compromise between mean absolute error and correct detection rate, with a processing time less than one-tenth of a second. Compared to the existing techniques, the directional maximum method is also superior in range accuracy and in eliminating artifacts, resulting in the best overall performance. The results indicate several trade-offs in the choice of ultrasonic arc-map processing techniques.
Auran, P.G. and Silven, O. (1996). Underwater sonar range sensing and 3-D image formation . Control Engineering Practice, 4(3): 393—400.
2.
Barshan, B. (1999). Ultrasonic surface profile determination by spatial voting. Electronics Letters, 35(25): 2232—2234.
3.
Barshan, B. and Başkent, D. (2000). Comparison of two methods of surface profile extraction from multiple ultrasonic range measurements . Measurement Science and Technology, 11(6): 833—844.
4.
Barshan, B. and Başkent, D. (2001a). Morphological surface profile extraction with multiple range sensors. Pattern Recognition , 34(7): 1459—1467.
5.
Barshan, B. and Başkent, D. (2001b). Map building from range data using mathematical morphology. In Active Sensors for Local Planning in Mobile Robotics (ed. P. Probert Smith), Chapter 7, pp. 111—135. Vol. 26 of World Scientific Series in Robotics and Intelligent Systems, World Scientific, NJ.
6.
Barshan, B. and Kuc, R. (1990). Differentiating sonar reflections from corners and planes by employing an intelligent sensor. IEEE Transactions on Pattern Analysis and Machine Intelligence, 12(6): 560—569.
7.
Barshan, B. and Kuc, R. (1992). A bat-like sonar system for obstacle localization . IEEE Transactions on Systems Man and Cybernetics, 22(4): 636—646.
8.
Başkent, D. and Barshan, B. (1999). Surface profile determination from multiple sonar data using morphological processing. International Journal of Robotics Research, 18(8): 788—808.
9.
Beckerman, M. and Oblow, E. (1990). Treatment of systematic errors in the processing of wide-angle sonar sensor data for robotic navigation. IEEE Transactions on Robotics and Automation, 6(2): 137—145.
10.
Bemporad, A., Di Marco, M., and Tesi, A. (1997). Wall-following controllers for sonar-based mobile robots. Proceedings of the IEEE International Conference on Decision and Control, San Diego, CA, December, Vol. 8, pp. 3063— 3068.
11.
Borenstein, J. and Koren, Y. (1991a). The vector field histogram: fast obstacle avoidance for mobile robots. IEEE Transactions on Robotics and Automation , 7(3): 278— 288.
12.
Borenstein, J. and Koren, Y. (1991b). Histogramic in-motion mapping for mobile robot obstacle avoidance. IEEE Transactions on Robotics and Automation , 7(4): 535—539.
13.
Borenstein, J., Everett, H.R., and Feng, L. (1996). Navigating Mobile Robots. A K Peters Ltd., Wellesley, MA.
14.
Bozma, Ö.I. (1992). A Physical Model-Based Approach to Analysis of Environments using Sonar. PhD thesis, Yale University, Dept. of Electrical Engineering, New Haven, CT.
15.
Bruce, J. and Veloso, M. (2002). Real-time randomized path planning for robot navigation . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, Lausanne, Switzerland, September/October, Vol. 3, pp. 2383—2388.
Choset, H. and Burdick, J., (2000). Sensor-based exploration: The hierarchical generalized Voronoi graph. International Journal of Robotics Research , 19(2): 96—125.
18.
Choset, H., Walker, S., Eiamsa-Ard, K., and Burdick, J. (2000). Sensor-based exploration: Incremental construction of the hierarchical generalized Voronoi graph. International Journal of Robotics Research, 19(2): 126—148.
19.
Choset, H., Nagatani, K., and Lazar, N. (2003). The arc-transversal median algorithm: a geometric approach to increasing ultrasonic sensor azimuth accuracy. IEEE Transactions on Robotics and Automation, 19(3): 513—522.
20.
Cox, I.J. (1991). Blanche: an experiment in guidance and navigation of an autonomous robot vehicle. IEEE Transactions on Robotics and Automation, 7(2): 193—204.
21.
Crowley, J.L. (1985). Navigation for an intelligent mobile robot. IEEE Transactions on Robotics and Automation, RA-1(1): 31—41.
22.
Drumheller, M. (1987). Mobile robot localization using sonar. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-9(2): 325—332.
23.
Elfes, A. (1987). Sonar based real-world mapping and navigation . IEEE Transactions on Robotics and Automation, RA-3(3): 249—265.
24.
Elfes, A. (1989). Using occupancy grids for mobile robot perception and navigation. IEEE Computer, 22(6): 46—57.
25.
Everett, H.R. (1995). Sensors for Mobile Robots, Theory and Application . A K Peters Ltd., Wellesley, MA .
26.
Gasos, J. and Martin, A. (1996). A fuzzy approach to build sonar maps for mobile robots. Computers in Industry, 32(2): 151—167.
27.
Gilbreath, G. and Everett, H. (1988) Path planning and collision avoidance for an indoor security robot. In Proceedings SPIE: Mobile Robots III, Vol. 1007 (ed. W. J. Wolfe ), pp. 19—27, Boston, MA.
28.
Grimson, W.E. and Lozano-Perez, T. (1984). Model-based recognition and localization from sparse range or tactile data. International Journal of Robotics Research, 3(3): 3— 35.
29.
Hong, M.L. and Kleeman, L. (1997a) Ultrasonic classification and location of 3-D room features using maximum likelihood estimation I. Robotica , 15(5): 483—491.
30.
Hong, M.L.and Kleeman, L. (1997b). Ultrasonic classification and location of 3-D room features using maximum likelihood estimation II. Robotica , 15(6): 645—652.
31.
Hsu, D., Kindel, R., Latombe, C., and Rock, S. (2002). Randomized kinodynamic motion planning with moving obstacles. International Journal of Robotics Research , 21(3): 233—255.
32.
Kleeman, L. and Kuc, R. (1995). Mobile robot sonar for target localization and classification. International Journal of Robotics Research , 14(4): 295—318.
33.
Kuc, R. and Siegel, M.W. (1987). Physically-based simulation model for acoustic sensor robot navigation. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-9(6): 766—778.
34.
Kurt, A. (2005). A Comparative Study of Five Algorithms for Processing Ultrasonic Arc Maps. Master's thesis, Bilkent University, Department of Electrical Engineering, Ankara, Turkey.
35.
Kurz, A. (1996). Constructing maps for mobile robot navigation based on ultrasonic range data. IEEE Transactions on Systems Man and Cybernetics, 26(2): 233—242.
36.
Lee, D. and Recce, M. (1994). Quantitative evaluation of the exploration strategies of an intelligent vehicle. International Journal of Robotics Research, 16(4): 413—447.
37.
Leonard, J.J. and Durrant-Whyte, H.F. (1992). Directed Sonar Sensing for Mobile Robot Navigation. Kluwer Academic Publishers , Boston, MA.
38.
McMullan, W.G., Delanghe, B.A., and Bird, J.S. (1996). A simple rising-edge detector for time-of-arrival estimation. IEEE Transactions on Instrumentation and Measurement , 45(4): 823—827.
39.
Mojsilovic, A., Popovic, M., Amodaj, N., Babic, R., and Ostojic, M. (1997). Automatic segmentation of intravascular ultrasound images: A texture-based approach. Annals of Biomedical Engineering , 25(6): 1059—1071.
40.
Moravec, H.P. and Elfes, A. (1986). High resolution maps from wide angle sonar. Proceedings of IEEE International Conference on Robotics and Automation , San Francisco, CA, April, pp. 116—121.
41.
Nomadic Technologies Inc. (1997) Nomad 200 Manual, Mountain View, CA.
42.
Oriolo, G., Ulivi, G., and Vendittelli, M. (1997). Fuzzy maps: a new tool for mobile perception and planning. Journal of Robotic Systems, 14(3): 179—197.
43.
Pagac, D., Nebot, E.M., and Durrant-Whyte, H.F. (1998). An evidential approach to map-building for autonomous vehicles. IEEE Transactions on Robotics and Automation, 14(4): 623—629.
44.
Peremans, H., Audenaert, K., and Van Campenhout, J.M. (1993). A high-resolution sensor based on tri-aural perception. IEEE Transactions on Robotics and Automation, 9(1): 36—48.
Serra, J. (1982). Image Analysis and Mathematical Morphology. Academic Press, New York.
47.
Tunstel, E. and Jamshidi, M. (1994). Embedded fuzzy logic-based wall-following behavior for mobile robot navigation. Proceedings of 1st International Joint Conference of NAFIPS/IFIS/NASA, San Antonio, TX, December, pp. 329— 330.
48.
Verly, J.G. and Delanoy, R.L. (1993). Some principles and applications of adaptive mathematical morphology for range imagery. Optical Engineering, 32(12): 3295— 3306.
49.
Wallner, F. and Dillman, R. (1995). Real-time map refinement by use of sonar and active stereo vision. Robotics and Autonomous Systems, 16(1): 47—56.
50.
Wijk, O. (2001). Triangulation Based Fusion of Sonar Data with Application in Mobile Robot Mapping and Localization. PhD thesis, Royal Institute of Technology, Stockholm , Sweden.
51.
Wijk, O. and Christensen, H.I. (2000a). Triangulation-based fusion of sonar data with application in robot pose tracking. IEEE Transactions on Robotics and Automation, 16(6): 740—752.
52.
Wijk, O. and Christensen, H.I. (2000b). Localization and navigation of a mobile robot using natural point landmarks extracted from sonar data. Robotics and AutonomousSystems, 31: 31—42.
53.
Yata, T., Kleeman, L., and Yuta, S. (1998). Wall following using angle information measured by a single ultrasonic transducer. Proceedings of IEEE International Conference on Robotics and Automation, Leuven, Belgium, May, Vol. 5, pp. 1590—1596.
54.
Yun, X. and Tan, K.-C. (1997). A wall-following method for escaping local minima in potential field based motion planning. Proceedings of the IEEE International Conference on Advanced Robotics, Monterey, CA, July, pp. 421—426.
55.
Zelinsky, A. (1988). Environment mapping with a mobile robot using sonar. In Proceedings of the Australian Joint Artificial Intelligence Conference-AI'88, November, pp. 373— 388.
