Planning Complex Inspection Tasks Using Redundant Roadmaps

详细信息    查看全文

• 刊名：Springer Tracts in Advanced Robotics
• 出版年：2017
• 出版时间：2017
• 年：2017
• 卷：100
• 期：1
• 页码：327-343
• 全文大小：938 KB
• 参考文献：1.D. Applegate, W. Cook, A. Rohe, Chained Lin-Kernighan for large traveling salesman problems. INFORMS J. Comput. 15(1), 82–92 (2003)MathSciNet CrossRef MATH
  2.D. Applegate, R. Bixby, V. Chvatal, W. Cook, The Traveling Salesman Problem: a Computational Study (Princeton University Press, Princeton, 2006)MATH
  3.E.M. Arkin, M.M. Halldorsson, R. Hassin, Approximating the tree and tour covers of a graph. Inform. Process. Lett. 47, 275–282 (1993)MathSciNet CrossRef MATH
  5.P. Atkar, A.L. Greenfield, D.C. Conner, H. Choset, A. Rizzi, Uniform coverage of automotive surface patches. Int. J. Robot. Res. 24(11), 883–898 (2005)CrossRef
  6.P. Atkar, A.L. Greenfield, D.C. Conner, H. Choset, A. Rizzi. Hierarchical segmentation of surfaces embedded in ℜ^{3 for auto-body painting, in Proceedings of IEEE International. Conference on Robotics and Automation (2005), pp. 572–577
  7.P.S. Blaer, P.K. Allen, View planning and automated data acquisition for three-dimensional modeling of complex sites. J. Field Robot. 26(11–12), 865–891 (2009)CrossRef
  4.P. Cheng, J. Keller, V. Kumar, Time-optimal UAV trajectory planning for 3D urban structure coverage, in Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (2008), pp. 2750–2757
  8.H. Choset, P. Pignon, Coverage path planning: the boustrophedon decomposition, in Proceedings of International Conference on Field and Service Robotics (1997)
  9.H. Choset, Coverage for robotics—a survey of recent results. Ann. Math. Artif. Intell. 31, 113–126 (2001)CrossRef MATH
  10.H. Choset, K.M. Lynch, S. Hutchinson, G. Kantor, W. Burgard, L.E. Kavraki, S. Thrun, Principles of Robot Motion: Theory, Algorithms, and Applications (MIT Press, Cambridge, 2005)MATH
  11.N. Christofides, Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report CS-93-13, Carnegie Mellon University (1976)
  12.J.R. Current, D.A. Schilling, The Covering Salesman Problem. Transp. Sci. 23(3), 208–213 (1989)MathSciNet CrossRef MATH
  13.T. Danner, L. Kavraki, Randomized planning for short inspection paths, in Proceedings of IEEE International Conference on Robotics and Automation, vol 2 (2000), pp. 971–976
  14.K. Easton, J. Burdick, A coverage algorithm for multi-robot boundary inspection, in Proceedings of IEEE International Conference on Robotics and Automation (2005), pp. 727–734
  15.P. Fazli, A. Davoodi, P. Pasquier, A.K. Mackworth, Complete and robust cooperative robot area coverage with limited range, in Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (2010), pp. 5577–5582
  16.M. Fischetti, J.J.S. Gonzalez, P. Toth, A branch-and-cut algorithm for the symmetric generalized traveling salesman problem. Oper. Res. 45(3), 378–394 (1997)MathSciNet CrossRef MATH
  17.M. Gendreau, G. LaPorte, F. Semet, The covering tour problem. Oper. Res. 45(4), 568–576 (1997)MathSciNet CrossRef MATH
  18.H. Gonzalez-Baños, J.-C. Latombe, Planning robot motions for range-image acquisition and automatic 3D model construction, in Proceedings of AAAI Fall Symposium (1998)
  19.H. Gonzalez-Baños, J.-C. Latombe, A randomized art gallery algorithm for sensor placement, in Proceedings of 17th Annual ACM Symposium on Computational Geometry (2001), pp. 232–240
  20.D.S. Hochbaum, Approximation algorithms for the set covering and vertex cover problems. 21.SIAM J. Comput. 11(3) (1982)
  21.F. Hover et al., A vehicle system for autonomous relative survey of in-water ships. J. Mar. Technol. Soc. 41(2), 44–55 (2007)CrossRef
  22.D.S. Johnson, Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9, 256–278 (1974)MathSciNet CrossRef MATH
  23.M. Kazhdan, M. Bolitho, H. Hoppe, Poisson surface reconstruction, in Proceedings of Fourth Eurographics Symposium on Geometry (2006)
  24.S. LaValle, J. Kuffner, Rapidly-exploring random trees: progress and prospects, in Proceedings of Workshop on the Algorithmic Foundations of Robotics (2000), pp. 293–308
  25.S. LaValle, Planning Algorithms (Cambridge University Press, Cambridge, UK, 2006)CrossRef MATH
  26.Y.N. Lien, E. Ma, Transformation of the generalized traveling salesman problem into the standard traveling salesman problem. Inf. Sci. 74, 177–189 (1993)MathSciNet CrossRef MATH
  27.S. Lin, B.W. Kernighan, An effective heuristic algorithm for the traveling salesman problem. Oper. Res. 21(2), 498–516 (1973)MathSciNet CrossRef MATH
  28.L. Lovasz, On the ratio of optimal integral and fractional covers. Discrete Math. 13, 383–390 (1975)MathSciNet CrossRef MATH
  29.C.E. Noon, J.C. Bean, An efficient transformation of the generalized traveling salesman problem. Technical Report 89-36, Department of Industrial and Operations Engineering (The University of Michigan, Ann Arbor, 1989)
  30.M. Saha, T. Roughgarden, J.-C. Latombe, G. Sanchez-Ante, Planning tours of robotic arms among partitioned goals. Int. J. Robot. Res. 25(3), 207–223 (2006)CrossRef
  31.G. Sanchez, J.-C. Latombe, On delaying collision checking in PRM planning: application to multi-robot coordination. Int. J. Robot. Res. 21(1), 5–26 (2002)CrossRef
  32.W. Scott, G. Roth, J. Rivest, View planning for automated three-dimensional object reconstruction and inspection. ACM Comput. Surv. 35(1), 64–96 (2003)CrossRef
  33.T. Shermer, Recent results in art galleries. Proc. IEEE 80(9), 1384–1399 (1992)CrossRef
  34.P. Wang, R. Krishnamurti, K. Gupta, View planning problem with combined view and traveling cost, in Proceedings of IEEE International Conference on Robotics and Automation (2007), pp. 711–716
  35.K. Williams, J. Burdick, Multi-robot boundary coverage with plan revision, in Proceedings of IEEE International Conference on Robotics and Automation (2006), pp. 1716–1723}
  
