“Designing actuation systems for animatronic figures via globally optimal discrete search” by Huber, Poranne and Coros

We present an algorithmic approach to designing animatronic figures – expressive robotic characters whose movements are driven by a large number of actuators. The input to our design system provides a high-level specification of the space of motions the character should be able to perform. The output consists of a fully functional mechatronic blueprint. We cast the design task as a search problem in a vast combinatorial space of possible solutions. To find an optimal design in this space, we propose an efficient best-first search algorithm that is guided by an admissible heuristic. The objectives guiding the search process demand that the design remains free of singularities and self-collisions at any point in the high-dimensional space of motions the character is expected to be able to execute. To identify worst-case self-collision scenarios for multi degree-of-freedom closed-loop mechanisms, we additionally develop an elegant technique inspired by the concept of adversarial attacks. We demonstrate the efficacy of our approach by creating designs for several animatronic figures of varying complexity.

1. Moritz Bächer, Stelian Coros, and Bernhard Thomaszewski. 2015. LinkEdit: interactive linkage editing using symbolic kinematics. ACM Trans. Graph. 34, 4 (2015), 99:1–99:8. Google ScholarDigital Library
2. Amit H. Bermano, Thomas A. Funkhouser, and Szymon Rusinkiewicz. 2017. State of the Art in Methods and Representations for Fabrication-Aware Design. Comput. Graph. Forum 36, 2 (2017), 509–535. Google ScholarDigital Library
3. James M. Bern, Pol Banzet, Roi Poranne, and Stelian Coros. 2019. Trajectory Optimization for Cable-Driven Soft Robot Locomotion. In Robotics: Science and Systems XV, University of Freiburg, Freiburg im Breisgau, Germany, June 22-26, 2019, Antonio Bicchi, Hadas Kress-Gazit, and Seth Hutchinson (Eds.). Google ScholarCross Ref
4. James M. Bern, Kai-Hung Chang, and Stelian Coros. 2017. Interactive design of animated plushies. ACM Trans. Graph. 36, 4 (2017), 80:1–80:11. Google ScholarDigital Library
5. Gaurav Bharaj, Stelian Coros, Bernhard Thomaszewski, James Tompkin, Bernd Bickel, and Hanspeter Pfister. 2015. Computational design of walking automata. In Proceedings of the 14th ACM SIGGRAPH / Eurographics Symposium on Computer Animation, SCA 2015, Los Angeles, CA, USA, August 7-9, 2015, Jernej Barbic and Zhigang Deng (Eds.). ACM, 93–100. Google ScholarDigital Library
6. Bernd Bickel, Peter Kaufmann, Mélina Skouras, Bernhard Thomaszewski, Derek Bradley, Thabo Beeler, Philip Jackson, Steve Marschner, Wojciech Matusik, and Markus H. Gross. 2012. Physical face cloning. ACM Trans. Graph. 31, 4 (2012), 118:1–118:10. Google ScholarDigital Library
7. Rainer E. Burkard, Eranda Çela, Panos M. Pardalos, and Leonidas S. Pitsoulis. 1998. The Quadratic Assignment Problem. Springer US, Boston, MA, 1713–1809. Google ScholarCross Ref
8. Stelian Coros, Bernhard Thomaszewski, Gioacchino Noris, Shinjiro Sueda, Moira Forberg, Robert W. Sumner, Wojciech Matusik, and Bernd Bickel. 2013. Computational design of mechanical characters. ACM Trans. Graph. 32, 4 (2013), 83:1–83:12. Google ScholarDigital Library
9. Ruta Desai, James McCann, and Stelian Coros. 2018. Assembly-aware Design of Printable Electromechanical Devices. In The 31st Annual ACM Symposium on User Interface Software and Technology, UIST 2018, Berlin, Germany, October 14-17, 2018, Patrick Baudisch, Albrecht Schmidt, and Andy Wilson (Eds.). ACM, 457–472. Google ScholarDigital Library
10. Tao Du, Adriana Schulz, Bo Zhu, Bernd Bickel, and Wojciech Matusik. 2016. Computational multicopter design. ACM Trans. Graph. 35, 6 (2016), 227:1–227:10. http://dl.acm.org/citation.cfm?id=2982427Google ScholarDigital Library
11. X. Feng, J. Liu, Y. Yang, H. Wang, H. Bao, B. Bickel, and W. Xu. 2019. Computational Design of Skinned Quad-Robots. IEEE Transactions on Visualization Computer Graphics 01 (dec 2019), 1–1. Google ScholarCross Ref
12. Moritz Geilinger, David Hahn, Jonas Zehnder, Moritz Bächer, Bernhard Thomaszewski, and Stelian Coros. 2020. ADD: analytically differentiable dynamics for multi-body systems with frictional contact. ACM Trans. Graph. 39, 6 (2020), 190:1–190:15. Google ScholarDigital Library
13. Moritz Geilinger, Roi Poranne, Ruta Desai, Bernhard Thomaszewski, and Stelian Coros. 2018. Skaterbots: optimization-based design and motion synthesis for robotic creatures with legs and wheels. ACM Trans. Graph. 37, 4 (2018), 160:1–160:12. Google ScholarDigital Library
14. Sehoon Ha, Stelian Coros, Alexander Alspach, James M Bern, Joohyung Kim, and Katsu Yamane. 2018a. Computational design of robotic devices from high-level motion specifications. IEEE Transactions on Robotics 34, 5 (2018), 1240–1251.Google ScholarDigital Library
15. Sehoon Ha, Stelian Coros, Alexander Alspach, Joohyung Kim, and Katsu Yamane. 2018b. Computational co-optimization of design parameters and motion trajectories for robotic systems. Int. J. Robotics Res. 37, 13-14 (2018). Google ScholarDigital Library
16. David Hahn, Pol Banzet, James M. Bern, and Stelian Coros. 2019. Real2Sim: visco-elastic parameter estimation from dynamic motion. ACM Trans. Graph. 38, 6 (2019), 236:1–236:13. Google ScholarDigital Library
17. Eric A. Hansen and Rong Zhou. 2007. Anytime Heuristic Search. J. Artif. Int. Res. 28, 1 (March 2007), 267–297.Google Scholar
18. Shayan Hoshyari, Hongyi Xu, Espen Knoop, Stelian Coros, and Moritz Bächer. 2019. Vibration-minimizing motion retargeting for robotic characters. ACM Trans. Graph. 38, 4 (2019), 102:1–102:14. Google ScholarDigital Library
19. Sandy H. Huang, Nicolas Papernot, Ian J. Goodfellow, Yan Duan, and Pieter Abbeel. 2017. Adversarial Attacks on Neural Network Policies. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Workshop Track Proceedings. OpenReview.net. https://openreview.net/forum?id=ryvlRyBKlGoogle Scholar
20. Milan Jelisavcic, Matteo de Carlo, Elte Hupkes, Panagiotis Eustratiadis, Jakub Orlowski, Evert Haasdijk, Joshua E. Auerbach, and A. E. Eiben. 2017. Real-World Evolution of Robot Morphologies: A Proof of Concept. Artificial Life 23, 2 (2017), 206–235. PMID: 28513201. Google ScholarDigital Library
21. Chris Leger et al. 1999. Automated synthesis and optimization of robot configurations: an evolutionary approach. Carnegie Mellon University USA.Google Scholar
22. Li-Ke Ma, Yizhonc Zhang, Yang Liu, Kun Zhou, and Xin Tong. 2017. Computational design and fabrication of soft pneumatic objects with desired deformations. ACM Trans. Graph. 36, 6 (2017), 239:1–239:12. Google ScholarDigital Library
23. Vittorio Megaro, Bernhard Thomaszewski, Damien Gauge, Eitan Grinspun, Stelian Coros, and Markus H. Gross. 2014. ChaCra: An Interactive Design System for Rapid Character Crafting. In The Eurographics / ACM SIGGRAPH Symposium on Computer Animation, SCA 2014, Copenhagen, Denmark, 2014, Vladlen Koltun and Eftychios Sifakis (Eds.). Eurographics Association, 123–130. Google ScholarCross Ref
24. Vittorio Megaro, Bernhard Thomaszewski, Maurizio Nitti, Otmar Hilliges, Markus H. Gross, and Stelian Coros. 2015. Interactive design of 3D-printable robotic creatures. ACM Trans. Graph. 34, 6 (2015), 216:1–216:9. Google ScholarDigital Library
25. Vittorio Megaro, Jonas Zehnder, Moritz Bächer, Stelian Coros, Markus H. Gross, and Bernhard Thomaszewski. 2017. A computational design tool for compliant mechanisms. ACM Trans. Graph. 36, 4 (2017), 82:1–82:12. Google ScholarDigital Library
26. Peng Song, Xiaofei Wang, Xiao Tang, Chi-Wing Fu, Hongfei Xu, Ligang Liu, and Niloy J. Mitra. 2017. Computational design of wind-up toys. ACM Trans. Graph. 36, 6 (2017), 238:1–238:13. Google ScholarDigital Library
27. Xiaoxun Sun and Sven Koenig. 2007. The Fringe-Saving A* Search Algorithm: A Feasibility Study. In Proceedings of the 20th International Joint Conference on Artifical Intelligence (Hyderabad, India) (IJCAI’07). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2391–2397.Google Scholar
28. Pengbin Tang, Jonas Zehnder, Stelian Coros, and Bernhard Thomaszewski. 2020. A harmonic balance approach for designing compliant mechanical systems with nonlinear periodic motions. ACM Trans. Graph. 39, 6 (2020), 191:1–191:14. Google ScholarDigital Library
29. Bernhard Thomaszewski, Stelian Coros, Damien Gauge, Vittorio Megaro, Eitan Grinspun, and Markus H. Gross. 2014. Computational design of linkage-based characters. ACM Trans. Graph. 33, 4 (2014), 64:1–64:9. Google ScholarDigital Library
30. Ran Zhang, Thomas Auzinger, Duygu Ceylan, Wilmot Li, and Bernd Bickel. 2017. Functionality-aware retargeting of mechanisms to 3D shapes. ACM Trans. Graph. 36, 4 (2017), 81:1–81:13. Google ScholarDigital Library
31. Allan Zhao, Jie Xu, Mina Konakovic-Lukovic, Josephine Hughes, Andrew Spielberg, Daniela Rus, and Wojciech Matusik. 2020. RoboGrammar: graph grammar for terrain-optimized robot design. ACM Trans. Graph. 39, 6 (2020), 188:1–188:16. Google ScholarDigital Library
32. Changxi Zheng, Timothy Sun, and Xiang Chen. 2016. Deployable 3D linkages with collision avoidance. In Proceedings of the ACM SIGGRAPH/Eurographics Symposium on Computer Animation, Zurich, Switzerland, July 11-13, 2016, Barbara Solenthaler, Matthias Teschner, Ladislav Kavan, and Chris Wojtan (Eds.). Eurographics Association / ACM, 179–188. http://dl.acm.org/citation.cfm?id=2982843Google ScholarDigital Library
33. Lifeng Zhu, Weiwei Xu, John Snyder, Yang Liu, Guoping Wang, and Baining Guo. 2012. Motion-guided mechanical toy modeling. ACM Trans. Graph. 31, 6 (2012), 127:1–127:10. Google ScholarDigital Library