Automating Rigid Origami Design

Jeremia Geiger, Karolis Martinkus, Oliver Richter, Roger Wattenhofer

TL;DR

This paper introduces a novel framework that transforms rigid origami design into a discrete, single-player board game. By leveraging the Principle of Three Units (PTU) kinematic model, the authors enable AI agents—ranging from reinforcement learning to evolutionary algorithms—to automatically discover brand-new, single-degree-of-freedom crease patterns that can approximate complex 3D shapes or satisfy abstract functional goals like folding into a usable chair or bucket.

What Problem Does This Paper Address?

Origami has evolved from an ancient art form into a vital engineering tool for deployable structures, aerospace components, and robotics. A particularly useful variant is rigid origami, where the material consists of rigid panels connected by hinges that fold without any bending or deformation. Ideally, these structures should possess a single degree of freedom (1-DOF), meaning the entire structure can be opened or closed by actuating just one single hinge.

However, finding a crease pattern that folds into a specific target 3D shape—known as the inverse origami problem—is notoriously difficult and computationally NP-hard. Existing automated design tools either generate patterns with too many degrees of freedom (making them impractical to actuate) or rely on minor variations of well-known, pre-existing tessellations (like the Miura Ori). This severely restricts creative freedom and limits the discovery of entirely novel, application-specific structures.

Methods

The authors reframe rigid origami design as a discrete optimization problem structured as a single-player token-placement game on a grid board.

Figure 1: Overview of our approach. Given a target shape or more generally a target objective function such as desired volume (a), we formulate the inverse origami problem as a token place game on a checkerboard (b). An agent can iteratively interact with this game formulation and improve its policy with respect to the objective. The best rollout can be converted into a crease pattern (c), which can be used to rigidly fold a flat sheet into the corresponding shape that maximizes the objective (d).

Key components of their approach include:

  • The Origami Game: The board represents a flat sheet of paper. An AI agent sequentially places vertices and connects directed crease lines on a fixed-size grid to build an origami graph.
  • PTU Kinematic Model: To simulate folding efficiently without expensive matrix inversions, the authors utilize the Principle of Three Units (PTU). This rule-based method sequentially solves for all folding angles using fast forward kinematics, assuming an acyclic graph structure.
  • Action Masking for Constraints: Rigid origami is highly constrained; panels cannot intersect, and specific geometric rules (like the triangle inequality for spherical triangles) must hold true. The environment uses strict action masking to prevent the agent from making illegal moves that would result in un-foldable patterns.
Figure 2: A degree 4 vertex with one incoming and 3 outgoing edges. Indicated are the sector angles α, the folding (dihedral) an- gles ρ and the unit angles U1, U2 and U3. The illustrations on the right show the effect of the rigid body mode M ∈{−1, 1} for the same input angle ρ0.

The authors benchmarked several search methods within this game environment: Random Search (RDM), Depth-First Tree Search (DFTS), Breadth-First Tree Search (BFTS), Monte Carlo Tree Search (MCTS), Proximal Policy Optimization (PPO), and an Evolutionary Algorithm (EVO).

Datasets

Because this is a procedural design task, the paper does not use standard external datasets. Instead, the authors evaluated their framework on two distinct task categories:

  1. Shape Approximation Targets: Four 3D meshes of increasing complexity: a Pyramid, a Cube, a non-developable Bowl, and a highly complex Human Face mesh (adapted from Apple ARKit).
  2. Abstract Functional Targets: Four custom-designed reward functions representing everyday objects: a Bucket (maximizing volume), a Shelf (maximizing parallel horizontal planes), a Table (positioning four legs on the ground plane), and a Chair (requiring a backrest and stable legs).

Key Insights and Ideas

  • The Ruggedness of Origami Space: The rigid origami design space is plagued by numerous, sharply isolated local optima. A single misplaced crease can render an entire pattern un-foldable, making it an exceptionally challenging environment for standard policy-based reinforcement learning.
  • Pruning via Monotonicity: Tree-based searches (DFTS and BFTS) perform remarkably well on moderately sized boards because the shape-matching objective can be broken down into a monotonically decreasing component. This allows the algorithms to aggressively prune unpromising design branches early on.
  • Evolution Scales Best to Complexity: For highly complex tasks like the human face, where the search space explodes, the Evolutionary Algorithm (EVO) vastly outperformed tree searches and RL. Maintaining a diverse population of candidate designs allows EVO to effectively balance exploration and exploitation without getting prematurely trapped in local minima.

Key Results

The performance of each search method was quantified by the final reward (higher/closer to zero is better), measuring how closely the folded pattern matched the target objective.

  • Simple Shapes: All algorithms successfully solved the Pyramid task. For the Cube, tree-search methods (DFTS and BFTS) found the absolute optimal pattern (achieving a top score of $-0.07$).
  • Complex Shapes: On the highly intricate Human Face target, the Evolutionary Algorithm achieved the best score ($-3.49$), significantly outperforming DFTS ($-4.38$) and standard PPO reinforcement learning ($-5.70$).
  • Generative Imagination: When given abstract functional rewards rather than explicit target shapes, the evolutionary agent successfully "imagined" entirely new, functional, 1-DOF folding designs for chairs, tables, and buckets from scratch.

Limitations and Future Work

While powerful, the current framework operates under a few key constraints:

  • Acyclic Restriction: The underlying PTU kinematic model is restricted to acyclic origami graphs, meaning it cannot currently design patterns with closed internal loops of faces.
  • Discretization Artifacts: Relying on a rigid grid board can introduce minor discretization errors, such as small gaps at the apex of folded shapes.
  • Scalability: As the grid size increases to accommodate finer details, the search space grows exponentially.

To overcome these limitations, the authors suggest that future work should explore more advanced generative optimization paradigms, such as GFlowNets, to better sample diverse and highly complex valid crease patterns.

Summary updated

Abstract

Rigid origami has shown potential in large diversity of practical applications. However, current rigid origami crease pattern design mostly relies on known tessellations. This strongly limits the diversity and novelty of patterns that can be created. In this work, we build upon the recently developed principle of three units method to formulate rigid origami design as a discrete optimization problem, the rigid origami game. Our implementation allows for a simple definition of diverse objectives and thereby expands the potential of rigid origami further to optimized, application-specific crease patterns. We showcase the flexibility of our formulation through use of a diverse set of search methods in several illustrative case studies. We are not only able to construct various patterns that approximate given target shapes, but to also specify abstract, function-based rewards which result in novel, foldable and functional designs for everyday objects.
BibTeX
@inproceedings{geiger2023automating,
  author = {Jeremia Geiger and Karolis Martinkus and Oliver Richter and Roger Wattenhofer},
  title = {{Automating Rigid Origami Design}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/645},
}
Figure