“RoboGrammar: graph grammar for terrain-optimized robot design” by Zhao, Xu, Konaković-Luković, Hughes, Spielberg, et al. …
Conference:
Type(s):
Title:
- RoboGrammar: graph grammar for terrain-optimized robot design
Session/Category Title: Computational Robotics
Presenter(s)/Author(s):
Abstract:
We present RoboGrammar, a fully automated approach for generating optimized robot structures to traverse given terrains. In this framework, we represent each robot design as a graph, and use a graph grammar to express possible arrangements of physical robot assemblies. Each robot design can then be expressed as a sequence of grammar rules. Using only a small set of rules our grammar can describe hundreds of thousands of possible robot designs. The construction of the grammar limits the design space to designs that can be fabricated. For a given input terrain, the design space is searched to find the top performing robots and their corresponding controllers. We introduce Graph Heuristic Search – a novel method for efficient search of combinatorial design spaces. In Graph Heuristic Search, we explore the design space while simultaneously learning a function that maps incomplete designs (e.g., nodes in the combinatorial search tree) to the best performance values that can be achieved by expanding these incomplete designs. Graph Heuristic Search prioritizes exploration of the most promising branches of the design space. To test our method we optimize robots for a number of challenging and varied terrains. We demonstrate that RoboGrammar can successfully generate nontrivial robots that are optimized for a single terrain or a combination of terrains.
References:
1. ZM Bi and Wen-Jun Zhang. 2001. Concurrent optimal design of modular robotic configuration. Journal of Robotic systems 18, 2 (2001), 77–87.Google ScholarCross Ref
2. Martin Bokeloh, Michael Wand, and Hans-Peter Seidel. 2010. A Connection between Partial Symmetry and Inverse Procedural Modeling. ACM Trans. Graph. 29, 4, Article Article 104 (July 2010), 10 pages. Google ScholarDigital Library
3. Josh C Bongard. 2013. Evolutionary robotics. Commun. ACM 56, 8 (2013), 74–83.Google ScholarDigital Library
4. Luzius Brodbeck, Simon Hauser, and Fumiya Iida. 2015. Morphological evolution of physical robots through model-free phenotype development. PloS one 10, 6 (2015), e0128444.Google ScholarCross Ref
5. Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter I Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. 2012. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games 4, 1 (2012), 1–43.Google ScholarCross Ref
6. I-Ming Chen and Joel W Burdick. 1995. Determining task optimal modular robot assembly configurations. In proceedings of 1995 IEEE International Conference on Robotics and Automation, Vol. 1. IEEE, 132–137.Google ScholarCross Ref
7. Benjamin E Childs, James H Brodeur, and Levente Kocsis. 2008. Transpositions and move groups in Monte Carlo tree search. In 2008 IEEE Symposium On Computational Intelligence and Games. IEEE, 389–395.Google ScholarCross Ref
8. Noam Chomsky. 1956. Three models for the description of language. IRE Transactions on Information Theory 2, 3 (Sep. 1956), 113–124. Google ScholarCross Ref
9. Erwin Coumans. 2015. Bullet physics simulation. In ACM SIGGRAPH 2015 Courses. ACM, 7.Google ScholarDigital Library
10. Minh Dang, Stefan Lienhard, Duygu Ceylan, Boris Neubert, Peter Wonka, and Mark Pauly. 2015. Interactive Design of Probability Density Functions for Shape Grammars. ACM Trans. Graph. 34, 6, Article Article 206 (Oct. 2015), 13 pages. Google ScholarDigital Library
11. Frances Downing and Ulrich Flemming. 1981. The bungalows of Buffalo. Environment and Planning B: Planning and Design 8, 3 (1981), 269–293.Google ScholarCross Ref
12. José Pinto Duarte. 2005. Towards the Mass Customization of Housing: The Grammar of Siza’s Houses at Malagueira. Environment and Planning B: Planning and Design 32, 3 (2005), 347–380. Google ScholarCross Ref
13. Roy Featherstone. 1983. The calculation of robot dynamics using articulated-body inertias. The International Journal of Robotics Research 2, 1 (1983), 13–30.Google ScholarCross Ref
14. Carlos E Garcia, David M Prett, and Manfred Morari. 1989. Model predictive control: theory and practice—a survey. Automatica 25, 3 (1989), 335–348.Google ScholarDigital Library
15. Sylvain Gelly, Levente Kocsis, Marc Schoenauer, Michele Sebag, David Silver, Csaba Szepesvári, and Olivier Teytaud. 2012. The grand challenge of computer Go: Monte Carlo tree search and extensions. Commun. ACM 55, 3 (2012), 106–113.Google ScholarDigital Library
16. Sylvain Gelly and David Silver. 2011. Monte-Carlo tree search and rapid action value estimation in computer Go. Artificial Intelligence 175, 11 (2011), 1856–1875.Google ScholarDigital Library
17. David Ha. 2018. Reinforcement learning for improving agent design. arXiv preprint arXiv:1810.03779 (2018).Google Scholar
18. Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Advances in neural information processing systems. 1024–1034.Google Scholar
19. David P Helmbold and Aleatha Parker-Wood. 2009. All-Moves-As-First Heuristics in Monte-Carlo Go.. In IC-AI. 605–610.Google Scholar
20. Jonathan Hiller and Hod Lipson. 2011. Automatic design and manufacture of soft robots. IEEE Transactions on Robotics 28, 2 (2011), 457–466.Google ScholarDigital Library
21. Gregory S Hornby and Jordan B Pollack. 2001. The advantages of generative grammatical encodings for physical design. In Proceedings of the 2001 Congress on Evolutionary Computation (IEEE Cat. No. 01TH8546), Vol. 1. IEEE, 600–607.Google ScholarCross Ref
22. Diego Jesus, António Coelho, and António Augusto Sousa. 2016. Layered Shape Grammars for Procedural Modelling of Buildings. Vis. Comput. 32, 6–8 (June 2016), 933–943. Google ScholarDigital Library
23. Gangyuan Jing, Tarik Tosun, Mark Yim, and Hadas Kress-Gazit. 2018. Accomplishing high-level tasks with modular robots. Autonomous Robots 42, 7 (2018), 1337–1354.Google ScholarDigital Library
24. Diederik P. Kingma and Jimmy Ba. 2015. Adam: A Method for Stochastic Optimization. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7–9, 2015, Conference Track Proceedings, Yoshua Bengio and Yann LeCun (Eds.). http://arxiv.org/abs/1412.6980Google Scholar
25. Thomas N Kipf and Max Welling. 2016. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907 (2016).Google Scholar
26. Gregor Klančar and Igor Škrjanc. 2007. Tracking-error model-based predictive control for mobile robots in real time. Robotics and autonomous systems 55, 6 (2007), 460–469.Google Scholar
27. Eric Klavins, Robert Ghrist, and David Lipsky. 2004. Graph grammars for self assembling robotic systems. In IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA’04. 2004, Vol. 5. IEEE, 5293–5300.Google ScholarCross Ref
28. Levente Kocsis and Csaba Szepesvári. 2006. Bandit based monte-carlo planning. In European conference on machine learning. Springer, 282–293.Google ScholarDigital Library
29. John R Koza. 1995. Survey of genetic algorithms and genetic programming. In Wescon conference record. Western Periodicals Company, 589–594.Google ScholarCross Ref
30. Lars Krecklau, Darko Pavic, and Leif Kobbelt. 2010. Generalized Use of Non-Terminal Symbols for Procedural Modeling. Computer Graphics Forum 29, 8 (2010), 2291–2303. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1111/j.1467-8659.2010.01714.x Google ScholarCross Ref
31. Felipe Kuhne, Walter Fetter Lages, and J Gomes da Silva Jr. 2004. Model predictive control of a mobile robot using linearization. In Proceedings of mechatronics and robotics. Citeseer, 525–530.Google Scholar
32. Manfred Lau, Akira Ohgawara, Jun Mitani, and Takeo Igarashi. 2011. Converting 3D furniture models to fabricatable parts and connectors. In ACM Transactions on Graphics (TOG), Vol. 30. ACM, 85.Google ScholarDigital Library
33. Gil Lederman, Markus N Rabe, Edward A Lee, and Sanjit A Seshia. 2018. Learning heuristics for automated reasoning through deep reinforcement learning. arXiv preprint arXiv:1807.08058 (2018).Google Scholar
34. Markus Lipp, Peter Wonka, and Michael Wimmer. 2008. Interactive Visual Editing of Grammars for Procedural Architecture. In ACM SIGGRAPH 2008 Papers (SIGGRAPH ’08). Association for Computing Machinery, New York, NY, USA, Article Article 102, 10 pages. Google ScholarDigital Library
35. Tianqiang Liu, Siddhartha Chaudhuri, Vladimir G. Kim, Qixing Huang, Niloy J. Mitra, and Thomas Funkhouser. 2014. Creating Consistent Scene Graphs Using a Probabilistic Grammar. ACM Trans. Graph. 33, 6, Article Article 211 (Nov. 2014), 12 pages. Google ScholarDigital Library
36. Kendall Lowrey, Aravind Rajeswaran, Sham Kakade, Emanuel Todorov, and Igor Mordatch. 2018. Plan online, learn offline: Efficient learning and exploration via modelbased control. arXiv preprint arXiv:1811.01848 (2018).Google Scholar
37. Jon McCormack, Alan Dorin, Troy Innocent, et al. 2004. Generative design: a paradigm for design research. Proceedings of Futureground, Design Research Society, Melbourne (2004).Google Scholar
38. Pascal Müller, Peter Wonka, Simon Haegler, Andreas Ulmer, and Luc Van Gool. 2006. Procedural Modeling of Buildings. ACM Trans. Graph. 25, 3 (July 2006), 614–623. Google ScholarDigital Library
39. Rémi Munos et al. 2014. From bandits to Monte-Carlo Tree Search: The optimistic principle applied to optimization and planning. Foundations and Trends® in Machine Learning 7, 1 (2014), 1–129.Google Scholar
40. Quan V Nguyen, Francis Colas, Emmanuel Vincent, and François Charpillet. 2017. Long-term robot motion planning for active sound source localization with Monte Carlo tree search. In 2017 Hands-free Speech Communications and Microphone Arrays (HSCMA). IEEE, 61–65.Google Scholar
41. Peter Norvig and Stuart Russell. 2002. Artificial Intelligence: A modern approach (3rd ed.). Prentice Hall.Google Scholar
42. Yoav I. H. Parish and Pascal Müller. 2001. Procedural Modeling of Cities. In Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques (SIGGRAPH ’01). Association for Computing Machinery, New York, NY, USA, 301–308. Google ScholarDigital Library
43. Deepak Pathak, Chris Lu, Trevor Darrell, Phillip Isola, and Alexei A Efros. 2019. Learning to control self-assembling morphologies: a study of generalization via modularity. arXiv preprint arXiv:1902.05546 (2019).Google Scholar
44. Xue Bin Peng, Glen Berseth, KangKang Yin, and Michiel Van De Panne. 2017. Deeploco: Dynamic locomotion skills using hierarchical deep reinforcement learning. ACM Transactions on Graphics (TOG) 36, 4 (2017), 1–13.Google ScholarDigital Library
45. Jordan B Pollack, Gregory S Hornby, Hod Lipson, and Pablo Funes. 2003. Computer creativity in the automatic design of robots. Leonardo 36, 2 (2003), 115–121.Google ScholarCross Ref
46. Jim Pugh and Alcherio Martinoli. 2007. Inspiring and modeling multi-robot search with particle swarm optimization. In 2007 IEEE Swarm Intelligence Symposium. IEEE, 332–339.Google ScholarDigital Library
47. Maarten PD Schadd, Mark HM Winands, H Jaap Van Den Herik, Guillaume MJ-B Chaslot, and Jos WHM Uiterwijk. 2008. Single-player monte-carlo tree search. In International Conference on Computers and Games. Springer, 1–12.Google ScholarDigital Library
48. Charles Schaff, David Yunis, Ayan Chakrabarti, and Matthew R Walter. 2019. Jointly learning to construct and control agents using deep reinforcement learning. In 2019 International Conference on Robotics and Automation (ICRA). IEEE, 9798–9805.Google ScholarDigital Library
49. Linda C Schmidt and Jonathan Cagan. 1997. GGREADA: a graph grammar-based machine design algorithm. Research in Engineering Design 9, 4 (1997), 195–213.Google ScholarCross Ref
50. Linda C Schmidt, Harshawardhan Shetty, and Scott C Chase. 1999. A graph grammar approach for structure synthesis of mechanisms. J. Mech. Des. 122, 4 (1999), 371–376.Google ScholarCross Ref
51. Karl Sims. 1994. Evolving virtual creatures. In Proceedings of the 21st annual conference on Computer graphics and interactive techniques. ACM, 15–22.Google ScholarDigital Library
52. SN Sivanandam and SN Deepa. 2008. Genetic algorithms. In Introduction to genetic algorithms. Springer, 15–37.Google Scholar
53. Brian Smith, Ayanna Howard, John-Michael McNew, Jiuguang Wang, and Magnus Egerstedt. 2009. Multi-robot deployment and coordination with embedded graph grammars. Autonomous Robots 26, 1 (2009), 79–98.Google ScholarDigital Library
54. Andrew Spielberg, Allan Zhao, Yuanming Hu, Tao Du, Wojciech Matusik, and Daniela Rus. 2019. Learning-In-The-Loop Optimization: End-To-End Control And Co-Design of Soft Robots Through Learned Deep Latent Representations. In Advances in Neural Information Processing Systems. 8282–8292.Google Scholar
55. Ondrej Št’ava, Bedrich Beneš, Radomir Měch, Daniel G Aliaga, and Peter Krištof. 2010. Inverse procedural modeling by automatic generation of L-systems. In Computer Graphics Forum, Vol. 29. Wiley Online Library, 665–674.Google Scholar
56. George Stiny. 1982. Spatial Relations and Grammars. Environment and Planning B: Planning and Design 9, 1 (1982), 113–114. Google ScholarCross Ref
57. George Stiny and James Gips. 1971. ‘Shape Grammars and the Generative Specification of Painting and Sculpture’. IFIP Congress 71, 1460–1465.Google Scholar
58. George Stiny and William J. Mitchell. 1978. The Palladian Grammar.Google Scholar
59. Fritz R Stöckli and Kristina Shea. 2015. A simulation-driven graph grammar method for the automated synthesis of passive dynamic brachiating robots. In ASME 2015 International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. American Society of Mechanical Engineers Digital Collection.Google ScholarCross Ref
60. Russ Tedrake, Teresa Weirui Zhang, and H Sebastian Seung. 2004. Stochastic policy gradient reinforcement learning on a simple 3D biped. In 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)(IEEE Cat. No. 04CH37566), Vol. 3. IEEE, 2849–2854.Google ScholarCross Ref
61. Merel Van Diepen and Kristina Shea. 2019. A spatial grammar method for the computational design synthesis of virtual soft locomotion robots. Journal of Mechanical Design 141, 10 (2019).Google Scholar
62. Rui Wang, Joel Lehman, Jeff Clune, and Kenneth O Stanley. 2019a. Paired open-ended trailblazer (poet): Endlessly generating increasingly complex and diverse learning environments and their solutions. arXiv preprint arXiv:1901.01753 (2019).Google Scholar
63. Tingwu Wang, Yuhao Zhou, Sanja Fidler, and Jimmy Ba. 2019b. Neural Graph Evolution: Towards Efficient Automatic Robot Design. arXiv preprint arXiv:1906.05370 (2019).Google Scholar
64. Richard A Watson, Sevan G Ficici, and Jordan B Pollack. 2002. Embodied evolution: Distributing an evolutionary algorithm in a population of robots. Robotics and Autonomous Systems 39, 1 (2002), 1–18.Google ScholarCross Ref
65. Grady Williams, Paul Drews, Brian Goldfain, James M Rehg, and Evangelos A Theodorou. 2016. Aggressive driving with model predictive path integral control. In 2016 IEEE International Conference on Robotics and Automation (ICRA). IEEE, 1433–1440.Google ScholarDigital Library
66. Peter Wonka, Michael Wimmer, François Sillion, and William Ribarsky. 2003. Instant Architecture. ACM Trans. Graph. 22, 3 (July 2003), 669–677. Google ScholarDigital Library
67. Fuzhang Wu, Dong-Ming Yan, Weiming Dong, Xiaopeng Zhang, and Peter Wonka. 2014. Inverse Procedural Modeling of Facade Layouts. ACM Transactions on Graphics 33 (08 2014). Google ScholarDigital Library
68. Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. 2018. Hierarchical graph representation learning with differentiable pooling. In Advances in neural information processing systems. 4800–4810.Google Scholar
