# Optimization Algorithm for Cutting Masonry with a Roboti Saw
## 2 Materials and Methods  
Two main objectives were addressed in this study. The first objective is to limit the wear of a cutting saw used for the splitting of brick blocks. The second objective is to minimize the number of brick blocks for the given geometry of the walls to be fully filled. The working principle of the mathematical model for the optimal design of masonry cuts is schematically illustrated by a flow chart, which can be seen in Figure 1. The diagram is divided into segments of inputs and outputs of the mathematical computational model or a digital bricklaying plan [19]. The first input involves a digital bricklaying plan of load-bearing and non-load-bearing wall blocks for different BIM objects. The plan is created with special software for bricklaying robots [19] after converting BIM objects [25] and their following export to a standard IFC format [26]. The second input is a database of masonry elements. The database provides brick specifications, such as the size and physical and mathematical parameters of masonry elements, as provided by manufacturers of building masonry systems. The digital laying plan of a building depends on the choice of specific masonry elements creating load-bearing and non-load-bearing walls. The choice of masonry can be made in the software for robotic bricklaying [19], which contains an extensive database of masonry systems and their relevant technical data and properties. If the building or facility is not modelled in a basic building module [26; 27], a certain number of cuts needs to be processed according to the parameters of the third input into the model--the robotic saw module. The mathematical core of the model is based on an algorithm, which is described in detail in the following section. The output of the model contains the lists of cuts, optimal compositions of cut assemblies, the number of masonry elements, waste pieces and the  
Figure 1: Flow chart of the mathematical model for the optimal design of masonry cuts. distribution of elements on a pallet for bricklaying processes (the mask on the pallet). After the cutting steps are implemented according to the output of the algorithm, the masonry elements are stacked in a specific order and at certain positions by the robotic bricklaying assembly needed for further technological bricklaying processes. One can define a mathematical problem as an optimization problem of finding the best solution from all feasible solutions. To optimize the cutting, an optimization problem was solved with the aim of minimizing the total amount of masonry elements and reducing CDW. The number of cuts should also be minimized to reduce the operation time of the robotic saw and to limit the wear and tear of its cutting plate. The optimization problem can be converted to the classical problem of packing algorithms (bin packing problem) [27; 28]. The class of packing problems in a container is described as an NP-hard (nondeterministic polynomial time/NP-hard) combinatorics task [29]. A number of mathematical algorithms exist that are capable of approximately solving this problem for various application methods, e.g., 2D packing, line packing, packing by weight and packing by value. The whole problem is focused on packing certain objects into containers of the same size in such a way that the total number of containers is minimized. The task is NP-hard (strong NP-completeness) [29], and the use of an exact solution using a search algorithm (brute force solution) is possible only for a small number of objects. The time requirement grows exponentially with the use of limiting conditions (e.g., the maximum number of objects in a container) or even factorially. Usually, approximate heuristic algorithms are applied to solve such tasks, e.g., Next-Fit (NF), First-Fit (FF), Best-Fit (BF), First-Fit Decreasing (FFD), Harmonic-k, etc. [30], and each algorithm has its own estimate of solution accuracy and time requirements. The specifics of employing a robotic saw to cut masonry elements assume certain simplifications and several special conditions.