Home » Events

Xants

 
jQuery UI Example Page

Cash Prizes Worth INR 34,000 !!

  1. Click here for submission details.
    The last date for preliminary submissions is 18th January 2010 11:59 PM IST.
  2. Click here to download the latest version of Xants Simulator
  3. Click here to register for this event.
  4. Click here for reading the tutorial of this event.
  5. Click here to post doubts on the "Xants" Forum.
Google Groups
Email:
Receive updates and discussions in your inbox by subscribing to this group 'Xants'
 
“An Xant on the move does more than a dozing ox.”

--the Lost Droid.

Peer into the deep recesses of an ant colony and you'll discover an extremely well organized community with thousands of workers quietly going about their jobs. Understanding the subtle cues and interactions that enable small-brained insects to build elaborate communities has become a major area of research, not only for biologists but also for engineers trying to solve intricate problems in computer science, network communications and even robotics.

Xants, are a whole new breed of robots, collaborating with each other to solve the most basic problem of nature, survival.

Problem Statement

ROBOTIX, with its tradition of presenting challenging programming and algorithm intensive problem statements, brings in its tenth edition, Xants, online programming contest, where the participant has to submit the code for a Xant Robot to explore a given scenario, and to bring back as much energy for its colony in a limited period of time cycles.
Please note that this competition is entirely online, and does not require you to attend Robotix in Kshitij 2010.

The objective is simple - the entire colony needs to collect as much energy as it can during a fixed interval of time. The effectiveness with which the energy has been collected is also taken into account (as will be apparent from the scoring formula) - the survival rate of the ant colony plays a big role in the final score of the participant.

The Elements

The Living Elements


The arena contains two distinct kinds of living elements - the Xants (whose
job is to scurry about here and there, gathering energy packets) and the
Xween, whose job is to co-ordinate the Xants and ensure they actually do
something useful.
The participant, in short, is supposed to code the brains of two living
elements, the Xween and the Xant.

The Xween
    1. The Xween is the queen of the colony. Her job is to help the Xants collaborate amongst themselves effectively. Before the simulation begins it is the Xween who decides the number of Xants to be spawned.
    2. The Xween ant also holds the power to broadcast messages. These messages can then be read by the other Xants (subject to certain conditions). The broadcast messages have a fixed upper length and may consist only of alphanumeric characters.
    3. The Xween does not reside anywhere in particular - she does not take up any space on the arena.
The Xants
    1. The job of an Xant is to increase the number of energy units deposited in the Xanthill repository. It does this by finding cell with a non-zero energy units, extracting one or more units of energy from the cell and depositing them onto the Xanthill.
    2. Before the simulation begins the Xween is queried about the number of Xants to be spawned. That many Xants (subject to an upper limit) are spawned and randomly distributed inside the Xanthill.
    3. Points to be Noted
      1. Xants can pick up energy packets from a cell containing a positive number energy packets. They do this by first moving over to the particular cell and then extracting the energy packets one by one. Extracting one energy packet consumes one time cycle. On a similar vein, depositing energy packets onto a cell requires the Xant to move to that particular cell and deposit the energy packets it is carrying one by one. Depositing one energy packet consumes one time cycle.
      2. Every Xant has a maximum energy carrying capacity. Attempting to carry beyond the specified maximum capacity results in the death of the Xant. The energy packets the Xant was carrying in that execution cycle are re- deposited onto the cell the Xant was last located in
      3. Xants are allowed to drop the energy packets they are carrying anywhere in the arena. This increases the number of energy packets housed by that particular arena cell by the number of energy packets dropped. If an Xant carrying no energy units attempts to drop an energy packet onto a cell it dies. However, in this case, the number of energy packets present in that particular cell does increase by one.
      4. None of the cells inside the Xanthill will house energy packets. Energy packets dropped onto cells are immediately added to the Xanthill repository. This is the only way to add energy packets to the same.
      5. Attempting to move to a cell containing an obstacle will cause the Xant to die. No obstacles shall be present inside the Xanthill.

  1. By consuming one time cycle an Xant may move to any of four adjacent cells in the North, South, East and West directions. Direct diagonal movement is not allowed. As already mentioned, the arena wraps around in all four directions. This means if, for instance, an Xant tries to move left from any cell in the left-most column, it will end up in the cell situated in the same row in the right-most column.
  2. Once an Xant dies it is no longer available for any practical purpose. The cell occupied by it becomes free for subsequent execution cycles. The energy units that it was carrying prior to it’s demise is deposited onto the cell it was present on before dying.
  3. The Xant takes input from the arena in the form of six sense matrices. Each matrix is nothing but a square array of integers, each representing some physical property of the adjacent cells. In no case is any information about the cell the Xant is currently on supplied. There is a one to one mapping between the matrix values and the arena cells.
    1. Neighbor Matrix This is a 3 × 3 binary matrix containing information about the neighbors present in the nearby cells. A one denotes the presence of a neighbor Xant and a zero denotes absence of the same.
    2. Smelliness Matrix This is a 5×5 matrix of integers which contains the smelliness values of the 5×5 square set of cells in whose center the Xant is currently situated.
    3. Energy Matrix This is a 3×3 matrix of integers which contains the (actual) energy values of the 3 × 3 square set of cells in whose center the Xant is currently situated.
    4. Home Matrix This is a 5 × 5 binary matrix containing information about whether the Xant close to the xanthill. A one denotes the corresponding cell being a part of the Xanthill while a zero denotes otherwise.
    5. Trail Matrix This is a 3 × 3 binary matrix containing information about the trails left by other Xants in the nearby cells. A one denotes the presence of a corresponding trail-marked cell and a zero denotes otherwise.
    6. Obstacle Matrix This is a 5 × 5 binary matrix containing information about the obstacles in the nearby cells. A one denotes the presence of a corresponding obstacle and a zero denotes otherwise.

  4. Like real ants, the Xants are capable of leaving trails which the other Xants may then detect. Xants may mark the cell they are currently on to eventually leave a trail. Marking a cell does not consume a separate execution cycle. Trails are not permanent - they vanish automatically after a specific time.
  5. Communication in limited form is allowed between the Xween and the Xants. The Xween is allowed to broadcast a single message (consisting of alphanumeric symbols and of limited length) every cycle. The Xants can request for access to the contents of the most recent broadcast (reading previous broadcasts are not allowed). Reading the broadcast requires one execution cycle. On a similar vein, Xants may also send hints (also consisting solely of alphanumeric characters and of limited length) to the Xween. The Xween is informed about these hints as and when they are generated by the Xants. A point to be noted is that the such communication may take place only if the Xant is present inside the Xanthill. No communication (either ways) is possible when the Xant is situated outside the Xanthill.

    6. In short, in one execution cycle, an Xant may do at most one of the following, in conjunction to optionally choosing to mark the current cell with their trail.

    1. Move one cell North
    2. Move one cell East
    3. Move one cell West
    4. Move one cell South
    5. Pick an energy packet from the current cell
    6. Drop an energy packet onto the current cell
    7. Request access to the latest broadcast by the Xween
    8. Push a hint onto the Xween


