Algorithms

Cartography strategy

We decided to proceed with two steps. First, we try to identify the boundaries in order to construct a map with the right size. After that we scout the stadium line by line. In case we meet an obstacle we draw the boundaries of the obstacle and then we go back to the line we were in but after the obstacle in order to continue our exploration.

Find the size of the stadium by finding the boundaries

source code :
while not initial position {
    while there is no obstacle in front of us // not a new boundary {
        start_boundary_x = x_position
        start_boundary_y = y_position;
        move(1s, forward)
        end_boundary_x = x_position;
        end_boundary_y=y_position;
        registerInLinkedListAllPositions(start_boundary_x, start_boundary_y, end_boundary_x, end_boundary_y)
        rotate_car(90, right)
        if(boundary still there) {
            rotate_car(90, left)
            start_boundary_x=x_position;
            start_boundary_y=y_position;
        }
        else { //the boundaries do not form a rectangle, it turns to the right
            move(1s, forward)
            if(there is an obstacle){ //the boundary turns slowly to the right, we already reached it
                find_right_angle_obst() //we turn the robot to be in front of the boundary with a 90 degrees angle
                rotate_car(90, left) //to be able to follow the boundary
            }
            else {
                rotate_car(right) //it turned stronger
                move(infinite, forward) //until we meet an obstacle
                find_right_angle_obst()
                rotate_car(90,left)
            }
            start_boundary_x=x_position;
            start_boundary_y=y_position;
        }
    }
    rotate_car(90,left) //change boundary
}
XMAX=findMaxX(linkedList)
YMAX=findMaxY(linkedList)
map=createMap(XMAX, YMAX, linkedList)

Scouting or how to explore the whole stadium

pseudo code :
// in all our codes we suppose that we are starting by going to the right of the stadium

void scouting(){
    bool goingRight= true
    while(notFinished){
        move(infinite, forward) //move until the robot meet an obstacle
        setThePositionsWeWentThroughToTheMapAsExploredAndEmpty
        if(our map says the obstacle in front of us is known as boundary) {
            moveBack //to have enough place to rotate
            rotate_car(90, goingRight)
            move(shortTime, forward)
            setThePositionsWeWentThroughToTheMapAsExploredAndEmpty
            rotate(90, goingRight)
            changeGoingRight
        }
        else if (there is an obstacle) {
            int obstacleType=distinguishObstacle()
            addThisPositionOnMap(map,x,y,obstacleType)
            getAround(obstacleType)
        }
    }
}

Handling of obstacles

Detect an obstacle

pseudo code

read value from UltraSound Sensor
if(distance < threshold or touching /*side Bumpers*/){
return true
}
return false

Distinguish the different type of obstacles

First version, needed to distinguish all types and there were only teacher's obstacles.
pseudo code :

int distinguish_obstacle()[
    read sensors
    if red{
        return MOVABLE
    }
    sleep
    read sensors
    if(difference of distance between before and after the sleep > threshold) {
        return ROBOT
    }
    if (isSizeMoreThan(45)) {
        return BOUNDARIES
    }
    return UNMOVABLE
}

bool isSizeMoreThan(45){
    find_right_angle_Obst() //put the robot at 90 degrees with the obstacle
    rotate(90, left) //be parallel with the obstacle
    move 45 cm forward
    if(we could do the entiere move){
        rotate(90,right)
        read sensors
        go to the initial position (rotate(90,R); move(45cm, forward);rotate(90,L))
        if the obstacle is still there {
            return true
        }
        else : return false

   }

    if stop before the end because there were another obstacle{
        go to initial position and try the same with the other side
        if move is done entierely : check if the obstacle is still there, go to initial position and send true or false like before
        else :
            go to initial position
            return true //because in this situation it is very likely a corner with boundaries
}

Second version is called only if we know that the obstacle is not a boundary according to our map.
pseudo code :

int distinguish_obstacle(){

    read sensors
    sleep
    read sensors
    if (distanceBefore and after sleep > threshold) : return ROBOT
    if color = red{
        if intensity>=3 : return MOVABLE
        return UNMOVABLE //object realeased by us or an opponent
    }
    return UNMOVABLE

}

To check if the detected obstacle is bounday, we look into the map for an area in front of the position of the robot depending on the ultra sound reading.

Get around an obstacle

The goal is here is get around a detected obstacle and back to scouting the whole map. More precisely it's about get around the obstacle and getting back to the same y coordinate with the same orientation and repeat scouting. To do that, similarly to detecting boundaries, on each side the robot moves aalong the obstacle and checks if the obstacle is still here. If not the robot will try thr get to the other side of the obstacle until the last side. The pseudo code:

void limitObst(int obstacleType){
move 3cm back from the obstacle
rotate 90 left if going right, right if going left
while (not same y coordinate as begining and abs(angle - initial angle)!=180){
move forward 5cm
rotate towards the obstacle
if (the obstacle is still here)
rotate away from the obstacle
else //go away from the corner of the obstacle
rotate away from the obstacle
  move forward 5cm
  rotate towards the obstacle
  move forward 10cm
if obstacle encountered on the way //We were too far from the obstace or the obstacle is round
  rotate away from the obstacle
continue //
else
continue // not rotating will make the robot change side
}
}

Exemple of scouting and handling obstacle

Competition

For the competition we only added a few things :
    - First, we consider that it is possible to meet an obstacle that turns out to be a robot. For this case we just supposed that the robot will move and so in the distinguish obstacle function (see before) we wait a little and see if there is still an obstacle or not. If not it was a robot. In this case, we wait a little more and then we continue the scouting we were doing.

    - For the big stadium, we first try to draw the boundaries, but it is possible to meet a robot. Fortunately, we know the dimensions of the first one so if we meet the robot before reaching the end of this one we just wait and then continue (we are still supposing that the opponent's robot will move). If it is after this boundary, as we check twice if there is an obstacle we will realize that it is gone and do not take it into account. Otherwise, we may suppose that the boundary was not straight.

   - Then, we also considered the possibility of release and catch obstacles. That's why add the beginning for the small stadium and after drawing the boundaries for the big stadium we realease our obstacle. The aim is to be close to a boundary in order to be more difficult to detect for an opponent.