Daniela Steidl, Martin Schuster, Saul Reynolds-Haertle, Richard Bormann

## Project Abstract:

In our final project we intend to find a heuristic for the mixed palletizing problem with the optimization criteria stability and density. This problem is about stacking as many rigid parcels of different sizes as possible onto a pallet such that the pile is stable. As a first approach we have planned to solve the problem for five different box sizes, which may have arbitrary continuous lenghts, packing only one pallet at a time and considering weight constraints, too, which may restrict which sort of and how many parcels can be stacked on top of each other. We chose the scenario of a supermarket distribution center where we have complete knowledge about the desired amounts of each kind of packet. The goal is to receive a sequence of which parcel has to be put where and in which order to yield a stable but high and densely packed stack. The plan should be visualized by the USARSim simulator since we want to participate in the ICRA robot challenge.

## Related Work:

*What has been done previously? Please download related papers, upload them somewhere and make them clickable. For each paper write a brief description of how it relates to your work. Make a list as follows:*

- J. Terno, G. Scheithauer, U. Sommerwei and J. Riehme "An efficient approach for the multi-pallet loading problem" European Journal of Operational Research 123 (2000) 372-381 - This paper describes an approach to solve the multi-pallet loading problem that uses layer-wise loading with an optimal two-dimensional loading strategy for each layer. A main aspect of the algorithm is the calculation of an upper and lower bound for the number of pallets needed. According to these values, the problem is split up into subconsignements.

- E. Bischoff "Stability aspects of pallet loading" OR Spectrum Vol. 13 No. 4 December, Springer-Verlag, 1991 (use the password rip09 for the zip file) - This paper gives a short review on the Bischoff-Dowsland method, which is able to stack homogeneous pallets for a range of box sizes and pallet sizes, and extends this algorithm by a pattern modification and some parcel adjustments in order to yield a stable packed pallet. The utilized stability definition is the one of Carpenter and Dowsland, which has the three criterions supportive, base contact and non-guillotine. On the one hand, we aspire to define our stability measure on the same basis as much as possible, on the other hand this paper describes an idea how to put parcels onto a pallet as long as they do not differ (which may become a subtask of our algorithm).

- E. Bischoff, F. Janetz and M. Ratcliff "Loading pallets with non-identical items" European Journal of Operational Research 84 (1995) 681-692 - Describes a heuristic for the "Distributor's Pallet Packing Problem". The loading pattern is constructed bottom up layer-wise having two different box types at a time. The choices are goverend by the resulting utilisation of the loading surface onto which a layer is to be placed.

- C. Wurll "'Pick From Belt' - Automated Order Picking with Industrial Robots" Proceedings of the 33rd International Symposium of Robotics, Stockholm, 2002 (use the password rip09 for the zip file) - Describes a "pick from belt" problem in a grocery distribution center case study. The robot has to pick one article out of 6 accumulated and may stack it on one of two available pallets. The article describes the whole system from conveyor over the vision system to the robot arm. Unfortunately, no details about the algorithms are revealed (industry cooperation), however, some valuable statistics can be drawn from this paper for comparison.

- C. Wurll, B. Schnoor "Robot Picking System (RPS) – Automated Order Picking With Industrial Robots" IASTED International Conference on Robotics and Applications, Salzburg, 2003 (use the password rip09 for the zip file) - Very similar to the above mentioned paper, but a little more detailed. It furthermore describes a whole depalletizing and mixed palletizing installation.

- W. Kocjan, K. Holmström "Generating Stable Loading Patterns for Pallet Loading Problems" The Fifth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems CPAIOR08, Paris, 2008 - Describes an integer programming model which calculates the space optimal loading pattern for homogeneous pallets with respect to the stability. This solution is not a heuristic and may help us with finding the right access to our problem concerning state space definition and gaining stability. It also may be helpful for finding solutions if complete layers can be stacked with equal-sized boxes.

- A. Hoene "Palletizing Software: PalletMix" 40th International Symposium on Robotics, Barcelona, 2009 - Since papers on this topic are quite rare we added this talk on KUKA's palletizing software PalletMix which puts emphasis on the challenges of mixed palletizing and their solutions. Some guidelines for a good planning are given as well as some implementation details.

## Proposed Work:

*In as much detail as possible, describe your proposed work. Separate this description into the planning (autonomous decision making) challenges and others. Make sure to include both the problems you will be solving and the methods you expect to use to solve those problems.*

Design and implement a planner for the mixed palletizing problem as described above.

**Planning Challenges***What about your problem makes it interesting from the perspective of planning. What challenges will you encounter that basic planners / motion planners / controllers do not address.*

