{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,7]],"date-time":"2025-11-07T13:30:56Z","timestamp":1762522256398,"version":"3.28.0"},"reference-count":54,"publisher":"IEEE","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018,10]]},"DOI":"10.1109\/iros.2018.8594417","type":"proceedings-article","created":{"date-parts":[[2019,1,24]],"date-time":"2019-01-24T02:33:30Z","timestamp":1548297210000},"page":"1-9","source":"Crossref","is-referenced-by-count":11,"title":["SEAR: A Polynomial- Time Multi-Robot Path Planning Algorithm with Expected Constant-Factor Optimality Guarantee"],"prefix":"10.1109","author":[{"given":"Shuai D.","family":"Han","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edgar J.","family":"Rodriguez","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jingjin","family":"Yu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2005.1545306"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2009.V.018"},{"key":"ref33","article-title":"Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning","author":"solovey","year":"2014","journal-title":"Proceedings Workshop on Algorithmic Foundations of Robotics"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1109\/TSSC.1968.300136"},{"key":"ref31","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546877","author":"lavalle","year":"2006","journal-title":"Planning Algorithms"},{"key":"ref30","volume":"124","author":"latombe","year":"2012","journal-title":"Robot Motion Planning"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2002.1014852"},{"key":"ref36","first-page":"1","article-title":"Efficient multi-robot motion planning for unlabeled discs in simple polygons","author":"adler","year":"0","journal-title":"Algorithmic Foundations of Robotics XI"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2012.6426233"},{"key":"ref34","article-title":"Complexity of the generalized mover's problem","author":"reif","year":"1985","journal-title":"DTIC Document Tech Rep"},{"key":"ref28","doi-asserted-by":"crossref","first-page":"541","DOI":"10.1007\/s00371-014-0946-1","article-title":"Velocity-based modeling of physical interactions in dense crowds","volume":"31","author":"kim","year":"2015","journal-title":"The Visual Computer"},{"key":"ref27","doi-asserted-by":"crossref","first-page":"696","DOI":"10.1109\/TRO.2011.2120810","article-title":"The hybrid reciprocal velocity obstacle","volume":"27","author":"snape","year":"2011","journal-title":"IEEE Transactions on Robotics"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(83)90014-3"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1177\/027836498400300405"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(84)90130-3"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2004.1307146"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008937911390"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s11036-009-0153-x"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.1995.525802"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1177\/0278364905059067"},{"key":"ref26","doi-asserted-by":"crossref","first-page":"94","DOI":"10.1109\/ROMAN.2012.6343737","article-title":"Pedestrian-inspired sampling-based multi-robot collision avoidance","author":"knepper","year":"2012","journal-title":"2012 IEEE RO-MAN The 21st IEEE International Symposium on Robot and Human Interactive Communication IEEE"},{"key":"ref25","article-title":"Cooperative search and rescue with a team of mobile robots","author":"jennings","year":"1997","journal-title":"Proceedings IEEE International Conference on Robotics & Automation"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2016.2593448"},{"key":"ref51","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1007\/978-3-319-51532-8_30","article-title":"An effective algorithmic framework for near optimal multi-robot path planning","author":"yu","year":"2018","journal-title":"Robotics Research"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2017.7989176"},{"journal-title":"The best known packings of equal circles in a circle (complete up to N = 2600)","year":"2016","author":"specht","key":"ref53"},{"journal-title":"Gurobi Optimizer Reference Manual","year":"2014","key":"ref52"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2008.4543489"},{"key":"ref11","first-page":"668","article-title":"Complete algorithms for cooperative pathfinding problems","author":"standley","year":"2011","journal-title":"Proceedings International Joint Conference on Artificial Intelligence"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1016\/S0921-8890(02)00256-7"},{"key":"ref12","article-title":"k-color multi-robot motion planning","author":"solovey","year":"2012","journal-title":"Proceedings Workshop on Algorithmic Foundations of Robotics"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913515307"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2015.XI.011"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2014.11.001"},{"key":"ref16","article-title":"Improved bounded-suboptimal multi-agent path finding solvers","author":"cohen","year":"2016","journal-title":"In International Joint Conference on Artificial Intelligence"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2017.7989657"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1007\/s004539910025"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509502"},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2015.2503143"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.15607\/RSS.2015.XI.046"},{"key":"ref6","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1007\/978-3-319-60916-4_34","article-title":"A complete algorithm for generating safe trajectories for multi-robot teams","author":"tang","year":"2018","journal-title":"Robotics Research Springer"},{"key":"ref5","first-page":"48","article-title":"Expected constant-factor optimal multi-robot path planning in well-connected environments","year":"2017","journal-title":"2017 International Symposium on Multi-Robot and Multi-Agent Systems (MRS) MRS"},{"key":"ref8","doi-asserted-by":"publisher","DOI":"10.1109\/70.736775"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.21236\/ADA196213"},{"key":"ref49","doi-asserted-by":"crossref","DOI":"10.1609\/aaai.v27i1.8592","article-title":"A general formal framework for pathfinding problems with multiple agents","author":"erdem","year":"2013","journal-title":"AAAI"},{"key":"ref9","first-page":"2612","article-title":"A distributed and optimal motion planning approach for multiple mobile robots","author":"guo","year":"2002","journal-title":"Proceedings IEEE International Conference on Robotics & Automation"},{"key":"ref46","article-title":"Finding the shortest move-sequence in the graph-generalized 15-puzzle is NP-hard","author":"goldreich","year":"1984","journal-title":"laboratory for Computer Science Massachusetts Institute of Technology Unpublished manuscript"},{"journal-title":"A linear time algorithm for the feasibility of pebble motion on graphs","year":"2013","author":"yu","key":"ref45"},{"key":"ref48","article-title":"Towards optimal cooperative path planning in hard setups through satisfiability solving","author":"surynek","year":"2012","journal-title":"Proc 4 Pacific Rim International Conference on Artificial Intelligence"},{"key":"ref47","article-title":"Icbs: The improved conflict-based search algorithm for multi-agent pathfinding","author":"boyarski","year":"2015","journal-title":"Eighth Annual Symposium on Combinatorial Search"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1177\/027836498600500304"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2006.282536"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-009-9290-7"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009259"}],"event":{"name":"2018 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS)","start":{"date-parts":[[2018,10,1]]},"location":"Madrid","end":{"date-parts":[[2018,10,5]]}},"container-title":["2018 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS)"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/8574473\/8593358\/08594417.pdf?arnumber=8594417","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,10]],"date-time":"2022-09-10T21:03:58Z","timestamp":1662843838000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/8594417\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,10]]},"references-count":54,"URL":"https:\/\/doi.org\/10.1109\/iros.2018.8594417","relation":{},"subject":[],"published":{"date-parts":[[2018,10]]}}}