Motion planning and control of a planar polygonal linkage

For a polygonal linkage, we produce a fast navigation algorithm on its configuration space. The basic idea is to approximate the configuration space by the vertex-edge graph of its cell decomposition discovered by the first author. The algorithm has three aspects: (1) the number of navigation steps does not exceed 15 (independent of the linkage), (2) each step is a disguised flex of a quadrilateral from one triangular configuration to another, which is a well understood type of flex, and (3) each step can be performed explicitly by adding some extra bars and obtaining a mechanism with one degree of freedom.