Non-revisiting Coverage Task with Minimal Discontinuities for Non-redundant Manipulators

Tong Yang (Zhejiang University); Jaime Valls Miro (University of Technology Sydney); Yue Wang (Zhejiang University); Rong Xiong (Zhejiang University)


A theoretically complete solution to the optimal Non-revisiting Coverage Path Planning (NCPP) problem of any arbitrarily-shaped object with a non-redundant manipulator is proposed in this work. Given topological graphs of surface cells corresponding to feasible and continuous manipulator configurations, the scheme is aimed at ensuring optimality with respect to the number of surface discontinuities, and extends the existing provable solution attained for simply-connected configuration cell topologies to any arbitrary shape. This is typically classified through their genus, or the number of "holes" which appear increasingly as configurations are further constrained with the introduction of additional metrics for the task at hand, e.g., manipulability thresholds, clearance from obstacles, end-effector orientations, tooling force/torque magnitudes, etc. The novel contribution of this paper is to show that no matter what the resulting topological shapes from such quality cell constraints may be, the graph is finitely solvable, and a multi-stage iterative solver is designed to find all such optimal solutions.

Live Paper Discussion Information

Start Time End Time
07/14 15:00 UTC 07/14 17:00 UTC

Virtual Conference Presentation

Supplementary Video

Paper Reviews

Review 1

Contribution: The main contribution of this paper lies in the detailed analysis on ways to convert genus 1, 2, n continuous sets into genus 0 sets. The paper shows that there is a finite number of ways of doing so, even though the number is exponential to the number of edges and sets. The analysis of converting genus 1 set into genus 0 sets is the most interesting and significant one while the cases of decomposing sets with genus 2 & n are straightforward. Quality: While the analyses provided in this paper is intriguing, the end results are not very exiting as the proposed method is essentially a brute force method and has the same time complexity as integer programming. The results shown in the figures 2, 10~13 are interesting and has practical significance but they do not seem to connect well with the analyses of the proposed method. The cutting paths connecting the "holes" to the outer boundary do not seem to play any important role in these examples. The holes seem to be simply removed because they are covered by other sets. The experiments also provide no comparison and do not report any statistical information about the proposed method. Decompositions from these examples are also not demonstrated. Clarity: The paper have much room for improvement in terms of the presentation. Several key terms are used without (clear) definition, including U_m in Eq. 6, and "cutting paths". All images are very small and the tiny text are not really legible. Many figures, such as fig 3, fig 6, fig 7 are not well explained. Significance: This work is significant as the first work that deals with more practical and complex surfaces. The case analyses investigated in this paper are of theoretical interest. However, the proposed method based on these analyses did not seem to provide any practical advantages over integer programming based methods. The paper should provide more comprehensive experiments to demonstrate the benefits of converting high genus cells into genus 0 cells.