Darkness 2005-05-11 09:00:00 UTC
 
Twilight 2005-05-12 09:00:00 UTC
 
Daylight 2005-05-13 09:00:00 UTC
 
Finish 2005-05-18 09:00:00 UTC

Ants - Rules

Arrow_down  Download Sample Code

This is the tenth MATLAB Online Programming Contest.

The Problem

Imagine a sandbox in which there are ants, sugar cubes, anthills, and rocks. Ants like sugar: collectively they want to bring as many sugar cubes as possible back to their anthills before sunset.

For this contest, you will write the control program used by each ant. Ants, being so small, have some limitations. Each ant can carry no more than one sugar cube at a time. Further, each ant can only see her local vicinity. Your program, which is run sequentially for each ant, knows only what that ant knows. Thus you must bring about the best possible global outcome based only on local conditions. The ants don't have any memory as such, but they can leave behind a chemical trail to guide themselves and others across the sandbox landscape.

Your score is determined by how much progress you make moving food towards and into the anthills. Ideally your ants will move all the sugar cubes into anthills. Practically this may not be possible; do the best you can. You receive credit even when you move a single sugar cube one step closer to an anthill.

Some considerations:

  • There may be any number of ants, anthills, sugar cubes, and rocks.
  • At each time interval, every ant runs the ant controller program.
  • An ant can carry no more than one sugar cube at a time.
  • A single square can contain multiple ants and multiple sugar cubes
  • For each turn, an ant can move a maximum of one square horizontally and one square vertically (i.e. diagonal motion is possible).
  • There is a limited number of time intervals (1000) before sunset.
  • Every ant has the opportunity to mark the square they are leaving with a number (0-100) that corresponds to a chemical scent
  • The scent deposited by ants on a single square is cumulative without bound. If five ants put a scent of 10 on a single square in the same time interval, that square will have a scent of 50 by the end of the turn.
  • Chemical trails dissipate over time. All scent is decremented by one each time interval.

Example

Here is a sample map that an ant might face.

The full 9x10 map is shown, but the ant only "sees" the 5x5 subset of the map indicated by the red outline. In this case, food is available on this map in two locations, but the ant has no knowledge of the food in the upper right corner. It is simply beyond her current horizon.

The ant controller code is called with four input arguments and must return four output arguments. 

[dy,dx,mark,carry] = ant(mainMap,foodMap,antMap,scentMap)

The inputs are all 5x5 matrices of integers with the ant at the (3,3) center location.

mainMap
Location of anthills (shown as 1) and impassable regions (-1). Open space is given by 0.
foodMap
Location of any sugar cubes. The number represents how many sugar cubes are at that location.
antMap
Location of any ants. There will always be at least 1 at location (3,3).
scentMap
Where and how much chemical scent has been deposited. The number in each cell is decremented by one every time interval (all ants get the chance to move before the completion of one time interval).

The outputs are all scalars.

dy
Delta in rows (-1 is up or north, 0 no move, 1 is down or south)
dx
Delta in columns (-1 is left or west, 0 no move, 1 is right or east)
mark
Scent left by the ant, any integer between 0 and 100
carry
Logical indicating if the ant will carry one unit of food or not.


If we step through this example, we get the following problem inputs (for the sake of readability, zeros in the following matrices are shown as dots). 

mainMap = [ .  .  .  .  . ]     foodMap = [ .  .  .  .  . ]
          [ .  .  .  .  1 ]               [ .  .  .  .  . ]
          [ .  .  .  .  . ]               [ 2  .  .  .  . ]
          [ .  .  .  .  . ]               [ .  .  .  .  . ]
          [-1  .  .  .  . ]               [ .  .  .  .  . ]

 antMap = [ .  .  .  .  . ]    scentMap = [ .  .  .  .  . ]
          [ .  .  .  .  . ]               [ .  .  .  .  . ]
          [ .  .  1  .  . ]               [ .  .  . 10  9 ]
          [ .  .  .  .  . ]               [ .  .  .  .  . ]
          [ .  .  .  .  . ]               [ .  .  .  .  . ]

