research-article

Open access

Programming-by-Demonstration for Long-Horizon Robot Tasks

Authors:

Meghana Missula,

Joydeep Biswas,

Işıl DilligAuthors Info & Claims

Proceedings of the ACM on Programming Languages, Volume 8, Issue POPL

Article No.: 18, Pages 512 - 545

https://doi.org/10.1145/3632860

Published: 05 January 2024 Publication History

Abstract

The goal of programmatic Learning from Demonstration (LfD) is to learn a policy in a programming language that can be used to control a robot’s behavior from a set of user demonstrations. This paper presents a new programmatic LfD algorithm that targets long-horizon robot tasks which require synthesizing programs with complex control flow structures, including nested loops with multiple conditionals. Our proposed method first learns a program sketch that captures the target program’s control flow and then completes this sketch using an LLM-guided search procedure that incorporates a novel technique for proving unrealizability of programming-by-demonstration problems. We have implemented our approach in a new tool called PROLEX and present the results of a comprehensive experimental evaluation on 120 benchmarks involving complex tasks and environments. We show that, given a 120 second time limit, PROLEX can find a program consistent with the demonstrations in 80% of the cases. Furthermore, for 81% of the tasks for which a solution is returned, PROLEX is able to find the ground truth program with just one demonstration. In comparison, CVC5, a syntax-guided synthesis tool, is only able to solve 25% of the cases even when given the ground truth program sketch, and an LLM-based approach, GPT-Synth, is unable to solve any of the tasks due to the environment complexity.

References

[1]

Constructions Aeronautiques, Adele Howe, Craig Knoblock, ISI Drew McDermott, Ashwin Ram, Manuela Veloso, Daniel Weld, David Wilkins SRI, Anthony Barrett, and Dave Christianson. 1998. Pddl| the planning domain definition language. Technical Report, Tech. Rep.

[2]

Rajeev Alur, Rastislav Bodík, Eric Dallal, Dana Fisman, Pranav Garg, Garvit Juniwal, Hadas Kress-Gazit, P. Madhusudan, Milo M. K. Martin, Mukund Raghothaman, Shambwaditya Saha, Sanjit A. Seshia, Rishabh Singh, Armando Solar-Lezama, Emina Torlak, and Abhishek Udupa. 2015. Syntax-Guided Synthesis. In Dependable Software Systems Engineering. 1–25.

[3]

Rajeev Alur, Pavol Černý, and Arjun Radhakrishna. 2015. Synthesis Through Unification. In Computer Aided Verification, Daniel Kroening and Corina S. Păsăreanu (Eds.). Springer International Publishing, Cham. 163–179. isbn:978-3-319-21668-3

[4]

Brenna D. Argall, Brett Browning, and Manuela Veloso. 2008. Learning robot motion control with demonstration and advice-operators. In 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems. 399–404. https://doi.org/10.1109/IROS.2008.4651020

[5]

Brenna D. Argall, Sonia Chernova, Manuela Veloso, and Brett Browning. 2009. A survey of robot learning from demonstration. Robotics and Autonomous Systems, 57, 5 (2009), 469–483. issn:0921-8890 https://doi.org/10.1016/j.robot.2008.10.024

[6]

Kumar Ashutosh, Rohit Girdhar, Lorenzo Torresani, and Kristen Grauman. 2023. HierVL: Learning Hierarchical Video-Language Embeddings. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 23066–23078.

[7]

Yoah Bar-David and Gadi Taubenfeld. 2003. Automatic Discovery of Mutual Exclusion Algorithms. In Proceedings of the Twenty-Second Annual Symposium on Principles of Distributed Computing (PODC ’03). Association for Computing Machinery, New York, NY, USA. 305. isbn:1581137087 https://doi.org/10.1145/872035.872080

[8]

Haniel Barbosa, Clark W. Barrett, Martin Brain, Gereon Kremer, Hanna Lachnitt, Makai Mann, Abdalrhman Mohamed, Mudathir Mohamed, Aina Niemetz, Andres Nötzli, Alex Ozdemir, Mathias Preiner, Andrew Reynolds, Ying Sheng, Cesare Tinelli, and Yoni Zohar. 2022. cvc5: A Versatile and Industrial-Strength SMT Solver. In Tools and Algorithms for the Construction and Analysis of Systems - 28th International Conference, TACAS 2022, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2022, Munich, Germany, April 2-7, 2022, Proceedings, Part I, Dana Fisman and Grigore Rosu (Eds.) (Lecture Notes in Computer Science, Vol. 13243). Springer, 415–442. https://doi.org/10.1007/978-3-030-99524-9_24

[9]

Gilles Barthe, Juan Manuel Crespo, Sumit Gulwani, Cesar Kunz, and Mark Marron. 2013. From Relational Verification to SIMD Loop Synthesis. In Proceedings of the 18th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP ’13). Association for Computing Machinery, New York, NY, USA. 123–134. isbn:9781450319225 https://doi.org/10.1145/2442516.2442529

[10]

Tom Baumeister, Bernd Finkbeiner, and Hazem Torfah. 2020. Explainable Reactive Synthesis. In Automated Technology for Verification and Analysis, Dang Van Hung and Oleg Sokolsky (Eds.). Springer International Publishing, Cham. 413–428. isbn:978-3-030-59152-6

[11]

A.W. Biermann, R.I. Baum, and F.E. Petry. 1975. Speeding up the Synthesis of Programs from Traces. IEEE Trans. Comput., C-24, 2 (1975), 122–136. https://doi.org/10.1109/T-C.1975.224180

[12]

Roderick Bloem, Barbara Jobstmann, Nir Piterman, Amir Pnueli, and Yaniv Saar. 2012. Synthesis of Reactive(1) designs. J. Comput. System Sci., 78, 3 (2012), 911–938. issn:0022-0000 https://doi.org/10.1016/j.jcss.2011.08.007 In Commemoration of Amir Pnueli

