DynStack Competition

Documentation

On this page we describe in more detail how the simulation works, constraints for your solver and information on the technical realization.

The Simulation

We created a discrete event simulation based on Sim# to simulate the operation of a gantry crane that relocates blocks in a storage area which acts as a buffer between an upstream and a downstream process. In this section we will give more detailed information on the processes in this simulation.

Arrival Process
The arrival process spawns new blocks at the bottom of the arrival stack in random intervals. If after such an interval the arrival stack is observed to be full, that block is considered to be "waste" and the arrival process is terminated.
The arrival process is revived after the crane picks up a block from the arrival stack and thus creates room for a new block, which is spawned again after a random interval.
Uncertainty estimation: The statistical or empirical distribution of those intervals is not disclosed, but the arrival intervals of the last 100 blocks are tracked by the simulation.
Handover Process
The handover process is initiated when the crane drops-off a block at the handover stack. It will immediately recognize whether the block is on time (its due date is older than the current simulation time) and update the KPIs. The handover stack will become not ready, but the block remains on the handover for some random interval (clearing time). Then the block disappears and the handover stack becomes ready again after another randomly drawn interval (recovery time).
Uncertainty estimation: The statistical or empirical distribution of those intervals is not disclosed, but the whole interval (clearing time + recovery time) of the last 100 blocks delivered are tracked by the simulation.
Block Process
The block process is initiated when a new block is created. Ready and due date will be randomly drawn from some distribution. The due date will be available to the solver, but the ready date will not be.
After its ready date, the block will become ready which can be observed in form of a world update from the simulation.
The process will also track the due date. If the block is still not at the handover when it is due, the respective KPIs are updated and the block will be recognized as overdue.
Crane Process
The crane process is initiated by the solver. It will perform the sequence of moves specified in the schedule. Moves are checked for validity before they are performed and any invalid move in the schedule will be skipped. Moves may become invalid for a number of reasons:
(1) "Block not found": the block is not found at the top of the source stack
(2) "Invalid Target": the block is to be relocated to the arrival stack
(3) "Invalid Source": the block is to be relocated from the handover stack
(4) "Height Violation": there is not enough capacity at the stack
(5) "Not Ready": the block is to be relocated to the handover, but either it is not ready or the handover is not ready
Whenever the solver sends a new schedule, there is a small simulated delay of 200ms before the crane will consider it. The current schedule will be aborted after completing the relocation that is currently in progress. Each schedule should have a higher sequence number than the previous so that the simulation knows which is the most recent schedule if there are several updates in the meantime.
The crane takes some time to move horizontally between stacks and some time to lower and raise the hoist. The longer the distance, the longer it takes for both directions. The actual time to perform a single move in one of those directions is again sampled from some distribution.
Uncertainty estimation: The statistical or empirical distribution of the crane movement times is not disclosed, but the material flow is often easily observable. Thus, the simulation tracks the duration of the last 100 relocations.

Simulation Settings

We have created a range of different settings from three buffer stacks to nine buffer stacks. We estimated the settings by approximating the process using queueing theory and Little's law to achieve a certain system and buffer utilization respectively. In general, the settings A to C are quite similar to each other, but represent a progression from high to medium buffer utilization while going from medium to high system utilization at the same time. System utilization (rho) is the ratio of arrival rate (lambda) to processing rate (mu), rho = lambda / mu. Buffer utilization depends on the capacity and the number of blocks in the system (L). If we assume a certain time W that blocks spend in the system (i.e., the lead time) we can estimate L through Little's law as L = lambda * W. Thus buffer utilization is L divided by the buffer capacity. By fixing several of the parameters in these equations we can obtain the others.
Thus, while the buffer utilization should be lower in scenarios C, the crane might still be quite challenged as the interarrival times on the production stack will also be lower. Simulation setting D is a bit different from A to C.

The settings for the scoring runs will not be disclosed.

Measuring Performance, Scoring and Ranking

We provide a number of KPIs that are computed in the simulation and which describe the performance of a stacking solver. We chose three "scoring KPIs" that create a lexicographic objective function for comparing all scoring runs of the competition. Each scoring run may only be started once. Thus, take the scoring runs only when you are sure your solver is ready. This is equal to making a "submission" in other competitions. Once you have started a scoring run it will run to completion and cannot be aborted. When you lose connection or there are other problems, make sure you reconnect swiftly.
For each scoring run a ranking will be created and the average of that ranking will determine the winner(s) and runner-ups .

  1. #1: Minimize Blocked Arrival Time
  2. #2: Maximize Total Blocks on Time
  3. #3: Minimize Crane Manipulations

Computing the scoring KPIs

  1. Blocked Arrival Time is counted as the total time within the runtime that the arrival process is suspended. As stated above, it suspends when there is no remaining capacity at the arrival stack AND a new block is about to be spawned and resumes as soon as there is again some capacity, i.e., when the crane picks up a block at the arrival stack.
  2. Total Blocks on Time counts all blocks that have been delivered before their due date, as well as those that are still at a stack, but are not overdue.
  3. Crane Manipulations are the total number of blocks that have been relocated by the crane. Moving a crane to a certain stack without carrying a block (i.e., an empty move) does not count as manipulation.

There are also a number of additional KPIs that are provided to you for analysis purposes and which are briefly described in the following

  • Delivered Blocks is the total number of blocks delivered (no matter whether they are due or not)
  • Mean Leadtime is the mean time that blocks spend in the system (from arrival to when they are put on handover)
  • Mean Service Level is the relative number of blocks that are on time (current + delivered)
  • Mean Buffer Utilization is the relative number of buffer capacity used
  • Mean Crane Utilization is the relative number of time that the crane works on schedules (includes empty moves)
  • Mean Handover Utilization is the relative number of time that the handover is not available
  • Mean Upstream Utilization is the relative number of time that the upstream process is running

The Solver

The simulation automatically publishes world updates to which the solver listens. The data format in the protocol is given below. The world update contains always the full world state and not the changes. If you rely on changes, you will have to calculate the difference for yourself.

To control the crane process, the solver has to send a message of type CraneSchedule which contains a sequence number and a list of moves. The sequence number is important, because the simulation will discard any schedules with a sequence number that is less than the last observed. The simulation will adopt a new crane schedule only between relocations. It will not interrupt any relocation that is currently being performed. A relocation starts when the crane has arrived at the source stack and ends when the block has been dropped off at the target stack and the hoist has moved up.
There may be two types of moves
Empty Moves: Indicated by EmptyMove = true. A TargetId of the stack to move to is expected.
Relocation Move: Indicated by EmptyMove = false. Expects that BlockId, SourceID, and TargetId are defined.
In addition, there is a sequence number that must be increased for every move in the schedule.

As has been stated above, the simulation model checks all moves for validity and will skip invalid moves. For instance, consider the case that your solver creates a schedule with two moves, the first relocates a block from stack 3 to the handover and the second relocates a block from stack 2 to stack 3. When the crane starts executing the schedule it may observe, that the handover is not ready and thus ignores the first move. However, it may see that the second move is valid and thus performs it.
A complete list of invalid moves has been stated above when describing the crane process.

The best strategy depends heavily on the frequency of new arrivals and on efficiently using the handover as well as the crane speed. The simulation will collect data for uncertainty estimation as has been described above which the solver can use in order to improve its decision making.

Technical details: ZeroMQ and Protocol Buffers

Our server exposes two ports, one for publishing world states and the other for sending crane schedules. The simulations run in the background on the server. The simulation IDs that you parameterize your solver with tell our server which world update you want to subscribe to and to which simulation the crane schedules should be forwarded.

We have chosen to use ZeroMQ sockets, because they offer a multitude of different patterns that we can use, because it is open source, and because ZeroMQ implementations are available for a wide range of programming languages. This enables us to develop the server and simulation in C# while you can use any programming language to implement your solver. Thus, you can use any framework that you are feeling comfortable with to write a crane control.

Data model

While ZeroMQ does all the networking for us, we still need a way to describe, serialize, and restore messages. We have chosen to go with Protocol Buffers (protobuf) for this task. Protobuf enables us to describe the simulation state and all relevant messages in a way that creates little overhead. You can serialize and deserialize the ZeroMQ messages to a data model in your programming language in one line of code. We think that this creates very little overhead and that you can concentrate on the most important part of this competition: your solver.

In the following we describe the messages in more detail and further below you find the message definition in proto3 syntax. You can just copy this to a .proto file and run the protobuf compiler on it so that it generates the data model.

Block
The message that describes a block. You get the Id, Release date, and Due date and whether that block is Ready or not. Release Date is equal to the date at which it first appeared at the arrival stack. These dates are given in milliseconds since the start of the simulation.
Crane
The message that describes the crane. It also has an Id, but in any simulation run there will be only one crane. More important are the LocationId which is the last location that it has acted upon (or moved to). Additionally, the Load denotes which block it is currently carrying. Most importantly, the Schedule denotes the current active moves to perform. Every time a move is completed it is removed from the schedule. Thus, a crane may have an empty schedule. The GirderPosition and HoistPosition denote its position relative to the bounds. The girder is moving horizontally in the continuous interval [0 = arrival stack, 1 = handover stack]. The hoist is moving vertically in the continuous interval [0 = ground, 1 = maximum height]. All stacks and vertical levels are distributed evenly in that range.
CraneMove
The message that describes a single crane operation. You need to define the Sequence of that move within its schedule. Then you must either specify whether it is an EmptyMove in which case only the TargetId is used or whether it is a relocation in which case BlockId, SourceId, and TargetId are used.
CraneSchedule
The SequenceNr should increase over the last schedule so that the simulation knows which is the latest schedule in case multiple updates arrive while the crane is still performing its current relocation. It mainly contains the list of crane moves as explained just above.
Handover
The message that describes the state of the handover stack. That stack may only contain a single block, thus there is only a Block field. It is also important to consider when it is Ready, otherwise the crane will refuse to put a block there. The Id should be used as a TargetId in a CraneMove when you want to move a block there, it is bigger than the Id of any other stack.
Performance
The message describes the KPIs that are calculated from the current state of the simulation. As for the units, the LeadTimeMean, BlockedArrivalTime, and TardinessMean are given in seconds. The properties ServiceLevelMean, *UtilizationMean are given in the interval ([0, 1]) and are to be interpreted as percentages.
Stack
These describe the arrival and the buffer stacks. The stack with Id = 1 is always the arrival stack, while those stacks with Ids > 1 are buffer stacks. For a CraneMove, TargetId may never be 1, as that would mean to put something on the arrival stack. You must consider the MaxHeight which usually only differs between the arrival and the buffer stacks, but all buffer stacks are of the same maximum height. Finally, BottomToTop lists all the blocks at that stack in this order, the first is at the bottom, the last is the topmost block.
TimeStamp
A simple message that describes elapsed time in MilliSeconds.
Uncertainties
This message contains the uncertainty estimations as mentioned above. The units for all intervals and times are seconds.
World
Finally, this is the outer-most message that you will receive from the simulation. Now holds the current elapsed time, while it is here explicit which is the arrival stack (called Production) and which are the buffer stacks. The rest of the properties have been discussed above.

 

syntax = "proto3";

message Block {
   int32 Id = 1;
   TimeStamp Release = 2;
   TimeStamp Due = 3;
   bool Ready = 4;
}
message Crane {
   int32 Id = 1;
   int32 LocationId = 2;
   Block Load = 3;
   CraneSchedule Schedule = 4;
   double GirderPosition = 5;
   double HoistPosition = 6;
}
message CraneMove {
   int32 BlockId = 1;
   int32 SourceId = 2;
   int32 TargetId = 3;
   int32 Sequence = 4;
   bool EmptyMove = 5;
}
message CraneSchedule {
   repeated CraneMove Moves = 1;
   int32 SequenceNr = 2;
}
message Handover {
   int32 Id = 1;
   bool Ready = 2;
   Block Block = 3;
}
message Performance {
   int32 CraneManipulations = 1;
   double ServiceLevelMean = 2;
   double LeadTimeMean = 3;
   int32 DeliveredBlocks = 4;
   int32 TotalBlocksOnTime = 5;
   double BlockedArrivalTime = 6;
   double TardinessMean = 7;
   double BufferUtilizationMean = 8;
   double CraneUtilizationMean = 9;
   double HandoverUtilizationMean = 10;
   double UpstreamUtilizationMean = 11;
}
message Stack {
   int32 Id = 1;
   int32 MaxHeight = 2;
   repeated Block BottomToTop = 3;
}
message TimeStamp {
   int64 MilliSeconds = 1;
}
message Uncertainties {
   repeated double ArrivalIntervals = 1 [packed = false];
   repeated double CraneMoveTimes = 2 [packed = false];
   repeated double HandoverReadyIntervals = 3 [packed = false];
}
message World {
   TimeStamp Now = 1;
   Stack Production = 2;
   repeated Stack Buffers = 3;
   Handover Handover = 4;
   Crane Crane = 5;
   Performance KPIs = 6;
   Uncertainties ObservationData = 7;
   repeated CraneMove InvalidMoves = 8;
}