Robotix 2007

Mission Mars

The complex collective social behavior of groups of ants, each by itself performing innocuously simple tasks is a revelation of nature's hidden order embedded in all enveloping chaos. From building gigantic structures to mind boggling coordination when hunting, these aspects of swarm intelligence have led researchers to explore their applications in fields like robotics, search, navigation, and collaborative task handling.

And now, NASA has decided to mimic the ant in its future efforts to explore the belt of asteroids that lie between Mars and Jupiter and the Martian surface itself . Your task is to code robot ants which can coordinate among themselves during their mission and to help them probe as much area of the planet as possible. Time is a constraint. You may write your code in C/C++/Java. No prior knowledge of networking is required for participating in this contest.

Even better - all you need to do is to submit the code to us ONLINE.

Task

Basic Principle

The basic idea of the problem is that there will be a Server program that controls and coordinates all the Clients programs, that is, the copies of the C or Java code that you submit. Once the server starts executing, the clients will have to connect to the server, and then the server will start interacting with the clients by sending environment information and the receiving their requests.

The server that we have provided has been written by the AI Heads of the Robotix Team. Run the server as directed in the instructions. As soon as the server starts, it waits for connection requests for the clients to come in for 5 seconds. You have to run the clients, in C or in Java within that time, as many copies as you want.

After 5 seconds, all the connection requests will be acknowledged and the first environment information will be sent to each client. Then the server will start running through cycles. It will wait for 2 seconds (can be changed as written in the Specifications) for requests from the clients. After that the server will process all the requests, check validity of the moves, etc and return the new environment info or the messages to each of the clients. This getting of request and sending of information is called a cycle, and the server will run for 400 such cycles. So you will be allowed to make 400 such moves or memory read/write requests.

In the client on the other hand, all the codes required for connecting to the server through networking have been provided. So you need not have any prior knowledge of networking. You have to use this client as a template for writing your own code. You will be writing your codes in a particular function called ProcessMessage. The parameter of the function is a string which stores the information the server sends. All the processing that needs to be done is done in that function and the request string that is to be sent back to the server is generated and returned by the function.

So finally, your aim is to try to maximize the total area covered by all the bots within the 400 cycles.

Rules

General Rules

• All the bots will have the same code. This means that you have to submit only one program which will contain the code for a single bot. Your code must be written in the clients that we will provide in the different language. You have to give us the single C or C++ or Java source file which we will compile and then run 100 copies of it.

• The objective is to maximize the number of squares covered in 400 server cycles.To evaluate the teams , we will run the server and clients three times on three different maps for a specified number of bots and take the average score. For example we will run the server for 400 cycles with 20 copies of your program and calculate the number of squares covered. This is done on three different maps, which remains same for all the participants. Then we will add up the number of squares in each case and your score is the total number of squares you cover averaged over the three runs. So if number of squares covered were 6000,5000,7000 in the three runs then we declare your score as 6000.

(Note : we will decide the number of bots i.e. the number of copies, at the time of the contest which will be specified in due course.)

• The starting position of each bot is decided randomly. The starting position is such that your bot starts on a square not already occupied by a bot or an obstacle. But for the evaluation the initial position of the bots will be fixed for all the participants.

• The robot can move to any of its 8 adjacent squares in a single cycle.

• The map wraps around vertically as well as horizontally. It means that if a bot moves right from a square in rightmost column then it will land up in the corresponding square in leftmost column. Same goes for rightmost cloumn and topmost and bottommost row.

• A robot is dead if it hits a landform. Its code will be terminated.

• If one robot moves to a square that was occupied by another robot in the previous cycle, although in the end they might be in the different squares, both robots get terminated.

• If there is a collision between two robots, that is, if they move to the same square then both the robots die.

• One move of all the robots is made at the same time. Consider this situation : Two robots are in adjacent squares at time t. This rule simply implies that they cannot make a move such that their positions are swapped at time t+1. If they try to swap positions it will be considered a collision and both will be declared dead.

• A robot cannot see beyond an obstacle or another robot. In the figure below dark blue represents the environment, light blue represents the area of vision of the robot, the orange represents the robot, maroon represents the obstacle while green represents the area blocked by the obstacle.

• Each square on the Martian surface has a height factor associated with it. When a robot is on level ground (i.e. height factor zero) it can see only five squares in each of the four directions. Thus it can see an 11x11 matrix centered at its position if no obstacle is present in the region of vision. But if a robot is on a square with a positive height factor, then its field of vision will increase, i.e. it will be able to see, lets say, a 13x13 matrix around it. Conversely, if it is at a square with negative height factor, then its field of vision will be reduced, lets say, to 9x9 matrix around it.

Height = -2, visible range = 7x7, obstacles visible = 1