[13]

James Bornholt, Emina Torlak, Dan Grossman, and Luis Ceze. 2016. Optimizing synthesis with metasketches. In ACM SIGPLAN Notices. 51, 775–788.

[14]

Matthew Bowers, Theo X. Olausson, Lionel Wong, Gabriel Grand, Joshua B. Tenenbaum, Kevin Ellis, and Armando Solar-Lezama. 2023. Top-Down Synthesis for Library Learning. Proc. ACM Program. Lang., 7, POPL (2023), Article 41, jan, 32 pages. https://doi.org/10.1145/3571234

[15]

José Cambronero, Sumit Gulwani, Vu Le, Daniel Perelman, Arjun Radhakrishna, Clint Simon, and Ashish Tiwari. 2023. FlashFill++: Scaling Programming by Example by Cutting to the Chase. Proc. ACM Program. Lang., 7, POPL (2023), Article 33, jan, 30 pages. https://doi.org/10.1145/3571226

[16]

Sarah E. Chasins, Maria Mueller, and Rastislav Bodik. 2018. Rousillon: Scraping Distributed Hierarchical Web Data. In Proceedings of the 31st Annual ACM Symposium on User Interface Software and Technology (UIST ’18). Association for Computing Machinery, New York, NY, USA. 963–975. isbn:9781450359481 https://doi.org/10.1145/3242587.3242661

[17]

Swarat Chaudhuri, Kevin Ellis, Oleksandr Polozov, Rishabh Singh, Armando Solar-Lezama, and Yisong Yue. 2021. Neurosymbolic Programming. Found. Trends Program. Lang., 7 (2021), 158–243.

[18]

Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, Alex Ray, Raul Puri, Gretchen Krueger, Michael Petrov, Heidy Khlaaf, Girish Sastry, Pamela Mishkin, Brooke Chan, Scott Gray, Nick Ryder, Mikhail Pavlov, Alethea Power, Lukasz Kaiser, Mohammad Bavarian, Clemens Winter, Philippe Tillet, Felipe Petroski Such, Dave Cummings, Matthias Plappert, Fotios Chantzis, Elizabeth Barnes, Ariel Herbert-Voss, William Hebgen Guss, Alex Nichol, Alex Paino, Nikolas Tezak, Jie Tang, Igor Babuschkin, Suchir Balaji, Shantanu Jain, William Saunders, Christopher Hesse, Andrew N. Carr, Jan Leike, Josh Achiam, Vedant Misra, Evan Morikawa, Alec Radford, Matthew Knight, Miles Brundage, Mira Murati, Katie Mayer, Peter Welinder, Bob McGrew, Dario Amodei, Sam McCandlish, Ilya Sutskever, and Wojciech Zaremba. 2021. Evaluating Large Language Models Trained on Code. arxiv:2107.03374.

[19]

Qiaochu Chen, Aaron Lamoreaux, Xinyu Wang, Greg Durrett, Osbert Bastani, and Isil Dillig. 2021. Web Question Answering with Neurosymbolic Program Synthesis. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI 2021). Association for Computing Machinery, New York, NY, USA. 328–343. isbn:9781450383912 https://doi.org/10.1145/3453483.3454047

[20]

Qiaochu Chen, Xinyu Wang, Xi Ye, Greg Durrett, and Isil Dillig. 2020. Multi-modal synthesis of regular expressions. In Proceedings of the 41st ACM SIGPLAN conference on programming language design and implementation. 487–502.

[21]

Wonhyuk Choi. 2021. Can Reactive Synthesis and Syntax-Guided Synthesis Be Friends? In Companion Proceedings of the 2021 ACM SIGPLAN International Conference on Systems, Programming, Languages, and Applications: Software for Humanity (SPLASH Companion 2021). Association for Computing Machinery, New York, NY, USA. 3–5. isbn:9781450390880 https://doi.org/10.1145/3484271.3484972

[22]

Michael Jae-Yoon Chung and Maya Cakmak. 2022. Authoring Human Simulators via Probabilistic Functional Reactive Program Synthesis. In 2022 17th ACM/IEEE International Conference on Human-Robot Interaction (HRI). 727–730. https://doi.org/10.1109/HRI53351.2022.9889630

[23]

Patrick Cousot and Radhia Cousot. 1977. Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. 238–252.

[24]

Ria Das, Joshua B. Tenenbaum, Armando Solar-Lezama, and Zenna Tavares. 2023. Combining Functional and Automata Synthesis to Discover Causal Reactive Programs. Proc. ACM Program. Lang., 7, POPL (2023), Article 56, jan, 31 pages. https://doi.org/10.1145/3571249

[25]

Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-HLT 2019, Minneapolis, MN, USA, June 2-7, 2019, Volume 1 (Long and Short Papers), Jill Burstein, Christy Doran, and Thamar Solorio (Eds.). Association for Computational Linguistics, 4171–4186. https://doi.org/10.18653/v1/n19-1423

[26]

Rui Dong, Zhicheng Huang, Ian Iong Lam, Yan Chen, and Xinyu Wang. 2022. WebRobot: Web Robotic Process Automation Using Interactive Programming-by-Demonstration. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI 2022). Association for Computing Machinery, New York, NY, USA. 152–167. isbn:9781450392655 https://doi.org/10.1145/3519939.3523711

[27]

Azadeh Farzan, Danya Lette, and Victor Nicolet. 2022. Recursion Synthesis with Unrealizability Witnesses. In Proceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI 2022). Association for Computing Machinery, New York, NY, USA. 244–259. isbn:9781450392655 https://doi.org/10.1145/3519939.3523726

[28]

