Abstract
Within this paper a new path planning algorithm for autonomous robotic exploration and inspection is presented. The proposed method plans online in a receding horizon fashion by sampling possible future configurations in a geometric random tree. The choice of the objective function enables the planning for either the exploration of unknown volume or inspection of a given surface manifold in both known and unknown volume. Application to rotorcraft Micro Aerial Vehicles is presented, although planning for other types of robotic platforms is possible, even in the absence of a boundary value solver and subject to nonholonomic constraints. Furthermore, the method allows the integration of a wide variety of sensor models. The presented analysis of computational complexity and thorough simulations-based evaluation indicate good scaling properties with respect to the scenario complexity. Feasibility and practical applicability are demonstrated in real-life experimental test cases with full on-board computation.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
RotorS: An MAV gazebo simulator, https://github.com/ethz-asl/rotors_simulator.
Ascending Technologies GmbH, http://www.asctec.de/.
Bridge Model, 3D Warehouse, https://3dwarehouse.sketchup.com/.
Pix4D, http://pix4d.com/.
References
Acar, E. U., Choset, H., Rizzi, A. A., Atkar, P. N., & Hull, D. (2002). Morse decompositions for coverage tasks. The International Journal of Robotics Research, 21(4), 331–344.
Adler, B., Xiao, J., & Zhang, J. (2014). Autonomous exploration of urban environments using unmanned aerial vehicles. Journal of Field Robotics, 31(6), 912–939.
Alexis, K., Papachristos, C., Siegwart, R., & Tzes, A. (2015). Uniform coverage structural inspection path-planning for micro aerial vehicles. In IEEE international symposium on intelligent control (ISIC) (pp. 59–64). IEEE.
Alexis, K., Nikolakopoulos, G., & Tzes, A. (2012). Model predictive quadrotor control: attitude, altitude and position experimental studies. Control Theory & Applications, IET, 6(12), 1812–1827.
Amigoni, F., Li, A. Q., & Holz, D. (2013) Evaluating the impact of perception and decision timing on autonomous robotic exploration. In 2013 european conference on mobile robots (ECMR) (pp. 68–73). IEEE.
Banta, J. E., Wong, L. M., Dumont, C., Abidi, M., et al. (2000). A next-best-view system for autonomous 3-d object reconstruction. IEEE Transactions on Systems, Man and Cybernetics, Part A: Systems and Humans, 30(5), 589–598.
Basilico, N., & Amigoni, F. (2011). Exploration strategies based on multi-criteria decision making for searching environments in rescue operations. Autonomous Robots, 31(4), 401–417.
Bircher, A., Alexis, K. (2016). Receding Horizon Next Best View Planner Code Release. https://github.com/ethz-asl/nbvplanner
Bircher, A., Alexis, K., Schwesinger, U., Omari, S., Burri, M., & Siegwart, R. (2016). An incremental sampling-based approach to inspection planning: the rapidly exploring random tree of trees. Robotica (pp. 1–14).
Bircher, A., Kamel, M., Alexis, K., & Siegwart, R. (2016). Next Best View Planning Dataset Release. https://github.com/ethz-asl/nbvplanner/wiki/Example-Results.
Bircher, A., Kamel, M., Alexis, K., Oleynikova, H., & Siegwart, R. (2016). Receding horizon “next-best-view” planner for 3D exploration. In 2016 IEEE international conference on robotics and automation (ICRA) (pp. 1462–1468). IEEE.
Bircher, A., Kamel, M., Alexis, K., Burri, M., Oettershagen, P., Omari, S., et al. (2016). Three-dimensional coverage path planning via viewpoint resampling and tour optimization for aerial robots. Autonomous Robots, 40(6), 1059–1078.
Bloesch, M., Omari, S., Hutter, M., & Siegwart, R. (2015). Robust visual inertial odometry using a direct ekf-based approach. In 2015 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 298–304). IEEE.
Burgard, W., Moors, M., Fox, D., Simmons, R., & Thrun, S. (2000) Collaborative multi-robot exploration. In Proceedings of the IEEE international conference on robotics and automation (ICRA’00) (Vol. 1, pp. 476–481). IEEE.
Burri, M., Nikolic, J., Hurzeler, C., Caprari, G., & Siegwart, R. (2012). Aerial service robots for visual inspection of thermal power plant boiler systems. In 2012 2nd international conference on applied robotics for the power industry (CARPI) (pp. 70–75).
Camacho, E. F., & Bordons, C. (2003). Model Predictive Control. Berlin: Springer.
Chin, R. T., & Harlow, C. A. (1982). Automated visual inspection: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 6, 557–573.
Choset, H., Pignon, P. (1998). Coverage path planning: The boustrophedon cellular decomposition. In Field and service robotics (pp. 203–209). Springer
Colas, F., Mahesh, S., Pomerleau, F., Liu, M., & Siegwart, R.(2013). 3d path planning and execution for search and rescue ground robots. In 2013 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 722–727). IEEE.
Connolly, C., et al. (1985). The determination of next best views. In Proceedings of the 1985 IEEE international conference on robotics and automation, (Vol. 2, pp. 432–435). IEEE.
Dewan, A., Mahendran, A., Soni, N., & Krishna, M.(2013). Heterogeneous UGV-MAV exploration using integer programming. In 2013 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 5742–5749). IEEE.
Dornhege, C., & Kleiner, A. (2013). A frontier-void-based approach for autonomous exploration in 3d. Advanced Robotics, 27(6), 459–468.
Faigl, J., & Kulich, M.(2015) On benchmarking of frontier-based multi-robot exploration strategies. In 2015 european conference on mobile robots (ECMR) (pp. 1–8). IEEE.
Faigl, J., Kulic, M., & Přeučil, L. (2012). Goal assignment using distance cost in multi-robot exploration. In 2012 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 3741–3746). IEEE.
Galceran, E., & Carreras, M. (2013). A survey on coverage path planning for robotics. Robotics and Autonomous Systems, 61(12), 1258–1276.
González-Banos, H. H., & Latombe, J.-C. (2002). Navigation strategies for exploring indoor environments. The International Journal of Robotics Research, 21(10–11), 829–848.
Heng, L., Gotovos, A., Krause, A., & Pollefeys, M. (2015). Efficient visual exploration and coverage with a micro aerial vehicle in unknown environments. In IEEE international conference on robotics and automation (ICRA).
Hornung, A., Wurm, K. M., Bennewitz, M., Stachniss, C., & Burgard, W. (2013). Octomap: An efficient probabilistic 3d mapping framework based on octrees. Autonomous Robots, 34(3), 189–206.
Hover, F. S., Eustice, R. M., Kim, A., Englot, B., Johannsson, H., Kaess, M., & Leonard, J. J.(2012). Advanced perception, navigation and planning for autonomous in-water ship hull inspection. The International Journal of Robotics Research, 31(12), 1445–1464.
Howard, A., Parker, L. E., & Sukhatme, G. S. (2006). Experiments with a large heterogeneous mobile robot team: Exploration, mapping, deployment and detection. The International Journal of Robotics Research, 25(5–6), 431–447.
Janoušek, P., & Faigl, J. (2013). Speeding up coverage queries in 3D multi-goal path planning. In 2013 IEEE international conference on robotics and automation (ICRA) (Vol. 1. IEEE, pp. 5082–5087).
Karaman, S., & Frazzoli, E. (2011). Sampling-based algorithms for optimal motion planning. The International Journal of Robotics Research, 30(7), 846–894.
Khanna, R., Moller, M., Pfeifer, J., Liebisch, F., Walter, A., & Siegwart, R. (2015). Beyond point clouds-3d mapping and field parameter measurements using uavs. In 2015 IEEE 20th conference on emerging technologies & factory automation (ETFA) (pp. 1–4). IEEE.
Kuipers, B., & Byun, Y.-T. (1991). A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations. Robotics and Autonomous Systems, 8(1), 47–63.
LaValle, S. M.(1998) Rapidly-exploring random trees a new tool for path planning.
Li, A. Q., Amigoni, F., & Basilico, N. (2012). Searching for optimal off-line exploration paths in grid environments for a robot with limited visibility. AAAI.
Lynen, S., Achtelik, M. W., Weiss, S., Chli, M., & Siegwart, R. (2013). A robust and modular multi-sensor fusion approach applied to mav navigation. In 2013 IEEE/RSJ international conference on intelligent robots and systems (IROS) (pp. 3923–3929). IEEE.
Nikolic, J., Burri, M., Rehder, J., Leutenegger, S., Huerzeler, C., & Siegwart, R. (2013). A UAV system for inspection of industrial facilities. In IEEE aerospace conference.
Omari, S., Gohl, P., Burri, M., Achtelik, M., & Siegwart, R. (2014). Visual industrial inspection using aerial robots. In 2014 3rd international conference on applied robotics for the power industry (CARPI) (pp. 1–5). IEEE.
Papadopoulos, G., Kurniawati, H., Patrikalakis, N. M.(2013). Asymptotically optimal inspection planning using systems with differential constraints. In 2013 IEEE international conference on robotics and automation (ICRA) (pp. 4126–4133). IEEE.
Pito, R. (1999). A solution to the next best view problem for automated surface acquisition. IEEE Transactions on Pattern Analysis and Machine Intelligence, 21(10), 1016–1030.
Rosenblatt, J., Williams, S., & Durrant-Whyte, H. (2002). A behavior-based architecture for autonomous underwater exploration. Information Sciences, 145(1), 69–87.
Surmann, H., Nüchter, A., & Hertzberg, J. (2003). An autonomous mobile robot with a 3d laser range finder for 3d exploration and digitalization of indoor environments. Robotics and Autonomous Systems, 45(3), 181–198.
Vasquez-Gomez, J. I., Sucar, L. E., Murrieta-Cid, R., & Lopez-Damian, E. (2014). Volumetric next best view planning for 3d object reconstruction with positioning error. International Journal of Advanced Robotic Systems, 11, 159.
Whaite, P., & Ferrie, F. P. (1997). Autonomous exploration: Driven by uncertainty. IEEE Transactions on Pattern Analysis and Machine Intelligence, 19(3), 193–205.
Yamauchi, B.(1997). A frontier-based approach for autonomous exploration. In Proceedings of the 1997 IEEE international symposium on computational intelligence in robotics and automation (CIRA’97) (pp. 146–151). IEEE.
Yoder, L., & Scherer, S. (2016). Autonomous exploration for infrastructure modeling with a micro aerial vehicle. In Field and service robotics (pp. 427–440). Springer.
Zlot, R., & Bosse, M. (2014). Efficient large-scale three-dimensional mobile mapping for underground mines. Journal of Field Robotics, 31(5), 758–779.
Zlot, R., & Stentz, A. (2006). Market-based multirobot coordination for complex tasks. The International Journal of Robotics Research, 25(1), 73–101.
Acknowledgements
This work has received funding from (a) the European Union’s Horizon 2020 Research and Innovation Programme under the Grant Agreement No. 644128, AEROWORKS, (b) from the VPRI supporting account of UNR.
Author information
Authors and Affiliations
Corresponding author
Additional information
This is one of several papers published in Autonomous Robots comprising the Special Issue on Active Perception.
Rights and permissions
About this article
Cite this article
Bircher, A., Kamel, M., Alexis, K. et al. Receding horizon path planning for 3D exploration and surface inspection. Auton Robot 42, 291–306 (2018). https://doi.org/10.1007/s10514-016-9610-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10514-016-9610-0