Height = 0, visible range = 11x11, obstacles visible = 3

Height = +2, visible range = 15x15, obstacles visible = 4

• In case the bot lands up on a square having a height factor of +3, or +4, it will be able to see above the obstacles. That is, the area that is being covered by the obstacles will be completely visible, when it is present at a height of +3 or above.

• If you expect so many robots to efficiently explore the Martian surface, there must be some sort of communication among the robots. For this purpose we have a chunk of memory, common to all the bots (i.e. that memory is shared by all the bots). All the bots can read and write to that memory, but there is a limitation. In one server cycle, a bot can EITHER read from the shared memory OR write to the shared memory OR make a move in the desired direction. When a it chooses to read the memory, then the messages in the memory is returned by the server, otherwise the environment is returned by the server. So the bot has to judiciously decide when to read/write from the memory and when to make a move.

• See the mission mars forum in the robotix forum for queries and clarifications regarding the rules. We will be posting regular updates and tutorials regarding the event on the forum. Discussions regarding the event will also be held on this forum.

Other Rules

• Each team can consist of a maximum of 4 members.

• The team members can be from different institutes or colleges.

• The right spirit of participation is expected form the participants.

• The decision of the ROBOTIX team will be final and binding.

Specifications

General Rules

• No prior knowledge of networking is required to participate in this event.

Languages

• The languages for the clients are restricted to C / C++ and Java .

• For communication with the server we will provide ready made Clients in C, C++ and Java, as a template to write the participants code. It will have all the codes required for the networking written in it. All the participant needs to do is take the input string (Server message) and generate the output string (Client request).

The Server

• For connecting to the server the client will send the message 'connect'. In response the server will send a message confirming the connection. The format of the message will be ‘connected;botid'. Here botid will be a number (greater than or equal to zero) which identifies the particular client. This part of the code for connecting to the server is already provided in the clients. The botid is directly accessible by the user, in the variable 'botid'.

• The server initially waits for 5 seconds for clients to connect, after which it will accept no further connection requests.

• In each cycle the server waits for a default period of 2000 milliseconds for incoming requests. This period can be set to any value through command line arguments. If we want to run the server with 1000 millisecond cycles then we type the following in the command prompt:

 >java Server 1000

• In each cycle only one request from each client can be processed. If a client sends more than one command then only the last sent request is processed.

The Client

• In each cycle a bot can move only one square or read from the shared memory or write to the shared memory.

• The movement commands are :

‘ n ' for moving to the square above the bot, in the vision matrix

‘ s ' for moving down

‘ e ' for moving right

‘ w ' for moving left

‘ ne ' for moving to top-right square

‘ nw ' for moving to top-left square

‘ se ' for moving to the bottom-right square

‘ sw ' for moving to the bottom-left square

‘ x ' for no movement

• The command to read the shared memory is ‘read'.

• The command to write to the shared memory is ‘write;message' where message is the string of maximum 20 bytes in length that the client wants to write to the shared memory.

• The server responds by returning the environment info for the movement and ‘write' commands. For ‘read' commands it returns the shared memory.

• Important: If you are using Java to code the client, then you must not use Java Threads in your code. We may use Java Threads to run many clients in parallel so there may be thread clashes.

Environment Information

• The environment info can be interpreted as follows:

1st byte - Size of the vision matrix (the area the bot can see). If the first byte is n (integer) then the size of the matrix is (2*n+1)x(2*n+1). So you need to convert that byte to integer to get ‘n'.

2nd byte – Separator (semi-colon)

Subsequent bytes – Row wise definition of the vision matrix

• The definition of the vision matrix has the following specifications

‘ A ' – Square at height -4

‘ B ' – square at height -3

‘ C ' – Square at height -2

‘ D ' – Square at height -1

‘ E ' – Square at height 0

‘ F ' – Square at height 1

‘ G ' – Square at height 2

‘ H ' – Square at height 3

‘ I ' – Square at height 4

‘ O ' – Obstacle

‘ R ' – Another robot

‘ S ' – Bot itself

‘ U ' – Undefined

• The bot cannot see beyond obstacles (unless it is situated on a square with a height factor greater than or equal to 3). The squares beyond the obstacles are marked undefined.

Suppose the server returns

3;EEDBOUUEDBBUUEEDBBOUEEDSCBCEEDCCBOEEEDDBUEFFEEOU

This represents a matrix of size 7x7 whose elements follow it. The matrix will be interpreted row first, that is the above message will be interpreted as the following matrix:

EEDBOUU
EEDBBUU
EEDBBOU
EEDSCBC
EEDCCBO
EEEDDBU
EFFEEOU

Shared Memory

• The shared memory is a chunk of memory common to all the bots. All the bots can read and write from it.