Yu Feng, Ruben Martins, Osbert Bastani, and Isil Dillig. 2018. Program Synthesis Using Conflict-Driven Learning. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2018). Association for Computing Machinery, New York, NY, USA. 420–435. isbn:9781450356985 https://doi.org/10.1145/3192366.3192382

[29]

Yu Feng, Ruben Martins, Osbert Bastani, and Isil Dillig. 2018. Program synthesis using conflict-driven learning. In ACM SIGPLAN Notices. 53, 420–435.

[30]

Yu Feng, Ruben Martins, Jacob Van Geffen, Isil Dillig, and Swarat Chaudhuri. 2017. Component-based synthesis of table consolidation and transformation tasks from examples. In Proc. of PLDI. 422–436.

[31]

Kasra Ferdowsifard, Shraddha Barke, Hila Peleg, Sorin Lerner, and Nadia Polikarpova. 2021. LooPy: Interactive Program Synthesis with Control Structures. Proc. ACM Program. Lang., 5, OOPSLA (2021), Article 153, oct, 29 pages. https://doi.org/10.1145/3485530

[32]

John K Feser, Swarat Chaudhuri, and Isil Dillig. 2015. Synthesizing data structure transformations from input-output examples. ACM SIGPLAN Notices, 50, 6 (2015), 229–239.

[33]

Bernd Finkbeiner and Felix Klein. 2018. Reactive Synthesis: Towards Output-Sensitive Algorithms. arxiv:1803.10104.

[34]

Bernd Finkbeiner, Felix Klein, Ruzica Piskac, and Mark Santolucito. 2019. Synthesizing Functional Reactive Programs. In Proceedings of the 12th ACM SIGPLAN International Symposium on Haskell (Haskell 2019). Association for Computing Machinery, New York, NY, USA. 162–175. isbn:9781450368131 https://doi.org/10.1145/3331545.3342601

[35]

Bernd Finkbeiner and Sven Schewe. 2013. Bounded synthesis. International Journal on Software Tools for Technology Transfer, 15, 5-6 (2013), 519–539.

[36]

Maria Fox and Derek Long. 2003. PDDL2. 1: An extension to PDDL for expressing temporal planning domains. Journal of artificial intelligence research, 20 (2003), 61–124.

[37]

Kevin French, Shiyu Wu, Tianyang Pan, Zheming Zhou, and Odest Chadwicke Jenkins. 2019. Learning Behavior Trees From Demonstration. In 2019 International Conference on Robotics and Automation (ICRA). 7791–7797. https://doi.org/10.1109/ICRA.2019.8794104

[38]

Tianao Ge, Zewei Mo, Kan Wu, Xianwei Zhang, and Yutong Lu. 2022. RollBin: Reducing Code-Size via Loop Rerolling at Binary Level. In Proceedings of the 23rd ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems (LCTES 2022). Association for Computing Machinery, New York, NY, USA. 99–110. isbn:9781450392662 https://doi.org/10.1145/3519941.3535072

[39]

Claire Glanois, Paul Weng, Matthieu Zimmer, Dong Li, Tianpei Yang, Jianye Hao, and Wulong Liu. 2021. A Survey on Interpretable Reinforcement Learning. https://doi.org/10.48550/ARXIV.2112.13112

[40]

Sumit Gulwani. 2011. Automating string processing in spreadsheets using input-output examples. In Proc. of POPL. 317–330.

[41]

Sumit Gulwani, Oleksandr Polozov, and Rishabh Singh. 2017. Program Synthesis. Foundations and Trends in Programming Languages, 4, 1-2, 1–119.

[42]

Keliang He, Morteza Lahijanian, Lydia E. Kavraki, and Moshe Y. Vardi. 2017. Reactive synthesis for finite tasks under resource constraints. In 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 5326–5332. https://doi.org/10.1109/IROS.2017.8206426

[43]

Stefan Heule, Manu Sridharan, and Satish Chandra. 2015. Mimic: Computing Models for Opaque Code. In Proceedings of the 2015 10th Joint Meeting on Foundations of Software Engineering (ESEC/FSE 2015). Association for Computing Machinery, New York, NY, USA. 710–720. isbn:9781450336758 https://doi.org/10.1145/2786805.2786875

[44]

Jonathan Ho and Stefano Ermon. 2016. Generative Adversarial Imitation Learning. In Advances in Neural Information Processing Systems, D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett (Eds.). 29, Curran Associates, Inc. https://proceedings.neurips.cc/paper/2016/file/cc7e2b878868cbae992d1fb743995d8f-Paper.pdf

[45]

Jarrett Holtz, Simon Andrews, Arjun Guha, and Joydeep Biswas. 2021. Iterative Program Synthesis for Adaptable Social Navigation. In Intelligent Robots and Systems (IROS), IEEE/RSJ International Conference on. 6256–6261. https://doi.org/10.1109/IROS51168.2021.9636540

[46]

Jarrett Holtz, Arjun Guha, and Joydeep Biswas. 2018. Interactive Robot Transition Repair With SMT. In International Joint Conference on Artificial Intelligence (IJCAI). 4905–4911. https://doi.org/10.24963/ijcai.2018/681

[47]

Jarrett Holtz, Arjun Guha, and Joydeep Biswas. 2020. Robot Action Selection Learning via Layered Dimension Informed Program Synthesis. In Conference on Robot Learning. 1471–1480. https://joydeepb.com/Publications/corl2020_ldips.pdf

[48]

Jarrett Holtz, Arjun Guha, and Joydeep Biswas. 2020. Robot Action Selection Learning via Layered Dimension Informed Program Synthesis. In Conference on Robot Learning.

[49]

