Project of Fall 2017: "Cartography"

Mindstorms NXT(TM)/EV3 robots are robots made of a main unit and a set of sensors and actuators. They have been sold by Lego for several few years now, starting with the NXT version, and now with the ev3 version. Many very elaborate designs have been made using the standard kit (see for example "Mindstorms: Not just a kid's toy"). You may also watch interesting videos on youtube, such as a breakfast machine, marble conveyor, a car factory, a walking dog, a scorpion, a forklift truck, the "holononic drive", a rubik's cube solver, a printer, and a sumo game. You can also find some other nice systems on battlebricks.

The project you will work on is not as complex as some aforementioned systems, yet, it requires spending quite a lot of design and programming time on the robot and its interfaces (sensors, actuators).
Test your robot, motors, and sensors as soon as possible! We may be able to repair/order parts with a few weeks notice, but there is very little we can do the day before the competition.

Project description

The robot you have to build shall be the winner of a cartography challenge. This section includes a description of the game and then a specification of the robot.

Note that the rules might evolve during the next weeks, along with the communication protocol until the final competition.

General description

The main objective of the game is to explore an area in order to send to a server a map of the area in at most 4 minutes. A game is described as follows.

First, a game server is started. Each playing robot should register to the server with their initial coordinate. The id of the robot in the server corresponds to the id of the student group, see the group section. The initial coordinate corresponds to its starting area, see below.

