Skip to main content
SpringerLink
Log in

Coverage for robotics – A survey of recent results

  • Published:
Annals of Mathematics and Artificial Intelligence Aims and scope Submit manuscript

Abstract

This paper surveys recent results in coverage path planning, a new path planning approach that determines a path for a robot to pass over all points in its free space. Unlike conventional point-to-point path planning, coverage path planning enables applications such as robotic de-mining, snow removal, lawn mowing, car-body painting, machine milling, etc. This paper will focus on coverage path planning algorithms for mobile robots constrained to operate in the plane. These algorithms can be classified as either heuristic or complete. It is our conjecture that most complete algorithms use an exact cellular decomposition, either explicitly or implicitly, to achieve coverage. Therefore, this paper organizes the coverage algorithms into four categories: heuristic, approximate, partial-approximate and exact cellular decompositions. The final section describes some provably complete multi-robot coverage algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Webster's Ninth New Collegiate Dictionary (Merriam-Webster, Springfield, MA, 1990).

  2. E.Acar and H. Choset, Critical point sensing in unknown environments, in: IEEE International Conference on Robotics and Automation, San Francisco, CA (2000).

  3. E.M. Arkin and H. Refael, Approximation algorithms for the geometric covering salesman problem, Discrete Appl. Math. 55 (1994) 197-218.

    Article  MATH  MathSciNet  Google Scholar 

  4. T. Balch, The case for randomized search, in: Workshop on Sensors and Motion, IEEE International Conference on Robotics and Automation, San Francisco, CA (May 2000).

  5. T. Balch and R.C. Arkin, Communication in reactive multiagent robotic systems, Autonom. Robots 1(1) (1995).

  6. R.A. Brooks, A robust layered control system for a mobile robot, IEEE J. Robotics Autom. (1986).

  7. Z.J. Butler, A.A. Rizzi and R.L. Hollis, Contact sensor-based coverage of rectilinear environments, in: Proc. of IEEE Int'l Symposium on Intelligent Control (September 1999).

  8. Z.J. Butler, A.A. Rizzi and R.L. Hollis, Complete distributed coverage of rectilinear environments. in: Proc. of the Workshop on the Algorithmic Foundations of Robotics (March 2000).

  9. J.F. Canny, The Complexity of Robot Motion Planning (MIT Press, Cambridge, MA, 1988).

    Google Scholar 

  10. Z. L. Cao, Y. Huang and E. Hall, Region filling operations with random obstacle avoidance for mobile robots. J. Robotic Syst. (1988) pp. 87-102.

  11. H. Choset, E. Acar, A. Rizzi and J. Luntz, Exact cellular decompositions in terms of critical points of morse functions, in: IEEE International Conference on Robotics and Automation, San Francisco, CA (2000).

  12. H. Choset and P. Pignon, Coverage path planning: The boustrophedon decomposition, in: Proceedings of the International Conference on Field and Service Robotics, Canberra, Australia (December 1997).

  13. J. Colegrave and A. Branch, A case study of autonomous household vacuum cleaner, in: AIAA/NASA CIRFFSS (1994).

  14. A. Elfes, Sonar-based real-world mapping and navigation, IEEE J. Robotics Autom. 3 (1987) 249-265.

    Article  Google Scholar 

  15. D. Gage, Randomized search strategies with imperfect sensors, in: Proc. SPIE Mobile Robots VIII, Boston, MA (September 1993) pp. 270-279.

  16. E. Gat and G. Dorais, Robot navigation by conditional sequencing, in: Proc. IEEE Int. Conf. on Robotics and Automation, San Diego, CA (May 1994) pp. 1293-1299.

  17. S. Hert, S. Tiwari and V. Lumelsky, A terrain-covering algorithm for an AUV, Autonom. Robots 3 (1996) 91-119.

    Article  Google Scholar 

  18. C. Hofner and G. Schmidt, Path planning and guidance techniques for an autonomous mobile cleaning robot, Robotics Autonom. Syst. 14 (1995) 199-212.

    Article  Google Scholar 

  19. W. Huang, Optimal line-sweep decompositions for coverage algorithms, Technical Report 00-3, Rensselaer Polytechnic Institute, Department of Computer Science, Troy, NY (2000).

    Google Scholar 

  20. Y.Y. Huang, Z.L. Cao and E.L. Hall, Region filling operations for mobile robot using computer graphics, in: Proceedings of the IEEE Conference on Robotics and Automation (1986) pp. 1607-1614.

  21. O. Khatib, Real-time obstacle avoidance for manipulators and mobile robots, Internat. J. Robotics Res. 5 (1986) 90-98.

    Google Scholar 

  22. D. Kurabayashi, J. Ota, T. Arai and E. Yoshida, Cooperative sweeping by multiple mobile robots, in: Int. Conf. on Robotics and Automation (1996).

  23. S. Land and H. Choset, Coverage path planning for landmine location, in: Third International Symposium on Technology and the Mine Problem, Monterey, CA (April 1998).

  24. J.C. Latombe, Robot Motion Planning (Kluwer Academic, Boston, MA, 1991).

    Google Scholar 

  25. V. Lumelsky, S. Mukhopadhyay and K. Sun, Dynamic path planning in sensor-based terrain acquisition, IEEE Trans. Robotics Autom. 6(4) (1990) 462-472.

    Article  Google Scholar 

  26. V. Lumelsky and A. Stepanov, Path planning strategies for point mobile automation moving amidst unknown obstacles of arbitrary shape, Algorithmica 2 (1987) 403-430.

    Article  MATH  MathSciNet  Google Scholar 

  27. D. MacKenzie and T. Balch, Making a clean sweep: Behavior based vacuuming, in: AAAI Fall Symposium, Instationating Real-World Agents (1996).

  28. H. Moravec and A. Elfes, High resolution maps for wide angles sonar, in: IEEE Int. Conf. on Robotics and Automation (1985).

  29. C. Ó'DÚnlaing and C.K. Yap, A “retraction” method for planning the motion of a disc, Algorithmica, 6 (1985) pp. 104-111.

    Article  MATH  Google Scholar 

  30. M. Ollis and A. Stentz, First results in vision-based crop line tracking. in: IEEE International Conference on Robotics and Automation (1996).

  31. F.P. Preparata and M.I. Shamos, Computational Geometry: An Introduction (Springer-Verlag, Berlin, 1985) pp. 198-257.

    Google Scholar 

  32. I. Rekleitis, G. Dudek and E. Milios, Multi-robot exploration of an unknown environment, efficiently reducing the odometry error, in: IJCAI, International Joint Conference in Artificial Intelligence, Vol. 2, Nagoya, Japan, August 1997 (Morgan Kaufmann, San Mateo, CA, 1997) pp. 1340-1345.

    Google Scholar 

  33. E. Rimon and D.E. Koditschek, Exact robot navigation using artificial potential functions, IEEE Trans. Robotics Autom. 8(5) (1992) 501-518.

    Article  Google Scholar 

  34. S.V. Spires and S.Y. Goldsmith, Exhaustive geographic search with mobile robots along space-filling curves, in: Collective Robotics; Proceedings of the First International Workshop, CRW'98. Paris, France, July 1998, Lecture Notes in Artificial Intelligence, Vol. 1456 (Springer, Berlin, 1998) pp. 1-12.

    Google Scholar 

  35. J. VanderHeide and N.S.V. Rao, Terrain coverage of an unknown room by an autonomous mobile robot, Technical report ORNL/TM-13117, Oak Ridge National Laboratory, Oak Ridge, TN (1995).

    Google Scholar 

  36. I. A. Wagner and A. M. Bruckstein, Cooperative Cleaners -- A Study in Ant-Robotics in Communications, Computation, Control, and Signal Processing: A Tribute to Thomas Kailath (Kluwer Academic, Dordrecht, 1997) pp. 289-308.

    Google Scholar 

  37. I.A. Wagner, M. Lindenbaum and A.M. Bruckstein, Smell as a computational resource -- a lesson we can learn from the ant, in: ISTCS'96 (1996) pp. 219-230.

  38. I.A. Wagner, M. Lindenbaum and A.M. Bruckstein, Efficiently searching a dynamic graph by a smell-oriented vertex process, Ann. Math. Artif. Intell. 24 (1998) 211-223.

    Article  MATH  MathSciNet  Google Scholar 

  39. I.A. Wagner, M. Lindenbaum and A.M. Bruckstein, Distributed covering by ant-robots using evaporating traces, IEEE Trans. Robotics Autom. 15(5) (1999) 918-933.

    Article  Google Scholar 

  40. I.A. Wagner, M. Lindenbaum and A.M. Bruckstein, ANTS: Agents, networks, trees, and subgraphs, Future Generation Computer Systems, Special issue on Ant Colony Optimization (2000).

  41. I.A. Wagner, M. Lindenbaum and A.M. Bruckstein, MAC vs. PC -- determinism and randomness as complementary approaches to robotic exploration of continuous unknown domains, Internat. J. Robotics Res. 19(1) (2000) 12-31.

    Article  Google Scholar 

  42. A. Zelinsky, R.A. Jarvis, J.C. Byrne and S. Yuta, Planning paths of complete coverage of an unstructured environment by a mobile robot, in: Proceedings of International Conference on Advanced Robotics, Tokyo, Japan (November 1993) pp. 533-538.

Download references

Author information

Authors and Affiliations

  1. Carnegie Mellon University, Pittsburgh, PA, 15213, USA

    Howie Choset

Authors
  1. Howie Choset
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Choset, H. Coverage for robotics – A survey of recent results. Annals of Mathematics and Artificial Intelligence 31, 113–126 (2001). https://doi.org/10.1023/A:1016639210559

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1016639210559

Search

Navigation