Qinheping Hu, Jason Breck, John Cyphert, Loris D’Antoni, and Thomas Reps. 2019. Proving Unrealizability for Syntax-Guided Synthesis. In Computer Aided Verification, Isil Dillig and Serdar Tasiran (Eds.). Springer International Publishing, Cham. 335–352. isbn:978-3-030-25540-4

[50]

Jiani Huang, Calvin Smith, Osbert Bastani, Rishabh Singh, Aws Albarghouthi, and Mayur Naik. 2020. Generating Programmatic Referring Expressions via Program Synthesis. In Proceedings of the 37th International Conference on Machine Learning, Hal Daumé III and Aarti Singh (Eds.) (Proceedings of Machine Learning Research, Vol. 119). PMLR, 4495–4506. https://proceedings.mlr.press/v119/huang20h.html

[51]

Jeevana Priya Inala, Yichen Yang, James Paulos, Yewen Pu, Osbert Bastani, Vijay Kumar, Martin Rinard, and Armando Solar-Lezama. 2020. Neurosymbolic Transformers for Multi-Agent Communication. In Proceedings of the 34th International Conference on Neural Information Processing Systems (NIPS’20). Curran Associates Inc., Red Hook, NY, USA. Article 1141, 12 pages. isbn:9781713829546

[52]

iRobot. 2023. iRobot Home App. https://www.irobot.com/en_US/irobot-home-app.html Accessed on March 30, 2023

[53]

Naman Jain, Skanda Vaidyanath, Arun Iyer, Nagarajan Natarajan, Suresh Parthasarathy, Sriram Rajamani, and Rahul Sharma. 2022. Jigsaw: Large Language Models Meet Program Synthesis. In Proceedings of the 44th International Conference on Software Engineering (ICSE ’22). Association for Computing Machinery, New York, NY, USA. 1219–1231. isbn:9781450392211 https://doi.org/10.1145/3510003.3510203

[54]

Susmit Jha, Sumit Gulwani, Sanjit A Seshia, and Ashish Tiwari. 2010. Oracle-guided component-based program synthesis. In 2010 ACM/IEEE 32nd International Conference on Software Engineering. 1, 215–224.

[55]

Susmit Jha, Sumit Gulwani, Sanjit A. Seshia, and Ashish Tiwari. 2010. Oracle-Guided Component-Based Program Synthesis. In Proceedings of the 32nd ACM/IEEE International Conference on Software Engineering - Volume 1 (ICSE ’10). Association for Computing Machinery, New York, NY, USA. 215–224. isbn:9781605587196 https://doi.org/10.1145/1806799.1806833

[56]

Ruyi Ji, Chaozhe Kong, Yingfei Xiong, and Zhenjiang Hu. 2023. Improving Oracle-Guided Inductive Synthesis by Efficient Question Selection. Proc. ACM Program. Lang., 7, OOPSLA1 (2023), Article 103, apr, 29 pages. https://doi.org/10.1145/3586055

[57]

Ashwin Kalyan, Abhishek Mohta, Oleksandr Polozov, Dhruv Batra, Prateek Jain, and Sumit Gulwani. 2018. Neural-Guided Deductive Search for Real-Time Program Synthesis from Examples. https://doi.org/10.48550/ARXIV.1804.01186

[58]

Jinwoo Kim, Loris D’Antoni, and Thomas Reps. 2023. Unrealizability Logic. Proc. ACM Program. Lang., 7, POPL (2023), Article 23, jan, 30 pages. https://doi.org/10.1145/3571216

[59]

Jinwoo Kim, Qinheping Hu, Loris D’Antoni, and Thomas Reps. 2021. Semantics-Guided Synthesis. Proc. ACM Program. Lang., 5, POPL (2021), Article 30, jan, 32 pages. https://doi.org/10.1145/3434311

[60]

Jens Kober, J. Andrew Bagnell, and Jan Peters. 2013. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32, 11 (2013), 1238–1274. https://doi.org/10.1177/0278364913495721 arxiv:https://doi.org/10.1177/0278364913495721.

[61]

Agneza Krajna, Mario Brcic, Tomislav Lipic, and Juraj Doncevic. 2022. Explainability in reinforcement learning: perspective and position. https://doi.org/10.48550/ARXIV.2203.11547

[62]

Paul Krogmeier, Umang Mathur, Adithya Murali, P. Madhusudan, and Mahesh Viswanathan. 2020. Decidable Synthesis of Programs with Uninterpreted Functions. In Computer Aided Verification, Shuvendu K. Lahiri and Chao Wang (Eds.). Springer International Publishing, Cham. 634–657. isbn:978-3-030-53291-8

[63]

Tessa A. Lau, Steven A. Wolfman, Pedro M. Domingos, and Daniel S. Weld. 2003. Programming by Demonstration Using Version Space Algebra. Machine Learning, 53 (2003), 111–156.

[64]

Jin Joo Lee, Amin Atrash, Dylan Glas, and Hanxiao Fu. 2023. Developing autonomous behaviors for a consumer robot to hang out near people in the home. In AAAI 2023 Spring Symposium Series. https://www.amazon.science/publications/developing-autonomous-behaviors-for-a-consumer-robot-to-hang-out-near-people-in-the-home

[65]

Mina Lee, Sunbeom So, and Hakjoo Oh. 2016. Synthesizing Regular Expressions from Examples for Introductory Automata Assignments. In Proceedings of the 2016 ACM SIGPLAN International Conference on Generative Programming: Concepts and Experiences (GPCE 2016). Association for Computing Machinery, New York, NY, USA. 70–80. isbn:9781450344463 https://doi.org/10.1145/2993236.2993244

[66]