Robots have 4 minutes at most to complete the cartography of the area. The area is delimited by a physical fence on at least 3 sides, and by a virtual fence on the remaining side. This virtual fence is always the only one touching the starting zone (see figure below.

The area contains movable and non-movable obstacles. A non-movable obstacle has a height and length/diameter larger than 5cm. A movable obstacle is always a red ball of diameter X. Non-movable obstacles must be represented on the map the robot has to compute, movable obstacles must not be represented on the map. If a robot pushes a non-movable obstacle, it gets a penalty.

Once a robot thinks it has completed the map, it must send it as a image matrix to the server via bluetooth. The specific bluetooth communication protocol is defined in the project repository. This repository also contains the code of the game server, and example code for ev3 robots. The server is started and configured before each gamed starts. The protocol contains a "CUSTOM" message that you may use between robots in order to send additional information.

Once a game is started, all participating robots must send their (id, x, y) information to the server every 2 seconds using a BT message (see the specification of the BT-based protocol). Position information (x, y) is given in coordinates as explained in the BT server site. Sending the message is optional only if the robot has not moved.

Robots also have the right to release at most two obstacles. These obtacles must have a minimum dimension of 6x6x6cm and maximum dimension of 10x10x10 centimeters. Whenever an obstacle is released, an "OBSTACLE" message must be sent to the BT server with the coordinates of the obstacle's final position. Similarly, robots have the right to grab all obstacles. Whenever an obtacle is grabbed, an "OBSTACLE" message must be sent to the BT server. Grabbing means the obstacle must be fully hold by the robot: pushing is not allowed for non movable obstacles.

The robot can be freely re-programmed between game rounds, but you don't have the right to add/remove lego bricks - apart from the obstacles -, sensors, etc.

Tournaments will be organized, and medals (master, diamond, platinum, gold, silver and bronze medals) will be given to robots according to their ranking. The ranking is first determined with the quality of the map, penalties and time taken are then used as a tiebreaker.

Areas to explore

The game will take place in different areas and with a variety of obstacles (bins, boxes, etc.).

The Small Stadium is explained in the next picture.

Specification of the small stadium. This stadium has a wooden fence.

Other arenas are typically a small room of Eurecom, or the end of a corridor. In the latter case, the starting fence could be a virtual fence, as explained below.

Specification of a game area. There might not be a fence between positive and negative y coordinates.

Specification of the robot

The robot must be contained in a cube of 35 cm maximum on each dimension at start-up.

Robots can use up to four sensors and up to four engines. You are free to use the sensors you want to among the following ones: touch sensor, light sensor, color sensor, ultrasonic sensor (i.e., distance sensor), compass sensor, gyroscope sensor, magnetic sensor.

The robot must contain a flag, on which the number of your group is clearly readable from at least two sides of your robot. The flag dimension is at most 10x10cm. It may also contain a logo, a drawing, and the name of the robot.

The communication protocol between robots (bluetooth) will be given (you don't have to specify it). Basically, robots communicate to a server (and possibly other robots).

A robot may change its shape (by deploying elements, or withdrawing them) during game phases, but it should fit in a 35cm cube at the start of the game.

Your robot is allowed to lose/throw parts on purpose - or not ;-) - during the game. Destructive weapons are NOT allowed. For your information, a EMP can be constructed for ~300 dollars as shown here.

It is forbidden to send orders - remotely or not - to your robot while it is playing, apart from the BT communication with the server: it must be fully autonomous as soon as the game starts, and until it ends. Trying to hijack BT messages, or other kinds of attacks is not allowed.

Competitions and reports

There are two "competitions", as described after. Your project grade takes into account the two competitions (the one in December, the one in January).

The 18th of December, 2017: your website should be started with at least the name of your robot (I don't expect more in the website for this deadline), and your robot should be able to explore the small arena, and to avoid bumping into obstacles. The four following tests will be performed alone in the small stadium:

Test #1. Small stadium: be able to explore/navigate the stadium without bumping into obstacles.
Test #2. Small stadium: be able to start from the beginner position, and send to the BT server the position of the robot while navigating in the arena.
Test #3. Be able to make the difference between non-movable and movable objects.
Test #4. Be able to release an object.

The 15th of January, 2018: final competition. For the final competition, the website must be fully completed. Also, during the final competition, I may interview each member of the group, so as to understand the contribution of each group member.

The competition will be as follows, with parallel competitions.

1-robot game in the small stadium (Linux room).
1 to 3-robot games in larger areas.

Your report consists of a website. The website shall contain the following information:

Description of the architecture of the robot: sensors and actuators, etc. Pictures of your robot on the web site would be appreciated.

Algorithms used for the two most important points: cartography strategy, handling of obstacles, competition with other robots, etc. Don't provide source code here, just try to describe the algorithms using a pseudo C language. Also, do comment those algorithms, and explain why you think they are efficient.

Source code, and instructions on how to use that source code: how to compile it, how to download it on the robot, and how to start the robot. To protect you work, you can set a password to access to the code, but make sure to give us access in order to grade it (e.g., private git repository). You could even put a fake code on your website until the very last moment ;-). I strongly advise you to rely on a versioning system (svn, git, hg) to work on the code. Also, frequently backup your code.

Videos / pictures of your robot in action [we may provide you with cameras and video recorders if necessary].

How you have worked in the group, i.e., who made what. Be clear about that. Each member of groups will get an individual grade. All members of a team must contribute to the source code. You source code must clearly indicate, with comments, who programmed which function.

Groups

(Total: 11 groups of 4, 3 groups of 3. Remaining: 1 group of 3)
(The group leader is listed first. BT address starting with 00:17).

Name of the members, name of robot and link to website, BT address.

Paolo MONTI, Martina FOGLIATO, Luca ROSSI, Valerio LANIERI. Picchio. A0:E6:F8:DC:88:B9

Camille MORIN, Benjamin CASTELLAN, Samuel PIERRE, Louis ROMAN. Robbie. 00:17:E9:F5:AF:56

Raphaël AVALOS, Thibaud LEMAIRE, Romain PARRACONE, Hugo YECHE. Defendum. A0:E6:F8:DC:88:C5

Abdelkoddous KHAMSI, Meryem GUEMIMI, Soufiane MOUTEI. InSight. A0:E6:F8:FC:BB:10

Jermaine EASTON, Berkay KÖKSAL, Ariane HORBACH, Yasmine DISSEM. Segfault. A0:E6:F8:FC:C2:59

Amund ASKELAND, Fredrik Flornes ELLERTSEN, Michele SIMILI, Jiří SKOŘEPA. Marvin. 00:17:E9:F5:B8:69

Olivier ROQUES, Erwan CULERIER, Nathan BIETTE. Claptrap. A0:E6:F8:DC:96:79

Paul FOURNIER, Pierre GIAUME, Jean-Raphael CORNEL, Grégoire PIGANEAU. A.R.E.S.. 00:17:E9:F5:B9:DE

Axel SOLL, Mariia GARETC, Natalia BALALAEVA, Vemund DAHLE. Suka. 00:17:E9:F5:AC:7D

Hugo BARBAROUX, Virgile UYTTERHAEGEN, Pawel BOSEK, Jianzhong LIANG. Optimus. 00-17-E9-F5-D0-97

Alaa BOUKHARY, Brenda FOTSA NYAMI, Janita Marielle JOHANSEN, Tristan CAMPSERVEUX. Robot_team11. 00:17:E9:F5:C2:B1

Henri AYNIE, Nino FILIU, Jean-Baptiste DURVILLE, Alix TARANTELLI. FRED. A0:E6:F8:DC:58:8B

Gautier DERVAUX, Justine DELOMENIE, Armand PERON, Mohammed SAEED. JuMAnGy. AD:E6:F8:FC:B4:B8.

Mathias Kjolleberg FORLAND, Halvor Bugge KULSRUD, Marius BJORKLI. C-ev3PO. 00:17:E9:F5:C9:DD

How do I borrow a robot?

There will be eleven groups of 4 students, and three groups of 3 students. Please, take care not to lose parts, especially cables and sensors. Also, a microsd card comes with the robot. The procedure to borrow a robot is as follows:

Make a group of 4 (or 3), and decide on a group leader.
The group leader sends me an email with the list of students of the group. List of: first_name, LAST_NAME, email. The leader shall be the first student in the list.
I will validate the group. If the group is not validated for some reason I will provide, go back to stage 1. Otherwise, go to next step. Note that I validate groups with a First Come First Served policy (Date of email sent).
Once I've answered your group with "validated", you can go to Franck Heurtematte's office, in the IT Department. You will be granted an ev3 box. Only the group leader has the right to enter in the office of Mr Heurtematte, and only during the morning or the afternoon breaks (do not go during lunch break).

Access to stadiums

Small stadium. The small stadium is located in room 52. You are free to use it whenever you want.

Other areas. You are free to test in other rooms and corridors ... but do not annoy other eurecomians ;-)

