Reinforcement learning for the 2D : packing problem

Abstract

Despite the fact that packing problems have been studied for several decades, there is still room for improvement. Among approximate algorithms, meta-heuristics are currently capable of producing excellent results and are considered the state of the art. However, as with all traditional methods, one limitation of meta-heuristics is that computational time must be spent in order to solve each given problem. The objective of this thesis is then to design a learning agent using machine learning methods. These are algorithms which are capable of learning from data in order to predict solutions for new problems, which will shave off the excess computational time required to run meta-heuristic algorithms. Under the framework of Markov Decision Processes, we formulate the 2D Strip Packing Problem, and use Reinforcement Learning to solve it. An Artificial Neural Network, acting as a component of the Reinforcement Learning agent, is used in order to model the qualitative value of a particular placement of an object. There are three contributions of this thesis. First, we present Reinforcement Learning as a viable method to solve the 2D Strip Packing Problem. Second, we find that Regularity Search procedures are useful in order to improve results in terms of the consistency of acquiring an accurate model. Third, we show that the proposed method is capable of generalizing to new 2D Strip Packing Cases, where either a different set of objects or strip is used. The performance of the learning agent was demonstrated with the MEP (Mechanical,Electrical, and Plumbing) Layout Design application. At the same time, we also attempt to improve the performance of the learning agent by searching for regularities in the model. An artificial neural network trained by embedded regularity search methods are then used to predict solutions for various new 2D Strip Packing Cases.

Date of Award	2015
Original language	English
Awarding Institution	The Hong Kong University of Science and Technology