Solving Tetris-like Puzzles with Informed Search and Machine Learning

Abstract: Assembling different kinds of items, everything from furniture to hobby models, takes a certain process to complete and this process can vary in complexity. An interesting aspect of this process is what components are available during assembly. The optimal scenario would be to have all required components available but sometimes that might not be the case. For a computer, this problem can be difficult to solve and requires specific environments to complete an assembly task. In this thesis work, block puzzles with various blueprints were used to complete assemblies with two different lists of components; one whole set of correct components and one with mixed that may or may not work for a blueprint. Three different methods were used to conduct the assemblies, one random based method, one that used the informed search method iterative deepening A' and one reinforcement learning method that used dueling deep Q-networks. The assembly time and accuracy between a completed configuration and the blueprint were measured for each method, where the informed search performed best in terms of accuracy but had a long assembly time. The reinforcement learning method did not perform well in terms of accu-racy between blueprint and configuration, but had fast assembly time, and in its current state would not be suitable to use to solve the given problem.