Abstract
3D map exploration is one of key technologies in robotics. However, finding an optimal exploration path is a challenge due to unknown environments. This research proposed the Topological Fourier Sparse Set (TFSS) algorithm to enable an unmanned aerial vehicle (UAV) to explore 3D environments with theoretical guarantees. The algorithm combines the Rips complex with Fourier sparse set representation to take the advantages of topological and submodular approaches. More specifically, the Rips complex is used for expanding the exploration subgoals, while the Fourier sparse set encodes a learned representation of the subgoal selection problem in the form of a submodular optimization problem. Since the objective function of spatial exploration is reformulated as a maximizing submodular function with path constraints, greedy algorithms can achieve \(\frac {1}{2}(1-e^{-1})\) of the optimum. Experiments conducted with this algorithm demonstrates that the TFSS explores unknown environments \(25\% \sim 127\%\) more than the NBV algorithm does. The TFSS exploration performance is close to the SFSS but it is 50 times faster than the SFSS.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Abed-alguni, B., Paul, D.J.: Hybridizing the cuckoo search algorithm with different mutation operators for numerical optimization problems. J. Intell. Syst. 29(1), 1043–1062 (2019)
Adams, H., Carlsson, G.: Evasion paths in mobile sensor networks. Int. J. Robot. Res. 34, 90–104 (2015)
Alkhateeb, F., Abed-alguni, B.: A hybrid cuckoo search and simulated annealing algorithm. J. Intell. Syst. 28(4), 683–698 (2019)
Balcan, M.F., Harvey, N.J.: Learning submodular functions. In: Proceedings of the 43rd annual ACM symposium on Theory of computing (2011)
Baraniuk, R.: Compressive sensing. IEEE Signal Process. Mag. 24(4), 118–121 (2007)
Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Journal on Imaging Sciences 2, 183–202 (2009)
Bhattacharya, S., Ghrist, R., Kumar, V.: Persistent homology for path planning in uncertain environments. IEEE Trans. Robot. 31(3), 578–590 (2015)
Bircher, A., Kamel, M., Alexis, K., Oleynikova, H., Siegwart, R.: Receding horizon “next–best–view” planner for 3d exploration. IEEE International Conference on Robotics and Automation (2016)
Bircher, A., Kamel, M., Alexis, K., Oleynikova, H., Siegwart, R.: Receding horizon path planning for 3d exploration and surface inspection. Auton. Robot. 42(2), 291–306 (2018)
Cadena, C., Carlone, L., Carrillo, H., Latif, Y., Scaramuzza, D., Neira, J., Reid, I., Leonard, J.: Past, present, and future of simultaneous localization and mapping: Toward the robust-perception age. IEEE Trans. Robot. 32(6), 1309–1332 (2016)
Candes, E., Romberg, J., Tao, T.: Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. IEEE Transaction on Information Theory 52(2), 489–509 (2006)
Chaslot, G.M.B., Winands, M.H., Szita, I., van den Herik, H.J.: Cross-entropy for monte-carlo tree search. Icga Journal 31(3), 145–156 (2008)
Cohen-Steiner, D., Edelsbrunner, H., Harer, J.: Stability of persistence diagrams. Discret. Comput. Geom. 37(1), 103–120 (2007)
De Boer, P.T., Kroese, D.P., Mannor, S., Rubinstein, R.Y.: A tutorial on the cross-entropy method. Ann. Oper. Res. 134(1), 19–67 (2005)
Derenick, J., Kumar, V., Jadbabaie, A.: Towards simplicial coverage repair for mobile robot teams. IEEE International Conference on Robotics and Automation (2010)
Durrant-Whyte, H., Bailey, T.: Simultaneous localization and mapping (SLAM): part i. IEEE Robot. Autom. Mag. 13(2), 99–110 (2006)
Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634–652 (1998)
Ghrist, R.: Elementary applied topology. Createspace (2014)
González-Baños, H.H., Latombe, J.C.: Navigation strategies for exploring indoor environments. Int. J. Robot. Res. 21, 829–848 (2002)
Govindarajan, V., Bhattacharya, S., Kumar, V.: Human-robot collaborative topological exploration for search and rescue applications. Distrib. Autonom. Robot. Syst. 112, 17–32 (2016)
Heng, L., Gotovos, A., Krause, A., Pollefeys, M.: Efficient visual exploration and coverage with a micro aerial vehicle in unknown environments. IEEE International Conference on Robotics and Automation (2015)
Hollinger, G., Choudhuri, C., Mitra, U., Sukhatme, G.S.: Squared error distortion metrics for motion planning in robotic sensor networks. In: Proceedings International Workshop Wireless Networking for Unmanned Autonomous Vehicles, pp 1426–1431 (2013)
Hollinger, G., Singh, S.: Proofs and experiments in scalable, near-optimal search by multiple robots. Robotics: Science and Systems 1426–1431 (2008)
Khuller, S., Moss, A., Naor, J.: The budgeted maximum coverage problem. Inf. Process. Lett. 70(1), 39–45 (1999)
LaValle, S.M. Jr, J.J.K: Randomized kinodynamic planning. IEEE International Conference on Robotics and Automation 473–479 (1999)
Lu, B.X., Tseng, K.S.: 3d map exploration via learning submodular functions in the fourier domain. International Conference on Unmanned Aircraft Systems (ICUAS) (2020)
Lu, B.X., Wu, J.J., Tsai, Y.C., Jiang, W.T., Tseng, K.S.: A novel telerobotic search system using an unmanned aerial vehicle. IEEE International Conference on Robotic Computing (2020)
Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions. Math. Program. 14, 265–294 (1978)
Rabadan, R., Blumberg, A.J.: Topological data analysis for genomics and evolution. Cambridge University Press (2019)
Ramaithitima, R., Whitzer, M., Bhattacharya, S., Kumar, V.: Sensor coverage robot swarms using local sensing without metric information. IEEE International Conference on Robotics and Automation (2015)
S, Q., Islamabad, P., Bilal, R., Iqbal, W., Naureen, M.: Compressive sensing: from theory to applications, a survey. J. Commun. Netw. 15(5), 443–456 (2013)
Schmidt, M.: Least squares optimization with l1-norm regularization (2005)
de Silva, V., Ghrist, R.: Coordinate-free coverage in sensor networks with controlled boundaries via homology. Int. J. Robot. Res. 25(12), 1205–1222 (2006)
Singh, A., Krause, A., Kaiser, W.: Nonmyopic adaptive informative path planning for multiple robots. Int. Joint Conf. Artif. Intell. 1843–1850 (2009)
Stobbe, P., Krause, A.: Learning fourier sparse set functions. In: Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, pp 1125–1133 (2012)
Tibshirani, R.: Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society Series B 58, 267–288 (1996)
Tsai, Y.C., Tseng, K.S.: Deep compressed sensing for learning submodular functions. Sensors 20(9), 2591 (2020)
Tseng, K.S.: Learning in human and robot search: Subgoal, submodularity, and sparsity. University of Minnesota Ph.D dissertation (2016)
Tseng, K.S.: Transfer learning of coverage functions via invariant properties in the fourier domain. Auton. Robot. 45, 519–542 (2021)
Tseng, K.S., Mettler, B.: Near-optimal probabilistic search via submodularity and sparse regression. Autonomous Robots (2015)
Tseng, K.S., Mettler, B.: Human planning and coordination in spatial search problems. 1st IFAC Conference on Cyber-Physical and Human-Systems (2016)
Tseng, K.S., Mettler, B.: Near-optimal probabilistic search using spatial fourier sparse set. Autonomous Robots (2017)
Tseng, K.S., Mettler, B.: Analysis of coordination patterns between gaze and control in human spatial search. 2nd IFAC Conference on Cyber-Physical and Human-Systems (2018)
Tseng, K.S., Mettler, B.: Analysis and augmentation of human performance on telerobotic search problems. IEEE Access 8, 56,590–56,606 (2020)
Wulfmeier, M., Ondruska, P., Posner, I.: Maximum entropy deep inverse reinforcement learning. Arxiv (2015)
Wulfmeier, M., Wang, D.Z., Posner, I.: Maximum entropy deep inverse reinforcement learning. IEEE/RSJ International Conference on Intelligent Robots and Systems 2153–0866 (2016)
Zhang, H., Vorobeychik, Y.: Submodular optimization with routing constraints. AAAI Conference on Artificial Intelligence (2016)
Acknowledgements
This research was completed thanks to the financial support from Taiwan MOST Grant 107-2218-E-008-017 and 108-2221-E-008-074-MY3.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Electronic supplementary material
Below is the link to the electronic supplementary material.
(MP4 51.4 MB)
Rights and permissions
About this article
Cite this article
Lu, BX., Tseng, KS. 3D Map Exploration Using Topological Fourier Sparse Set. J Intell Robot Syst 104, 75 (2022). https://doi.org/10.1007/s10846-021-01565-1
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10846-021-01565-1