Chengshu Li, Ruohan Zhang, Josiah Wong, Cem Gokmen, Sanjana Srivastava, Roberto Martín-Martín, Chen Wang, Gabrael Levine, Michael Lingelbach, Jiankai Sun, Mona Anvari, Minjune Hwang, Manasi Sharma, Arman Aydin, Dhruva Bansal, Samuel Hunter, Kyu-Young Kim, Alan Lou, Caleb R Matthews, Ivan Villa-Renteria, Jerry Huayang Tang, Claire Tang, Fei Xia, Silvio Savarese, Hyowon Gweon, Karen Liu, Jiajun Wu, and Li Fei-Fei. 2023. BEHAVIOR-1K: A Benchmark for Embodied AI with 1,000 Everyday Activities and Realistic Simulation. In Proceedings of The 6th Conference on Robot Learning, Karen Liu, Dana Kulic, and Jeff Ichnowski (Eds.) (Proceedings of Machine Learning Research, Vol. 205). PMLR, 80–93. https://proceedings.mlr.press/v205/li23a.html

[67]

Xiao Li, Zachary Serlin, Guang Yang, and Calin Belta. 2019. A formal methods approach to interpretable reinforcement learning for robotic planning. Science Robotics, 4, 37 (2019), eaay6276. https://doi.org/10.1126/scirobotics.aay6276 arxiv:https://www.science.org/doi/pdf/10.1126/scirobotics.aay6276.

[68]

Jacky Liang, Wenlong Huang, Fei Xia, Peng Xu, Karol Hausman, Brian Ichter, Pete Florence, and Andy Zeng. 2022. Code as policies: Language model programs for embodied control. arXiv preprint arXiv:2209.07753.

[69]

Zachary C. Lipton. 2018. The Mythos of Model Interpretability: In Machine Learning, the Concept of Interpretability is Both Important and Slippery. Queue, 16, 3 (2018), jun, 31–57. issn:1542-7730 https://doi.org/10.1145/3236386.3241340

[70]

Pengfei Liu, Weizhe Yuan, Jinlan Fu, Zhengbao Jiang, Hiroaki Hayashi, and Graham Neubig. 2023. Pre-Train, Prompt, and Predict: A Systematic Survey of Prompting Methods in Natural Language Processing. ACM Comput. Surv., 55, 9 (2023), Article 195, jan, 35 pages. issn:0360-0300 https://doi.org/10.1145/3560815

[71]

Abdoulaye O. Ly and Moulay Akhloufi. 2021. Learning to Drive by Imitation: An Overview of Deep Behavior Cloning Methods. IEEE Transactions on Intelligent Vehicles, 6, 2 (2021), 195–209. https://doi.org/10.1109/TIV.2020.3002505

[72]

P. Madhusudan, Umang Mathur, Shambwaditya Saha, and Mahesh Viswanathan. 2018. A Decidable Fragment of Second Order Logic With Applications to Synthesis. In 27th EACSL Annual Conference on Computer Science Logic (CSL 2018), Dan Ghica and Achim Jung (Eds.) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 119). Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany. 31:1–31:19. isbn:978-3-95977-088-0 issn:1868-8969 https://doi.org/10.4230/LIPIcs.CSL.2018.31

[73]

Kyle Mahowald, Anna A Ivanova, Idan A Blank, Nancy Kanwisher, Joshua B Tenenbaum, and Evelina Fedorenko. 2023. Dissociating language and thought in large language models: a cognitive perspective. arXiv preprint arXiv:2301.06627.

[74]

Jiayuan Mao, Chuang Gan, Pushmeet Kohli, Joshua B. Tenenbaum, and Jiajun Wu. 2019. The Neuro-Symbolic Concept Learner: Interpreting Scenes, Words, and Sentences From Natural Supervision. In International Conference on Learning Representations. https://openreview.net/forum?id=rJgMlhRctm

[75]

Benjamin Mariano, Yanju Chen, Yu Feng, Greg Durrett, and Işil Dillig. 2022. Automated Transpilation of Imperative to Functional Code Using Neural-Guided Program Synthesis. Proc. ACM Program. Lang., 6, OOPSLA1 (2022), Article 71, apr, 27 pages. https://doi.org/10.1145/3527315

[76]

Sergey Mechtaev, Alberto Griggio, Alessandro Cimatti, and Abhik Roychoudhury. 2018. Symbolic Execution with Existential Second-Order Constraints. In Proceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering (ESEC/FSE 2018). Association for Computing Machinery, New York, NY, USA. 389–399. isbn:9781450355735 https://doi.org/10.1145/3236024.3236049

[77]

Michael Lee Michael L. Scott. 2000. Programming language pragmatics. Morgan Kaufmann.

[78]

Anders Miltner, Adrian Trejo Nuñez, Ana Brendel, Swarat Chaudhuri, and Isil Dillig. 2022. Bottom-up Synthesis of Recursive Functional Programs Using Angelic Execution. Proc. ACM Program. Lang., 6, POPL (2022), Article 21, jan, 29 pages. https://doi.org/10.1145/3498682

[79]

Vijayaraghavan Murali, Letao Qi, Swarat Chaudhuri, and Chris Jermaine. 2017. Neural Sketch Learning for Conditional Program Generation. https://doi.org/10.48550/ARXIV.1703.05698

[80]

Chandrakana Nandi, Max Willsey, Adam Anderson, James R. Wilcox, Eva Darulova, Dan Grossman, and Zachary Tatlock. 2020. Synthesizing Structured CAD Models with Equality Saturation and Inverse Transformations. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2020). Association for Computing Machinery, New York, NY, USA. 31–44. isbn:9781450376136 https://doi.org/10.1145/3385412.3386012

[81]

Michal Nazarczuk and Krystian Mikolajczyk. 2020. V2A-Vision to Action: Learning robotic arm actions based on vision and language. In Proceedings of the Asian Conference on Computer Vision.

[82]

Daniel Neider. 2014. Applications of automata learning in verification and synthesis.

