  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, \refined{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 require 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.
