Automation of triangle straightedge-and-compass constructions using automated planning

Abstract

In this paper, we consider automated solving of triangle straightedge-and-compass construction problems by reducing them to automated planning. We consider the problems from the Wernick’s list, where each problem assumes that locations of three significant points of a triangle are given, and the goal is to construct all three vertices of the triangle. We develop two different models of the corresponding planning problem. In the first model, the planning problem is described using the PDDL language, which is suitable for solving with dedicated automated planners. The second model assumes that the planning problem is first expressed as a finite-domain constraint satisfaction problem, and then encoded in the MiniZinc language. Such model is suitable for solving with constraint solvers. In both cases, we employ existing artificial intelligence tools in search for a solution of our construction problem. The main benefit of using the existing tools for such purpose, instead of developing dedicated tools, is that we can rely on the efficient search that is already implemented within the tool, enabling us to focus on geometric aspects of the problem. We evaluate our approach on 74 solvable problems from the Wernick’s list, and compare it to the dedicated triangle construction solver ArgoTriCS. The results show that our approach tends to be superior to dedicated tools in terms of efficiency, while it requires much less effort to implement. Also, we are often able to find shorter construction plans, thanks to the optimization capabilities offered by the modern planners and constraint solvers. The presented approach is only a search method and does not address proving the correctness of the obtained constructions and discussing when solutions exist, leaving these tasks to other tools. Although the paper focuses on a specific set of construction problems, the approach can be generalized to other classes of problems, which will be explored in future work.