[83]

Julie L. Newcomb and Rastislav Bodík. 2019. Using human-in-the-loop synthesis to author functional reactive programs. ArXiv, abs/1909.11206 (2019), https://d-nb.info/1059276062/34

[84]

Scott Niekum, Sarah Osentoski, George Konidaris, Sachin Chitta, Bhaskara Marthi, and Andrew G. Barto. 2015. Learning grounded finite-state representations from unstructured demonstrations. The International Journal of Robotics Research, 34, 2 (2015), 131–157. https://doi.org/10.1177/0278364914554471 arxiv:https://doi.org/10.1177/0278364914554471.

[85]

Kore Nordmann. 2014. XML-Schema-learner. https://github.com/kore/XML-Schema-learner

[86]

Maxwell Nye, Luke Hewitt, Joshua Tenenbaum, and Armando Solar-Lezama. 2019. Learning to Infer Program Sketches. https://doi.org/10.48550/ARXIV.1902.06349

[87]

Shankara Pailoor, Yuepeng Wang, Xinyu Wang, and Isil Dillig. 2021. Synthesizing Data Structure Refinements from Integrity Constraints. In Proceedings of the 42nd ACM SIGPLAN International Conference on Programming Language Design and Implementation (PLDI 2021). Association for Computing Machinery, New York, NY, USA. 574–587. isbn:9781450383912 https://doi.org/10.1145/3453483.3454063

[88]

Sinno Jialin Pan and Qiang Yang. 2010. A Survey on Transfer Learning. IEEE Transactions on Knowledge and Data Engineering, 22 (2010), 1345–1359.

[89]

Noah Patton, Kia Rahmani, Meghana Missula, Joydeep Biswas, and Işil Dillig. 2023. Program Synthesis for Robot Learning from Demonstrations. arxiv:2305.03129.

[90]

Noah Patton, Kia Rahmani, Meghana Missula, Joydeep Biswas, and Isil Dillig. 2023. Programming-by-Demonstration for Long-Horizon Robot Tasks. https://doi.org/10.5281/zenodo.8423505

[91]

A. Pnueli and R. Rosner. 1989. On the Synthesis of a Reactive Module. In Proceedings of the 16th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’89). Association for Computing Machinery, New York, NY, USA. 179–190. isbn:0897912942 https://doi.org/10.1145/75277.75293

[92]

Nadia Polikarpova, Ivan Kuraj, and Armando Solar-Lezama. 2016. Program synthesis from polymorphic refinement types. In Proc. of PLDI. 522–538.

[93]

David Porfirio, Evan Fisher, Allison Sauppé, Aws Albarghouthi, and Bilge Mutlu. 2019. Bodystorming Human-Robot Interactions. In Proceedings of the 32nd Annual ACM Symposium on User Interface Software and Technology (UIST ’19). Association for Computing Machinery, New York, NY, USA. 479–491. isbn:9781450368162 https://doi.org/10.1145/3332165.3347957

[94]

David Porfirio, Laura Stegner, Maya Cakmak, Allison Sauppé, Aws Albarghouthi, and Bilge Mutlu. 2023. Sketching Robot Programs On the Fly. In Proceedings of the 2023 ACM/IEEE International Conference on Human-Robot Interaction (HRI ’23). Association for Computing Machinery, New York, NY, USA. 584–593. isbn:9781450399647 https://doi.org/10.1145/3568162.3576991

[95]

Kevin Pu, Rainey Fu, Rui Dong, Xinyu Wang, Yan Chen, and Tovi Grossman. 2022. SemanticOn: Specifying Content-Based Semantic Conditions for Web Automation Programs. In Proceedings of the 35th Annual ACM Symposium on User Interface Software and Technology (UIST ’22). Association for Computing Machinery, New York, NY, USA. Article 63, 16 pages. isbn:9781450393201 https://doi.org/10.1145/3526113.3545691

[96]

Kia Rahmani, Mohammad Raza, Sumit Gulwani, Vu Le, Daniel Morris, Arjun Radhakrishna, Gustavo Soares, and Ashish Tiwari. 2021. Multi-Modal Program Inference: A Marriage of Pre-Trained Language Models and Component-Based Synthesis. Proc. ACM Program. Lang., 5, OOPSLA (2021), Article 158, oct, 29 pages. https://doi.org/10.1145/3485535

[97]

Rodrigo C. O. Rocha, Pavlos Petoumenos, Björn Franke, Pramod Bhatotia, and Michael O’Boyle. 2022. Loop Rolling for Code Size Reduction. In Proceedings of the 20th IEEE/ACM International Symposium on Code Generation and Optimization (CGO ’22). IEEE Press, 217–229. isbn:9781665405843 https://doi.org/10.1109/CGO53902.2022.9741256

[98]

Antoni Rosinol, Andrew Violette, Marcus Abate, Nathan Hughes, Yun Chang, Jingnan Shi, Arjun Gupta, and Luca Carlone. 2021. Kimera: From SLAM to spatial perception with 3D dynamic scene graphs. The International Journal of Robotics Research, 40, 12-14 (2021), 1510–1546.

[99]

Andrei A. Rusu, Matej Vecerík, Thomas Rothörl, Nicolas Heess, Razvan Pascanu, and Raia Hadsell. 2017. Sim-to-Real Robot Learning from Pixels with Progressive Nets. In 1st Annual Conference on Robot Learning, CoRL 2017, Mountain View, California, USA, November 13-15, 2017, Proceedings (Proceedings of Machine Learning Research, Vol. 78). PMLR, 262–270. http://proceedings.mlr.press/v78/rusu17a.html

[100]

Kensen Shi, Jacob Steinhardt, and Percy Liang. 2019. FrAngel: Component-Based Synthesis with Control Structures. Proc. ACM Program. Lang., 3, POPL (2019), Article 73, jan, 29 pages. https://doi.org/10.1145/3290386

