Problem Solution
Progress to Date
Expected Results
Images
References
Cargo loading is generally considered a fairly simple problem, and has been solved in some form by numerous programs in the past. It consists of prioritizing packages and perhaps accounting for balance. We aim to increase the complexity of the project by minimizing the free space in the cargo hold so as to accommodate the most packages and to prevent packages from shifting during motion. These features we feel are important to accurately modeling a cargo hold and improving transportation safety.
Problem Solution:
In optimizing a cargo hold, it becomes necessary to fit as many packages as possible into a finite space and to carry as much as possible. This necessity constitutes an instance of the "knapsack" problem, since we aim to maximize masses while limiting volumes. Since no known polynomial time algorithm exists for solving such a problem (Pisinger 9), we intend to use a dynamic programming approach. Namely, our approach will use a neural network to optimize for the desirable criteria.
Initially, we will program a solution for the simplest relevant problem. Our packages will all be of uniform size, possess randomly generated weights, and be loaded by one of several methods. These loading methods will then be compared to determine how to optimize speed and carrying capacity. We aim to eventually write a program capable of determining the best way to load any given set of packages. Time allowing, we will expand into packages of various sizes and into three-dimensional solutions.
The type of artificial neural network we intend to use is the self-organizing map, developed by professor Teuvo Kohonen. Self-organizing maps (SOMs) are used to cause a computer to respond in a similar fashion to similar input. This is appropriate for our purposes, since we hope to eventually provide our program with any set of packages and receive output describing the loading method that is best for dealing with such a set.
SOMs begin by randomly generating values for each node in an array. It then compares the characteristics of input nodes iteratively to each output node, determines which node is closest (a node referred to as the Best Matching Unit, or BMU) and changes the characteristics of each output node by the following formula:
where Wv(t) is the vector representation of the output node, θ(v) is a function based on the distance from the BMU within which it is appropriate to update the node, α(t) is a learning coefficient that decreases over time, and D(t) is the input vector ("Self-organizing map"). We will use SOMs to respond to sets of packages with the best combination of one of several loading methods, one focusing on balance, one focusing on speed, and potentially other methods.
Progress to Date:
We have made classes to handle uniform 2D packages and a simple system for handling those packages. Each package has mass, size, and center of mass. We have also created simple classes to handle non-uniform 2D and 3D packages when we begin using more complex packages. In addition to mass, size, and center of mass, these also have values for determining the squarest side of a package, and the cubicity of a package. We originally planned to use the closeness of two-dimensional packages to squares (their "squareness") and the closeness of three-dimensional packages to cubes (their "cubicity") to prioritize the packages and load them with a single method, but these characteristics will most likely still prove useful in loading with other methods.
Our current method involves using a neural net or SOM and since we have no past experience with either of those, we have focused mainly on constructing a simple SOM in order to learn how to construct and use SOMs. This SOM's nodes are pixels with three characteristics each: red, green, and blue values. Favorable output, then, groups pixels of the same color with one another, creating patches of the same color pixels on the screen. We have tended to refer to this program as the "RGB SOM." While making the SOM we made a few mistakes which we would not have noticed as quickly if we had not used an RGB SOM. Our first mistake was in finding the BMU. Our method initially did not select only a certain number of pixels around the BMU for weighting toward the input vector and was also flawed because it did not compare all aspects of the input to a given pixel simultaneously and found several BMUs for a single input. This SOM also gave us a chance to experiment withy different Learning Coefficients. We initially used a function for the Learning Coefficient based on a 1/x translated left along the x-axis so that it started at 1. We found that it decreased too rapidly, so we began using a linear function with a negative slope. The linear function would eventually become negative and cause the SOM to started de-organizing. After that failed, we turned once again to 1/x. This time we applied more translations to it so that it starts at 1 and has an asymptote at .5 instead of 0. Our method for finding pixels around a BMU uses variable called "okToUpdate." Originally, we gave this variable a value of 1 or 0 and multiplied it by the other values in the update function. That gave us a circle changed completely to the input vector. By treating the variable as a layer like the alpha layer or selection layer which allows for a pixel to be partially selected or transparent we are able to apply the changes less to variable farther from the BMU. Our current function for setting okToUpdate using the preset update radius, "UPDATE_DISTANCE" and the distance of the pixel form the BMU, "dist" to find the "percent error" or the pixel given by (UPDATE_DISTANCE-dist)/UPDATE_DISTANCE.
Expected Results:
We hope to eventually write a program capable of analyzing sets of packages based on number, volume, and mass. In SOM format, such a program would allow the user to find an effective solution tailored to each set of input packages. This ultimate solution would also require that the computer be capable of combining elements from various loading procedures to best accommodate for a set of packages.
In the following images, the title bars read "SDL_app." This indicates that the graphics in our application are generated by Simple DirectMedia Layer, a graphics library.
3-1. A random map before organization.
3-2. A map with organization using the
Randomization seed = 0
Current hyperbolic function, (1/(x+2))+.5.
Randomization seed = 42
Number of iterations = 1008
Inputs = Red, Green, Blue
3-3. The same type of map as in 3-2 with different inputs.
Randomization seed = 42
Number of iterations = 100
Input 0 = 128,128,000
Input 1 = 255,000,128
Input 2 = 000,000,000
3-4. Same map as in 3-2 with more inputs.
Randomization seed = 42
Number of iterations = 100
Inputs = Black ,Red, Blue, Green, White
3-5. A map with organization using a hyperbolic learning coeffienct given by 1/(x-1).
The numbers under the window give the number of iterations.
Randomization seed = 0.
Works Cited
Pisinger, David. Algorithms for Knapsack Problems. Copenhagen, Denmark:Dept. of Computer
Science, University of Copenhagen, 1995.
"Self-organizing map." Wikipedia, the free encyclopedia. 17 November 2006. Wikimedia Foundation,
Inc. 9 December 2006.
Team Members:
Sponsoring Teachers:
Jennifer Keller
Stephen Schum