Finding an optimal LEGO® brick layout of voxelized 3D object using a genetic algorithm

Abstract

In this paper, we propose a genetic algorithm for a LEGO® brick layout problem. The task is to build a given 3D object with LEGO® bricks. A brick layout is modeled as a solution to a combinatorial optimization problem, through intermediate voxelization, which tries to maximize the connectivity and then minimize the number of used bricks. We attack the problem in the context of genetic search. The proposed randomized greedy algorithm produces initial solutions, and the solutions are effectively improved by an evolutionary process. New domain-specific methods are proposed as well, which include a random boundary mutation and a thickening approach. We tested our algorithm on various objects collected from the web. Experimental results showed that the algorithm produces efficient, and mostly optimal solutions for benchmark models. Unlike some previous works, our algorithm is not limited to assemble few specific objects, but it can deal with diverse kind of objects. To the best of our knowledge, this is the most extensive empirical study on the problem. © 2015 ACM.