ev3

For the ev3 system, the idea is to flash on the provided SDcard a Debian GNU/Linux system. Then, you will be able to use the development language of your choice (C, python, etc.). But we ask you to develop in C.

Installing Linux on ev3

All information to install Linux on your ev3 is given here. This page also explains how to connect to your ev3 via the usb cable, bluetooth, and ssh.

Using and programming ev3

Connect to the EV3 from ssh

maker

$ ssh robot@192.168.2.2

robot

sudo

Now, update the robot with the latest packages

$ sudo apt-get update&&sudo apt-get upgrade

Install extra packages you will need for the project:

$ sudo apt-get install gcc make libbluetooth-dev

You are now ready to compile a basic example, and to run it. To do so, you first need to install the development environment on the robot:

$ GIT_SSL_NO_VERIFY=true git clone https://github.com/in4lio/ev3dev-c.git
$ cd ~/ev3dev-c/source/ev3
$ make
$ sudo make install

Now, you need to get the example. The tester file runs all 3 motors, then tests the color, touch, sonar, and compass sensors, and is provided on the project git. You can either clone the git with the code on the robot, or on your host computer.

$ GIT_SSL_NO_VERIFY=true git clone https://gitlab.eurecom.fr/ludovic.apvrille/OS_Robot_Project_Fall2017.git
$ cd OS_Robot_Project_Fall2017/

$ scp tester.c Makefile robot@192.168.2.2:

Then, on the robot, you can compile the example main file, and then run it. You need tachos and sensors to be connected to the brick if you want the program to correctly execute.

$ gcc -I./ev3dev-c/source/ev3 -O2 -std=gnu99 -W -Wall -Wno-comment -c tester.c -o tester.o
$ gcc tester.o -Wall -lm -lev3dev-c -o tester

$ make

$ ./tester

$ make run

Other examples