• The messages to be written to the shared memory can be a maximum of 20 bytes in length. The characters beyond the first 20 bytes will be ignored.

• The shared memory can hold a total of 20 messages . When the 20 message space gets filled up, older messages will start getting deleted, and replaced by newer messages.

• When a bot wants to read the shared memory, then the whole memory (i.e. maximum 20 latest messages) is returned in the following format:

msg1,cycle-cycle1; Msg2,cycle-cycle2;…

Here ‘msg1' and ‘msg2' are the messages written by two bots earlier to the read command.
‘cycle' is the current server cycle. ‘cycle1' is the server cycle when the bot wrote the message to the shared memory. ‘cycle-cycle1' is always negative.

• So basically a single message will be interpreted as the following:

Msg(20 Bytes), Relative-Cycle(4 Bytes);

Further Queries

Downloads

Files

Java Server + Java Client + C Client for linux - MM2007_JS_JC_LC.zip (25 KB)
C Client for Windows - MM2007_WC.zip (815 KB)
The updated java client (released on 9 Jan 2007). Fixed a minor bug. Please use this version.
Event rules in PDF format MissionMars.pdf

Requirements

You will require the following softwares to execute the server and the client:

Java RE 1.5 - for running the server, if you are writing the client in java, then Java SDK 1.5 is required to compile your source codes.
Visual C++ 6.0 - if you are coding in C in Windows.
GNU C Compiler (or any Linux C Compiler) - for coding in C in Linux

Instructions

To run the server:

Make sure you have correctly installed Java RE (Runtime Environment). If you have installed Java SDK (Standard Development Kit) then RE gets installed along with it.
unzip the contents of MM2007_JS_JC_LC.zip into a folder.
from the command line, go into server folder inside the unzipped folder and type the following command:
```
> java Server
```
The server will immediately start off accepting connections from the clients, and will continue to do so for the next 5 seconds. All the clients need to start off executing within this period of time.

To run the java client:

Make sure you have Java SDK 1.5 (at least) installed. Download Client.java
unzip the contents of MM2007_JS_JC_LC.zip into a folder.
Go to folder Client inside the unzipped folder.
If Java is installed in the folder C:\Program Files\Java, then to compile the java code of the Client, you have to type at the command prompt in WinXP:
```
> "c:\Program Files\Java\jdk1.5.0\bin\javac" Client.java
```
This will compile the Client.java and generate a Client.class file.
Now to run the Client.class, type:
```
> java Client
```

To run the Windows C client:

Make sure Microsoft Visual C++ 6.0 is installed on your computer. Download the VC_Client.zip
Extract the MM2007_WC.zip file into a folder. Inside the folder you will find a file "Client.dsw". Double click on that file will open the project Client in the VC++.
Compile and execute the C code from VC++. If you want to execute it from command line, then go into the Debug folder and enter the following at command prompt:
```
> Client 
```

To run the Linux C client:

Download the file MM2007_JS_JC_LC.zip.
unzip the contents of MM2007_JS_JC_LC.zip into a folder.
Go to folder Client inside the unzipped folder.
Compile linclient.c using GCC compiler or any other compiler from the command prompt as follows:
```
$ gcc linclient.c -o Client
```
To execute the client
```
$./Client
```

Submissions

All codes have to be sent to the address - robotixiitkgp+mms@gmail.com in the following formats failing which your code will be rejected. The subject of the email should be code-mm.

You should send:

A file named details.pdf (Adobe Portable Document Format) which should contain the Name of the team, the details of the each team member (name, college, department, email id, telephone number, year).
A write-up of maximum 1000 words about your idea behind the code, in a file named idea.pdf. The prize for the best algorithm will be decided using this write up by the judges.
A file named instructions.pdf stating instructions on how to run the code.
The code should reside in a folder named code.

All the files should be zipped into one file which should have a filename in the following format:

mm<team-name>.zip

For example, suppose the team name is xyz, the zipped file should be mmxyz.zip.

Submission Deadlines:

THE DEADLINE HAS BEEN EXTENDED TO 22nd JANUARY, 11:59 PM.

Preliminary Submission: 7th January, 11:59pm

All the codes submitted before this date will be compiled and the participants will be informed whether their code is running fine (satisfies all restrictions). In case their code is not compiling or running then they must resubmit their code before the final submission deadline. If someone has missed the deadline for preliminary submission then he/she can submit the code before the final submission date.

Final Submission: 22nd January, 11:59pm

The codes submitted on or before the above date are eligible for the contest. The teams who have submitted their codes before the preliminary submission deadline can resubmit their code before the final deadline. We do not take any responsibility for codes that do not compile or run which have been submitted after the preliminary deadline.

Prize Money

Results

Contact

Abhinav Sarkar
robotixiitkgp+mm@gmail.com