It's a classic logistics planning problem. The exact optimal solution is NP-hard, therefore we try to find an approximate solution optimized towards density and stability of the resulting box stack and time-efficiency of the planner. So our main challenge is designing a good planning algorithm and heuristic for these problems:

- Optimizing density means minimizing the amout of air in the (bounding-box) volume that limits the pallet space, that is, pack as few air as possible.
- Optimizing stability is concerend with the stack of boxes being in a stable configuration that prevents items from falling off or the stack from tipping over.
- Planner efficiency means mainly the runtime to create such a plan, it should be at maximum in the dimension of xx minutes per pallet.

A planning challenge is to find a good state space representation as a naive one would have very high dimensionality (number of items * their parameters, some continous). The problem also has a lot of complex constraints like a weight distribution that provides stabilty and doesn't squash the items further down, that is, all items will have constraints on what weight can be put on top of them.

Most state-of-the-art-soltions work layer-wise and are often not able to provide really satisfying solutions for this problem.

You may want to watch some videos showing some mixed palletizing robots in action. We have collected the following videos:

http://www.youtube.com/watch?v=1khQAnGDCSo

http://www.youtube.com/watch?v=CAv3rMxZDkc

Our project is not concerned with the motion planner of the gripper as this is already provided to us in a simulation environment.

Another secondary challenge will be the integration of our planner in this simulation framework.

**Proposed Solutions***How will your work address these challenges. Be as specific as possible*

- Design an adequate definition of the search space and the constraints within. Since this is one of our crucial decisions, we have agreed to discuss this choice after having studied the literature on Wednesday, Oct. 21.
- Find a good measure for our main optimization goals: For minimizing open space in the pallet a simple and established (found in all our papers) measure is the percentage of used room by boxes inside the cuboid above the pallet. An accepted measure for stability is stated in Bischoff-1991 and was formulated by Carpenter and Dowsland:
- Supportive Criterion: Each parcel lies on top of at least two other parcels (which are covered by at least 5% of its base area).
- Base Contact Criterion: At least 85% of the parcel's base area are required to be in contact with the boxes below.
- Non-guillotine Criterion: No straight lines of boxes without any interruption from one edge to the other are allowed.

- Find a good algorithm, i.e. an algorithm which solves for high density, stable-packed mixed pallets which computes fast. By the nature of this very high dimensional problem, we do not expect to end up with a closed solution which is able to run in reasonable time. Consequently, we will probably have to approximate a good solution using a heurisitc which might try to:
- Create as many single height layers as possible with the given data and/or keep as much overlap with boxes below as possible.
- Put heavy weight articles to the bottom and light weight articles to the top.
- Keep the global goal in mind to minimize the amount of pallets by stacking each pallet as high as possible.
- … Many more ideas which has to be discussed during the team meeting on Wednesday, Oct. 21.

- Implement and integrate the algorithms into our simulator.
- In order to compare our results with other examples given in the literature (like Wurll-2002 and 2003) we will have to generate a representative set of single test scenarios (5 different box sizes, pallet size) and test our algorithm on all of them. By the nature of this problem, we cannot give a complete proof for our determined performance since the space of different test scenarios is way too large as to be checked in reasonable time. Instead, we will have to rely on our test set which really has to be representative. Prof. Christensen has offered to provide us with real world data.

**Implementation Challenges***What other problems do you expect to face in your implementation? Will you need some kind of robot hardware / software / sensors? Will you need to solve any problems in addition to planning.*ever is

- Since we have to use a (complex?) simulation environment (USARSim) there might be some accomodation time needed. Furthermore, we have to use some motion planner there and have to integrate our own planner into the environment.
- Some performance optimization (profiling, multicore, whatever is needed) might be necessary.

**Proposed Solutions***What algorithms will be required to make these tools useful to your planner? How will you acquire them / implement them?*

- Aquire simulator and motion planner for our problem (using the well known aquisition method "download" and then do all the ugly "get it running" stuff).
- Use existing libs for optimization algorithms, nearest neighbour, etc.

## Timeline

Week | General Task | Daniela | Martin | Richard | Saul |
---|---|---|---|---|---|

1 (10/12-10/18) | Write this wiki page. Create a presentation for the class. | presentation, project 2 (MM) | proposed work, related work, schedule, project 2 (MM) | abstract, related work, schedule, project 2 (3.1) | project 2 (3.2) |

2 (10/19-10/25) | Make concepts, brainstorm on search space definition and heuristics. | read papers and collect ideas for search space representation, give proposals for solution approaches in the respective representation; finish individual tasks on project 2 (Martin: Mobile Manipulation, Richard: Manipulation, Saul/Daniela: Videos and Documentation) | |||

