Applied Algorithms Project (2022-2023)

General presentation

In this project, the objective is to save the cities of a region from a fire. The goal is to place firefighters intervention points to prevent the fire from reaching the cities. This project will take place in several steps:

  1. Problem modeling;
  2. Implementation of algorithms solving the problem: brute force, progressive algorithms, approximation, etc...;
  3. Test your algorithms on various instances;
  4. Possible extensions.

About the organisation:

Problem

We start from a simplified image of the region with few colors, representing the inhabited areas (to be protected, but the firemen cannot intervene inside a city without causing damages), water areas, inaccessible for fire and firefighters, and agricultural or forest areas, accessible to both.

Some red pixels are added, representing fire starts. To simplify the problem, we assume that the fire propagates only in a straight line and therefore cannot go around an obstacle. Moreover, we can assume that the flames prevent the firefighters from getting too close to the fire. A firefighter can fireproof an area with a fixed radius around his position.

The goal is to save all the cities with as few firemen as possible. You will have to send back the image to which the pixels corresponding to the intervention positions of the firemen are modified.

The files at hand

The input and output images are in PPM format and accompanied by a text file.

PPM format

PPM format (standing for Portable Pixmap) is a very simple way to describe an image in textual form. In our case, it will be ASCII files of this format (see Wikipedia), with a storage corresponding to a row-major order (see Wikipedia):

P3 #PPM ASCII file with RGB format
# Created by GIMP... #We will work with GIMP pictues, that have this comment
3 2 # the picture has 3 columns and 2 ràws
255 # each R, G and B component is represented by an integer between 0 and 255
255 255  0
0    0   0
0    0  255 # end first row
255 255  0
0    0  255
255  0   0  #  end second row

Configuration file

associated to the PPM file, there is a confuguration file config.txt indicating:

The number of angles is an integer that discretizes the angles, we consider na rays starting from each fire start. It is up to you to choose a suitable value.

the radius of the fire (minimum distance at which one can approach the fire start)rf and the radius of action of a firefighter rp are two foats of value at least 1 pixel.

Finally, we define indices for each type of area whose interpretation is set below, and for each index, we associate a color of the image.

This is an exemple of configuration file, available here: config.txt

700             # number of angles
4.5             #radius of the fire
1.6             #radius of action of a firefighter
0 255  0   0    # red: Fire
1  0  255  0    # green: FireFighter position
2  0   0   0    # black: City
3  0   0  255   # blue: Inaccessible
4 255 255  0    # yellow: Free

Note that the green pixels (index 1) concern only the solution image.

A concrete example

Here is a concrete example of an area plan in Gironde.

This image has been greatly simplified (image creation steps will be explained later) to a smaller image in PPM format, download here.

If we open this file, one of the things we see is that the image is of size 100*100 : the first 100 triples represent the first row, triples 100 to 200 the second row and so on. This image contains 4 different colors:

  1. (255,0,0) : red ;
  2. (0,0,0) : black ;
  3. (0,0,255) : blue ;
  4. (255,255,0) : yellow ;

We can see that the blue color represents water areas, the black color represents city areas and the yellow color represents forest and agricultural areas. There are two fire starts: the red pixels.

It can be associated with the configuration file proposed as an example above, downloadable here.

Creating new PPM pictures

You can easily create other instances of your choice. Here is some help on how to create this kind of image in GIMP.

!!! Be careful, GIMP introduces a comment line in the second line, and by default it is assumed that this line is present. If you create ppm images in any other way, be aware of the possible offset.

  1. Go to uMap then click on “Créer une carte” ;
  2. Change the map background (vertical menu on the right) and choose a background on which the areas to be identified have fairly contrasting colors (for example OSM-Hydra);;
  3. take a screenshot of the desired area in a file.png file..

From this image, we will create a simplified one in GIMP, so to start, open file.png with GIMP ;

Then you will certainly have to decrease the number of pixels in the image. In order to do this:

  1. Image > Échelle et taille de l'image
  2. choose a value for the width (Largeur) ot the heigth (Hauteur), for exemple 100;
  3. Mise à l'échelle;
  4. Affichage > Zoom > choose an appropriate zoom value among those proposed.

You will then have to decrease the number of colors to reach the 3 basic ones (City/Inaccessible/Free):

  1. Image > Mode > Couleurs indexées ;
  2. “Générer une palette optimale” and choose the maximum number of colors. As there are many elements on the image, it is almost impossible to take 3 colors directly and get something close to the desired result. It is therefore preferable to proceed in stages, starting by reducing to 5 colors (for example).
  3. It is possible to modify the RGB values of each of the remaining colors, which allows to group colors (for example put the roads in the same color as the forests), and to choose the desired colors for each type of area in the final image for that:
  4. Image > Mode > RVB ;
  5. Image > Mode > Couleurs indexées ; This time choose 3 as the maximum number of colors. You can again change the RGV values of the colors to your liking.

Finally, to export the image in PPM format:

  1. Fichier > Exporter sous > file.ppm > Exporter ;
  2. choose ASCII.

You will then need to run the following command from a terminal:

foo@bar:~$ awk '{ ++x; if(x<=4) print $0; else { l1=$0; getline; l2=$0; getline; print l1 " " l2 " " $0; }}' file.ppm > res.ppm

We will obtain the final PPM file in a file named res.ppm. Here, the x<=4 means that the color of the pixel of coordinates (0,0) is on line 4 of file.ppm.

First report

We ask you to write a small report (text or PDF file) explaining:

Deadline: Friday, September 30th

Second report

We ask you to write a small report (text or PDF file) explaining:

Deadline: Friday, October 28th

Final report and Defence

We ask you to send your final report (PDF format) by January 16th. The defenses will take place on January 19th (CREMI, room 201) and will last 20 minutes per group. The presentations and questions/answers can be in French or English. The times for each group are:

We ask that you discreetly enter the room 10 minutes before your time and log on to a computer in order to avoid any loss of time. You will have to quickly present what you have done, we will then ask you questions about your project. You can use slides, but it is not mandatory.