Automating Rigid Origami Design

Jeremia Geiger, Karolis Martinkus, Oliver Richter, Roger Wattenhofer

Introduction

Rigid origami, a subset of origami where panels remain undeformed during folding, is a critical tool for engineering applications ranging from deployable space structures to minimally invasive medical devices. Despite its utility, designing these patterns is notoriously difficult. The "inverse origami problem"—determining a 2D crease pattern that folds into a specific 3D target—is NP-hard. Traditionally, designers have relied on modifying a few known templates, which limits the diversity of achievable shapes and often results in patterns with excessive degrees of freedom (DOF) that are hard to actuate.

This research introduces a novel framework that transforms rigid origami design into a discrete "game" played on a grid. By leveraging the Principle of Three Units (PTU) to guarantee rigid foldability and a single degree of freedom, the authors automate the discovery of complex, functional origami structures using modern search algorithms.

Methodology: The Rigid Origami Game

The core innovation lies in formulating design as a sequential optimization problem. The process is discretized by representing the unfolded material as a checkerboard grid. An agent "plays" the game by placing vertices on grid intersections and connecting them with edges, effectively building a crease pattern step-by-step.

The Rigid Origami Game pipeline: from target shape to automated search, crease pattern generation, and final folding.

The Principle of Three Units (PTU)

To ensure physical feasibility, the system incorporates the PTU kinematic model. PTU provides a set of geometric rules for expanding crease patterns. If these rules are followed, the resulting pattern is mathematically guaranteed to be rigidly foldable with exactly 1-DOF. By embedding these rules into the "action masking" of the search agent, the system avoids exploring invalid configurations.

The PTU kinematic model defines the relationship between sector angles and fold angles to maintain rigid foldability.

Search Strategies

The authors benchmarked several optimization strategies to navigate the vast search space:

  • Tree Searches: Depth-First (DFTS) and Breadth-First (BFTS) with branch-and-bound pruning for exhaustive exploration of smaller grids.
  • Reinforcement Learning: Proximal Policy Optimization (PPO) and Monte Carlo Tree Search (MCTS) to learn design policies.
  • Evolutionary Search (EVO): A population-based approach where successful design sequences reproduce and mutate.

Results and Functional Design

The framework was evaluated on two primary tasks: Shape Approximation (matching target meshes like cubes or human faces) and Functional Design (optimizing for abstract goals like volume or surface area).

Key Findings

  • Scalability: While tree-based methods are efficient for simple shapes like pyramids and cubes, they struggle as grid sizes increase. For complex tasks, such as approximating a human face mesh, Evolutionary Search (EVO) significantly outperformed RL agents, achieving a higher return by maintaining a diverse population of solutions.
  • Imagination over Imitation: Beyond simple shape matching, the system successfully "imagined" functional objects. It generated a 1-DOF "bucket" that maximizes interior volume and a "table" with four legs and a flat top, all folded from a single flat sheet. This demonstrates the potential for creating practical, everyday objects without needing a pre-existing 3D model.

Limitations and Future Directions

While the grid-based approach simplifies the search, it introduces constraints; vertices cannot be placed between grid points, occasionally leading to small gaps in the folded model. Additionally, the current implementation is restricted to acyclic origami graphs, preventing the discovery of closed-loop patterns.

Future work aims to integrate "collision-aware" action masking to prevent panel intersections during the search process and explore GFlowNets to sample a more diverse array of high-reward origami patterns. By bridging structural engineering with combinatorial optimization, this work paves the way for the automated design of the next generation of deployable systems.

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