3 (10/26-11/01) | Decide on algorithm ideas. Set up project environment for all team members, aquire everything else needed to get started with implementation | Draft of UML-diagramm for implementation and specification of functions. Set up all required classes. Started to implement. | Draft of UML-diagramm for implementation and specification of functions | Richard is occupied by 3 project deadlines for his other three courses | Find and collate VMAC requirements and simulator details. |

4 (11/02-11/8) | Start prototyping -> implementation of state representation and algorithms | implement and test the generation of drop maps and evaluation | integrate OpenCV library, 2D visualizations for our maps (height map, weight map, drop map, etc.) | implement finding the best box drops onto the pallet starting at a certain state, rewrite 2DMatrix class based on OpenCV matrices | Download and install simulator components (download complete, installation is failing repeatedly.) |

5 (11/09-11/15) | Work on planning algorithm and further implementation | refine drop map implementation, debugging | integrate search algorithm (A*) from project 1 | kill some of the many warnings, debug and unify many warning-related fuzzy code segments (potential floating point errors), implement heuristic for A* | UT2004 is installed and running (UT3 doesn't install). Having some trouble figuring out which version of USARsim goes with the exact version of UT I have and exactly where the files all go. Based on initial look at screenshots of UT2004, MOAST and USARsim's API, recommending to Martin that he write his own display system. Screenshots in this just look like brown and blarg. |

6 (11/16-11/22) | Implement own visualization, work on planning algorithms, implement file reader for package list, improve evaluation and check functions, implement an evaluation for resulting stack | reading package list from file, generate 3d drops | write a openGL based visualization for the pallet and its boxes | implement height tolerance for drops on surfaces with nearly same height, improve base support and interlock determination functions | Recovering from A) sickness and B) ER visit after being randomly attacked by malevolent passerby. No work done :( |

7 (11/23-11/29) | Code tuning and bugfixing, implement beam search instead of A*, polish visualization, finish heuristic, finish evaluation for final stack | speed ups: updating all maps iteratively | write new search algorithm (beam search), change file format to yaml, implement heap in search to remove identical results, improve visualization (colored box types, visualize stacking, take pictures) | improve children selection in beam search algorithm (best+fitness proportional selection), implement heuristic/state evaluation calculations, improve weight check function, collect important parameters in central class, implement package list with limited number of boxes | USARsim running, but having trouble with windows' IPC for some reason. No fix yet. Currently trying to figure out how to disable my firewall. |

8 (11/30-12/06) | Final tuning and bugfixing, collect test data and implement test framework, find results for comparison | acquire real world data for comparison, make package list files in our format | implement several program speedups (pass results between functions), output some intermediate results for explanation in paper, output runtimes, rescale fitness values in selection | write test framework and produce results/diagrams (Matlab script)/videos | Examined MOAST interface. It turns out that it's basically a message parser for USARsim and a set of precoded robots. In other words, writing anything for USARsim would be comparable in difficulty to doing the same task on a real robotic arm. Giving up on simulator in favor of evaluation critera. |

9 (12/07-12/11) | Write paper and prepare final presentation | introduction, related work, presentation | algorithm/methods, presentation | experiments/results | fine-tune evaluation criteria; future work |

*What did you accomplish? What results do you have to show for it. Pictures and videos are always welcome!*

## Week 1

We have written this wiki page and prepared a presentation. Although most realizations of mixed palletizing systems are industry-made and therefore no information on their algorithms is available, we were glad to finally find some papers with useful considerations addressing the homogeneous palletizing as well as the mixed palletizing problems. The parallel work on project 2 is on good progress.

## Week 2

<21 Oct>

Current discussion about the general approach of how to solve the problem. As this decision is a really big one, we still need time to figure it out. It's still not clear, whether we want to do search with an evaluation function or handle it only as an optimization problem or a combination of both.

<23 Oct>

We have collected several approaches for the search space definition (and resulting solving algorithms), written them together for comparison and decided for a height map representation of the pallet. Because of the nature of our chosen problem definition the algorithm should run in several steps, each dealing with a harder problem (e.g. first step: make homogeneous layers as long as possible, second step: build larger blocks from several packages to form same height layers, third step: make some fancy analysis for best placement of the remaining boxes [fancy means choosing the best box and best position for the next step of the palletizing plan by evaluating several criteria for a good placement and building a search tree with the best k options; our internal paper is more detailed about that, but we do not want to reveal all details in public before the final presentation]).

Because several assumptions about the ICRA robot challenge turned to be wrong when the organizers updated their webpage we have decided to focus on our problem first. This includes that we probably will not use the USARSim simulator which would need all the controls and arm planning code written by ourselves. Since this task was not our focus for this project we have decided to solve the main problem first and work with a simple 3D visualization of the pallet and its building process in which the packages are dropped "from heaven" onto the pallet without the robot arm (as stated before, the robot arm is nice for visualization but does not affect our problem).

## Week 3

We started with the implementation of the state representation and accomplished the generation of height maps (storing current stack height at each pallet position), weight maps (store how much can still be stacked on top) and drop index maps (for interlock determination), which are crucial matrices used by our search algorithm in order to evaluate our quality measures and to find possible positions to drop the next box on the stack. Sorry, but we cannot provide you with any exciting pictures, yet.

## Week 4

This week we did the implementation of a generator for scored drop maps, which are matrices storing numbers of how good it would be to drop a box at each (x,y)-position. Furthermore, we integrated OpenCV for means of visualization of our maps (height maps, weight maps, drop maps) and to implement our matrices as OpenCV matrices, which are implemented for taking advantage of MMX vector calculation speedups.

## Week 5

We improved the implementation of the scored drop map generator this week and started to implement the A* search algorithm together with the whole search framework from project 1 into our project. Moreover, we had to debug the code a little bit and remove some potential floating point errors concerning the accesses of our maps. This removed many critical compiler warnings, too. We also started trying to implement a heuristic for A*.

## Week 6

Because of the trouble with the simulation environment and the missing decisions on which simulator will be used, we decided to implement an own visualization in order to be able to review our results and judge them. We implemented an OpenGL visualization of the pallet and the stacked boxes, which can be viewed from all sides.

A further need was to read our package list from file, which defines which boxes (size, weight, weight constraints) are to stack. We implemented that in this week.

In order to evaluate our resulting stack, we started to write a function which is intended to calculate the above decribed measures.

Although we got some simple (but buggy -> overlaps, see below) results from our A* using a very simple heuristic, we figured out that A* was not really suited to our problem formulation because we could not really formulate an admissible heuristic which implemented all our quality measures. Another problem was to decide where to replan if an A* solution was not good enough and how to decrease the long runtime. Finally, we decided to switch to beam search which yields only linear computation effort and memory usage and gave us an easy way to implement our quality measures in the sense of a guide for the search.

## Week 7

This week, we switched our search algorithm to beam search (only keep k children and expand them, select the best k of them and repeat) in order to get a faster runtime of the whole algorithm and use our quality measures as incentives for the search direction. The selection was first only score-driven, i.e. we just used the best proposed drops. Since our k results did not differ substantially, we furthermore imlemented a) a hash map which detected identical stacking schemes and removed doubles and b)improved the selection by choosing only a part for the next generation to be the best choice. The other part is drawn by chance from all proposals proportional to their fitness.

