Inspection of ship hulls and marine structures using autonomous underwater vehicles has emerged as a unique and challenging application of robotics. The problem poses rich questions in physical design and operation, perception and navigation, and planning, driven by difficulties arising from the acoustic environment, poor water quality and the highly complex structures to be inspected. In this paper, we develop and apply algorithms for the central navigation and planning problems on ship hulls. These divide into two classes, suitable for the open, forward parts of a typical monohull, and for the complex areas around the shafting, propellers and rudders. On the open hull, we have integrated acoustic and visual mapping processes to achieve closed-loop control relative to features such as weld-lines and biofouling. In the complex area, we implemented new large-scale planning routines so as to achieve full imaging coverage of all the structures, at a high resolution. We demonstrate our approaches in recent operations on naval ships.
AcarEChosetHRizziAAtkarPHullD (2002) Morse decompositions for coverage tasks. International Journal of Robotics Research21(4): 331–344.
2.
ApplegateDCookWRoheA (2003) Chained Lin–Kernighan for large traveling salesman problems. INFORMS Journal of Computing15(1): 82–92.
3.
AtkarPGreenfieldAConnerDChosetHRizziA (2005) Uniform coverage of automotive surface patches. International Journal of Robotics Research24(11): 883–898.
4.
BaileyTDurrant-WhyteH (2006) Simultaneous localization and mapping (SLAM): Part II. Robotics & Automation Magazine13(3): 108–117.
5.
BallardRStagerLMasterDYoergerDMindellDWhitcombL. (2002) Iron age shipwrecks in deep water off Ashkelon, Israel. American Journal of Archaeology106(2): 151–168.
6.
BelcherEMatsuyamaBTrimbleG (2001) Object identification with acoustic lenses. In: IEEE/MTS OCEANS Conference and Exhibition, Honolulu, USA, 5–8 November 2001, pp. 6–11. Piscataway, USAIEEE Press.
7.
BelcherEHanotWBurchJ (2002) Dual-frequency identification sonar (DIDSON). In: 2002 International Symposium on Underwater Technology, Tokyo, Japan, 16–19 April 2002, pp. 187–192Piscataway: IEEE Press.
8.
BiberPStrasserW (2003) The normal distributions transform: a new approach to laser scan matching. In: IEEE/RSJ International Conference Intelligent Robots and Systems, Las Vegas, USA, 27–31 October 2003vol. 3, pp. 2743–2748. Piscataway: IEEE Press.
9.
CarvalhoASagriloLSilvaIRebelloJCarnevalR (2003) On the reliability of an automated ultrasonic system for hull inspection in ship-based oil production units. Applied Ocean Research25: 235–241.
10.
ChengPKellerJKumarV (2008) Time-optimal UAV trajectory planning for 3D urban structure coverage. In: IEEE/RSJ International Conference Intelligent Robots and Systems, Nice, France, 22–26 September 2008 pp. 2750–2757. Piscataway: IEEE Press.
11.
ChosetH (2000) Coverage of known spaces: The boustrophedon cellular decomposition. Autonomous Robots9(3): 247–253.
12.
ChosetH (2001) Coverage for robotics — a survey of recent results. Annals of Mathematics and Artificial Intelligence31: 113–26.
13.
ChristofidesN (1976) Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report CS-93-13, Carnegie Mellon University, USA.
14.
CignoniPCorsiniMRanzugliaG (2008) MeshLab: An open-source 3D mesh processing system. ERCIM News73: 45–46.
15.
ClineDJeschkeSWhiteKRazdanAWonkaP (2009) Dart throwing on surfaces. Computer Graphics Forum28(4): 1217–1226.
16.
CurlessBLevoyM (1996) A volumetric method for building complex models from range images. In: 23rd Annual Conference Computer Graphics and Interactive Techniques, New Orleans, USA, 4–9 August 1996, pp. 303–312. New York: ACM Press.
17.
D’AmaddioEHarrisSBergeronESlateE (2001) Method and apparatus for inspecting a submerged structure. US Patent 6317387.
18.
DannerTKavrakiL (2000) Randomized planning for short inspection paths. In: IEEE International Conference Robotics and Automation, San Francisco, USA, 24–28 April 2000, vol. 2, pp. 971–976. Piscataway: IEEE Press.
19.
Durrant-WhyteHBaileyT (2006) Simultaneous localization and mapping: Part I. IEEE Robotics & Automation Magazine13(2): 99–110.
20.
EnglotBHoverF (2010) Inspection planning for sensor coverage of 3D marine structures. In: IEEE/RSJ International Conference Intelligent Robots and Systems, Taipei, Taiwan, 18–22 October 2010, pp. 4412–4417. Piscataway: IEEE Press.
21.
EnglotBHoverF (2011) Planning complex inspection tasks using redundant roadmaps. In: International Symposium on Robotics Research, Flagstaff, USA. 28 August–1 September 2011. New York: Springer.
22.
EnglotBHoverF (2012) Sampling-based coverage path planning for inspection of complex structures. In: 22nd International Conference Automated Planning and Scheduling, Sao Paulo, Brazil, 25–29 June 2012, pp. 29–37, Palo Alto, CA: AAAI Press.
23.
EusticeRMPizarroOSinghH (2008) Visually augmented navigation for autonomous underwater vehicles. IEEE Journal of Oceanic Engineering33(2): 103–122.
24.
Gonzales-BañosHLatombeJC (2001) A randomized art gallery algorithm for sensor placement. In: ACM Symposium on Computational Geometry, Medford MA, USA, 3–5 June 2001, pp. 232–240. New York: ACM Press.
25.
HarrisSSlateE (1999) Lamp Ray: Ship hull assessment for value, safety, and readiness. In: IEEE/MTS OCEANS Conference and Exhibition, Seattle, USA, 13–16 September 1999, vol. 1, pp. 493–500. Piscataway: IEEE Press.
26.
HollingerGEnglotBHoverFMitraUSukhatmeG (2012) Uncertainty-driven view planning for underwater inspection. In: IEEE International Conference Robotics and Automation, St Paul, USA, 14–18 May 2012, pp. 4884–4891. Piscataway: IEEE Press.
27.
HoppeHDeRoseTDuChampTMcDonaldJStuetzleW (1992) Surface reconstruction from unorganized points. In: 19th Annual Conference Computer Graphics and Interactive Techniques (ed ThomasJ J), Chicago, USA, 26–31 July 1992, pp. 71–78. New York: ACM Press.
28.
HoverFVaganayJElkinsMWillcoxSPolidoroVMorashJ. (2007) A vehicle system for autonomous relative survey of in-water ships. Marine Technology Society Journal41(2): 44–55.
29.
HuangW (2001) Optimal line-sweep-based decompositions for coverage algorithms. In: IEEE International Conference Robotics and Automation, Seoul, South Korea, 21–26 May 2001, vol. 1, pp. 27–32. Piscataway: IEEE Press.
30.
HuangHLiDZhangHAscherUCohen-OrD (2009) Consolidation of unorganized point clouds for surface reconstruction. ACM Transactions on Graphics28(5): 176.
31.
JohannssonHKaessMEnglotBHoverFLeonardJJ (2010) Imaging sonar-aided navigation for autonomous underwater harbor surveillance. In: IEEE/RSJ International Conference Intelligent Robots and Systems, Taipei, Taiwan, 18–22 October 2010, pp. 4396–4403. Piscataway: IEEE Press.
32.
JohnsonD (1974) Approximation algorithms for combinatorial problems. Journal of Computer and System Sciences9: 256–278.
33.
KaessMRanganathanADellaertF (2008) iSAM: Incremental smoothing and mapping. IEEE Transactions on Robotics24(6): 1365–1378.
34.
KaessMDellaertF (2009) Covariance recovery from a square root information matrix for data association. Robotics and Autonomous Systems57: 1198–1210.
KaessMJohannssonHRobertsRIlaVLeonardJJDellaertF (2012) iSAM2: Incremental smoothing and mapping using the Bayes tree. International Journal of Robotics Research31: 217–236.
37.
KaramanSFrazzoliE (2011) Sampling-based algorithms for optimal motion planning. International Journal of Robotics Research30(7): 846–894.
38.
KazhdanMBolithoMHoppeH (2006) Poisson surface reconstruction. In: 4th Eurographics Symposium on Geometry Processing, Cagliari, Italy, 26–28 June 2006, pp. 61–70. Geneva: Eurographics.
39.
KimAEusticeRM (2009) Pose-graph visual SLAM with geometric model selection for autonomous underwater ship hull inspection. In: IEEE/RSJ International Conference Intelligent Robots and Systems, St Louis, USA, 11–15 October 2009, pp. 1559–1565. Piscataway: IEEE Press.
40.
KocakDDalgleishFCaimiFSchechnerY (2008) A focus on recent developments and trends in underwater imaging. Marine Technology Society Journal42(1): 52–67.
41.
KuffnerJLaValleS (2000) RRT-connect: An efficient approach to single-query path planning. In: IEEE International Conference Robotics and Automation, San Francisco, USA, 24–28 April 2000, vol. 2, pp. 995–1001Piscataway: IEEE Press.
42.
LoopC (1987) Smooth subdivision surfaces based on triangles. MSc thesis, University of Utah, USA.
43.
LoweD (2004) Distinctive image features from scale-invariant keypoints. International Journal of Computer Vision60(2): 91–110.
44.
MenegaldoLSantosMFerreiraGSiqueiraRMoscatoL (2008) SIRUS: A mobile robot for floating production storage and offloading (FPSO) ship hull inspection. In: International Workshop on Advanced Motion Control, Trento, Italy, 26–28 March 2008, pp. 27–32. Piscataway: IEEE Press.
45.
NegahdaripourSFiroozfamP (2006) An ROV stereovision system for ship hull inspection. IEEE Journal of Oceanic Engineering31(3): 551–546.
46.
NegahdaripourSSekkatiHPirsiavashH (2009) Opti-acoustic stereo imaging: On system calibration and 3-D target reconstruction. IEEE Transactions on Image Processing18(6): 1203–1214.
47.
OldsRB (2003) Marine mammals systems in support of force protection. In: SSC San Diego Biennial Review 2003. San Diego: Space and Naval Warfare Systems Center, ch. 3, pp. 131–135
48.
RidaoPCarrerasMRibasDGarciaR (2010) Visual inspection of hydroelectric dams using an autonomous underwater vehicle. Journal of Field Robotics27(6): 759–778.
49.
SahaMRoughgardenTLatombeJCSanchez-AnteG (2006) Planning tours of robotic arms among partitioned goals. International Journal of Robotics Research25(3): 207–223.
50.
ShermanJDavisROwensWValdesJ (2001) The autonomous underwater glider ‘Spray’. IEEE Journal of Oceanic Engineering26(4): 437–446.
51.
ShermerT (1992) Recent results in art galleries. Proceedings of the IEEE80(9): 1384–1399.
52.
TrimbleGBelcherE (2002) Ship berthing and hull inspection using the Cetus-II AUV and MIRIS high-resolution sonar. In: IEEE/MTS OCEANS Conference and Exhibition, Biloxi, USA, 29–31 October 2002, vol. 2, pp. 1172–1175. Piscataway: IEEE Press.
53.
VaganayJElkinsMWillcoxSHoverFDamusRDessetS. (2005) Ship hull inspection by hull-relative navigation and control. In: IEEE/MTS OCEANS Conference and Exhibition, Washington DC, USA, 18–23 September 2005, vol. 1, pp. 761–766. Piscataway: IEEE Press.
54.
VaganayJElkinsMEspositoDO’HalloranWHoverFKokkoM (2006) Ship hull inspection with the HAUV: US Navy and NATO demonstrations results. In: IEEE/MTS OCEANS Conference and Exhibition, Boston, USA, 18–21 September 2006, pp. 1–6. Piscataway: IEEE Press.
55.
VaganayJGurfinkelLElkinsMJankinsDShurnK (2009) Hovering autonomous underwater vehicle — system design improvements and performance evaluation results. In: 30th International Symposium on Unmanned Untethered Submarine Technology, Durham, USA, 23–26 August 2009. Piscataway: IEEE Press.
56.
WalterMHoverFLeonardJJ (2008) SLAM for ship hull inspection using exactly sparse extended information filters. In: IEEE International Conference Robotics and Automation, Pasadena, USA, 19–23 May 2008, pp. 1463–1470. Piscataway: IEEE Press.
57.
WebbDSimonettiPJonesC (2001) SLOCUM: An underwater glider propelled by environmental energy. IEEE Journal of Oceanic Engineering26(4): 447–452.
58.
WeissL (2011) Autonomous robots in the fog of war. IEEE Spectrum48(8): 30–36.
59.
WeyrichTPaulyMKeiserRHeinzleSScandellaSGrossM (2004) Post-processing of scanned 3D surface data. In: IEEE Eurographics Symposium on Point-Based Graphics, Zurich, Switzerland, 2–4 June 2004, pp. 85–94. Geneva: Eurographics.
YoergerDJakubaMBradleyABinghamB (2007) Techniques for deep sea near bottom survey using an autonomous underwater vehicle. Springer Tracts in Advanced Robotics28: 416–429.
62.
YuhJ (2000) Design and control of autonomous underwater robots: A survey. Autonomous Robots8: 7–24.
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
