{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,27]],"date-time":"2026-02-27T04:28:09Z","timestamp":1772166489826,"version":"3.50.1"},"reference-count":56,"publisher":"SAGE Publications","issue":"7","license":[{"start":{"date-parts":[[2021,4,29]],"date-time":"2021-04-29T00:00:00Z","timestamp":1619654400000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.sagepub.com\/licence-information-for-chorus"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["#N000141812374"],"award-info":[{"award-number":["#N000141812374"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2020,6]]},"abstract":"<jats:p> This article proposes a new highly scalable and asymptotically optimal control synthesis algorithm from linear temporal logic specifications, called [Formula: see text] for large-Scale optimal Temporal Logic Synthesis, that is designed to solve complex temporal planning problems in large-scale multi-robot systems. Existing planning approaches with temporal logic specifications rely on graph search techniques applied to a product automaton constructed among the robots. In our previous work, we have proposed a more tractable sampling-based algorithm that builds incrementally trees that approximate the state space and transitions of the synchronous product automaton and does not require sophisticated graph search techniques. Here, we extend our previous work by introducing bias in the sampling process that is guided by transitions in the B\u00fcchi automaton that belong to the shortest path to the accepting states. This allows us to synthesize optimal motion plans from product automata with hundreds of orders of magnitude more states than those that existing optimal control synthesis methods or off-the-shelf model checkers can manipulate. We show that [Formula: see text] is probabilistically complete and asymptotically optimal and has exponential convergence rate. This is the first time that convergence rate results are provided for sampling-based optimal control synthesis methods. We provide simulation results that show that [Formula: see text] can synthesize optimal motion plans for very large multi-robot systems, which is impossible using state-of-the-art methods. <\/jats:p>","DOI":"10.1177\/0278364920913922","type":"journal-article","created":{"date-parts":[[2020,4,30]],"date-time":"2020-04-30T06:18:07Z","timestamp":1588227487000},"page":"812-836","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":101,"title":["STyLuS<sup>*<\/sup>: A Temporal Logic Optimal Control Synthesis Algorithm for Large-Scale Multi-Robot Systems"],"prefix":"10.1177","volume":"39","author":[{"given":"Yiannis","family":"Kantaros","sequence":"first","affiliation":[{"name":"Department of Mechanical Engineering and Materials Science, Duke University, Durham, NC, USA"}]},{"given":"Michael M","family":"Zavlanos","sequence":"additional","affiliation":[{"name":"Department of Mechanical Engineering and Materials Science, Duke University, Durham, NC, USA"}]}],"member":"179","published-online":{"date-parts":[[2020,4,29]]},"reference":[{"key":"bibr1-0278364920913922","volume-title":"Principles of Model Checking","author":"Baier C","year":"2008"},{"key":"bibr2-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2004.1428674"},{"key":"bibr3-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2005.851359"},{"key":"bibr4-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918755924"},{"key":"bibr5-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509503"},{"key":"bibr6-0278364920913922","first-page":"7104","volume-title":"Conference on Decision and Control (CDC)","author":"Boskos D","year":"2015"},{"key":"bibr7-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/TCIAIG.2012.2186810"},{"key":"bibr8-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08867-9_22"},{"key":"bibr9-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2011.6160740"},{"key":"bibr10-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2011.2163434"},{"key":"bibr11-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1214\/aoap\/1037125856"},{"key":"bibr12-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1007\/s10703-006-0027-9"},{"key":"bibr13-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45657-0_29"},{"key":"bibr14-0278364920913922","volume-title":"Model Checking","author":"Clarke EM","year":"1999"},{"key":"bibr15-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2003.1249705"},{"key":"bibr16-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/ICST.2009.33"},{"key":"bibr17-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44585-4_6"},{"key":"bibr18-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914546174"},{"key":"bibr19-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2017.7989036"},{"key":"bibr20-0278364920913922","volume-title":"The SPIN Model Checker: Primer and Reference Manual","author":"Holzmann GJ","year":"2004"},{"key":"bibr21-0278364920913922","author":"Hong Y","year":"2011","journal-title":"Technical Report 11_2"},{"key":"bibr22-0278364920913922","author":"Huh J","year":"2019","journal-title":"arXiv preprint arXiv:1901.00101"},{"key":"bibr23-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915577958"},{"key":"bibr24-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2016.2626400"},{"key":"bibr25-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2019.2893161"},{"key":"bibr26-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2018.2861901"},{"key":"bibr27-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.2015.7421315"},{"key":"bibr28-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1145\/3055004.3055027"},{"key":"bibr29-0278364920913922","volume-title":"IEEE Transactions on Automatic Control","author":"Kantaros Y","year":"2018"},{"key":"bibr30-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/ICCPS.2018.00024"},{"key":"bibr31-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2018.8618922"},{"key":"bibr32-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"bibr33-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2012.6315419"},{"key":"bibr34-0278364920913922","author":"Khalidi D","year":"2018","journal-title":"arXiv preprint arXiv:1809.05817"},{"key":"bibr35-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1007\/11730637_27"},{"key":"bibr36-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2009.2035776"},{"key":"bibr37-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1007\/11871842_29"},{"key":"bibr38-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2007.363946"},{"key":"bibr39-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2009.2030225"},{"key":"bibr40-0278364920913922","volume-title":"Randomized Algorithms","author":"Motwani R","year":"2010"},{"key":"bibr41-0278364920913922","volume-title":"Artificial Intelligence: A Modern Approach","author":"Russell S","year":"1995"},{"key":"bibr42-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2014.6942758"},{"key":"bibr43-0278364920913922","volume-title":"13th International Symposium on Distributed Autonomous Robotic Systems","author":"Schillinger P","year":"2016"},{"key":"bibr44-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918774135"},{"key":"bibr45-0278364920913922","volume-title":"Algorithms","author":"Sedgewick R","year":"2011"},{"key":"bibr46-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911417911"},{"key":"bibr47-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914537008"},{"key":"bibr48-0278364920913922","doi-asserted-by":"crossref","unstructured":"Ulusoy A, Smith SL, Ding X, Belta C, Rus D (2011) LOMP: A toolset for optimal multi-robot path planning subject to LTL specifications. Available at: http:\/\/sites.bu.edu\/hyness\/lomp\/.","DOI":"10.1109\/IROS.2011.6048524"},{"key":"bibr49-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-55146-8_24"},{"key":"bibr50-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913487931"},{"key":"bibr51-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1177\/0278364905060132"},{"key":"bibr52-0278364920913922","volume-title":"1st Symposium in Logic in Computer Science (LICS)","author":"Vardi MY","year":"1986"},{"key":"bibr53-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6697051"},{"key":"bibr54-0278364920913922","author":"Zagoruyko S","year":"2019","journal-title":"arXiv preprint arXiv:1904.10348"},{"key":"bibr55-0278364920913922","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2008.4543787"},{"key":"bibr56-0278364920913922","volume-title":"IEEE 2018 International Conference on Robotics and Automation","author":"Zucker M","year":"2018"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364920913922","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364920913922","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364920913922","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364920913922","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,3]],"date-time":"2025-03-03T02:02:16Z","timestamp":1740967336000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364920913922"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,29]]},"references-count":56,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["10.1177\/0278364920913922"],"URL":"https:\/\/doi.org\/10.1177\/0278364920913922","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,4,29]]}}}