PPO Algorithm Cracks the Moving Sofa Problem, Reconstructing the Classic Gerver Sofa

When Reinforcement Learning Meets a Classic Math Problem

The moving sofa problem is a classic geometric optimization problem: how can a sofa-shaped object turn a corner in a right-angled hallway? This seemingly simple problem has puzzled mathematicians for decades, and its optimal solution is known as the Gerver sofa. Recently, a developer without a deep mathematical background used the PPO (Proximal Policy Optimization) algorithm to reconstruct an approximate shape of the Gerver sofa through reinforcement learning, demonstrating AI's potential for solving complex mathematical problems.

The Moving Sofa Problem: A Geometric Optimization Challenge

The moving sofa problem was first posed by Leo Moser in 1966: in a right-angled hallway of width 1, what is the maximum area of a sofa that can be maneuvered around the corner? In 1968, John Hammersley proposed a similar shape with an area of π/2 + 2/π ≈ 2.2074. In 1992, Joseph Gerver constructed a better shape with an area of approximately 2.2195 and proved its optimality. However, Gerver's proof relies on complex analysis, and the shape is defined piecewise.

Traditionally, solving such problems requires deep mathematical analysis and constructive proofs. But this developer took a different approach, using reinforcement learning to explore the space of sofa shapes.

Gerver's optimality proof is not a simple geometric construction but is based on a meticulous analysis of the contact-point constraints during the sofa's motion. Gerver parameterized the sofa shape as a series of curve segments and used variational methods and optimal control theory to derive boundary conditions that satisfy the feasibility of turning, ultimately proving that the area upper bound of his construction cannot be exceeded. Notably, this proof remains the only widely accepted rigorous optimality argument for this problem, but its complexity also means it is difficult to generalize to three dimensions or more complex hallway geometries. The reinforcement learning approach bypasses this analytical difficulty and directly searches in a high-dimensional shape space, but at the cost of losing the rigor of a proof.

Training Sofa Shapes with PPO

The project uses the PPO algorithm, a policy gradient method widely used in reinforcement learning. The developer modeled the problem as a task where an agent controls a sofa moving through a hallway: the sofa is defined by a set of points, and the agent learns to adjust the positions of these points so that the sofa can pass the corner while maximizing its area. During training, the agent optimizes its policy through trial and error and reward signals (such as receiving a positive reward for successfully passing the corner).

After training, PPO is able to generate a shape approximating the Gerver sofa, with an area close to the theoretical optimum. This shows that reinforcement learning can discover complex geometric shapes without prior mathematical knowledge.

PPO (Proximal Policy Optimization) is a policy gradient reinforcement learning algorithm proposed by OpenAI in 2017. Its core idea is to limit the difference between the new and old policies at each update, preventing training collapse due to excessively large step sizes. It constrains the magnitude of policy updates by clipping the importance sampling ratio, striking a balance between sample efficiency and training stability. Because of its simple implementation and robust hyperparameter tuning, PPO has become the default baseline algorithm in fields such as continuous control and game AI. In this project, the agent needs to output continuous actions (adjusting the coordinates of the sofa shape points), and PPO's support for continuous action spaces fits this requirement perfectly.

Significance and Limitations

The significance of this experiment lies in demonstrating the potential of reinforcement learning as a tool for mathematical exploration. For problems that are difficult to solve analytically, RL can provide approximate solutions through numerical optimization. However, this method also has limitations: the generated shape is approximate, and the training process may be unstable; moreover, RL cannot provide mathematical proofs and can only offer candidate solutions.

Nevertheless, this experiment provides an interesting case study for AI-assisted mathematical discovery. As algorithms and computational resources advance, reinforcement learning may play a role in more mathematical challenges.

Symbolic regression is a class of methods that automatically discover mathematical expressions from data, with typical tools including genetic programming and sparse regression (such as SINDy). Unlike black-box fitting with neural networks, symbolic regression outputs explicit analytical formulas, making them more interpretable and easier for mathematicians to verify or further derive. The idea of combining RL with symbolic regression is: first use RL to search for high-reward shapes or policies, then use symbolic regression to infer possible analytical relationships from numerical trajectories, thereby turning "numerical discovery" into a starting point for "mathematical conjecture." This paradigm has seen preliminary attempts in areas such as the discovery of physical laws, but its application to geometric optimization problems is still in the exploratory stage.

Future Outlook

The developer suggests that future work could try more complex reward functions and network architectures to improve the accuracy of the solution. At the same time, combining RL with techniques such as symbolic regression may help discover new mathematical structures. For mathematical researchers, RL can serve as a heuristic tool to assist in conjecture and verification.

This experiment also reminds us that AI is not only an engineering tool but can also be a partner in scientific exploration.