{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T01:19:51Z","timestamp":1760059191091,"version":"build-2065373602"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA2","funder":[{"DOI":"10.13039\/501100012166","name":"National Key R&D Program of China","doi-asserted-by":"crossref","award":["2022YFB4501903"],"award-info":[{"award-number":["2022YFB4501903"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSFC Program","award":["62172429"],"award-info":[{"award-number":["62172429"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2025,10,9]]},"abstract":"<jats:p>Behavior trees (BTs) are widely adopted in the field of agent control, particularly in robotics, due to their modularity and reactivity. However, constructing a BT that meets the desired expectations is time-consuming and challenging, especially for non-experts. This paper presents BtBot, a multi-modal sketch-based behavior tree synthesis technique. Given a natural language task description and a set of positive and negative examples, BtBot automatically generates a BT program that aligns with the natural language description and meets the requirements of the examples. Inside BtBot, an LLM is employed to understand the task\u2019s natural language description and generate a sketch of the task execution. Then, BtBot searches the sketch to synthesize a candidate BT program consistent with the user-provided positive and negative examples. When the sketch is proven to be incapable of generating the target BT, BtBot provides a multi-step repairing method that modifies the control nodes and structure of the sketch to search for the desired BT. We have implemented BtBot in a prototype and evaluated it on a benchmark of 70 tasks across multiple scenarios. The experimental results indicate that BtBot outperforms the existing BT synthesis techniques in effectiveness and efficiency. In addition, two user studies have been conducted to demonstrate the usefulness of BtBot.<\/jats:p>","DOI":"10.1145\/3763178","type":"journal-article","created":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T08:49:50Z","timestamp":1759999790000},"page":"3560-3587","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Multi-modal Sketch-Based Behavior Tree Synthesis"],"prefix":"10.1145","volume":"9","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-0646-6219","authenticated-orcid":false,"given":"Wenmeng","family":"Zhang","sequence":"first","affiliation":[{"name":"National University of Defense Technology, Changsha, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4066-7892","authenticated-orcid":false,"given":"Zhenbang","family":"Chen","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, Changsha, China"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7092-3658","authenticated-orcid":false,"given":"Weijiang","family":"Hong","sequence":"additional","affiliation":[{"name":"National University of Defense Technology, Changsha, China"}]}],"member":"320","published-online":{"date-parts":[[2025,10,9]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"David \u00c5ngstr\u00f6m. 2022. Genetic Algorithms for optimizing behavior trees in air combat."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591248"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2020.2970634"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2021.3074337"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCIAIG.2012.2186810"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1609\/AAAI.V35I7.16755"},{"key":"e_1_2_1_7_1","unstructured":"Guillaume Maurice Jean-Bernard Chaslot Chaslot. 2010. Monte-carlo tree search."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3622863"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385988"},{"key":"e_1_2_1_10_1","volume-title":"IJCAI","author":"Chen Xinglin","year":"2024","unstructured":"Xinglin Chen, Yishuai Cai, Yunxin Mao, Minglong Li, Wenjing Yang, Weixia Xu, and Ji Wang. 2024. Integrating Intent Understanding and Optimal Behavior Planning for Behavior Tree Generation from Human Instructions. IJCAI 2024."},{"volume-title":"Behavior trees in robotics and AI: An introduction","author":"Colledanchise Michele","key":"e_1_2_1_11_1","unstructured":"Michele Colledanchise and Petter \u00d6gren. 2018. Behavior trees in robotics and AI: An introduction. CRC Press."},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Maaike de Boer Quirine Smit Michael van Bekkum Andr\u00e9 Meyer-Vitali and Thomas Schmid. 2024. Design Patterns for LLM-based Neuro-Symbolic Systems.","DOI":"10.1177\/29498732251377499"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/B978-0-444-88074-1.50021-4"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3192366.3192382"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2737977"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2019.8794104"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.2991\/essaeme-16.2016.120"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.18653\/V1\/2022.ACL-LONG.576"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-71237-6_1"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1561\/2500000010"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/RO-MAN53752.2022.9900603"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","unstructured":"David Harel Dexter Kozen and Jerzy Tiuryn. 2001. Dynamic logic. SIGACT News 66\u201369. https:\/\/doi.org\/10.1145\/568438.568456 10.1145\/568438.568456","DOI":"10.1145\/568438.568456"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-99-8664-4_5"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","unstructured":"Jiang Hua Liangcai Zeng Gongfa Li and Zhaojie Ju. 2021. Learning for a robot: Deep reinforcement learning imitation learning transfer learning. Sensors 1278. https:\/\/doi.org\/10.3390\/S21041278 10.3390\/S21041278","DOI":"10.3390\/S21041278"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3054912"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","unstructured":"Matteo Iovino and Christian Smith. 2023. Behavior Trees for Robust Task Level Control in Robotic Applications. CoRR https:\/\/doi.org\/10.48550\/ARXIV.2301.06434 10.48550\/ARXIV.2301.06434","DOI":"10.48550\/ARXIV.2301.06434"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Raisa Islam and Owana Marzia Moushi. 2024. Gpt-4o: The cutting-edge advancement in multimodal llm. Authorea Preprints.","DOI":"10.36227\/techrxiv.171986596.65533294\/v1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS58592.2024.10802304"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.2505.07270"},{"key":"e_1_2_1_30_1","volume-title":"Decomposed Prompting: A Modular Approach for Solving Complex Tasks. In The Eleventh International Conference on Learning Representations, ICLR","author":"Khot Tushar","year":"2023","unstructured":"Tushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, and Ashish Sabharwal. 2023. Decomposed Prompting: A Modular Approach for Solving Complex Tasks. In The Eleventh International Conference on Learning Representations, ICLR 2023. https:\/\/openreview.net\/forum?id=_nGgzQjzaRy"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3106237.3106309"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","unstructured":"Fu Li Xueying Wang Bin Li Yunlong Wu Yanzhen Wang and Xiaodong Yi. 2024. A Study on Training and Developing Large Language Models for Behavior Tree Generation. CoRR https:\/\/doi.org\/10.48550\/ARXIV.2401.08089 10.48550\/ARXIV.2401.08089","DOI":"10.48550\/ARXIV.2401.08089"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3597503.3639180"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPRW63382.2024.00230"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/S40869-017-0040-9"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2014.6907656"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/S10462-024-10903-2"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","unstructured":"Petter \u00d6gren and Christopher I Sprague. 2022. Behavior trees in robot control systems. Annual Review of Control Robotics and Autonomous Systems 81\u2013107. https:\/\/doi.org\/10.1146\/ANNUREV-CONTROL-042920-095314 10.1146\/ANNUREV-CONTROL-042920-095314","DOI":"10.1146\/ANNUREV-CONTROL-042920-095314"},{"key":"e_1_2_1_39_1","unstructured":"Magnus Olsson. 2016. Behavior trees for decision-making in autonomous driving."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.61961\/injei.v1i1.7"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","unstructured":"Noah Patton Kia Rahmani Meghana Missula Joydeep Biswas and Isil Dillig. 2023. Program Synthesis for Robot Learning from Demonstrations. CoRR https:\/\/doi.org\/10.48550\/ARXIV.2305.03129 10.48550\/ARXIV.2305.03129","DOI":"10.48550\/ARXIV.2305.03129"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/IROS40897.2019.8967861"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.32"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485535"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/INISTA.2015.7276774"},{"key":"e_1_2_1_46_1","unstructured":"Bill Roscoe. 1994. Model- checking CSP."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA48506.2021.9561027"},{"volume-title":"Concurrent and real-time systems: the CSP approach","author":"Schneider Steve","key":"e_1_2_1_48_1","unstructured":"Steve Schneider. 1999. Concurrent and real-time systems: the CSP approach. John Wiley & Sons."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218213017300010"},{"volume-title":"Program synthesis by sketching","author":"Solar-Lezama Armando","key":"e_1_2_1_50_1","unstructured":"Armando Solar-Lezama. 2008. Program synthesis by sketching. University of California, Berkeley."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10672-9_3"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065010.1065045"},{"key":"e_1_2_1_53_1","first-page":"13139","article-title":"Language-conditioned imitation learning for robot manipulation tasks","volume":"2020","author":"Stepputtis Simon","year":"2020","unstructured":"Simon Stepputtis, Joseph Campbell, Mariano Phielipp, Stefan Lee, Chitta Baral, and Heni Ben Amor. 2020. Language-conditioned imitation learning for robot manipulation tasks. NeurIPS 2020, 33 (2020), 13139\u201313150. https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/9909794d52985cbc5d95c26e31125d1a-Abstract.html","journal-title":"NeurIPS"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2024.3387941"},{"key":"e_1_2_1_55_1","volume-title":"ICML","author":"Verma Abhinav","year":"2018","unstructured":"Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. 2018. Programmatically interpretable reinforcement learning. In ICML 2018. 5045\u20135054. http:\/\/proceedings.mlr.press\/v80\/verma18a.html"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158151"},{"key":"e_1_2_1_57_1","volume-title":"Prediction during natural language comprehension. Cerebral cortex, 26, 6","author":"Willems Roel M","year":"2016","unstructured":"Roel M Willems, Stefan L Frank, Annabel D Nijhof, Peter Hagoort, and Antal Van den Bosch. 2016. Prediction during natural language comprehension. Cerebral cortex, 26, 6 (2016), 2506\u20132516."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/3133887"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v38i17.29918"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3591301"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","unstructured":"Wenmeng Zhang Zhenbang Chen and Weijiang Hong. 2025. Artifact for: Multi-modal Sketch-based Behavior Tree Synthesis. https:\/\/doi.org\/10.5281\/zenodo.16921187 10.5281\/zenodo.16921187","DOI":"10.5281\/zenodo.16921187"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.18653\/V1\/2021.NAACL-MAIN.217"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA57147.2024.10610183"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763178","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T17:41:03Z","timestamp":1760031663000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763178"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,9]]},"references-count":63,"journal-issue":{"issue":"OOPSLA2","published-print":{"date-parts":[[2025,10,9]]}},"alternative-id":["10.1145\/3763178"],"URL":"https:\/\/doi.org\/10.1145\/3763178","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2025,10,9]]},"assertion":[{"value":"2025-03-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-12","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}