To support autonomous, in-water inspection of a ship hull, we propose and implement new techniques for coverage path planning over complex 3D structures. Our main contribution is a comprehensive methodology for sampling-based design of inspection routes, including an algorithm for planning, an algorithm for smoothing, and an analysis of probabilistic completeness. The latter two outcomes are the first of their kind in the area of coverage planning. Our algorithms give high-quality solutions over expansive structures, and we demonstrate this with experiments in the laboratory and on a 75 m Coast Guard cutter.
AcarEChosetHRizziAAtkarPHullD (2002) Morse decompositions for coverage tasks. The International Journal of Robotics Research21(4): 331–344.
2.
AkgunBStilmanM (2011) Sampling heuristics for optimal motion planning in high dimensions. In: Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, San Francisco, CA, pp. 2640–2645.
3.
AlterovitzRPatilSDerbakovaA (2011) Rapidly-exploring roadmaps: Weighing exploration vs. refinement in optimal motion planning. In: Proceedings IEEE International Conference on Robotics and Automation, Shanghai, China, pp. 3706–3712.
4.
ApplegateDBixbyRChvatalVCookW (2006) The Traveling Salesman Problem: A Computational Study. Princeton, NJ: Princeton University Press.
5.
ApplegateDCookWRoheA (2003) Chained Lin-Kernighan for large traveling salesman problems. INFORMS Journal on Computing15(1): 82–92.
6.
AtkarPChosetHRizziAAcarE (2001) Exact cellular decomposition of closed orientable surfaces embedded in ℜ3. In: Proceedings IEEE International Conference on Robotics and Automation, vol. 1, pp. 699–704.
7.
AtkarPGreenfieldAConnerDChosetHRizziA (2005a) Hierarchical segmentation of surfaces embedded in ℜ3 for auto-body painting. In: Proceedings IEEE International Conference on Robotics and Automation, pp. 572–577.
8.
AtkarPGreenfieldAConnerDChosetHRizziA (2005b) Uniform coverage of automotive surface patches. The International Journal of Robotics Research24(11): 883–898.
9.
BelcherEHanotWBurchJ (2002) DIDSON: Dual frequency identification sonar. In: Proceedings of the International Symposium on Underwater Technology, Tokyo, Japan, pp. 187–192.
10.
BeslPMcKayN (1992) A method for registration of 3-D shapes. IEEE Transactions on Pattern Analysis and Machine Intelligence14(2): 239–256.
11.
BlaerPAllenP (2009) View planning and automated data acquisition for three-dimensional modeling of complex sites. Journal of Field Robotics26(11–12): 865–891.
12.
BrönnimannHGoodrichM (1995) Almost optimal set covers in finite VC-dimension. Discrete and Computational Geometry14(1): 463–479.
13.
BülowHBirkA (2011) Spectral registration of noisy sonar data for underwater 3D mapping. Autonomous Robots30(3): 307–331.
14.
CastellaniUFusielloAMurinoV (2002) Registration of multiple acoustic range views for underwater scene reconstruction. Computer Vision and Image Understanding87(1–3): 78–89.
15.
ChengPKellerJKumarV (2008) Time-optimal UAV trajectory planning for 3D urban structure coverage. In: Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 2750–2757.
16.
ChinWNtafosS (1988) Optimum watchman routes. Information Processing Letters28(1): 39–44.
17.
ChosetH (2001) Coverage for robotics - a survey of recent results. Annals of Mathematics and Artificial Intelligence31: 113–126.
18.
ChosetHPignonP (1997) Coverage path planning: the boustrophedon decomposition. In: Proceedings International Conference on Field Service Robotics
19.
ChristofidesN (1976) Worst-case Analysis of a New Heuristic for the Traveling Salesman Problem. Technical Report CS-93-13, Carnegie Mellon University.
20.
ChvatalV (1979) A greedy heuristic for the set-covering problem. Mathematics of Operations Research4(3): 233–235.
21.
CurrentJSchillingD (1989) The covering salesman problem. Transportation Science23(3): 208–213.
22.
DannerTKavrakiL (2000) Randomized planning for short inspection paths. In: Proceedings IEEE International Conference on Robotics and Automation, vol. 2, pp. 971–976.
23.
DobsonAKrontirisABekrisK (2012) Sparse roadmap spanners. In: Proceedings of the Workshop on the Algorithmic Foundations of Robotics, Cambridge, MA.
24.
EastonKBurdickJ (2005) A coverage algorithm for multi-robot boundary inspection. In: Proceedings IEEE International Conference on Robotics and Automation, pp. 727–734.
25.
EnglotB (2012) Sampling-Based Coverage Path Planning for Complex 3D Structures. PhD thesis, Massachusetts Institute of Technology.
26.
EnglotBHoverF (2011) Planning complex inspection tasks using redundant roadmaps. In: Proceedings International Symposium on Robotics Research, Flagstaff, AZ.
27.
EnglotBHoverF (2012) Sampling-based coverage path planning for inspection of complex structures. In: Proceedings of the International Conference on Automated Planning and Scheduling, Sao Paulo, Brazil, pp. 29–37.
28.
ErdemUSclaroffS (2006) Automated camera layout to satisfy task-specific and floor plan-specific coverage requirements. Computer Vision and Image Understanding103(3): 156–169.
29.
FazliPDavoodiAPasquierPMackworthA (2010) Complete and robust cooperative robot area coverage with limited range. In: Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, Taipei, Taiwan, pp. 5577–5582.
30.
FischettiMGonzalezJTothP (1997) A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Operations Research45(3): 378–394.
31.
FuscoGGuptaH (2010) ϵ-net approach to sensor k-coverage. EURASIP Journal on Wireless Communications and Networking2010: 12.
32.
GabrielyYRimonE (2001) Spanning-tree based coverage of continuous areas by a mobile robot. Annals of Mathematics and Artificial Intelligence31(1–4): 77–98.
33.
Gonzalez-BañosHLatombeJC (1998) Planning robot motions for range-image acquisition and automatic 3D model construction. In: Proceedings of the AAAI Fall Symposium Series, Integrated Planning for Autonomous Agent Architectures, Orlando, FL, pp. 23–25.
34.
Gonzalez-BañosHLatombeJC (2001) A randomized art gallery algorithm for sensor placement. In: Proceedings of the 17th Annual ACM Symposium on Computational Geometry, pp. 232–240.
35.
HausslerDWelzlE (1987) Epsilon-nets and simplex range queries. Discrete and Computational Geometry2(1): 127–151.
36.
HochbaumD (1982) Approximation algorithms for the set covering and vertex cover problems. SIAM Journal on Computing11(3): 555–556.
37.
HollingerGEnglotBHoverFMitraUSukhatmeG (2013) Active planning for underwater inspection and the benefit of adaptivity. The International Journal of Robotics Research32(1): 3–18.
38.
HörsterELienhartR (2006) On the optimal placement of multiple visual sensors. In: ACM International Workshop on Video Surveillance and Sensor Networks, Santa Barbara, CA, pp. 111–120.
39.
HoverFEusticeRKimA. (2012) Advanced perception, navigation, and planning for autonomous in-water ship hull inspection. The International Journal of Robotics Research31(12): 1445–1464.
40.
HoverFVaganayJElkinsM. (2007) A vehicle system for autonomous relative survey of in-water ships. Marine Technical Society Journal41(2): 44–55.
41.
HuangW (2001) Optimal line-sweep-based decompositions for coverage algorithms. In: Proceedings IEEE International Conference on Robotics and Automation, Seoul, South Korea, pp. 27–32.
42.
IslerVKannanSDaniilidisK (2004a) Sampling based sensor-network deployment. In: Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 1780–1785.
43.
IslerVKannanSDaniilidisK (2004b) VC-dimension of exterior visibility. IEEE Transactions on Pattern Analysis and Machine Intelligence26(5): 667–671.
44.
JohnsonD (1974) Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences9: 256–278.
45.
KaramanSFrazzoliE (2011) Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research30(7): 846–894.
46.
KavrakiLKolountzakisMLatombeJC (1998) Analysis of probabilistic roadmaps for path planning. IEEE Transactions on Robotics and Automation14(1): 166–171.
47.
KazazakisGArgyrosA (2002) Fast positioning of limited-visibility guards for the inspection of 2D workspaces. In: Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, Lausanne, Switzerland, pp. 2843–2848.
KuffnerJLaValleS (2000) RRT-connect: An efficient approach to single-query path planning. In: Proceedings IEEE International Conference on Robotics and Automation, volume 2, pp. 995–1001.
50.
KurabayashiDOtaJAraiTYoshidaE (1996) Cooperative sweeping by multiple mobile robots. In: Proceedings IEEE International Conference on Robotics and Automation, Minneapolis, MN, pp. 1744–1749.
51.
LamirauxFLaumondJP (1996) On the expected complexity of random path planning. In: Proceedings IEEE International Conference on Robotics and Automation, vol. 4, pp. 3014–3019.
52.
LaValleSKuffnerJ (2001) Randomized kinodynamic planning. The International Journal of Robotics Research20(5): 378–400.
53.
LeonardJHowJTellerS. (2008) A perception-driven autonomous urban vehicle. Journal of Field Robotics25(10): 727–774.
54.
LinSKernighanB (1973) An effective heuristic for the traveling-salesman problem. Operations Research21(2): 498–516.
55.
LovaszL (1975) On the ratio of optimal integral and fractional covers. Discrete Mathematics13(4): 383–390.
56.
MannadiarRRekleitisI (2010) Optimal coverage of known arbitrary environments. In: Proceedings IEEE International Conference on Robotics and Automation, Anchorage, AK, pp. 5525–5530.
57.
MarbleJBekrisK (2011) Asymptotically near-optimal is good enough for motion planning. In: Proceedings International Symposium on Robotics Research, Flagstaff, AZ.
58.
NiederreiterH (1992) Random Number Generation and Quasi-Monte Carlo Methods. Philadelphia, PA: Society for Industrial and Applied Mathematics.
59.
O’RourkeJ (1987) Art Gallery Theorems and Algorithms. Oxford, UK: Oxford University Press.
60.
ReifJ (1979) Complexity of the mover’s problem and generalizations. In: Proceedings of the IEEE Symposium on the Foundations of Computer Science, pp. 421–427.
61.
RekleitisILee-ShueVNewAChosetH (2004) Limited-communication, multi-robot team based coverage. In: ProceedingsIEEE International Conference on Robotics and Automation, New Orleans, LA, pp. 3462–3468.
62.
SahaMSanchez-AnteGLatombeJC (2003) Planning multi-goal tours for robot arms. In: Proceedings IEEE International Conference on Robotics and Automation, Taipei, Taiwan, pp. 3797–3803.
63.
SahaMSanchez-AnteGRoughgardenTLatombeJC (2006) Planning tours of robotic arms among partitioned goals. The International Journal of Robotics Research25(3): 207–223.
64.
SanchezGLatombeJC (2002) Using a PRM planner to compare centralized and decoupled planning for multi-robot systems. In: Proceedings IEEE International Conference on Robotics and Automation, Washington, DC, pp. 2112–2118.
65.
ShenSMichaelNKumarV (2011) Autonomous multi-floor indoor navigation with a computationally constrained MAV. In: Proceedings IEEE International Conference on Robotics and Automation, Shanghai, China, pp. 20–25.
66.
SpitzSRequichaA (2000) Multiple-goals path planning for coordinate measuring machines. In: Proceedings IEEE International Conference on Robotics and Automation, San Francisco, CA, pp. 2322–2327.
67.
VaganayJElkinsMWilcoxS. (2005) Ship hull inspection by hull-relative navigation and control. In: Proceedings IEEE/ MTS OCEANS Conference and Exhibition, vol. 1, Washington, DC, pp. 761–766.
68.
VapnikVChervonenkisA (1971) On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and its Applications16(2): 264–279.
69.
WangPKrishnamurtiRGuptaK (2007) View planning problem with combined view and traveling cost. In: Proceedings IEEE International Conference on Robotics and Automation, Rome, Italy, pp. 711–716.
70.
WangPKrishnamurtiRGuptaK (2010) Generalized watchman route problem with discrete view cost. International Journal of Computational Geometry and Applications20(2): 119–146.
71.
YaoYChenCHAbidiBPageDKoschanAAbidiM (2010) Can you see me now? Sensor positioning for automated and persistent surveillance. IEEE Transactions on Systems, Man, and Cybernetics – Part B: Cybernetics40(1): 101–115.
72.
ZelinskyAJarvisRByrneJYutaS (1993) Planning paths of complete coverage of an unstructured environment by a mobile robot. In: Proceedings of the International Conference on Advanced Robotics, Tokyo, Japan, pp. 533–538.
