{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T22:30:29Z","timestamp":1765233029806,"version":"3.37.3"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,2,3]],"date-time":"2021-02-03T00:00:00Z","timestamp":1612310400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,2,3]],"date-time":"2021-02-03T00:00:00Z","timestamp":1612310400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61702242","61976109"],"award-info":[{"award-number":["61702242","61976109"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100010018","name":"Doctoral Start-up Foundation of Liaoning Province","doi-asserted-by":"publisher","award":["2019-BS-153","2019-BS-014"],"award-info":[{"award-number":["2019-BS-153","2019-BS-014"]}],"id":[{"id":"10.13039\/501100010018","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2021,4]]},"DOI":"10.1007\/s10878-021-00705-5","type":"journal-article","created":{"date-parts":[[2021,2,3]],"date-time":"2021-02-03T13:03:58Z","timestamp":1612357438000},"page":"625-639","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["The simple grid polygon exploration problem"],"prefix":"10.1007","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2326-0601","authenticated-orcid":false,"given":"Qi","family":"Wei","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jie","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuehou","family":"Tan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaolin","family":"Yao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yonggong","family":"Ren","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,2,3]]},"reference":[{"key":"705_CR1","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1016\/j.robot.2018.11.005","volume":"112","author":"JPLSD Almeida","year":"2019","unstructured":"Almeida JPLSD, Nakashima RT, Neves-Jr F, Arruda LVRD (2019) Bio-inspired on-line path planner for cooperative exploration of unknown environment by a multi-robot system. Robot Auton Syst 112:32\u201348","journal-title":"Robot Auton Syst"},{"issue":"4","key":"705_CR2","doi-asserted-by":"publisher","first-page":"33:1","DOI":"10.1145\/2700223","volume":"11","author":"J Chalopin","year":"2015","unstructured":"Chalopin J, Das S, Disser Y, Mihal\u00e1k M, Widmayer P (2015) Mapping simple polygons: The power of telling convex from reflex. ACM Trans Algorithms 11(4):33:1\u201333:16","journal-title":"ACM Trans Algorithms"},{"key":"705_CR3","doi-asserted-by":"crossref","unstructured":"Deng X, Kameda T, Papadimitriou C (1991) How to learn an unknown environment. In: Proceedings 32nd annual symposium of foundations of computer science, pp. 298\u2013303","DOI":"10.1109\/SFCS.1991.185382"},{"key":"705_CR4","doi-asserted-by":"crossref","unstructured":"Dereniowski D, Disser Y, Kosowski A, Paja\u0327k D, Uzna\u0144ski P (2015) Fast collaborative graph exploration. Inf Comput 243:37\u201349","DOI":"10.1016\/j.ic.2014.12.005"},{"key":"705_CR5","doi-asserted-by":"crossref","unstructured":"Doi K, Yamauchi Y, Kijima S, Yamashita M (2018) Exploration of finite 2d square grid by a metamorphic robotic system. In: Izumi T, Kuznetsov P (eds.) Stabilization, Safety, and Security of Distributed Systems, Lecture Notes in Computer Science, vol. 11201, pp. 96\u2013110. Springer, Berlin","DOI":"10.1007\/978-3-030-03232-6_7"},{"key":"705_CR6","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.tcs.2015.11.017","volume":"655","author":"KT Foerster","year":"2016","unstructured":"Foerster KT, Wattenhofer R (2016) Lower and upper competitive bounds for online directed graph exploration. Theoret Comput Sci 655:15\u201329","journal-title":"Theoret Comput Sci"},{"issue":"3","key":"705_CR7","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/S0925-7721(02)00110-4","volume":"24","author":"Y Gabriely","year":"2003","unstructured":"Gabriely Y, Rimon E (2003) Competitive on-line coverage of grid environments by a mobile robot. Comput Geom 24(3):197\u2013224","journal-title":"Comput Geom"},{"issue":"4","key":"705_CR8","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/j.cosrev.2010.05.001","volume":"4","author":"SK Ghosh","year":"2010","unstructured":"Ghosh SK, Klein R (2010) Online algorithms for searching and exploration in the plane. Comput Sci Rev 4(4):189\u2013201","journal-title":"Comput Sci Rev"},{"key":"705_CR9","unstructured":"Hagius R, Icking C, Langetepe E (2004) Lower bounds for the polygon exploration problems. In: 20th European Workshop Computer Geometry, pp. 135\u2013138"},{"issue":"2","key":"705_CR10","doi-asserted-by":"publisher","first-page":"577","DOI":"10.1137\/S0097539799348670","volume":"31","author":"F Hoffmann","year":"2002","unstructured":"Hoffmann F, Icking C, Klein R, Kriegel K (2002) The polygon exploration problem. SIAM J Comput 31(2):577\u2013600","journal-title":"SIAM J Comput"},{"key":"705_CR11","doi-asserted-by":"crossref","unstructured":"Icking C, Kamphans T, Klein R, Langetepe E (2002) On the competitive complexity of navigation tasks. In: Hager GD, Christensen HI, Bunke H, Klein R (eds) Sensor Based Intelligent Robots, vol 2238. Lecture Notes in Computer Science. pp 245\u2013258. Springer, Berlin","DOI":"10.1007\/3-540-45993-6_14"},{"key":"705_CR12","doi-asserted-by":"crossref","unstructured":"Icking C, Kamphans T, Klein R, Langetepe E (2005) Exploring simple grid polygons. In: Wang L (ed) Computing and Combinatorics, vol 3595. Lecture Notes in Computer Science. pp 524\u2013533. Springer, Berlin","DOI":"10.1007\/11533719_53"},{"key":"705_CR13","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.tcs.2016.01.024","volume":"621","author":"F Keshavarz-Kohjerdi","year":"2016","unstructured":"Keshavarz-Kohjerdi F, Bagheri A (2016) Hamiltonian paths in l-shaped grid graphs. Theoret Comput Sci 621:37\u201356","journal-title":"Theoret Comput Sci"},{"key":"705_CR14","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1016\/j.tcs.2012.06.034","volume":"463","author":"N Megow","year":"2012","unstructured":"Megow N, Mehlhorn K, Schweitzer P (2012) Online graph exploration: New results on old and new algorithms. Theoret Comput Sci 463:62\u201372","journal-title":"Theoret Comput Sci"},{"key":"705_CR15","doi-asserted-by":"crossref","unstructured":"Ortolf C, Schindelhauer C (2012) 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, SPAA \u201912, pp 27\u201336. ACM, New York, USA","DOI":"10.1145\/2312005.2312010"},{"key":"705_CR16","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/j.robot.2016.08.015","volume":"90","author":"DP Strom","year":"2017","unstructured":"Strom DP, Bogoslavskyi I, Stachniss C (2017) Robust exploration and homing for autonomous robots. Robot Auton Syst 90:125\u2013135","journal-title":"Robot Auton Syst"},{"key":"705_CR17","doi-asserted-by":"crossref","unstructured":"Tan X, Wei Q (2015) An improved on-line strategy for exploring unknown polygons. Combinatorial Optimization and Applications, vol 9486. Lecture Notes in Computer Science. pp 163\u2013177. Springer, Berlin","DOI":"10.1007\/978-3-319-26626-8_13"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00705-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-021-00705-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00705-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,10]],"date-time":"2021-03-10T08:37:12Z","timestamp":1615365432000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-021-00705-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,3]]},"references-count":17,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["705"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00705-5","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2021,2,3]]},"assertion":[{"value":"19 January 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 February 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}