Self‐folding is a powerful approach to fabricate materials with complex 3D forms and advanced properties using planar patterning steps, but suffers from intrinsic limitations in robustness due to the highly bifurcated nature of configuration space around the flat state. Here, a simple mechanism is introduced to achieve robust self‐folding of microscale origami by separating actuation into two discrete steps using different thermally responsive hydrogels. First, the vertices are pre‐biased to move in the desired direction from the flat state by selectively swelling one of the two hydrogels at high temperature. Subsequently, the creases are folded toward their target angles by activating swelling of the second hydrogel upon cooling to room temperature. Since each vertex can be individually programmed to move upward or downward, it is possible to robustly select the desired branch even in multi‐vertex structures with reasonably high complexity. This strategy provides key new principles for designing shaping‐morphing materials that avoid undesired distractor states, expanding their potential applications in areas such as soft robotics, sensors, mechanical metamaterials, and deployable devices.
Rigid foldability is NPhard
In this paper, we show that the rigidfoldability of a given crease pattern using all creases is weakly NPhard by a reduction from the partition problem, and that rigidfoldability with optional creases is NPhard by a reduction from the 1in3 SAT problem. Unlike flatfoldabilty of origami or flexibility of other kinematic linkages, whose complexity originates in the complexity of the layer ordering and possible selfintersection of the material, rigid foldabilltiy from a planar state is hard even though there is no potential selfintersection. In fact, the complexity comes from the combinatorial behavior of the different possible rigid folding configurations at each vertex. The results underpin the fact that it is harder to fold from an unfolded sheet of paper than to unfold a folded state back to a plane, frequently encountered problem when realizing foldingbased systems such as selffolding matters and reconfigurable robots.
more »
« less
 NSFPAR ID:
 10209599
 Date Published:
 Journal Name:
 Journal of computational geometry
 Volume:
 11
 Issue:
 1
 ISSN:
 1920180X
 Page Range / eLocation ID:
 93–124
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

Abstract 
Rigid origami, with applications ranging from nanorobots to unfolding solar sails in space, describes when a material is folded along straight crease line segments while keeping the regions between the creases planar. Prior work has found explicit equations for the folding angles of a flatfoldable degree4 origami vertex and some cases of degree6 vertices. We extend this work to generalized symmetries of the degree6 vertex where all sector angles equal 60 ∘ . We enumerate the different viable rigid folding modes of these degree6 crease patterns and then use secondorder Taylor expansions and prior rigid folding techniques to find algebraic folding angle relationships between the creases. This allows us to explicitly compute the configuration space of these degree6 vertices, and in the process we uncover new explanations for the effectiveness of Weierstrass substitutions in modelling rigid origami. These results expand the toolbox of rigid origami mechanisms that engineers and materials scientists may use in origamiinspired designs.more » « less

Bojanczy, Mikolaj ; Chekuri, Chandra (Ed.)Oneway functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the averagecase hardness of computing timebounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence for the averagecase hardness of some natural NPcomplete problem. In this paper, we make progress on this question by studying a conditional variant of the Minimum KTcomplexity Problem (MKTP), which we call McKTP, as follows. 1) First, we prove that if McKTP is averagecase hard on a polynomial fraction of its instances, then there exist OWFs. 2) Then, we observe that McKTP is NPcomplete under polynomialtime randomized reductions. 3) Finally, we prove that the existence of OWFs implies the nontrivial averagecase hardness of McKTP. Thus the existence of OWFs is inextricably linked to the averagecase hardness of this NPcomplete problem. In fact, building on recentlyannounced results of Ren and Santhanam [Rahul Ilango et al., 2021], we show that McKTP is hardonaverage if and only if there are logspacecomputable OWFs.more » « less

null (Ed.)Given a locally flatfoldable origami crease pattern $G=(V,E)$ (a straightline drawing of a planar graph on the plane) with a mountainvalley (MV) assignment $\mu:E\to\{1,1\}$ indicating which creases in $E$ bend convexly (mountain) or concavely (valley), we may \emph{flip} a face $F$ of $G$ to create a new MV assignment $\mu_F$ which equals $\mu$ except for all creases $e$ bordering $F$, where we have $\mu_F(e)=\mu(e)$. In this paper we explore the configuration space of face flips that preserve local flatfoldability of the MV assignment for a variety of crease patterns $G$ that are tilings of the plane. We prove examples where $\mu_F$ results in a MV assignment that is either never, sometimes, or always locally flatfoldable, for various choices of $F$. We also consider the problem of finding, given two locally flatfoldable MV assignments $\mu_1$ and $\mu_2$ of a given crease pattern $G$, a minimal sequence of face flips to turn $\mu_1$ into $\mu_2$. We find polynomialtime algorithms for this in the cases where $G$ is either a square grid or the Miuraori, and show that this problem is NPcomplete in the case where $G$ is the triangle lattice.more » « less

This work presents innovative origami optimization methods for the design of unit cells for complex origami tessellations that can be utilized for the design of deployable structures. The design method used to create origami tiles utilizes the principles of discrete topology optimization for ground structures applied to origami crease patterns. The initial design space shows all possible creases and is given the desired input and output forces. Taking into account foldability constraints derived from Maekawa's and Kawasaki's theorems, the algorithm designates creases as active or passive. Geometric constraints are defined from the target 3D object. The periodic reproduction of this unit cell allows us to create tessellations that are used in the creation of deployable shelters. Design requirements for structurally sound tessellations are discussed and used to evaluate the effectiveness of our results. Future work includes the applications of unit cells and tessellation design for origami inspired mechanisms. Special focus will be given to selfdeployable structures, including shelters for natural disasters.more » « less