{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T10:03:30Z","timestamp":1777716210065,"version":"3.51.4"},"reference-count":75,"publisher":"SAGE Publications","issue":"9","license":[{"start":{"date-parts":[[2025,4,24]],"date-time":"2025-04-24T00:00:00Z","timestamp":1745452800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62173226, 92367203"],"award-info":[{"award-number":["62173226, 92367203"]}],"id":[{"id":"10.13039\/501100001809","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":[[2025,8]]},"abstract":"<jats:p>\n                    In this paper, we investigate the graph-based robot path planning problem for high-level specifications described by co-safe linear temporal logic (scLTL) formulae. Our focus is on scenarios where the map geometry of the workspace is only\n                    <jats:italic toggle=\"yes\">partially-known<\/jats:italic>\n                    . Specifically, we assume the existence of unknown regions, where the robot lacks\n                    <jats:italic toggle=\"yes\">prior knowledge<\/jats:italic>\n                    of their successor regions unless it physically reaches these areas. In contrast to the standard non-deterministic synthesis approach that optimizes the worst-case cost, in the paper, we propose using\n                    <jats:italic toggle=\"yes\">regret<\/jats:italic>\n                    as the metric for planning in such partially-known environments. Regret measures the difference between the actual cost incurred and the best-response cost the robot could have achieved if it were aware of the actual environment from the start. We present a formal model for this problem setting and develop an efficient algorithm to find an optimal strategy in the sense that it meets the scLTL specification while minimizing the regret of the strategy. Our approach provides a quantitative method for evaluating the trade-off between exploration and non-exploration, rather than relying on the heuristic determinations used in many existing works. Case studies on firefighting and collaborative robots are provided to illustrate the effectiveness of our framework. Furthermore, we conduct numerical experiments on a large number of randomly generated systems and compare the performance of the regret-based strategy with other path planning strategies. The experimental results indicate that regret is a highly meaningful metric for path planning in partially-unknown environments, especially in cases where no probabilistic a priori knowledge is available.\n                  <\/jats:p>","DOI":"10.1177\/02783649251315758","type":"journal-article","created":{"date-parts":[[2025,4,25]],"date-time":"2025-04-25T02:20:16Z","timestamp":1745547616000},"page":"1526-1552","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":7,"title":["No-regret path planning for temporal logic tasks in partially-known environments"],"prefix":"10.1177","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1579-0522","authenticated-orcid":false,"given":"Jianing","family":"Zhao","sequence":"first","affiliation":[{"name":"Shanghai Jiao Tong University"}]},{"given":"Keyi","family":"Zhu","sequence":"additional","affiliation":[{"name":"Michigan State University"}]},{"given":"Mingyang","family":"Feng","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University"}]},{"given":"Shaoyuan","family":"Li","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1944-1570","authenticated-orcid":false,"given":"Xiang","family":"Yin","sequence":"additional","affiliation":[{"name":"Shanghai Jiao Tong University"}]}],"member":"179","published-online":{"date-parts":[[2025,4,24]]},"reference":[{"key":"e_1_3_4_2_1","doi-asserted-by":"crossref","unstructured":"Ayala AM Andersson SB Belta C (2013) Temporal logic motion planning in unknown environments. In: 2013 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS) Tokyo Japan 03\u201307 November 2013. IEEE 5279\u20135284.","DOI":"10.1109\/IROS.2013.6697120"},{"key":"e_1_3_4_3_1","volume-title":"Principles of Model Checking","author":"Baier C","year":"2008","unstructured":"Baier C, Katoen JP (2008) Principles of Model Checking. Cambridge: MIT Press."},{"key":"e_1_3_4_4_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-control-053018-023717"},{"key":"e_1_3_4_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-50763-7"},{"key":"e_1_3_4_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2006.01.004"},{"key":"e_1_3_4_7_1","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1956.6.1"},{"key":"e_1_3_4_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-013-0191-5"},{"key":"e_1_3_4_9_1","doi-asserted-by":"crossref","unstructured":"Bozkurt AK Wang Y Zavlanos MM et al. (2020) Control synthesis from linear temporal logic specifications using model-free reinforcement learning. In: IEEE International Conference on Robotics and Automation (ICRA) 31 May - 31 August 2020 Virtual 10349\u201310355.","DOI":"10.1109\/ICRA40945.2020.9196796"},{"key":"e_1_3_4_10_1","doi-asserted-by":"crossref","unstructured":"Brafman RI De Giacomo G (2019) Planning for LTLf\/LDLf goals in non-markovian fully observable nondeterministic domains. In: International Joint Conference on Artificial Intelligence (IJCAI) August 10-16 2019 Macao China 1602\u20131608.","DOI":"10.24963\/ijcai.2019\/222"},{"key":"e_1_3_4_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-016-0276-z"},{"key":"e_1_3_4_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17127-8_8"},{"key":"e_1_3_4_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2020.3006967"},{"key":"e_1_3_4_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2021.3138704"},{"key":"e_1_3_4_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2023.3246844"},{"key":"e_1_3_4_16_1","doi-asserted-by":"publisher","DOI":"10.1177\/02783649241247285"},{"key":"e_1_3_4_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-013-0182-6"},{"key":"e_1_3_4_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2017.2727514"},{"key":"e_1_3_4_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00374-0"},{"key":"e_1_3_4_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2014.2298143"},{"key":"e_1_3_4_21_1","doi-asserted-by":"crossref","unstructured":"Fiaz UA Baras JS (2020) Fast composable rescue mission planning for uavs using metric temporal logic. In: 21st IFAC World Congresse July 11-17 2020 Virtual 15404\u201315411.","DOI":"10.1016\/j.ifacol.2020.12.2361"},{"key":"e_1_3_4_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15155-2_31"},{"key":"e_1_3_4_23_1","doi-asserted-by":"crossref","unstructured":"Fridovich-Keil D Fisac JF Tomlin CJ (2019) Safely probabilistically complete real-time planning and exploration in unknown environments. In: International Conference on Robotics and Automation (ICRA) Montreal Canada 20\u201324 May 2019. IEEE 7470\u20137476.","DOI":"10.1109\/ICRA.2019.8793905"},{"key":"e_1_3_4_24_1","volume-title":"Robotics: Science and Systems","author":"Fu J","year":"2014","unstructured":"Fu J, Topcu U (2014) Probably approximately correct mdp learning and control with temporal logic constraints. Robotics: Science and Systems. USA: MIT Press."},{"key":"e_1_3_4_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2016.2518639"},{"key":"e_1_3_4_26_1","doi-asserted-by":"publisher","DOI":"10.1609\/icaps.v28i1.13880"},{"key":"e_1_3_4_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2023.3253304"},{"key":"e_1_3_4_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2021.3064220"},{"key":"e_1_3_4_29_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364914546174"},{"key":"e_1_3_4_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2018.2799561"},{"key":"e_1_3_4_31_1","doi-asserted-by":"crossref","unstructured":"Hasanbeig M Kantaros Y Abate A et al. (2019) Reinforcement learning for temporal logic control synthesis with probabilistic satisfaction guarantees. In: 58th IEEE Conference on Decision and Control (CDC) Nice France 11\u201313 December 2019. IEEE 5338\u20135343.","DOI":"10.1109\/CDC40024.2019.9028919"},{"key":"e_1_3_4_32_1","doi-asserted-by":"publisher","DOI":"10.1561\/2400000013"},{"key":"e_1_3_4_33_1","first-page":"408","volume-title":"Algorithmic Learning Theory","author":"Hazan E","year":"2020","unstructured":"Hazan E, Kakade S, Singh K (2020) The nonstochastic control problem. Algorithmic Learning Theory PMLR, 408\u2013421."},{"key":"e_1_3_4_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2023.3340029"},{"key":"e_1_3_4_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-016-0268-z"},{"key":"e_1_3_4_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2024.3386024"},{"key":"e_1_3_4_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2018.2853558"},{"key":"e_1_3_4_38_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364920913922"},{"key":"e_1_3_4_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2022.3144073"},{"key":"e_1_3_4_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2009.2035776"},{"key":"e_1_3_4_41_1","doi-asserted-by":"crossref","unstructured":"Kloetzer M Mahulea C (2016) Multi-robot path planning for syntactically co-safe LTL specifications. In: 13th International Workshop on Discrete Event Systems (WODES) Xi\u2019an China 30 May 2016\u201301 June. IEEE 452\u2013458.","DOI":"10.1109\/WODES.2016.7497887"},{"key":"e_1_3_4_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10626-019-00300-1"},{"key":"e_1_3_4_43_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-control-060117-104838"},{"key":"e_1_3_4_44_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev-control-042820-010947"},{"key":"e_1_3_4_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2019.103289"},{"key":"e_1_3_4_46_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364919856695"},{"key":"e_1_3_4_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2016.2544339"},{"key":"e_1_3_4_48_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546877"},{"key":"e_1_3_4_49_1","doi-asserted-by":"publisher","DOI":"10.1177\/02783649221082115"},{"key":"e_1_3_4_50_1","doi-asserted-by":"publisher","DOI":"10.1142\/S2301385014300029"},{"key":"e_1_3_4_51_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.automatica.2023.111377"},{"key":"e_1_3_4_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3342355"},{"key":"e_1_3_4_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2022.3181948"},{"key":"e_1_3_4_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2021.3061983"},{"key":"e_1_3_4_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.conengprac.2023.105600"},{"key":"e_1_3_4_56_1","volume-title":"Path Planning of Cooperative Mobile Robots Using Discrete Event Models","author":"Mahulea C","year":"2020","unstructured":"Mahulea C, Kloetzer M, Gonz\u00e1lez R (2020) Path Planning of Cooperative Mobile Robots Using Discrete Event Models. Hoboken: John Wiley & Sons."},{"key":"e_1_3_4_57_1","doi-asserted-by":"crossref","unstructured":"Muise C Belle V McIlraith S (2014) Computing contingent plans via fully observable non-deterministic planning. In: Proceedings of the AAAI Conference on Artificial Intelligence July 27\u201331 2014 Qu\u00e9bec City Qu\u00e9bec Canada Vol. 28.","DOI":"10.1609\/aaai.v28i1.9049"},{"key":"e_1_3_4_58_1","doi-asserted-by":"crossref","unstructured":"Muvvala K Amorese P Lahijanian M (2022) Let\u2019s collaborate: regret-based reactive synthesis for robotic manipulation. In: 2022 International Conference on Robotics and Automation (ICRA) Philadelphia PA 23\u201327 May 2022. IEEE 4340\u20134346.","DOI":"10.1109\/ICRA46639.2022.9812298"},{"key":"e_1_3_4_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2019.2957669"},{"key":"e_1_3_4_60_1","doi-asserted-by":"crossref","unstructured":"Scher G Kress-Gazit H (2020) Warehouse automation in a day: from model to implementation with provable guarantees. In: 16th IEEE International Conference on Automation Science and Engineering (CASE) Hong Kong China 20\u201321 August 2020 280\u2013287.","DOI":"10.1109\/CASE48305.2020.9217012"},{"key":"e_1_3_4_61_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000018"},{"key":"e_1_3_4_62_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911417911"},{"key":"e_1_3_4_63_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364913487931"},{"key":"e_1_3_4_64_1","unstructured":"Vardi MY Wolper P (1986) An automata-theoretic approach to automatic program verification. In: 1st Symposium in Logic in Computer Science (LICS) June 16-18 1986 Cambridge MA USA. IEEE Computer Society."},{"key":"e_1_3_4_65_1","doi-asserted-by":"publisher","DOI":"10.1177\/0278364920918919"},{"key":"e_1_3_4_66_1","doi-asserted-by":"crossref","unstructured":"Wang Y Nalluri S Pajic M (2020) Hyperproperties for robotics: planning via hyperltl. In: 2020 IEEE International Conference on Robotics and Automation (ICRA) 31 May - 31 August 2020 Virtual. IEEE 8462\u20138468.","DOI":"10.1109\/ICRA40945.2020.9196874"},{"key":"e_1_3_4_67_1","volume-title":"Robotics: Science and Systems","author":"Wolff EM","year":"2012","unstructured":"Wolff EM, Topcu U, Murray RM (2012) Optimal control with weighted average costs and temporal logic specifications. Robotics: Science and Systems. USA: MIT Press."},{"key":"e_1_3_4_68_1","doi-asserted-by":"crossref","unstructured":"Wolff EM Topcu U Murray RM (2013) Optimal control of non-deterministic systems for a computationally efficient fragment of temporal logic. In: 52nd IEEE Conference on Decision and Control (CDC). IEEE 3197\u20133204.","DOI":"10.1109\/CDC.2013.6760371"},{"issue":"273","key":"e_1_3_4_69_1","first-page":"1","article-title":"Online non-stochastic control with partial feedback","volume":"24","author":"Yan YH","year":"2023","unstructured":"Yan YH, Zhao P, Zhou ZH (2023) Online non-stochastic control with partial feedback. Journal of Machine Learning Research 24(273): 1\u201350.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_4_70_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.arcontrol.2024.100940"},{"key":"e_1_3_4_71_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2021.3088764"},{"key":"e_1_3_4_72_1","article-title":"Online control synthesis for uncertain systems under signal temporal logic specifications","author":"Yu P","year":"2023","unstructured":"Yu P, Gao Y, Jiang FJ, et al. (2023) Online control synthesis for uncertain systems under signal temporal logic specifications. The International Journal of Robotics Research.","journal-title":"The International Journal of Robotics Research"},{"issue":"6","key":"e_1_3_4_73_1","first-page":"765","article-title":"Continuous-time control synthesis under nested signal temporal logic specifications","volume":"43","author":"Yu P","year":"2024","unstructured":"Yu P, Tan X, Dimarogonas DV (2024) Continuous-time control synthesis under nested signal temporal logic specifications. IEEE Transactions on Robotics 43(6): 765\u2013790.","journal-title":"IEEE Transactions on Robotics"},{"key":"e_1_3_4_74_1","unstructured":"Zhao J Zhu K Li S et al. (2023) To explore or not to explore: regret-based ltl planning in partially-known environments. In: 22nd IFAC World Congresse 9 July \u2013 14 July 2023 Yokohama Japan 12171\u201312177."},{"key":"e_1_3_4_75_1","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2021.3071527"},{"key":"e_1_3_4_76_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2023.3322090"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649251315758","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/02783649251315758","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649251315758","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:17:41Z","timestamp":1777457861000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783649251315758"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,4,24]]},"references-count":75,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2025,8]]}},"alternative-id":["10.1177\/02783649251315758"],"URL":"https:\/\/doi.org\/10.1177\/02783649251315758","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,4,24]]}}}