On larger problems, our planner calculated for quite a long time. This was the reason to decide that some speedup measures were necessary. The most important was to update our maps for each following state using the data from its predecessor instead of calculating all maps again from scratch in a new state. This reduced the runtime even for large problems to some minutes (with resolution 1 pixel/cm, several hundred boxes stacked). Further speedups are sheduled for the next week.

For viewing convenience, we improved the visualization by using different colors for different box types and we implemented the option of making the stacking progress visible. Now, it is even possible to take pictures from the visualization.

As another improvement to the program, we modified the file reader to work with yaml files which could be written much more human-readable. Furthermore, our program can keep track of how many parcels are used, now, and outputs how many of the parcels from the list could finally be stacked.

As mentioned above, we could now implement our evaluation (scoring) criteria for the (intermediate) states in the search tree to guide the search space exploration. You can review how the results got better below.

Here are two simple results, a small and a large one, which do not use the interlock function but could be calculated quite fast and use a quite good amount of the pallet volume:

Here we present you the stacking procedure where you can observe that interlocks are enforced, now, yielding an intermediate result (compared to later pictures):

http://home.arcor.de/rib.rib/simpleVideo.wmv

This example also takes care about interlocks and has an amazingly good pallet density:

Here we have checked the weight constraints (the red boxes can only lift one further box, the yellow and blue boxes can lift 2 and the green one can lift many):

The gaps at the top of the stack are caused by weight constraints.

## Week 8

During this week, we refined the evaluation criteria to obtain even slightly better stacks than we got in the last week especially with respect to interlocks.

For further speedup, we rearranged some pieces of the code to reuse some costly results inside a state. The speedup was around 15% which made the effort worth.

With the real world data, we finally could use our testing framework to adjust our parameters. All final results will be shown in the final presentation.

Here are some more outputs of our pallet planner obtained in ca. 7 minutes for around 60 boxes stacked on a 125x145x140cm pallet (width x depth x height):

## Week 9

We wrote the paper and prepared the presentation this week.