{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,8]],"date-time":"2025-12-08T22:35:02Z","timestamp":1765233302144,"version":"3.38.0"},"reference-count":56,"publisher":"SAGE Publications","issue":"4-5","license":[{"start":{"date-parts":[[2023,3,28]],"date-time":"2023-03-28T00:00:00Z","timestamp":1679961600000},"content-version":"vor","delay-in-days":365,"URL":"http:\/\/www.sagepub.com\/licence-information-for-chorus"}],"funder":[{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-18-1-0313"],"award-info":[{"award-number":["W911NF-18-1-0313"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2023,4]]},"abstract":"<jats:p> 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 \u2212 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. <\/jats:p>","DOI":"10.1177\/02783649211069156","type":"journal-article","created":{"date-parts":[[2022,3,28]],"date-time":"2022-03-28T15:27:09Z","timestamp":1648481229000},"page":"176-195","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":8,"title":["Joint search of optimal topology and trajectory for planar linkages"],"prefix":"10.1177","volume":"42","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9348-526X","authenticated-orcid":false,"given":"Zherong","family":"Pan","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Illinois at Urbana-Champaign, Urbana, IL, USA"},{"name":"Lightspeed & Quantum Studio, Tencent America, Bellevue, WA, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3086-315X","authenticated-orcid":false,"given":"Min","family":"Liu","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Electrical & Computer Engineering, University of Maryland at College Park, College Park, MD, USA"}]},{"given":"Xifeng","family":"Gao","sequence":"additional","affiliation":[{"name":"Lightspeed & Quantum Studio, Tencent America, Bellevue, WA, USA"},{"name":"Department of Computer Science, Florida State University, Tallahassee, FL, USA"}]},{"given":"Dinesh","family":"Manocha","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Electrical & Computer Engineering, University of Maryland at College Park, College Park, MD, USA"}]}],"member":"179","published-online":{"date-parts":[[2022,3,28]]},"reference":[{"key":"bibr1-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1145\/2766985"},{"key":"bibr2-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1007\/s12206-018-0103-7"},{"key":"bibr3-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1214\/ss\/1177011077"},{"key":"bibr4-02783649211069156","volume-title":"Introduction to Linear Optimization","volume":"6","author":"Bertsimas D","year":"1997"},{"key":"bibr22-02783649211069156","doi-asserted-by":"crossref","unstructured":"Bixby Bob (2007) The gurobi optimizer. Transp. Research Part B. 41(2): 159\u2013178.","DOI":"10.1016\/j.trb.2006.02.002"},{"key":"bibr5-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1145\/1531326.1531383"},{"key":"bibr6-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1007\/0-387-30065-1_4"},{"key":"bibr7-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1016\/S0094-114X(02)00051-4"},{"key":"bibr8-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1080.0354"},{"key":"bibr9-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461953"},{"key":"bibr10-02783649211069156","unstructured":"Coumans E et al. (2013) Bullet Physics Engine. Erwin Coumans. Open Source Software: http:\/\/bulletphysics.org.2010."},{"key":"bibr11-02783649211069156","unstructured":"Dai H, Izatt G, Tedrake R (2017) Global Inverse Kinematics Via Mixed-Integer Convex Optimization, Puerto Varas, Chile: International Symposium on Robotics Research, pp. 1\u201316."},{"key":"bibr12-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1109\/HUMANOIDS.2014.7041373"},{"key":"bibr13-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1109\/CASE.2011.6042462"},{"key":"bibr14-02783649211069156","first-page":"3","volume":"10","author":"Eggensperger K","year":"2013","journal-title":"NIPS Workshop on Bayesian Optimization in Theory and Practice"},{"key":"bibr15-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1016\/j.mechmachtheory.2008.02.002"},{"key":"bibr16-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-006-0026-1"},{"volume-title":"Rigid Body Dynamics Algorithms","year":"2014","author":"Featherstone R","key":"bibr17-02783649211069156"},{"key":"bibr18-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1115\/1.1425393"},{"key":"bibr19-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1090\/mcom\/3120"},{"key":"bibr20-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1109\/70.56660"},{"key":"bibr21-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1109\/VR.2005.1492754"},{"key":"bibr23-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2018.2830419"},{"key":"bibr24-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918771172"},{"key":"bibr25-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2020.2992983"},{"key":"bibr26-02783649211069156","unstructured":"HEBI (2019) Hebi robotics. http:\/\/www.hebirobotics.com\/"},{"key":"bibr27-02783649211069156","doi-asserted-by":"publisher","DOI":"10.21125\/inted.2016.0579"},{"key":"bibr28-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2019.8794333"},{"key":"bibr29-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1007\/s11081-011-9172-0"},{"key":"bibr30-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009743909765"},{"key":"bibr31-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s1-7.1.213"},{"key":"bibr32-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1145\/545261.545266"},{"key":"bibr33-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-015-0322-3"},{"key":"bibr34-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-09686-5_7"},{"key":"bibr35-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1287\/opre.14.4.699"},{"key":"bibr36-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2019.8793802"},{"key":"bibr37-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1007\/s10288-004-0038-6"},{"key":"bibr38-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1016\/j.advengsoft.2016.07.017"},{"key":"bibr39-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1109\/PTC.2003.1304279"},{"key":"bibr40-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1145\/3072959.3073636"},{"key":"bibr41-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1109\/TMECH.2002.806220"},{"key":"bibr42-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-018-00734-1"},{"key":"bibr43-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1016\/j.proeng.2013.09.238"},{"key":"bibr44-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1109\/IROS45743.2020.9341017"},{"key":"bibr45-02783649211069156","unstructured":"Pan Z, Liu M, Gao X, 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"},{"key":"bibr46-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1109\/LRA.2018.2795646"},{"key":"bibr47-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1007\/s00158-010-0557-z"},{"issue":"3","key":"bibr48-02783649211069156","first-page":"243","volume":"28","author":"Soong RC","year":"2007","journal-title":"J. Chin. Soc. Mech. Eng"},{"key":"bibr49-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2017.7989587"},{"key":"bibr50-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601143"},{"key":"bibr51-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601129"},{"key":"bibr52-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1137\/1038003"},{"key":"bibr53-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-009-0295-4"},{"volume-title":"Combinatorial Scientific Computing, number 09061 in Dagstuhl Seminar Proceedings. Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik","year":"2009","author":"W\u00e4chter A","key":"bibr54-02783649211069156"},{"key":"bibr55-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i06.6611"},{"key":"bibr56-02783649211069156","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366146"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649211069156","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/full-xml\/10.1177\/02783649211069156","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649211069156","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/02783649211069156","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T17:39:37Z","timestamp":1740850777000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/02783649211069156"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,3,28]]},"references-count":56,"journal-issue":{"issue":"4-5","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["10.1177\/02783649211069156"],"URL":"https:\/\/doi.org\/10.1177\/02783649211069156","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"type":"print","value":"0278-3649"},{"type":"electronic","value":"1741-3176"}],"subject":[],"published":{"date-parts":[[2022,3,28]]}}}