{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T01:45:17Z","timestamp":1778031917236,"version":"3.51.4"},"reference-count":71,"publisher":"SAGE Publications","issue":"8","license":[{"start":{"date-parts":[[2021,6,4]],"date-time":"2021-06-04T00:00:00Z","timestamp":1622764800000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.sagepub.com\/licence-information-for-chorus"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1035588"],"award-info":[{"award-number":["CNS-1035588"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["NRI-1426907"],"award-info":[{"award-number":["NRI-1426907"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["MURI N00014- 09-1051"],"award-info":[{"award-number":["MURI N00014- 09-1051"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["MURI N00014-10-10952"],"award-info":[{"award-number":["MURI N00014-10-10952"]}],"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,7]]},"abstract":"<jats:p>We develop a sampling-based motion planning algorithm that combines long-term temporal logic goals with short-term reactive requirements. The mission specification has two parts: (1) a global specification given as a linear temporal logic (LTL) formula over a set of static service requests that occur at the regions of a known environment, and (2) a local specification that requires servicing a set of dynamic requests that can be sensed locally during the execution. The proposed computational framework consists of two main ingredients: (a) an off-line sampling-based algorithm for the construction of a global transition system that contains a path satisfying the LTL formula; and (b) an on-line sampling-based algorithm to generate paths that service the local requests, while making sure that the satisfaction of the global specification is not affected. The off-line algorithm has four main features. First, it is incremental, in the sense that the procedure for finding a satisfying path at each iteration scales only with the number of new samples generated at that iteration. Second, the underlying graph is sparse, which implies low complexity for the overall method. Third, it is probabilistically complete. Fourth, under some mild assumptions, it has the best possible complexity bound. The on-line algorithm leverages ideas from LTL monitoring and potential functions to ensure progress towards the satisfaction of the global specification while servicing locally sensed requests. Examples and experimental trials illustrating the usefulness and the performance of the framework are included.<\/jats:p>","DOI":"10.1177\/0278364920918919","type":"journal-article","created":{"date-parts":[[2020,6,4]],"date-time":"2020-06-04T10:38:18Z","timestamp":1591267098000},"page":"1002-1028","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":49,"title":["Reactive sampling-based path planning with temporal logic specifications"],"prefix":"10.1177","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1132-1462","authenticated-orcid":false,"given":"Cristian Ioan","family":"Vasile","sequence":"first","affiliation":[{"name":"Laboratory for Information and Decision Systems,Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, Cambridge, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiao","family":"Li","sequence":"additional","affiliation":[{"name":"Department of Mechanical Engineering, Boston University, Boston, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Calin","family":"Belta","sequence":"additional","affiliation":[{"name":"Department of Mechanical Engineering, Boston University, Boston, MA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"179","published-online":{"date-parts":[[2020,6,4]]},"reference":[{"key":"bibr1-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913501564"},{"key":"bibr2-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2007.902731"},{"key":"bibr3-0278364920918919","volume-title":"Principles of Model Checking","author":"Baier C","year":"2008"},{"key":"bibr4-0278364920918919","unstructured":"Bauer A, Leucker M, Schallhart C (2007) Runtime verification for LTL and TLTL. Technical Report TUM-I0724, Institut f\u00fcr Informatik, Technische Universit\u00e4t M\u00fcnchen."},{"key":"bibr5-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-018-9766-x"},{"key":"bibr6-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2005.851359"},{"key":"bibr7-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-50763-7"},{"key":"bibr8-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2010.5509503"},{"key":"bibr9-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2007.363984"},{"key":"bibr10-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6225075"},{"key":"bibr11-0278364920918919","volume-title":"Principles of Robot Motion: Theory, Algorithms, and Implementations","author":"Choset H","year":"2005"},{"key":"bibr12-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-6568-7"},{"key":"bibr13-0278364920918919","unstructured":"Cranen S, Groote JF, Reniers M (2010) A linear translation from LTL to the first-order modal \u03bc-calculus. Technical Report 10-09, Computer Science Reports, Eindhoven University of Technology."},{"key":"bibr14-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/MRA.2011.942117"},{"key":"bibr15-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2013.11.030"},{"key":"bibr16-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6631156"},{"key":"bibr17-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/MRS.2017.8250940"},{"key":"bibr18-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46520-3_8"},{"key":"bibr19-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2000.876993"},{"key":"bibr20-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44585-4_6"},{"key":"bibr21-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1145\/2071379.2071382"},{"key":"bibr22-0278364920918919","first-page":"11","volume-title":"Proceedings of the 7th Python in Science Conference (SciPy2008)","author":"Hagberg AA","year":"2008"},{"key":"bibr23-0278364920918919","first-page":"193","volume-title":"Algorithmic Foundations of Robotics IX","author":"Hauser K","year":"2011"},{"key":"bibr24-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2016.2602363"},{"key":"bibr25-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2017.8206426"},{"key":"bibr26-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2018.2853558"},{"key":"bibr27-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2009.5400278"},{"key":"bibr28-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406761"},{"key":"bibr29-0278364920918919","first-page":"735","author":"Karaman S","year":"2012","journal-title":"American Control Conference (ACC)"},{"key":"bibr30-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2018.8462968"},{"key":"bibr31-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/70.508439"},{"key":"bibr32-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-control-060117-105226"},{"key":"bibr33-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2018.2888947"},{"key":"bibr34-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2007.914952"},{"key":"bibr35-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2007.363946"},{"key":"bibr36-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-control-060117-104838"},{"key":"bibr37-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/TCST.2008.2012116"},{"key":"bibr38-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2016.2544339"},{"key":"bibr39-0278364920918919","volume-title":"Robot Motion Planning","volume":"124","author":"Latombe JC","year":"2012"},{"key":"bibr40-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877"},{"key":"bibr41-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1177\/02783640122067453"},{"key":"bibr42-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1177\/0278364908099462"},{"key":"bibr43-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6631298"},{"key":"bibr44-0278364920918919","first-page":"4588","author":"Livingston SC","year":"2013","journal-title":"International Conference on Robotics and Automation (ICRA)"},{"key":"bibr45-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1983.1676196"},{"key":"bibr46-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1088\/1748-3182\/9\/2\/025013"},{"key":"bibr47-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2017.2783445"},{"key":"bibr48-0278364920918919","volume-title":"A Mathematical Introduction to Robotic Manipulation","author":"Murray RM","year":"1994","edition":"1"},{"key":"bibr49-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/TCST.2015.2501351"},{"key":"bibr50-0278364920918919","unstructured":"Penedo \u00c1lvarez F, Vasile CI, Belta C (2016) Language-guided sampling-based planning using temporal relaxation. In: Workshop on the Algorithmic Foundations of Robotics (WAFR), San Francisco, CA, pp. 1\u201316. Available at: http:\/\/wafr2016.berkeley.edu\/papers\/WAFR_2016_paper_22.pdf"},{"key":"bibr51-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2016.7487151"},{"key":"bibr52-0278364920918919","first-page":"1","volume-title":"Robotics: Science and Systems (RSS)","author":"Raman V","year":"2013"},{"key":"bibr53-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2013.6760374"},{"key":"bibr54-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918774135"},{"key":"bibr55-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2018.8593574"},{"key":"bibr56-0278364920918919","first-page":"1","volume-title":"International Symposium on Experimental Robotics 2018 (ISER)","author":"Serlin Z","year":"2018"},{"key":"bibr57-0278364920918919","unstructured":"Sucan IA, Chitta S (2018) MoveIt!. http:\/\/moveit.ros.org"},{"key":"bibr58-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009362"},{"key":"bibr59-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/ACC.2013.6579837"},{"key":"bibr60-0278364920918919","first-page":"1","volume-title":"Robotics: Science and Systems (RSS)","author":"Ulusoy A","year":"2013"},{"key":"bibr61-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6630596"},{"key":"bibr62-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913487931"},{"key":"bibr63-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911406562"},{"key":"bibr64-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2013.6697051"},{"key":"bibr65-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6907486"},{"key":"bibr66-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2016.7799415"},{"key":"bibr67-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2017.8206235"},{"key":"bibr68-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2017.7989177"},{"key":"bibr69-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2013.6631299"},{"key":"bibr70-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1109\/CDC.2009.5399536"},{"key":"bibr71-0278364920918919","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2003.08.004"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364920918919","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/0278364920918919","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364920918919","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364920918919","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:16:31Z","timestamp":1777457791000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364920918919"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,4]]},"references-count":71,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["10.1177\/0278364920918919"],"URL":"https:\/\/doi.org\/10.1177\/0278364920918919","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,6,4]]}}}