Abstract
This article introduces multi-agent strategy enabling multiple agents to explore an unknown environment with many obstacles, while generating a topological map in a cooperative way. Once a topological map is built, it can be used for various purposes, such as path planning or intruder capture. Multiple agents generate a Voronoi graph as a topological map of the environment, while dropping indexed markers at Voronoi vertices. Each agent has range sensors to detect nearby obstacles, thus can move along a Voronoi edge. Also, each agent stores the boundary for the explored region thus far, and unite its boundary with the boundary of another agent if some conditions are met. In this way, multiple agents can explore the entire workspace in a time efficient manner. The proposed exploration strategy doesn’t require localization of an agent or a marker in global coordinate systems. To the best of our knowledge, this article is unique in addressing a multi-agent exploration and map building strategy, such that each agent drops indexed markers for generating a topological map of the environment. The effectiveness of the proposed exploration and mapping strategy is demonstrated utilizing MATLAB simulations.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Code Availability
Not applicable.
References
Kim, J.: Multirobot exploration while building power-efficient sensor networks in three dimensions. IEEE Transactions on Cybernetics, pp. 1–8 (2018)
Zedadra, O., Jouandeau, N., Seridi, H., G. F. S.: Multi-agent foraging: state-of-the-art and research challenge. Complex Adaptive Systems Modeling, vol. 5, no. 1
Kim, J.: Three-dimensional discrete-time controller to intercept a targeted uav using a capture net towed by multiple aerial robots. IET Radar, Sonar & Navigation 13(5), 682–688 (2019)
Kim, J.: Cooperative exploration and protection of a workspace assisted by information networks. Ann. Math. Artif. Intell. 70, 203–220 (2014)
Choset, H., Nagatani, K.: Topological simultaneous localization and mapping (SLAM): toward exact localization without explicit localization. IEEE Trans. Robot. Autom. 17, 125–137 (2001)
Lavalle, S.M.: Planning algorithms. Cambridge University Press (2006)
Pimenta, L.C.A., Schwager, M., Lindsey, Q., Kumar, V., Rus, D., Mesquita, R.C., Pereira, G.A.S.: Simultaneous coverage and tracking (scat) of moving targets with robot networks. In: Proc. of Workshop on the Algorithmic Foundations of Robotics (WAFR), pp. 85–99. Mexico (2008)
Culler, D., Estrin, D., Srivastava, M.: Overview of sensor networks. IEEE Comput. Mag. 37(8), 41–49 (2004)
Souryal, M.R., Geissbuehler, L.E., Miller, J., Moayeri, N.: Real-time deployment of multihop relays for range extension. In: Proceedings of the 5th international conference on Mobile systems, applications and services (MobiSys 07), pp. 85–98. New York, NY, USA, ACM (2007)
Brass, P., Gasparri, A., Cabrera-Mora, F., Xiao, J.: Multi-robot tree and graph exploration. In: Proc. of IEEE International Conference on Robotics and Automation, pp. 2332–2337. Japan (2009)
Liu, H., Li, J., Xie, Z., Lin, S., Whitehouse, K., Stankovic, J.A., Siu, D.: Automatic and robust breadcrumb system deployment for indoor firefighter applications. In: Proceedings of the 8th international conference on Mobile systems, applications, and services (MobiSys 10), pp. 21–34. San Francisco, California, USA, ACM (2010)
Bailey, T., Durrant-Whyte, H.: Simultaneous localization and mapping: Part II. IEEE Robot. Autom. Mag. 13, 108–117 (2006)
Chen, C., Zhu, H., Li, M., You, S.: A review of visual-inertial simultaneous localization and mapping from filtering-based and optimization-based perspectives. Robotics 7(45), 1–20 (2018)
Lynen, S., Zeisl, B., Aiger, D., Bosse, M., Hesch, J., Pollefeys, M., Siegwart, R., Sattler, T.: Large-scale, real-time visual–inertial localization revisited. Int J Robot Res 39(9), 1061–1084 (2020)
Chen, C., Zhu, H., Li, M., You, S.: A review of visual-inertial simultaneous localization and mapping from filtering-based and optimization-based perspectives. Robotics 7(3), 1–20 (2018)
Kelly, J., Sukhatme, G.S.: Visual-inertial simultaneous localization, mapping and sensor-to-sensor self-calibration. In: 2009 IEEE International Symposium on Computational Intelligence in Robotics and Automation - (CIRA), pp. 360–368 (2009)
Howard, A.: Multi-robot simultaneous localization and mapping using particle filters. Int. J. Robot. Res. 25(12), 1243–1256 (2006)
Burgard, W., Moors, M., Stachniss, C., Schneider, F.: Coordinated multi-robot exploration. IEEE Trans. Robot. 21, 376–386 (2005)
Fox, D., Ko, J., Stewart, B., Konolige, K., Limketkai, B.: Distributed multirobot exploration and mapping. Proc. IEEE 94(7), 1325–1339 (2006)
Kim, J., Zhang, F., Egerstedt, M.: A provably complete exploration strategy by constructing Voronoi diagrams. Auton. Robot. 29(3-4), 367–380 (2010)
Kim, J.: Cooperative exploration and networking while preserving collision avoidance. IEEE Trans. Cybern. PP, 1–11 (2016)
Douglas, B.W.: Introduction to Graph Theory, 2nd edn. Prentice Hall, Illinois, USA (2001)
Kim, J., Zhang, F., Egerstedt, M.: Simultaneous cooperative exploration and networking based on Voronoi diagrams. In: Proc. of IFAC Workshop on Networked Robotics, Colorado, USA, pp 1–6 (2009)
Bhattacharya, P., Gavrilova, M.L.: Roadmap-based path planning - using the Voronoi diagram for a clearance-based shortest path. IEEE Robot. Autom. Mag. 15, 58–66 (2008)
Funding
Not applicable.
Author information
Authors and Affiliations
Contributions
The paper is written by only Jonghoek Kim.
Corresponding author
Ethics declarations
Ethics approval
Not applicable.
Conflict of Interests
Not applicable.
Additional information
Availability of data and material
Not applicable.
Consent to participate
Not applicable.
Consent for Publish
Not applicable.
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Kim, J. Topological Map Building with Multiple Agents Having Abilities of Dropping Indexed Markers. J Intell Robot Syst 103, 18 (2021). https://doi.org/10.1007/s10846-021-01473-4
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s10846-021-01473-4