[Review] Survey of Coverage Path Planning

February 28, 2019 ยท 4 minute read

Article Review 28-02-2019

A Survey On Coverage Path Planning

Enric Galceran, Marc Carreras, Robotics and Autonomous systems 61, no. 12(2013):1258-1276

Article was presented in class here

Aims of the paper

To provide a review of the most successful methods in the last decade. Provide a comprehensive review of most recent breakthroughs as well as discussing applications of the technology. The authors also aim for this work to be a starting point for new researchers in the field of Coverage Path Planning and discusses and presents the key concepts within.

Paper Summary

This paper presents a comprehensive review of many of the seminal papers in the field since the 1990s. This is the only survey paper since the previous paper by H.Choset in 2001. It begins by providing a definition for Coverage Path Planning(CPP) and discussing several problem which illustrate some of the major issues within the CPP field. These include:

  1. Covering Salesman Problem - optimally visiting the neighbourhood of each city
  2. Lawnmower Problem - optimal path to cut all the grass in a garden
  3. Piano-Mover Problem - collision free path planning
  4. Art-Gallery Problem - where do we place guards such that all areas are visible
  5. Watchman Problem - what is the shortest route of one guard where all areas are visible

A taxonomy/classification of off-line/ on-line and heuristic/ complete is adopted from the previous survey paper with the addition of coverage environment and application. The papers are then broken-down by both category of methodology and application:

  • Classical Cellular Decomposition/ Voronoi CPP
  • Natural Landmark CPP
  • Contact Sensing CPP
  • Grid-Based Coverage
  • Graph-Based Coverage
  • 3D Coverage
  • Optimal Coverage (offline)
  • Coverage under uncertainty
  • Multi-Robot Coverage

The first section offers historical perspective on the problem and explains core concepts such as Trapezoidal and Boustrophedon decomposition. The following chapters then go on to cover the rest of the work done in the past decade. Each section is preceded by a short summary of the concepts and mathematical tools required to understand the papers, with a short summary of each paper along with a fair analysis of the results. Many diagrams have also been included for clarity of explanation.

The conclusion then summarises the pros and cons of each method presented (along with a very succinct table) and wraps up with some short ideas for future work.

Paper Review

All in all a decent paper. The style of the paper reads very much like a textbook chapter on Coverage Path Planning with the concise and thought-through explanations of the methods presented in each section. For me personally, this was very useful as it gave me a very broad understanding of the field of CPP, and prepared me with the base concepts to do my own reading. In my opinion, it has therefore indeed met its aims of being a good starting point for new researchers in the field. This paper also provides what feels like a very comprehensive review of most of the major works up to 2013 with a variety of papers of different techniques and applications. The breadth of techniques and methodologies being experimented with was a surprise to me. The fair appraisal and criticism of each paper is also a very valuable resource as it allows the reader to quickly identify the problems which still remain in the field. Finally the liberal use of tables and figures was very beneficial for indexing and conveying the information.

However, I was disappointed to find that no summary or analysis was conducted to provide insights into the research and direction of this field. Having read so many papers as part of this survey, I feel that it would be most beneficial to provide such a commentary as now the paper is literally a summary of all the papers. I also get the feeling that this paper is - in effect - a literary review section of the author’s own works as many of the works seen are related to the author’s field of autonomous underwater vehicles, and there perhaps lacks material from similar problem areas such as the sensor placement problem and the exploration problem.

Nevertheless, I do indeed recommend this paper to any new researcher in this field as it does give a good foundation for understanding newer works in CPP. Although outdated, it still provides useful insight to the state of the art at the time. I do not recommend this paper if you are already in the field as it does not provide any new insight into the state of the field itself.