{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T11:42:02Z","timestamp":1781264522461,"version":"3.54.1"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2012,4,6]],"date-time":"2012-04-06T00:00:00Z","timestamp":1333670400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"},{"start":{"date-parts":[[2012,4,6]],"date-time":"2012-04-06T00:00:00Z","timestamp":1333670400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/2.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Braz Comput Soc"],"published-print":{"date-parts":[[2012,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>This paper describes a new method of path-planning for multiple robots in unknown environments. The method, called Space\u00a0D*, is based on two algorithms: the\u00a0D*, which is an incremental graph search algorithm, and the Space Colonization algorithm, previously used to simulate crowd behaviors. The path-planning is achieved through the exchange of information between the robots. So decentralized, each robot performs its path-planning, which provides an obstacle-free path with the least number of robots around. The major contribution of the proposed method is that it generates paths in spacious environments facilitating the control of robots and thus presenting itself in a viable way for using in areas populated with multiple robots. The results obtained validate the approach and show the advantages in comparison with using only the\u00a0D*\u00a0method.<\/jats:p>","DOI":"10.1007\/s13173-012-0071-9","type":"journal-article","created":{"date-parts":[[2012,4,5]],"date-time":"2012-04-05T07:53:56Z","timestamp":1333612436000},"page":"363-373","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Space D*"],"prefix":"10.1007","volume":"18","author":[{"given":"Luan","family":"Silveira","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Renan Q.","family":"Maffei","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Silvia S. C.","family":"Botelho","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"suffix":"Jr.","given":"Paulo L.","family":"Drews","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alessandro de L.","family":"Bicho","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nelson L.","family":"Duarte Filho","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2012,4,6]]},"reference":[{"issue":"2","key":"71_CR1","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1016\/j.cag.2011.12.004","volume":"36","author":"AL Bicho","year":"2012","unstructured":"Bicho AL, Rodrigues RA, Musse SR, Jung CR, Paravisi M, Magalh\u00e3es LP (2012) Simulating crowds based on a space colonization algorithm. Comput Graph 36(2):70\u201379","journal-title":"Comput Graph"},{"key":"71_CR2","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1080\/095119200407660","volume":"12","author":"M Bonert","year":"2000","unstructured":"Bonert M, Shu LH, Benhabib B (2000) Motion planning for multi-robot assembly systems. Int J Comput Integr Manuf 12:301\u2013310","journal-title":"Int J Comput Integr Manuf"},{"key":"71_CR3","first-page":"476","volume-title":"Proceedings of the IEEE international conference on robotics and automation (ICRA)","author":"W Burgard","year":"2000","unstructured":"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), pp\u00a0476\u2013481"},{"key":"71_CR4","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1109\/TRO.2004.839232","volume":"21","author":"W Burgard","year":"2005","unstructured":"Burgard W, Moors M, Stachniss C, Schneider FE (2005) Coordinated multi-robot exploration. IEEE Trans Robot 21:376\u2013386","journal-title":"IEEE Trans Robot"},{"key":"71_CR5","first-page":"721","volume-title":"Proceedings of the IEEE international symposium on computational intelligence in robotics and automation","author":"J Chen","year":"2005","unstructured":"Chen J, Li LR (2005) Path planning protocol for collaborative multi-robot systems. In: Proceedings of the IEEE international symposium on computational intelligence in robotics and automation, pp 721\u2013726"},{"key":"71_CR6","first-page":"3034","volume-title":"Proceedings of the international conference on robotics and automation (ICRA)","author":"H Choset","year":"1994","unstructured":"Choset H, Burdick JW (1994) Sensor-based planning and nonsmooth analysis. In: Proceedings of the international conference on robotics and automation (ICRA), pp 3034\u20133041"},{"key":"71_CR7","volume-title":"Proceedings of the international symposium on artificial intelligence, robotics","author":"CM Clark","year":"2003","unstructured":"Clark CM, Rock SM, Latombe JC (2003) Dynamic networks for motion planning in multi-robot space systems. In: Proceedings of the international symposium on artificial intelligence, robotics and automation in space (i-SAIRAS)"},{"key":"71_CR8","first-page":"1926","volume-title":"Proceedings of the international symposium on robotics research (ISRR)","author":"D Ferguson","year":"2005","unstructured":"Ferguson D, Stentz A, Field D (2005) An interpolation-based path planner and replanner. In: Proceedings of the international symposium on robotics research (ISRR), pp 1926\u20131931"},{"key":"71_CR9","doi-asserted-by":"crossref","unstructured":"Fraichard T (1998) Trajectory planning amidst moving obstacles: path-velocity decomposition revisited. J Braz Comput Soc 4(3)","DOI":"10.1590\/S0104-65001998000100002"},{"key":"71_CR10","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1109\/TMECH.2009.2013617","volume":"14","author":"A Franchi","year":"2009","unstructured":"Franchi A, Freda L, Oriolo G, Vendittelli M (2009) The sensor-based random graph method for cooperative robot exploration. IEEE\/ASME Trans Mechatron 14:163\u2013175","journal-title":"IEEE\/ASME Trans Mechatron"},{"key":"71_CR11","first-page":"317","volume-title":"Proceedings of the 11th international conference on advanced robotics","author":"BP Gerkey","year":"2003","unstructured":"Gerkey BP, Vaughan RT, Howard A (2003) The Player\/Stage project: tools for multi-robot and distributed sensor systems. In: Proceedings of the 11th international conference on advanced robotics, pp 317\u2013323"},{"key":"71_CR12","first-page":"2612","volume-title":"Proceedings of IEEE international conference on robotics and automation (ICRA)","author":"Y Guo","year":"2002","unstructured":"Guo Y, Parker LE (2002) A distributed and optimal motion planning approach for multiple mobile robots. In: Proceedings of IEEE international conference on robotics and automation (ICRA), pp\u00a02612\u20132619"},{"key":"71_CR13","first-page":"126","volume":"48","author":"JH Jung","year":"2010","unstructured":"Jung JH, Park S, Kim SL (2010) Multi-robot path finding with wireless multihop communications. IEEE Commun Mag 48:126\u2013132","journal-title":"IEEE Commun Mag"},{"key":"71_CR14","first-page":"968","volume-title":"Proceedings of the international conference on robotics and automation (ICRA)","author":"S Koenig","year":"2002","unstructured":"Koenig S, Likhachev M (2002) Improved fast replanning for robot navigation in unknown terrain. In: Proceedings of the international conference on robotics and automation (ICRA), pp 968\u2013975"},{"key":"71_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4022-9","volume-title":"Robot motion planning","author":"JC Latombe","year":"1991","unstructured":"Latombe JC (1991) Robot motion planning. Kluwer Academic, Dordrecht"},{"key":"71_CR16","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877","volume-title":"Planning algorithms","author":"SM LaValle","year":"2006","unstructured":"LaValle SM (2006) Planning algorithms. Cambridge University Press, Cambridge"},{"key":"71_CR17","first-page":"1118","volume-title":"Proceedings of the international joint conference on artificial intelligence (IJCAI)","author":"S Leroy","year":"1999","unstructured":"Leroy S, Laumond JP, Simeon T (1999) Multiple path coordination for mobile robots: a geometric algorithm. In: Proceedings of the international joint conference on artificial intelligence (IJCAI), pp 1118\u20131123"},{"key":"71_CR18","first-page":"262","volume-title":"Proceedings of the fifteenth international conference on automated planning and scheduling (ICAPS)","author":"M Likhachev","year":"2005","unstructured":"Likhachev M, Ferguson DI, Gordon GJ, Stentz A, Thrun S (2005) Anytime dynamic A*: an anytime, replanning algorithm. In: Proceedings of the fifteenth international conference on automated planning and scheduling (ICAPS), pp 262\u2013271"},{"key":"71_CR19","first-page":"607","volume-title":"Proceedings of the VIII ENIA\/CSBC","author":"RQ Maffei","year":"2011","unstructured":"Maffei RQ, Botelho SSC, Silveira L, Drews P Jr, Duarte Filho NL, Bicho AL, Almeida FR, Longaray MM (2011) Space D*: um algoritmo para path-planning multi-rob\u00f4s. In: Proceedings of the VIII ENIA\/CSBC, pp 607\u2013618"},{"key":"71_CR20","doi-asserted-by":"publisher","first-page":"164","DOI":"10.1145\/267658.267691","volume-title":"Proceedings of the first international conference on autonomous agents","author":"R L\u00f3pez de M\u00e0ntaras","year":"1997","unstructured":"L\u00f3pez de M\u00e0ntaras R, Amat J, Esteva F, L\u00f3pez M, Sierra C (1997) Generation of unknown environment maps by cooperative low-cost robots. In: Proceedings of the first international conference on autonomous agents, pp 164\u2013169"},{"key":"71_CR21","first-page":"328","volume-title":"Proceedings of the international conference on collaborative computing: networking, applications and worksharing","author":"T Okada","year":"2007","unstructured":"Okada T, Beuran R, Nakata J, Tan Y, Shinoda Y (2007) Collaborative motion planning of autonomous robots. In: Proceedings of the international conference on collaborative computing: networking, applications and worksharing, pp 328\u2013335"},{"key":"71_CR22","doi-asserted-by":"publisher","first-page":"1170","DOI":"10.1109\/TRO.2007.909810","volume":"23","author":"L Pallottino","year":"2007","unstructured":"Pallottino L, Scordio VG, Frazzoli E, Bicchi A (2007) Decentralized cooperative policy for conflict resolution in multi-vehicle systems. IEEE Trans Robot 23:1170\u20131183","journal-title":"IEEE Trans Robot"},{"key":"71_CR23","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1109\/ROBOT.1990.125937","volume-title":"Proceedings of IEEE international conference on robotics and automation (ICRA)","author":"D Parsons","year":"1990","unstructured":"Parsons D, Canny J (1990) A motion planner for multiple mobile robots. In: Proceedings of IEEE international conference on robotics and automation (ICRA), pp 8\u201313"},{"key":"71_CR24","first-page":"267","volume-title":"Proceedings of the second multirobot systems workshop","author":"GAS Pereira","year":"2003","unstructured":"Pereira GAS, Das AK, Kumar V, Campos MFM (2003) Decentralized motion planning for multiple robots subject to sensing and communication constraints. In: Proceedings of the second multirobot systems workshop, pp 267\u2013278"},{"key":"71_CR25","first-page":"1340","volume-title":"Proceedings of the fifteenth international joint conference on artificial intelligence","author":"IM Rekleitis","year":"1997","unstructured":"Rekleitis IM, Dudek G, Milios EE (1997) Multi-robot exploration of an unknown environment, efficiently reducing the odometry error. In: Proceedings of the fifteenth international joint conference on artificial intelligence, pp 1340\u20131345"},{"key":"71_CR26","doi-asserted-by":"publisher","first-page":"702","DOI":"10.1145\/1073204.1073251","volume":"24","author":"A Runions","year":"2005","unstructured":"Runions A, Fuhrer M, Lane B, Rolland-Lagan PFAG, Prusinkiewicz P (2005) Modeling and visualization of leaf venation patterns. ACM Trans Graph 24:702\u2013711","journal-title":"ACM Trans Graph"},{"key":"71_CR27","volume-title":"Proceedings of the international joint conference on artificial intelligence","author":"A Stentz","year":"1995","unstructured":"Stentz A (1995) The focussed D* algorithm for real-time replanning. In: Proceedings of the international joint conference on artificial intelligence"},{"key":"71_CR28","volume-title":"Proceedings of the robotics: science and systems","author":"J Van den Berg","year":"2009","unstructured":"Van den Berg J, Snoeyink J, Lin M, Manocha D (2009) Centralized path-planning for multiple robots: optimal decoupling into sequential plans. In: Proceedings of the robotics: science and systems (RSS)"},{"key":"71_CR29","first-page":"2366","volume-title":"Proceedings of the IEEE international conference on robotics and automation (ICRA)","author":"JP Van den Berg","year":"2006","unstructured":"Van den Berg JP, Ferguson D, Kuffner J (2006) Anytime path-planning and replanning in dynamic environments. In: Proceedings of the IEEE international conference on robotics and automation (ICRA), pp 2366\u20132371"},{"key":"71_CR30","first-page":"139","volume-title":"Proceedings of the 12th computer vision winter workshop (CVWW)","author":"D Wagner","year":"2007","unstructured":"Wagner D, Schmalstieg D (2007) ARToolKitPlus for pose tracking on mobile devices. In: Proceedings of the 12th computer vision winter workshop (CVWW), pp 139\u2013146"},{"key":"71_CR31","first-page":"1160","volume-title":"Proceedings of the IEEE\/RSJ international conference on intelligent robots and systems","author":"KM Wurm","year":"2008","unstructured":"Wurm KM, Stachniss C, Burgard W (2008) Coordinated multi-robot exploration using a segmentation of the environment. In: Proceedings of the IEEE\/RSJ international conference on intelligent robots and systems, pp 1160\u20131165"},{"key":"71_CR32","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1145\/280765.280773","volume-title":"Proceedings of the second international conference on autonomous agents","author":"B Yamauchi","year":"1998","unstructured":"Yamauchi B (1998) Frontier-based exploration using multiple robots. In: Proceedings of the second international conference on autonomous agents, pp 47\u201353"}],"container-title":["Journal of the Brazilian Computer Society"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-012-0071-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s13173-012-0071-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-012-0071-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s13173-012-0071-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,1]],"date-time":"2021-09-01T18:37:14Z","timestamp":1630521434000},"score":1,"resource":{"primary":{"URL":"https:\/\/journal-bcs.springeropen.com\/articles\/10.1007\/s13173-012-0071-9"}},"subtitle":["A path-planning algorithm for multiple robots in unknown environments"],"short-title":[],"issued":{"date-parts":[[2012,4,6]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,11]]}},"alternative-id":["71"],"URL":"https:\/\/doi.org\/10.1007\/s13173-012-0071-9","relation":{},"ISSN":["0104-6500","1678-4804"],"issn-type":[{"value":"0104-6500","type":"print"},{"value":"1678-4804","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,4,6]]},"assertion":[{"value":"10 October 2011","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 March 2012","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 April 2012","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}