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 two gantry cranes that relocate blocks in a storage area which acts as a buffer between multiple upstream and downstream processes. In this section we will give more detailed information on the processes in this simulation.

Arrival Process
The arrival process generates new vehicles that transport blocks to the warehouse. Vehicles have to park at arrival locations and are dispatched first come first serve. Once an upstream vehicle parks, the simulation generates move requests for all loaded blocks. These blocks must then be pickup from the arrival location and dropped on a buffer location. If all arrival locations are blocked, i.e. a vehicle is parked in each arrival location, newly created vehicles are queued. Once an arrival location becomes available again, the next upstream vehicle in the queue is dispatched.
Uncertainty estimation: The statistical or empirical distribution of the block intervals are apparent when a move request is created.
Handover Process
The handover process generates new vehicles that transport blocks out of the warehouse. Vehicles have to park at handover locations and are dispatched first come first serve. Once a downstream vehicle parks, the simulation generates move requests for all blocks that have to be loaded onto the vehicle. These blocks must then be pickup from the buffer locations and dropped on the handover location. If all handover locations are blocked, i.e. a vehicle is parked in each handover location, newly created vehicles are queued. Once a handover location becomes available again, the next downstream vehicle in the queue is dispatched. Once the required number of blocks have been dropped off at the requested handover location, the parked downstream vehicle is considered to be serviced. A load check is done and the number of (in-)correctly delivered blocks is recorded.
Uncertainty estimation: The statistical or empirical distribution of the block intervals are apparent when a move request is created.
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. Moves in the crane schedule are processed by index. Each agent receives the first non-active move as its next move, if it is assigned to the respective crane, and otherwise idles until a move becomes available.
Whenever the solver sends a new CraneSchedulingSolution, there is a small delay of 200ms before it is accepted in the simulation. The new list of scheduled moves will replace the current schedule, except those that are already active. Thus, you have to include existing planned moves that you want to keep. The simulation automatically generates moves for existing move requests, however, you are not oligated to schedule those and can instead create your own custom moves. As negative move IDs are reserved for generated moves, custom moves must have positive move IDs. Moves generated by the simulation cannot be changed anymore, but custom moves can be updated.
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.

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.

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 scheduling/stacking solver. We chose four "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 Delivery Errors
  2. #2: Maximize Handled Blocks
  3. #3: Minimize Max Parking Duration

Computing the scoring KPIs

  1. Delivery Errors is the number of blocks that were incorrectly loaded onto downstream vehicles. This number is incremented during load checks after downstream vehicles have received their required number of blocks.
  2. Handled Blocks are the total number of handled up-/downstream blocks that have been picked up from arrival locations or dropped off at handover locations by the crane.
  3. Max Parking Duration is the longest parking duration of all currently parked vehicles.

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

  • Crane Manipulations are the total number of lifting operations by the crane. Picking up a block counts as manipulation, dropping off a block counts as manipulation. Moving a crane to a certain stack without carrying a block (i.e., an empty move) does not count as manipulation.
  • Total Girder Distance is the summed up total girder (i.e. horizontal) movement distance of all cranes.
  • Total Hoist Distance is the summed up total hoist (i.e. vertical) movement distance of all cranes.
  • Total Upstream Service Time is the summed service time of all serviced upstream vehicles.
  • Total Downstream Service Time is the summed service time of all serviced downstream vehicles.
  • Mean Upstream Service Time is the mean timespan required for an upstream vehicle to be serviced.
  • Mean Downstream Service Time is the mean timespan required for a downstream vehicle to be serviced.
  • Serviced Upstream Vehicles is the total number of upstream vehicles that have been serviced.
  • Serviced Downstream Vehicles is the total number of downstream vehicles that have been serviced.
  • Total Upstream Parking Time is the summed parking time of all currently parked upstream vehicles.
  • Total Downstream Parking Time is the summed parking time of all currently parked downstream vehicles.
  • Mean Upstream Parking Time is the mean parking time required for an upstream vehicle to be serviced.
  • Mean Downstream Parking Time is the mean timespan required for a downstream vehicle to be serviced.
  • Parking Upstream Vehicles is the total number of upstream vehicles that are currently parked.
  • Parking Downstream Vehicles is the total number of downstream vehicles that are currently parked.

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 CraneSchedulingSolution which contains a sequence a list of custom moves and a schedule. Upon receiving a solution, the simulation validates the contents to some extent and applies the schedule if everything seems to be in order. 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, Amount and MovedBlockIds are defined. As only one block can be moved by a crane at a time, Amount must in this case always be 1 and MovedBlockIds must only contain a single block ID. The other fields (except Id and Type) are optional.
Each custom move must include a unique positive ID which ideally is unique during the whole run.

