Challenge Details

Introduction

Disaster Scotland have been allocated a special area at Edinburgh Airport to fly out the very large amounts of aid collected for the Phrygian Earthquake disaster. Each type of aid is packed into a large metal container for easy transportation. Here are examples of the types of container:

           Antibiotics, Blankets, Children's clothing, Milk powder, 
             Oatmeal, Surgical supplies, Tents, Water-purification tablets

Airlines have made a cargo plane available, and a local company have given them free use of two Autonomous Robot Loaders, (ARLs), state-of-the-art robots that can automatically find a container of the specified type if given its position in the storage area and load it onto the aircraft. They have built-in navigation that means they do not get in each other's way. The aircraft can take 10 containers on each flight. The Challenge is to build a system that will output a set of instructions to the ARLs so that the most urgent aid is packed into the aircraft as quickly as possible for a given flight.

The storage area has room for rows of 6 containers each. For more than 6 containers, lorries stack new arrivals on top of the ones already there. Due to safety restrictions and the lifting range of the ARLs, stacks must be no more than 4 containers high. If more than 24 containers have arrived, lorries will have unloaded the new ones behind the row already there and then stacked onto those. Of course containers can only be stacked on the ground or another container, and can only be unstacked if no other container is on top or in front of them.

Lorries stack all the containers in the storage area in no particular order, and your work starts when all the containers have arrived with a list from the on-the-spot team in Phrygia of which 10 containers they need most urgently. This could vary from a whole plane-load of antibiotics to a number of different types of containers.

Challenge

The challenges are:

Individual submission :

build a system that :-
- Shows the initial state of the storage area: how many of what sort of crates and how they are stacked.

Your program should be able to handle the following cases:

There are 6 or fewer containers in which case they are all loaded into the cargo plane in any order

There are 10 or fewer containers, in which case all of them are loaded into the cargo plane in an order determined by how they were stacked

There are more than 10 but at most 24 containers and unstacking is needed to access the 10 required containers. Unstacked containers may be placed on any pile with fewer than 4 containers in it or on the ground in front of the first row.

There are more than 24 containers and some containers needed may be in the back row

Stacking and unstacking takes time (one time unit per action) and time is of the essence: better programs are those that produce shorter sequences of actions.

Group submission :

extend the individual submission to enable :-

A graphical simulation of the loading process.

Assessment criteria will include the design and ease of use of the system.

Format

Test storage area layouts will be provided as text files. Each container has a unique non-zero integer ID number and a code for its contents. Here are the codes:

A == Antibiotics

B == Blankets

C == Children's clothing

M == Milk powder

O == Oatmeal

S == Surgical supplies

T == Tents

W == Water-purification tablets

- == no container

The loading area can be imagined as a grid and the starting layout is represented from the front row, nearest to the ARLs, backwards. Each row starts with a row number, and is followed by six codes for each layer that has any containers in it. It is terminated by the character '*'. A 'no container' entry has a 0 as its ID number.

The layout of the loading area is terminated by '***' and followed by the request for containers, in the form:

 n1n2...n8

where n1 is the number of containers of Antibiotics, and so on to n8, the number of containers of Water-purification tablets. The total specified will be 10.

So an example of input data for two rows, where row 1 is closer to the ARLs and row 2 is behind it, and for an order of 10 containers following it, would be:

1
1A2B3C4M5O6S
7T8W0-0-9A10B
11C0-0-0-12M13O
*

2
14S15T16W17A18B19C
20M21O22S0-0-0-
***
50002120

The instructions generated for the ARLs are either to Unstack or Stack a container, and must include the following information:

Which of ARL-1 and ARL-2 the instruction is for

Stack or Unstack

The ID of the container

What type of aid it contains

The location it is being unstacked from or stacked to: row, column, layer or the aircraft

So instructions could look like this for example:

ARL-1 unstack container 1 Blankets at row 2 col 3 slot 3

ARL-1 stack container 1 Blankets at row 2 col 1 slot 2

ARL-1 unstack container 13 Oatmeal at row 2 col 3 slot 2

ARL-1 stack container 13 Oatmeal at Cargo Plane

Exactly how you display the instructions is up to you but lining up the instructions for ARL-1 and ARL-2 in columns would make it clear where the two of them were working simultaneously.

Guidance

This robot planning problem can be split into deciding which container to select and then what stacking and unstacking may be needed to get at it. It is important to keep a representation of where everything is (the 'state space') after each projected action while a sequence is being constructed in case it doesn't work out and the program has to backtrack and try something else. So each action in a sequence must be related to the state in which it was chosen and point to the state it will produce. An array is an obvious way of representing the state-space, while actions and sequences of actions might be better represented as objects in a list, though arrays would also work.

Note though that the conditions under which a stack or unstack can be carried out are generic. To unstack, the selected container must be clear of other containers at its top and front and the ARL must not be currently carrying a container. To stack, the ARL must be carrying the container to be stacked and the chosen position must be clear to the front and top and have the ground or another container below it, or be the aircraft. In the same way the consequences of stacking and unstacking are also known.

Quicker loading will take place if both ARLs can work at once, but then the two sequences must be compatible so that one ARL doesn't move a container the other was going to pick up.

Good sequences will be as short as possible and be evenly divided over the two ARLs. They must respect the constraints:

containers can only be unstacked if on the top of a pile with nothing in front of them

containers can only be stacked on top of another container, on the ground or in the aircraft

piles can be no more than 4 containers tall

An ARL can only move one container at a time.

ARLs cannot pick up the same container at the same time and one of them cannot stack onto a container the other ARL is unstacking

There are two obvious approaches to the interface:

command line: user enters textual commands/details and system displays textual responses.
graphical user interface (GUI): user deploys menus/buttons/text fields to select actions/ enter details, and system uses text/graphics to display responses.

It might be interesting to generate several different sequences and then pick the best.

How to enter

Entries will be accepted only from schools that have registered: each may submit one individual entry and one team entry where the team has no more than four members.

The competition rules are available here and all entrants will be assumed to have accepted them.

Click here to register using the online form.

Important Dates

Registration starts: 5th July 2010

Challenge starts: 23rd August 2010

Submission: 13th-17th December 2010

Results: 4th April 2011

Information/Contact

email: challenge@macs.hw.ac.uk