Sample code is also provided in the ev3c-master repository. Samples of how to control the motors and sensors are included in tester.c. The Ultrasonic Sensor is described here.

If your compass sensor does not correctly work with the test_sensor program, we provide a code specific to the use of this sensor. Use the "i2c" target of the provided Makefile to compile the file.

Other examples can be downloaded from the ev3dev C library here. Examples are provided in eg/tacho and eg/sensor.

rfcomm-client.c is an example of how to communicate with the server over bluetooth. Compile with gcc rfcomm-client.c -o rfcomm-client -lbluetooth.

If you can't get your robot working, bring it along to course staff.

Cross compilation

Basic

You may want to compile your source code on your laptop, e.g. to check the syntax of your code or to speed up the compilation process. Cross-compilation for ev3 is available as an ev3 docker image. Here is what I've made to make this work on my Linux computer:

I have first installed docker, created a docker group, added myself to the docker group, and started the docker service. Installing docker may require more than a simple apt-get, so please refer to the document of your OS, e.g. for the one for ubuntu

$ sudo apt-get install docker-engine
$ sudo groupadd docker
$ sudo gpasswd -a ${USER} docker
$ sudo service docker start

Then, I have installed the ev3 docker image:

$ docker pull ev3dev/debian-jessie-armel-cross:latest

Once done, I've created a helloworld in C:

$ cat > hello.c
#include 

int main(int argc, const char *argv[])
{
    printf("OS is fantastic!!\n");

    return 0;
}

I've compiled the file using the cross compiler provided within the docker image, and tested the generated file. The following command assumes that hello.c is located in /tmp on your host system (but you can place it wherever you want: update the following command accordingly).

$ docker run -e LOCAL_USER_ID=`id -u $USER`  --rm -it -v /tmp:/src -w /src ev3dev/debian-jessie-cross
[Shell in container]$ arm-linux-gnueabi-gcc -o hello hello.c

$ sudo apt-get install qemu-user-static
[Shell in container]$ ./hello
OS is fantastic!!

For handling the compilation for your ev3, you need to make additional stages (thanks to Paolo!):

Tag the docker image:

$ docker tag ev3dev/debian-jessie-cross ev3cc

Install ev3 lib, put them in the project directory, and start the docker image:

$ git clone https://github.com/in4lio/ev3dev-c
$ docker run --rm -it -h ev3 -v PATH/TO/PROJECT/:/src -w /src ev3cc /bin/bash

In the container, run the following commands:

[Shell in container]$ cd ev3dev-c/source/ev3/&&make&&sudo make install&&make shared&&sudo make shared-install

Another way to do

(Way suggested by Fredrik Flornes Ellertsen. Note: on our side, for the tester.c file, we had to put the exact location of included files such as ev3.h. And also we had to remove the lines that use 'ev3_brick_addr', which the compiler cannot understand)

This has been tested on native Ubuntu 17.04 and on Windows using the Windows Subsystem for Linux.

In an empty folder (here called robot_code/) on your computer, clone the ev3dev repository:

$ git clone https://github.com/in4lio/ev3dev-cs

Install the cross compiler (source: https://www.acmesystems.it/arm9_toolchain):

$ sudo apt-get install gcc-arm-linux-gnueabi

In order to compile code that links to the ev3dev-c and/or bluetooth libraries, we need to use the robot's own versions of these libraries: libbluetooth.a and libev3dev-c.a. By linking statically we eliminate the need to install anything on the robot itself. Place these files in robot_code/libraries.

Create a Makefile to simplify the compilation process. The following example Makefile expects the project to be organized like illustrated below, but will naturally depend on the group's project:

	robot_code/
		Makefile
		ev3dev-c/
		libraries/
			libbluetooth.a
			libev3dev-c.a
		include/
			bt_client.h
			messages.h
			movement.h
			sensors.h
		source/
			bt_client.c
			messages.c
			movement.c
			sensors.c
			main.c

scp

Competitions results

First tests, December the 18th, 2017

Final competition, January the 15th, 2018

Evaluation form (draft). Points and evaluation criteria could be updated during competition to better reflect the capacities of robots.

Podium