{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T15:06:32Z","timestamp":1769094392341,"version":"3.49.0"},"publisher-location":"Cham","reference-count":22,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319165943","type":"print"},{"value":"9783319165950","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-16595-0_42","type":"book-chapter","created":{"date-parts":[[2015,4,29]],"date-time":"2015-04-29T13:42:10Z","timestamp":1430314930000},"page":"729-746","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":24,"title":["Pebble Motion on Graphs with Rotations: Efficient Feasibility Tests and Planning Algorithms"],"prefix":"10.1007","author":[{"given":"Jingjin","family":"Yu","sequence":"first","affiliation":[]},{"given":"Daniela","family":"Rus","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,4,30]]},"reference":[{"key":"42_CR1","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/PL00009259","volume":"23","author":"V Auletta","year":"1999","unstructured":"Auletta, V., Monti, A., Parente, M., Persiano, P.: A linear-time algorithm for the feasibility of pebble motion on trees. Algorithmica 23, 223\u2013245 (1999)","journal-title":"Algorithmica"},{"key":"42_CR2","unstructured":"Babai, L., Beals, R., Seress, \u00c1.: On the diameter of the symmetric group: polynomial bounds. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1108\u20131112 (2004)"},{"key":"42_CR3","doi-asserted-by":"crossref","unstructured":"Driscoll J.R., Furst M.L.: On the diameter of permutation groups. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pp. 152\u2013160 (1983)","DOI":"10.1145\/800061.808744"},{"issue":"2","key":"42_CR4","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1016\/0890-5401(87)90043-5","volume":"72","author":"JR Driscoll","year":"1987","unstructured":"Driscoll, J.R., Furst, M.L.: Computing short generator sequences. Inf. Comput. 72(2), 117\u2013132 (1987)","journal-title":"Inf. Comput."},{"key":"42_CR5","unstructured":"Goldreich, O.: Finding the shortest move-sequence in the graph-generalized 15-puzzle is np-hard. Laboratory Computer Science Massachusetts Institute of Technology, unpublished manuscript (1984)"},{"key":"42_CR6","doi-asserted-by":"publisher","first-page":"610","DOI":"10.1007\/s00453-009-9290-7","volume":"58","author":"G Goraly","year":"2010","unstructured":"Goraly, G., Hassin, R.: Multi-color pebble motion on graph. Algorithmica 58, 610\u2013636 (2010)","journal-title":"Algorithmica"},{"issue":"11","key":"42_CR7","doi-asserted-by":"publisher","first-page":"933","DOI":"10.1177\/0278364905059067","volume":"24","author":"EJ Griffith","year":"2005","unstructured":"Griffith, E.J., Akella, S.: Coordinating multiple droplets in planar array digital microfluidic systems. Int. J. Robot. Res. 24(11), 933\u2013949 (2005)","journal-title":"Int. J. Robot. Res."},{"key":"42_CR8","doi-asserted-by":"crossref","unstructured":"Kornhauser, D., Miller, G., Spirakis, P.: Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. In: Proceedings of the 25th Annual Symposium on Foundations of Computer Science, pp. 241\u2013250 (1984)","DOI":"10.1109\/SFCS.1984.715921"},{"key":"42_CR9","unstructured":"Krontiris, A., Luna, R., Bekris, K.E.: From feasibility tests to path planners for multi-agent pathfinding. In: Symposium on Combinatorial Search (2013)"},{"key":"42_CR10","volume-title":"Mathematical Puzzles of Sam Loyd","author":"S Loyd","year":"1959","unstructured":"Loyd, S.: Mathematical Puzzles of Sam Loyd. Dover, New York (1959)"},{"key":"42_CR11","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/S0747-7171(08)80001-6","volume":"10","author":"D Ratner","year":"1990","unstructured":"Ratner, D., Warmuth, M.: The $$(n^2-1)$$-puzzle and related relocation problems. J. Symb. Comput. 10, 111\u2013137 (1990)","journal-title":"J. Symb. Comput."},{"key":"42_CR12","doi-asserted-by":"crossref","unstructured":"Reif, J.H., Slee, S.: Asymptotically optimal kinodynamic motion planning for self-reconfigurable robots. In: The Seventh International Workshop on Algorithmic Foundations of Robotics (2006)","DOI":"10.15607\/RSS.2007.III.020"},{"key":"42_CR13","doi-asserted-by":"crossref","unstructured":"Solovey, K., Halperin, D.: $$k$$-color multi-robot motion planning. In: The Tenth International Workshop on Algorithmic Foundations of Robotics (2012)","DOI":"10.1007\/978-3-642-36279-8_12"},{"key":"42_CR14","unstructured":"Standley, T., Korf R.: Complete algorithms for cooperative pathfinding problems. In: Twenty-Second International Joint Conference on Artificial Intelligence, pp. 668\u2013673 (2011)"},{"key":"42_CR15","doi-asserted-by":"publisher","first-page":"399","DOI":"10.2307\/2369236","volume":"2","author":"EW Story","year":"1879","unstructured":"Story, E.W.: Note on the \u201815\u2019 puzzle. Am. J. Math. 2, 399\u2013404 (1879)","journal-title":"Am. J. Math."},{"key":"42_CR16","doi-asserted-by":"crossref","unstructured":"Surynek, P.: An optimization variant of multi-robot path planning is intractable. In: The Twenty-Fourth AAAI Conference on Artificial Intelligence, pp. 1261\u20131263 (2010)","DOI":"10.1609\/aaai.v24i1.7767"},{"issue":"2","key":"42_CR17","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1137\/0201010","volume":"1","author":"RE Tarjan","year":"1972","unstructured":"Tarjan, R.E.: Depth-first search and linear graph algorithms. SIAM J. Comput. 1(2), 140\u2013160 (1972)","journal-title":"SIAM J. Comput."},{"key":"42_CR18","doi-asserted-by":"crossref","unstructured":"van den Berg, J., Snoeyink, J., Lin, M., Manocha, D.: Centralized path planning for multiple robots: optimal decoupling into sequential plans. In: Proceedings Robotics Science and Systems (2009)","DOI":"10.15607\/RSS.2009.V.018"},{"key":"42_CR19","doi-asserted-by":"crossref","unstructured":"Wagner, G., Choset. H.: M*: a complete multirobot path planning algorithm with performance bounds. In: Proceedings IEEE\/RSJ International Conference on Intelligent Robots and Systems, pp. 3260\u20133267 (2011)","DOI":"10.1109\/IROS.2011.6095022"},{"key":"42_CR20","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/0095-8956(74)90098-7","volume":"16","author":"RM Wilson","year":"1974","unstructured":"Wilson, R.M.: Graph puzzles, homotopy, and the alternating group. J. Comb. Theory (B) 16, 86\u201396 (1974)","journal-title":"J. Comb. Theory (B)"},{"key":"42_CR21","unstructured":"Yu, J.: A linear time algorithm for the feasibility of pebble motion on graphs. arXiv:1301.2342 (2013)"},{"key":"42_CR22","doi-asserted-by":"crossref","unstructured":"Yu, J., LaValle S.M.: Structure and intractability of optimal multi-robot path planning on graphs. In: Proceedings AAAI National Conference on Artificial Intelligence, pp. 1444\u20131449 (2013)","DOI":"10.1609\/aaai.v27i1.8541"}],"container-title":["Springer Tracts in Advanced Robotics","Algorithmic Foundations of Robotics XI"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-16595-0_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,21]],"date-time":"2023-02-21T02:50:48Z","timestamp":1676947848000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-16595-0_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319165943","9783319165950"],"references-count":22,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-16595-0_42","relation":{},"ISSN":["1610-7438","1610-742X"],"issn-type":[{"value":"1610-7438","type":"print"},{"value":"1610-742X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"30 April 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}