Abstract
In applications such as vacuum cleaning, painting, demining and foraging, a mobile robot must cover an unknown surface. The efficiency and completeness of coverage is improved by the construction of a map while the robot covers the surface. Existing methods generally use grid maps, which are susceptible to odometry error and may require considerable memory and computation. We propose a new ”slice decomposition” ideally suited to coverage by a simple zigzag path. Cell boundaries are large, easily detectable natural landmarks. Therefore, the decomposition is robust against uncertainty in sensors. It can also handle a wider variety of environments. The proposed method has been evaluated using simulation and real robot experiments.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Latombe, J.C.: Robot Motion Planning. Kluwer, Dordrecht (1991)
Elfes, A.: Sonar-based real-world mapping and navigation. IEEE Journal of Robotics and Automation RA-3, 249–265 (1987)
Zelinsky, A.: A mobile robot exploration algorithm. IEEE Transactions on Robotics and Automation 8, 707–717 (1992)
Gabriely, Y., Rimon, E.: Spiral-STC: An on-line coverage algorithm of grid environments by a mobile robot. In: Proceedings of the IEEE International Conference on Robotics and Automation, Washington, DC, pp. 954–960 (2002)
Castellanos, J.A., Tardós, J.D., Schmidt, G.: Building a global map of the environment of a mobile robot: The importance of correlations. In: Proceedings IEEE International Conference on Robotics and Automation (ICRA), vol. 2, pp. 1053–1059 (1997)
Thrun, S.: Learning metric-topological maps for indoor mobile robot navigation. Artificial Intelligence 99, 21–71 (1998)
Choset, H., Pignon, P.: Coverage path planning: The boustrophedon decomposition. In: Proceedings of the International Conference on Field and Service Robotics, Canberra, Australia (1997)
Butler, Z.J., Rizzi, A.A., Hollis, R.L.: Contact sensor-based coverage of rectilinear environments. In: Proceedings IEEE International Symposium on Intelligent Control/Intelligent Systems and Semiotics, pp. 266–271 (1999)
Acar, E.U., Choset, H., Rizzi, A.A., Atkar, P.N., Hull, D.: Morse decompositions for coverage tasks. International Journal of Robotics Research 21, 331–344 (2002)
Acar, E.U., Choset, H.: Sensor-based coverage of unknown environments: Incremental construction of morse decompositions. International Journal of Robotics Research 21, 345–366 (2002)
Wong, S.C., MacDonald, B.A.: A topological coverage algorithm for mobile robots. In: Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Las Vegas, Nevada, vol. 4, pp. 1685–1689 (2003)
Foley, J.D., et al.: Computer graphics: principles and practice, 2nd edn. Addison-Wesley, Reading (1990)
Chazelle, B.: Approximation and decomposition of shapes. In: Schwartz, J.T., Yap, C.K. (eds.) Algorithmic and Geometric Aspects of Robotics, pp. 145–185. Lawrence Erlbaum Associates, Mahwah (1987)
Mataric, M.J.: Integration of representation into goal-driven behavior-based robots. IEEE Transactions on Robotics and Automation 8, 304–312 (1992)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Wong, S.C., MacDonald, B.A. (2004). Complete Coverage by Mobile Robots Using Slice Decomposition Based on Natural Landmarks. In: Zhang, C., W. Guesgen, H., Yeap, WK. (eds) PRICAI 2004: Trends in Artificial Intelligence. PRICAI 2004. Lecture Notes in Computer Science(), vol 3157. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-28633-2_72
Download citation
DOI: https://doi.org/10.1007/978-3-540-28633-2_72
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22817-2
Online ISBN: 978-3-540-28633-2
eBook Packages: Springer Book Archive