We present an algorithm to compute planar linkage topology and geometry, given a user-specified end-effector trajectory. Planar linkage structures convert rotational or prismatic motions of a single actuator into an arbitrarily complex periodic motion, which is an important component when building low-cost, modular robots, mechanical toys, and foldable structures in our daily lives (chairs, bikes, and shelves). The design of such structures requires trial and error even for experienced engineers. Our research provides semi-automatic methods for exploring novel designs given high-level specifications and constraints. We formulate this problem as a non-smooth numerical optimization with quadratic objective functions and non-convex quadratic constraints involving mixed-integer decision variables (MIQCQP). We propose and compare three approximate algorithms to solve this problem: mixed-integer conic-programming (MICP), mixed-integer nonlinear programming (MINLP), and simulated annealing (SA). We evaluated these algorithms searching for planar linkages involving 10 − 14 rigid links. Our results show that the best performance can be achieved by combining MICP and MINLP, leading to a hybrid algorithm capable of finding the planar linkages within a couple of hours on a desktop machine, which significantly outperforms the SA baseline in terms of optimality. We highlight the effectiveness of our optimized planar linkages by using them as legs of a walking robot.
BächerMCorosSThomaszewskiB (2015) Linkedit: interactive linkage editing using symbolic kinematics. ACM Transactions on Graphics (TOG)34(4): 99.
2.
BaiZFJiangXLiF, et al. (2018) Reducing undesirable vibrations of planar linkage mechanism with joint clearance. Journal of Mechanical Science and Technology32(2): 559–565.
3.
BertsimasDTsitsiklisJ, et al. (1993) Simulated annealing. Statistical Science8(1): 10–15.
4.
BertsimasDTsitsiklisJN (1997) Introduction to Linear Optimization. MA: Athena Scientific Belmont, Vol. 6.
5.
BixbyBob (2007) The gurobi optimizer. Transp. Research Part B. 41(2): 159–178.
6.
BommesDZimmerHKobbeltL (2009) Mixed-integer quadrangulation. ACM Transactions On Graphics (TOG)28(3): 77.
7.
ByrdRHNocedalJWaltzRA (2006) Knitro: an integrated package for nonlinear optimization. In: Large-scale nonlinear optimization, Springer, pp. 35–59.
8.
CabreraJASimonAPradoM (2002) Optimal synthesis of mechanisms with genetic algorithms. Mechanism and Machine Theory37(10): 1165–1177.
9.
ConfortiMDi SummaMEisenbrandF, et al. (2009) Network formulations of mixed-integer programs. Mathematics of Operations Research34(1): 194–209.
10.
CorosSThomaszewskiBNorisG, et al. (2013) Computational design of mechanical characters. ACM Transactions on Graphics32(4): 1–12.
DaiHIzattGTedrakeR (2017) Global Inverse Kinematics Via Mixed-Integer Convex Optimization, Puerto Varas, Chile: International Symposium on Robotics Research, pp. 1–16.
13.
DeitsRTedrakeR (2014) Footstep planning on uneven terrain with mixed-integer convex optimization. In: 2014 IEEE-RAS international conference on humanoid robots, Madrid, Spain, 18-20 November 2014, IEEE, pp. 279–286.
14.
DingHReißigGGroßD, et al. (2011) Mixed-integer programming for optimal path planning of robotic manipulators. In: 2011 IEEE International Conference on Automation Science and Engineering, Trieste, Italy, 24-27 August 2011, IEEE, pp. 133–138.
15.
EggenspergerKFeurerMHutterF, et al. (2013) Towards an empirical foundation for assessing bayesian optimization of hyperparameters. NIPS Workshop on Bayesian Optimization in Theory and Practice10: 3.
16.
ErkayaSUzmayİ (2009) Determining link parameters using genetic algorithm in mechanisms with joint clearance. Mechanism and Machine Theory44(1): 222–234.
17.
ExlerOSchittkowskiK (2007) A trust region sqp algorithm for mixed-integer nonlinear programming. Optimization Letters1(3): 269–280.
18.
FeatherstoneR (2014) Rigid Body Dynamics Algorithms. Springer.
19.
FengBMoritaNToriiT (2002) A new optimization method for dynamic design of planar linkage with clearances at joints-optimizing the mass distribution of links to reduce the change of joint forces. Journal of Mechanical Design124(1): 68–73.
20.
GalletMKoutschanCLiZ, et al. (2017) Planar linkages following a prescribed motion. Mathematics of Computation86(303): 473–506.
21.
GosselinCAngelesJ (1990) Singularity analysis of closed-loop kinematic chains. IEEE Transactions on Robotics and Automation6(3): 281–290. DOI: 10.1109/70.56660.
22.
GovindarajuNKLinMCManochaD (2005) Quick-cullide: fast inter-and intra-object collision culling using graphics hardware. In: IEEE Proceedings. VR 2005. Virtual Reality. Bonn, Germany, 12-16 March 2005, IEEE, pp. 59–66.
23.
HaSCorosSAlspachA, et al. (2018a) Computational design of robotic devices from high-level motion specifications. IEEE Transactions on Robotics34(5): 1240–1251. DOI: 10.1109/TRO.2018.2830419.
24.
HaSCorosSAlspachA, et al. (2018b) Computational co-optimization of design parameters and motion trajectories for robotic systems. The International Journal of Robotics Research37(13–14): 1521–1536.
25.
HayakawaT.KamimuraTKajiS, et al. (2020) Autonomous distributed system for gait generation for single-legged modular robots connected in various configurations. IEEE Transactions on Robotics36(5): 1491–1510. DOI: 10.1109/TRO.2020.2992983.
HernándezAGómezCCrespoJ, et al (2016) A home made robotic platform based on theo jansen mechanism for teaching robotics. In: INTED2016 proceedings, 10th international technology, education and development conference, IATED, pp. 6689–6698. ISBN 978-84-608-5617-7.
28.
HuYLiuJSpielbergA, et al. (2019) Chainqueen: a real-time differentiable physical simulator for soft robotics. In: 2019 international conference on robotics and automation (ICRA), pp. 6265–6271. DOI: 10.1109/ICRA.2019.8794333.
29.
KannoY (2013) Topology optimization of tensegrity structures under compliance constraint: a mixed integer linear programming approach. Optimization and Engineering14(1): 61–96.
30.
KecskeméthyAKruppTHillerM (1997) Symbolic processing of multiloop mechanism dynamics using closed-form kinematics solutions. Multibody System Dynamics1(1): 23–45.
31.
KempeAB (1875) On a general method of describing plane curves of the nth degree by linkwork. Proceedings of the London Mathematical Societys1-7(1): 213–216.
32.
KimYJOtaduyMALinMC, et al. (2002) Fast penetration depth computation for physically-based animation. In: Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation, New York, NY, USA, July 2002, pp. 23–31.Proceedings of the 2002 ACM SIGGRAPH/Eurographics symposium on Computer animation
33.
KronqvistJLundellAWesterlundT (2016) The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming. Journal of Global Optimization64(2): 249–272.
34.
LaurentM (2009) Sums of squares, moment matrices and optimization over polynomials. In: Emerging applications of algebraic geometry, New York, 24 September 2008, Springer, pp. 157–270.
35.
LawlerELWoodDE (1966) Branch-and-bound methods: a survey. Operations Research14(4): 699–719.
36.
LiaoTWangGYangB, et al. (2019) Data-efficient learning of morphology and controller for a microrobot. In: 2019 international conference on robotics and automation (ICRA), Montreal, QC, Canada, 20-24 May 2019, pp. 2488–2494. DOI: 10.1109/ICRA.2019.8793802.
37.
LibertiL (2004) Reformulation and convex relaxation techniques for global optimization. PhD Thesis. Springer.
38.
LiuJMaY (2016) A survey of manufacturing oriented topology optimization methods. Advances in Engineering Software100: 161–175.
39.
LobatoEEchavarrenFRoucoL, et al. (2003) A mixed-integer lp based network topology optimization algorithm for overload alleviation. IEEE Bologna Power Tech Conference Proceedings. Bologna, Italy, 23-26 June 2003, IEEE, Vol. 2, p. 5.
40.
MegaroVZehnderJBächerM, et al. (2017) A computational design tool for compliant mechanisms. ACM Trans. Graph36(4): 82–91.
41.
MurataSYoshidaEKamimuraA, et al. (2002) M-tran: self-reconfigurable modular robotic system. IEEE/ASME Transactions on Mechatronics7(4): 431–441. DOI: 10.1109/TMECH.2002.806220.
42.
NagarajanHLuMWangS, et al. (2019) An adaptive, multivariate partitioning algorithm for global optimization of nonconvex programs. Journal of Global Optimization74(4): 639–675.
43.
NansaiSElaraMRIwaseM (2013) Dynamic analysis and modeling of jansen mechanism. Procedia Engineering64: 1562–1571.
44.
PanZHeLGaoX (2020) Inner-approximation of manipulable and reachable regions using bilinear matrix inequalities, 2020 IEEE/RSJ `stems (IROS), Las Vegas, 27 October 2020, pp. 6585–6592. DOI: 10.1109/IROS45743.2020.9341017.
45.
PanZLiuMGaoX, et al. (2019) Globally optimal joint search of topology and trajectory for planar linkages. In: The international symposium on robotics research (ISRR), North Carolina, 22-May-2019
46.
SaarKAGiardinaFIidaF (2018) Model-free design optimization of a hopping robot and its comparison with a human designer. IEEE Robotics and Automation Letters3(2): 1245–1251.
47.
SokółT (2011) A 99 line code for discretized michell truss optimization written in mathematica. Structural and Multidisciplinary Optimization43(2): 181–190.
48.
SoongRCYanHS (2007) Simultaneous minimization of shaking moment, driving torque, and bearing reactions of complete force balanced linkages. J. Chin. Soc. Mech. Eng28(3): 243–254.
49.
SpielbergAArakiBSungC, et al. (2017) Functional co-optimization of articulated robots. In: IEEE international conference on robotics and automation (ICRA). Singapore, 29 May-3 June 2017, IEEE, pp. 5035–5042
50.
ThomaszewskiBCorosSGaugeD, et al. (2014) Computational design of linkage-based characters. ACM Trans. Graph33(4): 64. 1–64:9.
51.
UmetaniNKoyamaYSchmidtR, et al. (2014) Pteromys. ACM Transactions on Graphics33(4): 1–10.
VielmaJPNemhauserGL (2011) Modeling disjunctive constraints with a logarithmic number of binary variables and constraints. Mathematical Programming128(1–2): 49–72.
54.
WächterA (2009) Short tutorial: getting started with ipopt in 90 minutes. In: NaumannUSchenkOSimonHD, et al. (eds) Combinatorial Scientific Computing, number 09061 in Dagstuhl Seminar Proceedings. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik. Germany. http://drops.dagstuhl.de/opus/volltexte/2009/2089
55.
WhitmanJBhirangiRTraversM, et al. (2020) Modular robot design synthesis with deep reinforcement learning. Proceedings of the AAAI Conference on Artificial Intelligence34: 10418–10425.
56.
ZhuLXuWSnyderJ, et al. (2012) Motion-guided mechanical toy modeling. ACM Trans. Graph31(6): 127. 1–127:10.
Supplementary Material
Please find the following supplemental material available below.
For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.
For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.