Based on the information available to the ant, we want to move west, towards the two nearby sugar cubes. Accordingly we issue the following commands. 

dy = 0
dx = -1
mark = 10
carry = 0

We are leaving a scent trail marker of ten to show where we've been. Since we're not in a square with any sugar cubes, there is no need to set the carry bit.

Inconsistent outputs

  • Setting the carry bit to true when there is no food present does not cause an error.
  • If dx and dy are set such that the ant will move into an obstacle, there is no error, but no move occurs.

Passing information

You're not allowed to explicitly pass information from one ant to the next through the use of programming techniques, like persistent variables, global variables, or similar. The challenge in this contest is to find ways to externalize information using smell or the like.

Scoring

The overall score for your entry is a combination of how well your algorithm does and how fast it runs on a multi-problem test suite. How well your algorithm does (which we call the "result") is determined by how thoroughly you move all the sugar cubes to the anthills. At the end of the total available simulated time, your result will be determined by calculating the aggregate improvement in the total Euclidean distance of all sugar cubes to the nearest holes.

In the example above, there are two sugar cubes at location (r=5,c=2), one sugar cube at location (r=1,c=8), and an anthill at location (r=4,c=6). The result is currently 

2 * sqrt((6-2)^2 + (4-5)^2) + sqrt((6-8)^2 + (4-1)^2) = 11.85

If the ant in the diagram picks up one of the two sugar cubes to the left of the anthill and moves it one column closer to the anthill (east), the overall result would be improved (lowered) to 

sqrt((6-3)^2 + (4-5)^2) + sqrt((6-2)^2 + (4-5)^2) + sqrt((6-8)^2 + (4-1)^2) = 10.89

The best possible result is zero.

The average result for the entire test suite, along with the associated runtime of your entry, gets passed to our scoring algorithm before returning a final score, according to the equation

We don't publish the values k1, k2, and k3, but they aren't hard to figure out. Your entry will time out and be disqualified if it takes more than 180 seconds (three minutes).

Developing Your Entry

The files you need to get started on the contest are included in a ZIP-file available on the MATLAB Central File Exchange. If you download and uncompress this ZIP-file, you will have the files described below.

The ant control routine is solver.m. 

[dy,dx,mark,carry] = solver(mainMap,foodMap,antMap,scentMap)

Keep in mind that this function must have the right signature: four input arguments, four scalar output arguments. Variable names are unimportant. To test this function with the test suite in the ZIP-file, run runcontest.m. 

>> runcontest

Code Length Limitation

The column in our MySQL database that stores the M-code is of type text, which is limited of 65535 characters. It will truncate code above that limit.

Collaboration and Editing Existing Entries

Once an entry has been submitted, it cannot be changed. However, any entry can be viewed, edited, and resubmitted as a new entry. You are free to view and copy any entry in the queue. If your modification of an existing entry improves its score, then you are the "author" for the purpose of determining the winners of this contest. We encourage you to examine and optimize existing entries.

We also encourage you to discuss your solutions and strategies with others. You can do this by posting to the comp.soft-sys.matlab thread that we've started from our newsreader.

Fine Print

The allowable functions are those contained in the basic MATLAB package available in $MATLAB/toolbox/matlab, where $MATLAB is the root MATLAB directory. Functions from other toolboxes will not be available. Entries will be tested against MATLAB version 7.0.4 (R14sp2).

The following are prohibited:

  • MEX-files
  • Java commands or object creation
  • eval, feval, inline, function handles, etc.
  • Shell escape such as !, dos, unix
  • Handle Graphics commands
  • ActiveX commands
  • File I/O commands
  • Debugging commands
  • Printing commands
  • Simulink commands
  • Benchmark commands such as tic, toc, flops, clock, pause
  • error, clear, persistent

FAQ

Check our FAQ for answers to frequently asked questions about the contest.

About named visibility periods

Contests are divided into segments where some or all of the scores and code may be hidden for some users. Here are the segments for this contest:

  • Darkness - You can't see the code or scores for any of the entries.
  • Twilight - You can see scores but no code.
  • Daylight - You can see scores and code for all entries.
  • Finish - Contest end time.