The Gameplay

As mentioned, the game is essentially a simulation. The participant is expected to submit runnable code which shall be executed in conjunction with our simulator. The simulator essentially re-creates the above elements in a virtual world and then the game proceeds as under.

  1. The game begins with the simulator querying the Xween about the number of Xants to be spawned.
  2. The above number of Xants are spawned at random locations within the Xanthill. Energy packets are distributed throughout the arena.
  3. The simulation operates in cycles. Each cycle consists of
    1. Querying the Xants about their intentions. The Xants express their desires in terms of movement in various directions, picking or dropping energy packets and communication with the Xween.
    2. The Xween is informed about the messages sent to her by the various Xants. She is queried about he next broadcast message.
    3. All the above information is accumulated and the a net outcome (in terms of the new positions of the Xants, energy accumulated etc.) is generated. A predefined number of cycles are run and the final score is calculated.
    4. A predefined number of cycles are run and the final score is calculated.
 

 

The Arena

The event shall take place inside a virtual arena of rectangular shape. The arena shall be divided into discreet cells, each cell having integral co-ordinates with both the co-ordinates greater than or equal to zero. The exact arena dimensions will be available in the simulator.

Each cell of the arena may either be

  1. Empty

  2. Contain some positive integral amount of energy units

  3. An obstacle

Only one Xant may occupy a specific arena cell at any given point of time - trying to move to a cell already occupied by another Xant will kill the Xant which initiated the said move. A rectangular region shall exist inside the arena which shall be permanently marked as the Xanthill - it is in this region where the Xants shall be spawned and it is shall be here where the energy packets be deposited.

The Smelliness Matrix
The arena is smothered by an all-pervading smelliness matrix. Each arena
cell with the co-ordinate (x, y) has an associated smelliness value S(x, y),
calculated by the formula

Where n is the number of cells containing a non-zero amount of energy
units and (i, j) are the co-ordinates of the kth such cell. F(i, j) denotes the
number energy units contained in the cell (i, j). As it is intuitively clear
from the formula, each cell containing energy units has a linearly decreasing
smelliness field associated with it. The net smelliness value at a cell is
the superposition of all these smell values. Note that the energy packets
currently being carried by an Xant do not contribute to the smelliness values
in any way.

 

Scoring Rules

After the end of 500 time cycles, the simulation is halted, and score is calculated with following formula.

scoringrules

The 1.3b version of the Xants Simulator is up for download.




A GNU/Linux version of the same shall be uploaded soon.
This software is made available under the GNU Public License v3. In accordance to the mentioned license the source code of the same shall be made available for download after the completion of the event.


Version History:
  • 13th January: Version 1.3 b is uploaded with some additional improvements
  • 12th January 2010: Version 1.3 is released with some bug fixes.
  • 4th December 2009: Release Candidate 1.1 is uploaded with some bugfixes.
  • 29th November 2009: The release candidate is available for participants to download.
  • 14th November 2009: The Beta Version of the Simulator is up for download.

The Latest Setup Contains:
  1. XantsLaunchPad
  2. Xants Client Code (Java)
  3. Xants Client Code Python
  4. Instruction Manual to use Java Client
  5. Java Client Code Package Documentation

Please post any problems you are facing on our Forum Click Here

Here is a Video to help you get started.


‹ TribotX ChampionshipupXplode ›
»