• 作者单位：Brendan Englot (5)
  Franz Hover (5)
  
  5. Massachusetts Institute of Technology, 77 Massachusetts Ave, Cambridge, MA, 02139, UK
  
• 丛书名：Robotics Research
• ISBN：978-3-319-29363-9
• 刊物类别：Engineering
• 刊物主题：Automation and Robotics
  Control Engineering
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1610-742X
• 卷排序：100

文摘

The aim of this work is fast, automated planning of robotic inspections involving complex 3D structures. A model comprised of discrete geometric primitives is provided as input, and a feasible robot inspection path is produced as output. Our algorithm is intended for tasks in which 2.5D algorithms, which divide an inspection into multiple 2D slices, and segmentation-based approaches, which divide a structure into simpler components, are unsuitable. This degree of 3D complexity has been introduced by the application of autonomous in-water ship hull inspection; protruding structures at the stern (propellers, shafts, and rudders) are positioned in close proximity to one another and to the hull, and clearance is an issue for a mobile robot. A global, sampling-based approach is adopted, in which all the structures are simultaneously considered in planning a path. First, the state space of the robot is discretized by constructing a roadmap of feasible states; construction ceases when each primitive is observed by a specified number of states. Once a roadmap is produced, the set cover problem and traveling salesman problem are approximated in sequence to build a feasible inspection tour. We analyze the performance of this procedure in solving one of the most complex inspection planning tasks to date, covering the stern of a large naval ship, using an a priori triangle mesh model obtained from real sonar data and comprised of 100,000 primitives. Our algorithm generates paths on a par with dual sampling, with reduced computational effort.