{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,6]],"date-time":"2025-12-06T05:01:40Z","timestamp":1764997300023},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030430887"},{"type":"electronic","value":"9783030430894"}],"license":[{"start":{"date-parts":[[2020,1,1]],"date-time":"2020-01-01T00:00:00Z","timestamp":1577836800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2020]]},"DOI":"10.1007\/978-3-030-43089-4_57","type":"book-chapter","created":{"date-parts":[[2020,5,6]],"date-time":"2020-05-06T16:04:08Z","timestamp":1588781048000},"page":"896-911","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A Geometric Approach for Multi-Robot Exploration in Orthogonal Polygons"],"prefix":"10.1007","author":[{"given":"Aravind Preshant","family":"Premkumar","sequence":"first","affiliation":[]},{"given":"Kevin","family":"Yu","sequence":"additional","affiliation":[]},{"given":"Pratap","family":"Tokekar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,5,7]]},"reference":[{"key":"57_CR1","doi-asserted-by":"crossref","unstructured":"Rao, N.S., Kareti, S., Shi, W., Iyengar, S.S.: Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms. Technical report, Citeseer (1993)","DOI":"10.2172\/10180101"},{"key":"57_CR2","unstructured":"Juli\u00e1, M., Gil, A., Reinoso, O.: A comparison of path planning strategies for autonomous exploration and mapping of unknown environments. Autonomous Robots 33(4) (2012) 427\u2013444"},{"key":"57_CR3","unstructured":"Bhattacharya, A., Ghosh, S.K., Sarkar, S.: Exploring an unknown polygonal environment with bounded visibility. In: International Conference on Computational Science, Springer (2001) 640\u2013648"},{"key":"57_CR4","doi-asserted-by":"crossref","unstructured":"Charrow, B., Kahn, G., Patil, S., Liu, S., Goldberg, K., Abbeel, P., Michael, N., Kumar, V.: Information-theoretic planning with trajectory optimization for dense 3d mapping. In: Proceedings of Robotics: Science and Systems. (2015)","DOI":"10.15607\/RSS.2015.XI.003"},{"key":"57_CR5","unstructured":"Yamauchi, B.: A frontier-based approach for autonomous exploration. In: Computational Intelligence in Robotics and Automation, 1997. CIRA\u201997., Proceedings., 1997 IEEE International Symposium on, IEEE (1997) 146\u2013151"},{"key":"57_CR6","doi-asserted-by":"crossref","unstructured":"Motwani, R., Raghavan, P.: Randomized algorithms. Chapman & Hall\/CRC (2010)","DOI":"10.1201\/9781584888239-c12"},{"key":"57_CR7","unstructured":"Deng, X., Kameda, T., Papadimitriou, C.: How to learn an unknown environment. i: the rectilinear case. Journal of the ACM (JACM) 45(2) (1998) 215\u2013245"},{"key":"57_CR8","unstructured":"O\u2019Rourke, J.: Art gallery theorems and algorithms. Oxford University Press Oxford (1987)"},{"key":"57_CR9","doi-asserted-by":"crossref","unstructured":"Chin,W.p., Ntafos, S.: Optimum watchman routes. Information Processing Letters 28(1) (1988) 39\u201344","DOI":"10.1016\/0020-0190(88)90141-X"},{"key":"57_CR10","unstructured":"Fleischer, R., Kamphans, T., Klein, R., Langetepe, E., Trippen, G.: Competitive online approximation of the optimal search ratio. SIAM Journal on Computing 38(3) (2008) 881\u2013898"},{"key":"57_CR11","doi-asserted-by":"crossref","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Shortest paths without a map. Theoretical Computer Science 84(1) (1991) 127\u2013150","DOI":"10.1016\/0304-3975(91)90263-2"},{"key":"57_CR12","doi-asserted-by":"crossref","unstructured":"Chvatal, V.: A combinatorial theorem in plane geometry. Journal of Combinatorial Theory, Series B 18(1) 18\u201341","DOI":"10.1016\/0095-8956(75)90061-1"},{"key":"57_CR13","doi-asserted-by":"crossref","unstructured":"Fisk, S.: A short proof of chv\u00e1tal\u2019s watchman theorem. Journal of Combinatorial Theory, Series B 24(3) (1978) 374","DOI":"10.1016\/0095-8956(78)90059-X"},{"key":"57_CR14","unstructured":"Schuchardt, D., Hecker, H.D.: Two np-hard art-gallery problems for orthopolygons. Mathematical Logic Quarterly 41(2) (1995) 261\u2013267"},{"key":"57_CR15","unstructured":"Ghosh, S.K., Burdick, J.W., Bhattacharya, A., Sarkar, S.: Online algorithms with discrete visibility-exploring unknown polygonal environments. IEEE robotics & automation magazine 15(2) (2008) 67\u201376"},{"key":"57_CR16","doi-asserted-by":"crossref","unstructured":"Hoffmann, F., Icking, C., Klein, R., Kriegel, K.: The polygon exploration problem. SIAM Journal on Computing 31(2) (2001) 577\u2013600","DOI":"10.1137\/S0097539799348670"},{"key":"57_CR17","unstructured":"Mitchell, J.S.: Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric tsp, k-mst, and related problems. SIAM Journal on Computing 28(4) (1999) 1298\u20131309"},{"key":"57_CR18","unstructured":"Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. Journal of the ACM (JACM) 45(5) (1998) 753\u2013782"},{"key":"57_CR19","unstructured":"Fraigniaud, P., Gasieniec, L., Kowalski, D.R., Pelc, A.: Collective tree exploration. Networks 48(3) (2006) 166\u2013177"},{"key":"57_CR20","unstructured":"Dynia, M., \u0141opusza$$\\acute{\\text{N}}$$ski, J., Schindelhauer, C.: Why robots need maps. In: International Colloquium on Structural Information and Communication Complexity, Springer (2007) 41\u201350"},{"key":"57_CR21","unstructured":"Higashikawa, Y., Katoh, N., Langerman, S., Tanigawa, S.i.: Online graph exploration algorithms for cycles and trees by multiple searchers. Journal of Combinatorial Optimization 28(2) (2014) 480\u2013495"},{"key":"57_CR22","unstructured":"Dynia, M., Kuty lowski, J., auf der Heide, F.M., Schindelhauer, C.: Smart robot teams exploring sparse trees. In: International Symposium on Mathematical Foundations of Computer Science, Springer (2006) 327\u2013338"},{"key":"57_CR23","unstructured":"Ortolf, C., Schindelhauer, C.: Online multi-robot exploration of grid graphs with rectangular obstacles. In: Proceedings of the twenty-fourth annual ACM symposium on Parallelism in algorithms and architectures, ACM (2012) 27\u201336"},{"key":"57_CR24","unstructured":"Burgard, W., Moors, M., Stachniss, C., Schneider, F.E.: Coordinated multi-robot exploration. IEEE Transactions on robotics 21(3) (2005) 376\u2013386"},{"key":"57_CR25","unstructured":"Schwager, M., Dames, P., Rus, D., Kumar, V.: A multi-robot control policy for information gathering in the presence of unknown hazards. In: Proceedings of International Symposium on Robotics Research, Aug. (2011)"},{"key":"57_CR26","unstructured":"Cesare, K., Skeele, R., Yoo, S.H., Zhang, Y., Hollinger, G.: Multi-uav exploration with limited communication and battery. In: 2015 IEEE International Conference on Robotics and Automation (ICRA), IEEE (2015) 2230\u20132235"},{"key":"57_CR27","unstructured":"Holz, D., Basilico, N., Amigoni, F., Behnke, S.: A comparative evaluation of exploration strategies and heuristics to improve them. In: ECMR. (2011) 25\u201330"},{"key":"57_CR28","unstructured":"Whaite, P., Ferrie, F.P.: Autonomous exploration: Driven by uncertainty. IEEE Transactions on Pattern Analysis and Machine Intelligence 19(3) (1997) 193\u2013205"},{"key":"57_CR29","unstructured":"Moorehead, S.J., Simmons, R., Whittaker, W.L.: Autonomous exploration using multiple sources of information. In: Robotics and Automation, 2001. Proceedings 2001 ICRA. IEEE International Conference on. Volume 3., IEEE (2001) 3098\u20133103"},{"key":"57_CR30","doi-asserted-by":"crossref","unstructured":"Julian, B.J., Karaman, S., Rus, D.: On mutual information-based control of range sensing robots for mapping applications. The International Journal of Robotics Research (2014) 0278364914526288","DOI":"10.1109\/IROS.2013.6697102"},{"key":"57_CR31","unstructured":"Amigoni, F., Caglioti, V.: An information-based exploration strategy for environment mapping with mobile robots. Robotics and Autonomous Systems 58(5) (2010) 684\u2013699"},{"key":"57_CR32","unstructured":"Quigley, M., Gerkey, B., Conley, K., Faust, J., Foote, T., Leibs, J., Berger, E., Wheeler, R., Ng, A.: ROS: an open-source Robot Operating System. In: ICRA Workshop on Open Source Software. (2009)"},{"key":"57_CR33","unstructured":"Koenig, N., Howard, A.: Design and use paradigms for gazebo, an open-source multi-robot simulator. In: Intelligent Robots and Systems, 2004.(IROS 2004). Proceedings. 2004 IEEE\/RSJ International Conference on. Volume 3., IEEE (2004) 2149\u20132154"},{"key":"57_CR34","doi-asserted-by":"crossref","unstructured":": AMCL ROS Packagel. \nhttp:\/\/wiki.ros.org\/amcl Accessed\n\n: 2016-10-30.","DOI":"10.1101\/gad.283598.116"},{"key":"57_CR35","unstructured":"Hornung, A., Wurm, K.M., Bennewitz, M., Stachniss, C., Burgard, W.: Octomap: An efficient probabilistic 3d mapping framework based on octrees. Autonomous Robots 34(3) (2013) 189\u2013206"},{"key":"57_CR36","unstructured":"Labb\u00e9, M., Michaud, F.: Online global loop closure detection for large-scale multisession graph-based slam. In: 2014 IEEE\/RSJ International Conference on Intelligent Robots and Systems, IEEE (2014) 2661\u20132666"},{"key":"57_CR37","unstructured":"Labbe, M., Michaud, F.: Appearance-based loop closure detection for online largescale and long-term operation. IEEE Transactions on Robotics 29(3) (2013) 734\u2013745"}],"container-title":["Springer Proceedings in Advanced Robotics","Algorithmic Foundations of Robotics XII"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-43089-4_57","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,6]],"date-time":"2020-05-06T16:21:06Z","timestamp":1588782066000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-43089-4_57"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020]]},"ISBN":["9783030430887","9783030430894"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-43089-4_57","relation":{},"ISSN":["2511-1256","2511-1264"],"issn-type":[{"type":"print","value":"2511-1256"},{"type":"electronic","value":"2511-1264"}],"subject":[],"published":{"date-parts":[[2020]]},"assertion":[{"value":"7 May 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}