[101]

Kavan Singh Sikand, Logan Zartman, Sadegh Rabiee, and Joydeep Biswas. 2021. Robofleet: Open source communication and management for fleets of autonomous robots. In 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). 406–412.

[102]

Zachary D. Sisco, Jonathan Balkind, Timothy Sherwood, and Ben Hardekopf. 2023. Loop Rerolling for Hardware Decompilation. Proc. ACM Program. Lang., 7, PLDI (2023), Article 123, jun, 23 pages. https://doi.org/10.1145/3591237

[103]

Armando Solar-Lezama. 2008. Program synthesis by sketching. Citeseer.

[104]

Armando Solar-Lezama. 2009. The Sketching Approach to Program Synthesis. In Proc. of APLAS. 4–13.

[105]

Armando Solar-Lezama, Liviu Tancau, Rastislav Bodík, Sanjit A. Seshia, and Vijay A. Saraswat. 2006. Combinatorial sketching for finite programs. In Proc. of ASPLOS. 404–415.

[106]

Arturo Daniel Sosa-Ceron, Hugo Gustavo Gonzalez-Hernandez, and Jorge Antonio Reyes-Avendaño. 2022. Learning from Demonstrations in Human and Robot Collaborative Scenarios: A Survey. Robotics, 11, 6 (2022), issn:2218-6581 https://doi.org/10.3390/robotics11060126

[107]

Sanjana Srivastava, Chengshu Li, Michael Lingelbach, Roberto Martín-Martín, Fei Xia, Kent Elliott Vainio, Zheng Lian, Cem Gokmen, Shyamal Buch, Karen Liu, Silvio Savarese, Hyowon Gweon, Jiajun Wu, and Li Fei-Fei. 2022. BEHAVIOR: Benchmark for Everyday Household Activities in Virtual, Interactive, and Ecological Environments. In Proceedings of the 5th Conference on Robot Learning, Aleksandra Faust, David Hsu, and Gerhard Neumann (Eds.) (Proceedings of Machine Learning Research, Vol. 164). PMLR, 477–490. https://proceedings.mlr.press/v164/srivastava22a.html

[108]

Jennifer J. Sun, Megan Tjandrasuwita, Atharva Sehgal, Armando Solar-Lezama, Swarat Chaudhuri, Yisong Yue, and Omar Costilla-Reyes. 2022. Neurosymbolic Programming for Science. https://doi.org/10.48550/ARXIV.2210.05050

[109]

Niko Sünderhauf, Oliver Brock, Walter Scheirer, Raia Hadsell, Dieter Fox, Jürgen Leitner, Ben Upcroft, Pieter Abbeel, Wolfram Burgard, Michael Milford, and Peter Corke. 2018. The limits and potentials of deep learning for robotics. The International Journal of Robotics Research, 37, 4-5 (2018), 405–420. https://doi.org/10.1177/0278364918770733 arxiv:https://doi.org/10.1177/0278364918770733.

[110]

Matthew E. Taylor and Peter Stone. 2009. Transfer Learning for Reinforcement Learning Domains: A Survey. J. Mach. Learn. Res., 10 (2009), dec, 1633–1685. issn:1532-4435

[111]

Ashish Tiwari, Adrià Gascón, and Bruno Dutertre. 2015. Program Synthesis Using Dual Interpretation. In Automated Deduction - CADE-25, Amy P. Felty and Aart Middeldorp (Eds.). Springer International Publishing, Cham. 482–497. isbn:978-3-319-21401-6

[112]

Nicholay Topin and Manuela Veloso. 2019. Generation of Policy-Level Explanations for Reinforcement Learning. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence (AAAI’19/IAAI’19/EAAI’19). AAAI Press, Article 310, 8 pages. isbn:978-1-57735-809-1 https://doi.org/10.1609/aaai.v33i01.33012514

[113]

Martin Vechev, Eran Yahav, and Greta Yorsh. 2010. Abstraction-Guided Synthesis of Synchronization. SIGPLAN Not., 45, 1 (2010), jan, 327–338. issn:0362-1340 https://doi.org/10.1145/1707801.1706338

[114]

Gust Verbruggen, Vu Le, and Sumit Gulwani. 2021. Semantic Programming by Example with Pre-Trained Models. Proc. ACM Program. Lang., 5, OOPSLA (2021), Article 100, oct, 25 pages. https://doi.org/10.1145/3485477

[115]

Abhinav Verma, Hoang M. Le, Yisong Yue, and Swarat Chaudhuri. 2019. Imitation-Projected Programmatic Reinforcement Learning. Curran Associates Inc., Red Hook, NY, USA.

[116]

Abhinav Verma, Vijayaraghavan Murali, Rishabh Singh, Pushmeet Kohli, and Swarat Chaudhuri. 2018. Programmatically Interpretable Reinforcement Learning. https://doi.org/10.48550/ARXIV.1804.02477

[117]

Xinyu Wang, Isil Dillig, and Rishabh Singh. 2018. Program synthesis using abstraction refinement. PACMPL, 2, POPL (2018), 63:1–63:30.

[118]

Yuepeng Wang, James Dong, Rushi Shah, and Isil Dillig. 2019. Synthesizing Database Programs for Schema Refactoring. In Proceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI 2019). ACM, New York, NY, USA. 286–300. isbn:978-1-4503-6712-7 https://doi.org/10.1145/3314221.3314588

[119]

Yuepeng Wang, James Dong, Rushi Shah, and Isil Dillig. 2019. Synthesizing database programs for schema refactoring. In Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI.

[120]

Yuepeng Wang, Rushi Shah, Abby Criswell, Rong Pan, and Isil Dillig. 2020. Data migration using datalog program synthesis. VLDB.