Agents will skip moves that they cannot perform, e.g. because they should pick up a block from a location that contains none.

The best strategy depends heavily on utilizing the crane to a high degree. Avoiding longer idling periods and conducting moves in parallel is highly recommended. A tradeoff between scheduling and stacking needs to be achieved and there should at least be one arrival and handover location that can accept a upcoming vehicles.

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 and Class. However, the class is not important yet.
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, buffer, or a handover location, and a Class, is not important yet.
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.
CraneSchedulingSolution
The collection of custom moves, as well as a move schedule that is to be executed by the crane agents. The individual custom moves are given in the list of CustomMoves.
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. The IDs of preceeding moves may be given which prevents the scheduler from assigning the move before the others are active. Note that you have to make sure not to include a cycle in those precedences, otherwise, those moves never get scheduled.
CraneSchedule
The schedule indicates which move is assigned to which crane. Cranes work on moves in the order specified in the schedule. The ScheduleNr is irrelevant and only for debugging purposes.
MoveRequest
As detailed above, the arrival and handover processes indicate that blocks are to be moved from/to the respective locations by creating a MoveRequest. The properties TargetLocationId indicates the location that block should be moved to. MoveRequests created by the upstream process always have a TargetLocationId of -1, indicating that these blocks can be stored on any free buffer location of choice. The request's BlockId denotes the ID of the block. The DueDate is not important yet.
Performance
The message describes the KPIs that are calculated from the current state of the simulation. As for the units, distances are given in meters and durations are given in seconds.
TimeStamp
A simple message that describes elapsed time in MilliSeconds.
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 Block {
   int32 Id = 1;
   int32 Class = 2;
}
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;
   double PickupGirderPosition = 4;
   int32 DropoffLocationId = 5;
   double DropoffGirderPosition = 6;
   int32 Amount = 7;
   TimeStamp ReleaseTime = 8;
   TimeStamp DueDate = 9;
   int32 RequiredCraneId = 10;
   repeated int32 ProtobufPredecessorIds = 12 [packed = false];
   repeated int32 ProtobufMovedBlockIds = 13 [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 CraneSchedulingSolution {
   repeated CraneMove CustomMoves = 1;
   CraneSchedule Schedule = 2;
}
message Location {
   int32 Id = 1;
   double GirderPosition = 2;
   int32 MaxHeight = 3;
   Stack Stack = 4;
   StackTypes Type = 5;
   int32 Class = 6;
}
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;
   int32 UpstreamBlocks = 2;
   int32 DownstreamBlocks = 3;
   int32 DeliveryErrors = 4;
   double TotalGirderDistance = 5;
   double TotalHoistDistance = 6;
   int32 ServicedUpstreamVehicles = 7;
   int32 ServicedDownstreamVehicles = 8;
   double UpstreamServiceTime = 9;
   double DownstreamServiceTime = 10;
   int32 ParkingUpstreamVehicles = 11;
   int32 ParkingDownstreamVehicles = 12;
   double UpstreamParkingTime = 13;
   double DownstreamParkingTime = 14;
   double MaxParkingDuration = 15;
}
message Stack {
   repeated Block BottomToTop = 1;
}
enum StackTypes {
   ArrivalStack = 0;
   Buffer = 1;
   HandoverStack = 2;
}
message TimeStamp {
   int64 MilliSeconds = 1;
}
message World {
   TimeStamp Now = 1;
   int32 Height = 2;
   double Width = 3;
   repeated Location Locations = 4;
   repeated CraneMove CraneMoves = 5;
   repeated Crane Cranes = 6;
   repeated MoveRequest MoveRequests = 7;
   CraneSchedule CraneSchedule = 8;
   Performance KPIs = 9;
}