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 two gantry cranes that relocate 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 delivers new blocks from the blockyard and adds them ontop of the arrival stack. It delivers blocks in batches, each batch contains one block with the smallest sequence number, but may also contain other blocks. If the arrival stacks are all full, or a crane is positioned at a free arrival stack then the delivery is postponed until either a stack becomes free and / or the crane has moved away. Note that, the crane is instructed to move away by the simulation itself, nevertheless it is also possible to send it away. Uncertainty estimation: The time until a delivery arrives is given in the data. In addition, the total time from start to finish (including waiting times) is also tracked as uncertainty by the simulation.
- Mill Process
-
The mill process is continuously active and will remove the topmost block from the corresponding handover stack
after some interval. If the right block is not at the top, the mill process creates a MoveRequest with the
deadline being the time at which the block is removed. Failing to meet the deadline will have the mill process waiting
which is bad (2nd objective). The mill process will remove whatever block is at the top, even if it may not be the next
in sequence or may be for the other mill. These cases severly degrade the performance of the scenario (1st objective).
In addition, mills need to synchronize every couple of blocks, basically, when a new program id is started. The last block of a program has to be rolled before the next block can start.
Uncertainty estimation: The statistical or empirical distribution of the block intervals are apparent when a move request is created. In addition the intervals of the last 30 blocks that are rolled are tracked by the simulation. - Crane Agent
-
The crane is implemented as an agent that performs the moves assigned to it by the crane scheduler. It will attempt to dodge
should the other crane require to move in a position that it currently occupies. Priority is given to the crane working on the
move with the lowest id.
Whenever the solver sends a new list of PlannedCraneMoves, there is a small delay of 200ms before it is accepted in the simulation. The new list of planned moves will replace the current moves, except those that are already scheduled. Thus, you have to include existing planned moves that you want to keep. Once a move with a certain id is in the simulation it cannot be changed anymore. You'll have to omit this move and instead introduce a move with a new id.
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 30 intervals between pickup and dropoff.
Simulation Settings
We have created a range of different settings that increase in size. 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 crane 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 intervals in the mill process will also be lower.
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: Minimize Rolling Program Messups
- #2: Minimize Blocked Mill Time
- #3: Minimize Crane Manipulations
Computing the scoring KPIs
- Rolling Program Messups is counted as incidents at which a block is removed from the handover that is not the next in sequence. If it is the wrong mill, then +10 will be added.
- Blocked Mill Time how often the mill had to wait on the next block, because it was not yet delivered.
- 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)
- Total Blocks on Time is the total number of blocks delivered on time
- 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
- Mean Buffer Utilization is the relative number of buffer capacity used (separate for shuffle and sorted buffer)
- Mean Crane Utilization is the relative number of time that the crane works on schedules (includes empty moves and separate for shuffle and handover crane)
- Mean Mill Utilization is the relative number of time that the mill waits for handovers
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 agent, the solver has to send a message of type PlannedCraneMoves which contains a sequence
number and a list of moves. The sequence number in this case is only for debugging purposes and not relevant.
Upon receiving such moves, the scheduler is started to attempt to assign these moves to the cranes. The basic scheduler will only
assign one move to each crane and then the next when the previous is finished. Any move that is scheduled cannot be removed anymore.
There may be two types of moves
Empty Moves: Indicated by Type == MoveTypes.MoveToPickup. It is expected that the PickupLocationId is given.
Relocation Move: Indicated by Type == MoveTypes.PickupAndDropoff. Expects that PickupLocationId, DropoffLocationId,
and Amount are defined. The other fields (except Id and Type) are optional.
Each move must include a unique id which ideally is unique during the whole run.
As has been stated above, the agents will skip moves that they cannot perform, e.g. because they should pick up 2 blocks from a location that contains only 1.
The best strategy depends heavily on utilizing the crane to a high degree. Moving larger batches instead of individual blocks is highly recommended. A tradeoff between sorting and sering the handovers need to be achieved and there should at least be one arrival stack that can accept an upcoming delivery. 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 one port, it will send world states and receive crane schedules through that port. 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, Sequence, Type, ProgramId, Arrived, and Rolled. The Sequence is constantly updated and the block with Sequence = 1 is always the next to be rolled. Type indicates to which mill it belongs. Arrived is set after the arrival process has put the block on the arrival stack.
- Stack
- The message that describes an ordered sequence of blocks (first entry is bottom-most block).
- Location
- The message that describes a location that is positioned somewhere along the girder and which contains a Stack. It has a MaxHeight field to indicate the number of blocks that it can contain, a Type field to indicate whether it is an Arrival location, Shuffle- or SortedBuffer, or a Handover. For Handover types, additionally, the MillType field indicates to which mill it belongs (A or B). There is only ONE handover per mill.
- Crane
- The message that describes a crane. It also has an Id and there will always be two cranes. It has a maximum block carrying capacity given in CraneCapacity. It's Width indicates the safety distance, half of that to each side. Any crane can only move between MinPosition and MaxPosition within the girder. The GirderPosition and HoistLevel indicate its current position while Load denotes the current stack it is carrying.
- PlannedCraneMoves
- The collection of moves that are to be executed by the crane agents. The sequence number is used only for debugging purposes. The individual moves are given in the list of Moves.
- CraneMove
- The message that describes a single crane operation. You need to define the Id of that move in order to identify it. Then you must specify its Type in which case the PickupLocationId is of prime importance or whether it is a relocation in which case Amount, PickupLocationId, and DropoffLocationId are used. A move can be limited to a certain crane by setting the RequiredCraneId, otherwise, the scheduler will decide this. In addition, the ids of preceeding moves may be given which prevents the scheduler from assigning the move before the others are completed. Note that you have to make sure not to include a cycle in those precedences, otherwise, those moves never get scheduled.
- CraneSchedule
- The ScheduleNr is irrelevant and only for debugging purposes. It indicates which move is assigned to which crane with which priority (see CraneScheduleActivity). Cranes work on moves in ascending order of priority. This priority is global, thus a move for crane A with priority of 2 will not get executed until a move for crane B with priority 0 has finished for instance.
- MoveRequest
- As detailed above, the mill process indicates that a block is required to be moved to the handover location by creating a MoveRequest. The properties TargetLocationId indicates the specific Handover location, BlockId denotes the id of the block and DueDate indicates the time at which it should be removed from the handover.
- Arrival
- Indicates which stack (Load) is arriving at which date (ArrivalEstimate). The Vehicle is irrelevant.
- Performance
- The message describes the KPIs that are calculated from the current state of the simulation. As for the units, the LeadTimeMean, BlockedMillTime, and TardinessMean are given in seconds. The properties ServiceLevelMean, *UtilizationMean are given in the interval ([0, 1]) and are to be interpreted as percentages.
- 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, Width the total length of the girder and Height the total height (at least maximum location height + crane capacity + 1). The rest of the properties contain lists of messages that have been discussed above.
syntax = "proto3";
message Arrival {
int32 Vehicle = 1;
Stack Load = 2;
TimeStamp ArrivalEstimate = 3;
}
message Block {
int32 Id = 1;
int32 Sequence = 2;
MillTypes Type = 3;
int32 ProgramId = 4;
TimeStamp Arrived = 5;
bool Rolled = 6;
}
message Crane {
int32 Id = 1;
Stack Load = 2;
double GirderPosition = 3;
double HoistLevel = 4;
int32 CraneCapacity = 5;
double Width = 6;
double MinPosition = 7;
double MaxPosition = 8;
}
message CraneMove {
int32 Id = 1;
MoveType Type = 2;
int32 PickupLocationId = 3;
int32 DropoffLocationId = 4;
int32 Amount = 7;
TimeStamp ReleaseTime = 8;
TimeStamp DueDate = 9;
int32 RequiredCraneId = 10;
repeated int32 ProtobufPredecessorIds = 11 [packed = false];
repeated int32 ProtobufMovedBlockIds = 12 [packed = false];
}
message CraneSchedule {
int32 ScheduleNr = 1;
repeated CraneScheduleActivity Activities = 2;
}
message CraneScheduleActivity {
int32 MoveId = 1;
int32 CraneId = 2;
int32 Priority = 3;
CraneScheduleActivityState State = 4;
}
enum CraneScheduleActivityState {
Created = 0;
Activatable = 1;
Active = 2;
}
message Location {
int32 Id = 1;
double GirderPosition = 2;
int32 MaxHeight = 3;
Stack Stack = 4;
StackTypes Type = 5;
MillTypes MillType = 6;
}
enum MillTypes {
A = 0;
B = 1;
}
message MoveRequest {
int32 Id = 1;
int32 TargetLocationId = 2;
int32 BlockId = 3;
TimeStamp DueDate = 4;
}
enum MoveType {
MoveToPickup = 0;
PickupAndDropoff = 1;
}
message Performance {
int32 CraneManipulations = 1;
double ServiceLevelMean = 2;
double LeadTimeMean = 3;
int32 DeliveredBlocks = 4;
int32 TotalBlocksOnTime = 5;
double TardinessMean = 6;
double ShuffleBufferUtilizationMean = 7;
double SortedBufferUtilizationMean = 8;
double ShuffleCraneUtilizationMean = 9;
double HandoverCraneUtilizationMean = 10;
double MillAUtilizationMean = 11;
double MillBUtilizationMean = 12;
int32 RollingProgramMessups = 13;
double BlockedMillTime = 14;
}
message PlannedCraneMoves {
int32 SequenceNr = 1;
repeated CraneMove Moves = 2;
}
message Stack {
repeated Block BottomToTop = 1;
}
enum StackTypes {
ArrivalStack = 0;
ShuffleBuffer = 1;
SortedBuffer = 2;
HandoverStack = 3;
}
message TimeStamp {
int64 MilliSeconds = 1;
}
message Uncertainties {
repeated double ArrivalIntervals = 1 [packed = false];
repeated double CraneMoveTimes = 2 [packed = false];
repeated double MillBlockIntervals = 3 [packed = false];
}
message World {
TimeStamp Now = 1;
int32 Height = 2;
double Width = 3;
repeated Location Locations = 4;
repeated Block BlocksAtSlabYard = 5;
repeated Arrival ArrivalsFromSlabYard = 6;
PlannedCraneMoves CraneMoves = 7;
repeated MoveRequest MoveRequests = 8;
CraneSchedule CraneSchedule = 9;
Crane ShuffleCrane = 10;
Crane HandoverCrane = 11;
Performance KPIs = 12;
Uncertainties ObservationData = 13;
}