[121]

Yuepeng Wang, Xinyu Wang, and Isil Dillig. 2018. Relational Program Synthesis. PACMPL, 2, OOPSLA (2018), 155:1–155:27.

[122]

Jules White, Quchen Fu, Sam Hays, Michael Sandborn, Carlos Olea, Henry Gilbert, Ashraf Elnashar, Jesse Spencer-Smith, and Douglas C. Schmidt. 2023. A Prompt Pattern Catalog to Enhance Prompt Engineering with ChatGPT. arxiv:2302.11382.

[123]

Jonas Witt, Stef Rasing, Sebastijan Dumančić, Tias Guns, and Claus-Christian Carbon. 2023. A Divide-Align-Conquer Strategy for Program Synthesis. https://doi.org/10.48550/ARXIV.2301.03094

[124]

Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Remi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. 2020. Transformers: State-of-the-Art Natural Language Processing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations. Association for Computational Linguistics, Online. 38–45. https://doi.org/10.18653/v1/2020.emnlp-demos.6

[125]

Xuesu Xiao, Joydeep Biswas, and Peter Stone. 2021. Learning Inverse Kinodynamics for Accurate High-Speed Off-Road Navigation on Unstructured Terrain. https://doi.org/10.48550/ARXIV.2102.12667

[126]

Jimmy Xin, Linus Zheng, Jiayi Wei, Kia Rahmani, Jarrett Holtz, Isil Dillig, and Joydeep Biswas. 2023. PLUNDER: Probabilistic Program Synthesis for Learning from Unlabeled and Noisy Demonstrations. https://doi.org/10.48550/ARXIV.2303.01440

[127]

Navid Yaghmazadeh, Yuepeng Wang, Isil Dillig, and Thomas Dillig. 2017. SQLizer: query synthesis from natural language. PACMPL, 1, OOPSLA (2017), 63:1–63:26.

[128]

Xi Ye, Qiaochu Chen, Isil Dillig, and Greg Durrett. 2020. Optimal Neural Program Synthesis from Multimodal Specifications. arXiv preprint arXiv:2010.01678.

[129]

Eric Zhan, Jennifer J. Sun, Ann Kennedy, Yisong Yue, and Swarat Chaudhuri. 2021. Unsupervised Learning of Neurosymbolic Encoders. https://doi.org/10.48550/ARXIV.2107.13132

[130]

Brian D. Ziebart, Andrew Maas, J. Andrew Bagnell, and Anind K. Dey. 2008. Maximum Entropy Inverse Reinforcement Learning. In Proceedings of the 23rd National Conference on Artificial Intelligence - Volume 3 (AAAI’08). AAAI Press, 1433–1438. isbn:9781577353683

Cited By

Mariano BWang ZPailoor SCollberg CDillig I(2024)Control-Flow Deobfuscation using Trace-Informed Compositional Program SynthesisProceedings of the ACM on Programming Languages10.1145/36897898:OOPSLA2(2211-2241)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689789
Xin JZheng LRahmani KWei JHoltz JDillig IBiswas J(2024)Programmatic Imitation Learning From Unlabeled and Noisy DemonstrationsIEEE Robotics and Automation Letters10.1109/LRA.2024.33856919:6(4894-4901)Online publication date: Jun-2024
https://doi.org/10.1109/LRA.2024.3385691

Index Terms

Programming-by-Demonstration for Long-Horizon Robot Tasks

Recommendations

Safe and Robust Robot Learning from Demonstration through Conceptual Constraints
HRI '20: Companion of the 2020 ACM/IEEE International Conference on Human-Robot Interaction

This thesis summary presents research focused on incorporating high-level abstract behavioral requirements, called 'conceptual constraints', into the modeling processes of robot Learning from Demonstration (LfD) techniques. This idea is realized via an ...
Deep imitation learning for 3D navigation tasks

Deep learning techniques have shown success in learning from raw high-dimensional data in various applications. While deep reinforcement learning is recently gaining popularity as a method to train intelligent agents, utilizing deep learning in ...
Interactive Robot Training for Temporal Tasks
HRI '20: Companion of the 2020 ACM/IEEE International Conference on Human-Robot Interaction

Imagine a future where a domestic robot ships with a state-of-theart learning from demonstrations (LfD) system to learn household tasks. You would like the robot to set the dinner-table for you when you get home at dinner time. After you demonstrate how ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Programming Languages

Proceedings of the ACM on Programming Languages Volume 8, Issue POPL

January 2024

2820 pages

EISSN:2475-1421

DOI:10.1145/3554315

Editor:
Michael Hicks
Amazon, USA

Issue’s Table of Contents

Copyright © 2024 Owner/Author.

This work is licensed under a Creative Commons Attribution 4.0 International License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 January 2024

Published in PACMPL Volume 8, Issue POPL

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Author Tags

Qualifiers

Research-article

Funding Sources

NSF (National Science Foundation)

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
561
Total Downloads

Downloads (Last 12 months)561
Downloads (Last 6 weeks)80

Reflects downloads up to 01 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mariano BWang ZPailoor SCollberg CDillig I(2024)Control-Flow Deobfuscation using Trace-Informed Compositional Program SynthesisProceedings of the ACM on Programming Languages10.1145/36897898:OOPSLA2(2211-2241)Online publication date: 8-Oct-2024
https://dl.acm.org/doi/10.1145/3689789
Xin JZheng LRahmani KWei JHoltz JDillig IBiswas J(2024)Programmatic Imitation Learning From Unlabeled and Noisy DemonstrationsIEEE Robotics and Automation Letters10.1109/LRA.2024.33856919:6(4894-4901)Online publication date: Jun-2024
https://doi.org/10.1109/LRA.2024.3385691

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents