Mixed box palletizing; a suggestion to detect and pack unknown sized objects in bins using point clouds and genetic algorithms

Abstract

Palletering av bokser er gjort med roboter i mange år. Det er en enkel oppgave å velge en boks og stable den på en pall. Men hvis boksen har ukjent størrelse og posisjoner, er løsningen til dette problemet ikke triviell. I denne oppgaven skal to metoder som er ment å være en del av et fullt automatisert palleteringssystem utvikles. Den første metoden oppdager størrelser, posision og orientering av alle bokser som er tilstede i en scene. Den andre metoden bestemmer hvilken boks som skal velges først og hvor den skal plasseres.

Boksdeteksjonsmetoden er utviklet ved bruk av vanlige punktsky-operasjoner og selvutviklede metoder. Alle disse er implementert i C ++ ved hjelp av point cloud library, PCL. En punktskyssimulator er utviklet for å kartlegge resultatene av alle delene av metoden. Boksdeteksjonsmetoden er testet på punktskyer fra simulatoren og Zivid-kameraet. Resultatene viser nøyaktighet og presisjon som er større enn hva industrielle applikasjoner krever, og med en beregnings-tid omtrent som opptakstiden til Zivid-kameraet, er ytelsen tilstrekkelig.

Den andre metoden er Robotic bin packing. Ved å utnytte forskningen som er gjort på Bin packing problem, metoden regner ut fremtidige kostnader for de tilgjengelige basert på fremtidige bokser og nåværende løsning. Med denne kostnaden er beslutningen om hvilken boks å velge først gjort. Alt dette er implementere med bruk av Python. Metoden er testet på data tilfeldig generert med typiske industrielle egenskaper. Utførelsen av denne metoden viser betydelig forbedring sammenlignet med en ren erfaringsbasert pakking, og i mange tilfeller optimal pakking.

Resultatene fra de to metodene viser at begge metodene kunne implementeres i en industriell applikasjon. Ved å implementere funnene i denne oppgaven i industrien, kan frakt- og distribusjonssektoren få et betydelig skritt mot en mer optimal prosess. Konsekvensene for en slik optimalisering vil være redusert behov for fraktbåter, og dermed redusere kostnadene for frakt og redusere karbonavtrykket i denne sektoren.

Palletizing of boxes has been done for robots for many years. It is a simple task to pick a box and place it at a pallet. However, if the box has unknown size and positions, the solution to pick-and-place is not trivial. In this thesis, there are going to be addressed two methods that are meant to be a part of a fully automated palletizing system. The first method detects the sizes and poses of all boxes that are present in a point cloud. The second method decides which box should be picked first and where to place it.

The Box detection method is developed by the use of common point cloud operations and self-developed methods. All of these are implemented in C++ with the help of point cloud library, PCL. In order to map the result of all the parts of the method, there is developed a point cloud simulator. The box detection method is tested on point cloud from the simulator and Zivid-camera. The results show accuracy and precision that is far greater then what industrial applications need with a computational-time approximately equal to the capture time of the Zivid-camera.

The second method is the Robotic bin packing. By utilizing the research done on Bin packing problem, the method calculates the future cost of the available boxes and current solution. With this cost, the decision of which box to pick first is made. This is implemented in Python. The method is tested on data randomly generated with industrial properties. The performance of the methods show significant improvement compared to a simple heuristic packing, and in many cases optimal.

The results of the two methods show that both of the methods could be implemented in an industrial application. By implementing the findings in this thesis in industry, the shipping and distribution sector may obtain a significant step towards a more optimal process. The consequences for such an optimization would be reduced need for freight carriers, thus lowering the cost for shipping and reducing the carbon footprint in this sector.