No description, website, or topics provided.
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Type Name Latest commit message Commit time
Failed to load latest commit information.


sisyphus is a piece of software I wrote the context of my graduate automation project. My class was taking part in the IEEE ICRA 2012 Virtual Manufacturing Automation Competition and part of the competition, was to efficiently stack boxes of different sizes on a pallet.

As the knapsack problem is NP hard, sisyphus implements hybrid between heuristic and bruteforce approach.

The heuristic is, to group articles of same height into layers, and then stack those layers on top of each other.

Different techniques to form layers and different orderings of stacking them are then tried out in a bruteforce manner.

get the code

$ git clone
$ cd sisyphus

compile evaluation library

$ wget
$ tar xf palletandtruckviewer-3.0.tar.gz
$ cd palletandtruckviewer-3.0
$ patch -p0 < ../palletViewer-sharedlib.diff
$ autoreconf -fi
$ ./configure --libdir=`pwd`/..
$ make
$ make install-strip
$ cd ..

test evaluation library (optional)

$ python examples/icra2012/packlist_R1.xml examples/icra2012/scorecog.xml

$ python examples/icra2012/Challenge2.order.xml examples/icra2012/packlist_R2.xml examples/icra2012/scorecog.xml

$ python examples/icra2012/Challenge2.order.xml examples/icra2012/packlist_R3.xml examples/icra2012/scorecogoverlap.xml

generate packlist files

$ ./ examples/icra2011/palDay1R1Order.xml packlist.xml examples/icra2011/scoreAsPlannedConfig1.xml

Usage takes an order.xml and tries different strategies to create many lists of layerlists. Each layerlist is built with a different selection of strategies. Available strategies are article rotation and pallet rotation which can both be either true or false. Per default, tries all combinations of article and pallet rotations, which means that for each new layer, there are four possibilities how articles can be arranged in it.

A layerlist is the result of one specific combinations of strategies. For example: first layer with article rotation and pallet rotation, second layer without article rotation but with pallet rotation, third layer with neither and so forth. outputs those layerlists one per line in python pickle gzipped and base64 encoded format. Python pickle is used as a fast serialization format. The data is gzipped because it is given to as a commandline argument and those must not exceed an OS specific value. The data is base64 encoded to avoid zero bytes, newlines and other whitespace characters in them.

As a result, the output of can not only be saved in a file, but you can also used split(1) on it to distribute it onto many machines for evaluations. You can also use head(1), tail(1), sort(1) or uniq(1) on the output. takes as arguments an order.xml, a packlist.xml output file, a scoring.xml file and a number of layerlists, encoded as described above. For each layerlist it will try every possible permutation of how to place them on top of each other and evaluate each of them by using palletViewer.

Multiple instances of can be run on the same machine. Before exits, it will put a file lock on score_max.lock and read the currently highest score from score_max. If the just calculated score is higher, it will write its own score into score_max and update the contents of packlist.xml as well.

Since score_max always contains the currently highest score, it can always easily be checked during a run, what the currently highest score achieved is.

Since packlist.xml always contains the best packlist found so far, can always be aborted in the middle of execution, should it take too long to evaluate while still maintaining the current best packlist. One does not need to wait until finished execution.

Since score_max contains the highest score, it should be removed before each new run. This is already done by

environment variables


rot_article         - try different article rotations (default: True)
rot_pallet          - try different pallet rotations (default: True)
rot_article_default - default article rotation (default: False)
rot_pallet_default  - default pallet rotation (default: False)
iterations          - maximum number of iterations (default: -1)
randomize           - try random strategies instead of sequential (default: False)


multi_pallet        - respect pallet max height and spread over multiple pallets (default: False)
permutations        - whether to try all layer permutations or not permute at all (default: True)
iterations          - maximum number of iterations (default: -1)
randomize           - try random strategies instead of sequential (default: False)

For orders that are too big to enumerate all possible permutations of layer strategies and orderings, using randomize and iterations for and is recommended.

The according line in could be changed to:

iterations=100 randomize=1 python $1 | randomize=1 iterations=1000 xargs --max-procs=4 --max-args=1 python $1 $2 $3

utility scripts

    takes a single or multi pallet packlist.xml and adds the three approach
    points to all the articles in it, relative to each articles position

    takes an order.xml and prints all barcodes in it

    takes an order.xml and prints the density of all articles

    takes an order.xml and prints a table with the description, ID, type,
    family, size and weight of every article

    takes a multiple pallet packlist.xml and a scoring.xml and prints out
    the score that this packlist achieves

    takes an order.xml, a single pallet packlist.xml and a scoring.xml and
    prints out the score that this packlist achieves

    takes an order.xml and prints the number of articles within

    takes a single or multi pallet packlist.xml and prints the number of
    articles within

    takes an order.xml and prints a table with the length, width, maximum
    load height and maximum load weight

    takes a multiple pallet packlist.xml and outputs pairs of single pallet
    packlist.xml and order.xml files by appending _$i.xml and _order_$i.xml
    to the original packlist.xml filename, respectively. The integer $i
    starts at 0 and	will be incremented with each subsequent pallet.

evaluation of multi pallet packlists

palletViewer cannot parse multi pallet packlists, hence the packlists have to be split into several single pallet packlists. Each of those packlists is then given to palletViewer for evaluation. The individual results are averaged for a final score. To avoid each of the palletViewer instances complain about missing articles, an according order.xml file is created for each single pallet packlist.xml.

Multi pallet packlists can evaluated like this:

python packlist.xml scoring.xml

Or manually like this:

python packlist.xml
python packlist.xml_order_0.xml packlist_R1.xml_0.xml scoring.xml
python packlist.xml_order_1.xml packlist_R1.xml_1.xml scoring.xml


there is a "memory leak" in Every loop iteration where a new permutation is tried out will stay in memory. This is not needed and should not be the case. This is the reason why supplies with only one layerlist at a time because otherwise, memory consumption would grow too big.


Sisyphus won the IEEE ICRA 2012 Virtual Manufacturing Automation Competition. Here is some media about our submission:

Round1: ./examples/icra2012/packlist_R1.xml

Round2: ./examples/icra2012/packlist_R2.xml

Round3: ./examples/icra2012/packlist_R3.xml