An Encoder-Decoder Approach for Packing Circles
Akshay Kiran Jose Gangadhar Karevvanavar Rajshekhar V Bhat
The problem of packing smaller objects within a larger object has been of
interest since decades. In these problems, in addition to the requirement that
the smaller objects must lie completely inside the larger objects, they are
expected to not overlap or have minimum overlap with each other. Due to this,
the problem of packing turns out to be a non-convex problem, obtaining whose
optimal solution is challenging. As such, several heuristic approaches have
been used for obtaining sub-optimal solutions in general, and provably optimal
solutions for some special instances. In this paper, we propose a novel
encoder-decoder architecture consisting of an encoder block, a perturbation
block and a decoder block, for packing identical circles within a larger
circle. In our approach, the encoder takes the index of a circle to be packed
as an input and outputs its center through a normalization layer, the
perturbation layer adds controlled perturbations to the center, ensuring that
it does not deviate beyond the radius of the smaller circle to be packed, and
the decoder takes the perturbed center as input and estimates the index of the
intended circle for packing. We parameterize the encoder and decoder by a
neural network and optimize it to reduce an error between the decoder's
estimated index and the actual index of the circle provided as input to the
encoder. The proposed approach can be generalized to pack objects of higher
dimensions and different shapes by carefully choosing normalization and
perturbation layers. The approach gives a sub-optimal solution and is able to
pack smaller objects within a larger object with competitive performance with
respect to classical methods.