{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,3]],"date-time":"2025-03-03T14:40:23Z","timestamp":1741012823872,"version":"3.38.0"},"reference-count":32,"publisher":"SAGE Publications","issue":"3","license":[{"start":{"date-parts":[[2007,3,1]],"date-time":"2007-03-01T00:00:00Z","timestamp":1172707200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2007,3]]},"abstract":"<jats:p> The following motion coordination problem is studied: given n mobile vehicles and n source-destination pairs in the plane, what is the minimum time needed to transfer each vehicle from its source to its destination, avoiding conflicts with other vehicles? In the proposed model, vehicles do not explicitly communicate their intentions, and only have sensory information about the current position and velocity of their neighbors to ensure no conflicts. The environment is free of obstacles and a conflict occurs when the distance between any two vehicles is smaller than a velocity-dependent safety distance. The situation analyzed in which the vehicle size is such that at least a constant fraction of the n vehicles can be fitted inside the environment simultaneously. In the \u201cbest\u201d case in which the source and destination points can be chosen ideally to maximize the transfer efficiency, it is shown that the transfer takes \u0398 ([UNKNOWN][UNKNOWN]n) time to complete, where [UNKNOWN] is the average distance between the source and destination points. It is shown that there exist a \u201cworst\u201d case distribution of the source and destination points, for which the transfer of vehicles takes at least \u03a9(n) time. The case is also analyzed in which source and destination points are generated randomly according to a uniform distribution, and an algorithm is presented providing a constructive upper bound on the time needed to transfer vehicles from sources to their corresponding destinations, proving that the transfer takes \u0398 ([UNKNOWN]n) time, with high probability, thus recovering the best case performance. <\/jats:p>","DOI":"10.1177\/0278364906076226","type":"journal-article","created":{"date-parts":[[2007,2,26]],"date-time":"2007-02-26T14:49:17Z","timestamp":1172501357000},"page":"255-271","source":"Crossref","is-referenced-by-count":25,"title":["Transfer Time Complexity of Conflict-free Vehicle Routing with no Communications"],"prefix":"10.1177","volume":"26","author":[{"given":"Vikrant","family":"Sharma","sequence":"first","affiliation":[{"name":"Aerospace Engineering Department, University of Illinois at Urbana-Champaign, Urbana, IL 61801;"}]},{"given":"Michael","family":"Savchenko","sequence":"additional","affiliation":[{"name":"Aerospace Engineering Department, University of Illinois at Urbana-Champaign, Urbana, IL 61801;"}]},{"given":"Emilio","family":"Frazzoli","sequence":"additional","affiliation":[{"name":"Aeronautical and Astronautical Engineering Department, Massachusetts Institute of Technology, Cambridge, MA 02139;"}]},{"given":"Petros G.","family":"Voulgaris","sequence":"additional","affiliation":[{"name":"Aerospace Engineering Department and the Coordinated Science Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL 61801;"}]}],"member":"179","published-online":{"date-parts":[[2007,3,1]]},"reference":[{"first-page":"624","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"Akella, S.","key":"atypb1"},{"first-page":"2573","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"Alami, R.","key":"atypb2"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1109\/70.143360"},{"volume-title":"Applied Optimal Control","year":"1975","author":"Bryson, A. E.","key":"atypb4"},{"first-page":"322","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"Buckley, S. J.","key":"atypb5"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1109\/21.279000"},{"first-page":"3981","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"Chitsaz, H.","key":"atypb7"},{"volume-title":"Proceedings of IEEE International Symposium on Parallel and Distributed Processing","author":"Chlebus, B. S.","key":"atypb8"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.2307\/2687522"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2002.808466"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/BF01840371"},{"first-page":"171","volume-title":"Proceedings of Sixth International Workshop on Algorithmic Foundation of Robotics","author":"Ghrist, R.","key":"atypb12"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2001.916631"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1109\/18.825799"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1177\/027836498400300405"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1177\/027836498600500304"},{"volume-title":"Proceedings of Fifth International Workshop on the Algorithmic Foundations of Robotics","author":"Klavins, E.","key":"atypb17"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1109\/70.736775"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2005.1582595"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2005.1583508"},{"volume-title":"Proceedings of Conference on Information Sciences and Systems","author":"Neely, M. D.","key":"atypb21"},{"first-page":"484","volume-title":"Proceedings of IEEE International Conference on Robotics and Automation","author":"O'Donnell, P. A.","key":"atypb22"},{"key":"atypb23","volume-title":"Probability, Random Variables, and Stochstic Processes","author":"Papoulis, A.","year":"1984","edition":"2"},{"first-page":"221","volume-title":"Proceedings of Fifth International Workshop on the Algorithmic Foundations of Robotics (WAFR)","author":"Peng, J.","key":"atypb24"},{"first-page":"421","volume-title":"Proceedings of the 20th IEEE Symposium on Foundations of Computer Science","author":"Reif, J. H.","key":"atypb25"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(83)90014-3"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1177\/027836498300200304"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160360305"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1109\/70.988973"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718515"},{"key":"atypb31","volume-title":"Introduction to Graph Theory","author":"West, D.","year":"2000","edition":"2"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1023\/B:WINE.0000013081.09837.c0"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364906076226","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364906076226","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,3]],"date-time":"2025-03-03T13:32:28Z","timestamp":1741008748000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364906076226"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,3]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2007,3]]}},"alternative-id":["10.1177\/0278364906076226"],"URL":"https:\/\/doi.org\/10.1177\/0278364906076226","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"type":"print","value":"0278-3649"},{"type":"electronic","value":"1741-3176"}],"subject":[],"published":{"date-parts":[[2007,3]]}}}