Algorithmie et programmation
L'algorithmie est à la base de n'importe quel comportement de n'importe quel robot. En effet, le robot suit des instructions préalablement initialisées dans un programme. Ce programme, c'est ce que l'on appelle un algorithme.
De manière très simple, on peut comparer un algorithme à une recette de cuisine: il s'agit d'une suite d'instructions, qui, à partir de données, permettent d'obtenir des résultats clairement définis ou en un nombre fini d'étapes. Ainsi, en prenant l'exemple d'une recette de galettes au beurre, les données sont les ingrédients: 250g de beurre, 250g de farine, 250g de sucre, 5 oeufs etc; les instructions correspondent à celles données par la recette: casser les oeufs puis les mettre dans un saladier, ajouter le sucre, puis le beurre fondu... qui aboutissent à notre résultat défini: les galettes.
On divise donc un algorithme, ou programme, en trois parties successives :
1) ENTRÉE: les données
2) TRAITEMENT: les instructions
3) SORTIE: le résultat
Exemple:
De manière très simple, on peut comparer un algorithme à une recette de cuisine: il s'agit d'une suite d'instructions, qui, à partir de données, permettent d'obtenir des résultats clairement définis ou en un nombre fini d'étapes. Ainsi, en prenant l'exemple d'une recette de galettes au beurre, les données sont les ingrédients: 250g de beurre, 250g de farine, 250g de sucre, 5 oeufs etc; les instructions correspondent à celles données par la recette: casser les oeufs puis les mettre dans un saladier, ajouter le sucre, puis le beurre fondu... qui aboutissent à notre résultat défini: les galettes.
On divise donc un algorithme, ou programme, en trois parties successives :
1) ENTRÉE: les données
2) TRAITEMENT: les instructions
3) SORTIE: le résultat
Exemple:
Pour écrire un algorithme, il nécessaire de procéder à trois étapes :
- analyser le problème posé
- écrire un algorithme en language naturel
- traduire dans un language que comprend la machine
C'est le métier des programmateurs que ce soit dans le domaine de l'informatique, de la recherche ou de la robotique.
Prenons un exemple concret: on souhaite sortir de ce labyrinthe :
- analyser le problème posé
- écrire un algorithme en language naturel
- traduire dans un language que comprend la machine
C'est le métier des programmateurs que ce soit dans le domaine de l'informatique, de la recherche ou de la robotique.
Prenons un exemple concret: on souhaite sortir de ce labyrinthe :
Le problème est donc: comment sortir de ce labyrinthe en créant un programme simple ?
Le suivant, écrit en language naturel, semble être une solution des plus simples :
- entrez dans le labyrinthe
- posez la main droite sur le mur de votre droite
- lâchez le mur et sortez du labyrinthe.
Il ne reste plus au programmateur qu'à traduire cet algorithme dans le language de sa machine, si il veut créer un robot capable de sortir de n'importe quel labyrinthe par exemple.
À l'image de notre exemple, on se rend compte que l'algorithmie peut devenir très vite complexe.
• La réalisation de certains problème nécessite la mise en place d'un test pour effectuer une tâche :
- si le test est positifif, on effectue une tâche,
- si le test est négatif, on effectue une tâche différente ou on passe à la suite.
L'exemple suivant, un robot qui doit avancer jusqu'à ce qu'il rencontre un mur, contient une condition.
Exemple : avancer jusqu'à rencontrer un mur (Vidéo)
Le suivant, écrit en language naturel, semble être une solution des plus simples :
- entrez dans le labyrinthe
- posez la main droite sur le mur de votre droite
- lâchez le mur et sortez du labyrinthe.
Il ne reste plus au programmateur qu'à traduire cet algorithme dans le language de sa machine, si il veut créer un robot capable de sortir de n'importe quel labyrinthe par exemple.
À l'image de notre exemple, on se rend compte que l'algorithmie peut devenir très vite complexe.
• La réalisation de certains problème nécessite la mise en place d'un test pour effectuer une tâche :
- si le test est positifif, on effectue une tâche,
- si le test est négatif, on effectue une tâche différente ou on passe à la suite.
L'exemple suivant, un robot qui doit avancer jusqu'à ce qu'il rencontre un mur, contient une condition.
Exemple : avancer jusqu'à rencontrer un mur (Vidéo)
Comme je l'ai expliqué, si le robot ne rencontre pas un mur, il continue d'avancer. Au contraire, si il en rencontre un, il s'arrête.
• La réalisation de certains problèmes nécessite la mise en place de tâches répétitives, on parle alors de boucle.
Le programme suivant, écrit en langage naturel, en contient une :
- Choisir un nombre
- Le multiplier par 1, puis 2, puis 3... jusqu'à 30.
- Afficher le résultat.
Écrit en language de calculatrice, on aboutit au programme suivant :
ENTRÉE
n est de type nombre
i est de type nombre
TRAITEMENT
Prompt n
Pour i, allant de 1 jusqu'à 30
Faire n x i
Fin Pour
SORTIE Afficher le résultat
• Tant qu'une certaine condition est vérifiée, les instructions sont répétées. La boucle s'arrête lorsque la condition est remplie. L'exemple du laybinthe s'inscrit parfaitement dans ce cas (tant que vous n'avez pas atteint la sortie, longez systématiquement le mur, ne le lâchant jamais de votre main droite).
On peut très vite faire face à des erreurs en algorithmie, par exemple lorsqu'il a été mal construit, on peut aboutir à ce que l'on appelle des boucles infinies, source de bug. La définition d'une boucle infine par wikipedia est la suivante: une boucle infinie est, en programmation informatique, une boucle dont la condition de sortie n'a pas été définie ou ne peut être satisfaite. En conséquence, la boucle ne peut se terminer qu'à l'interruption du programme qui l'utilise.
En robotique, il s'agira alors d'une boucle dont la condition ne peut être satisfaite et qui va résulter un bug dans le programme du robot.
La situation suivante crée une boucle infinie :
i=0
Tant que i < 10 :
i=1
En effet, la boucle se termine lorsque i n'est plus inférieur à 10, or l'instruction présente dans la boucle donne toujours à i la valeur 1 ; la condition d'entrée de la boucle est donc toujours vraie.
Dans l'exemple ci-dessous nous avons une boucle infinie, le robot ne s'arrêtera jamais de monter des marches car la variable qui est testée dans la condition n'est jamais incrémentée :
nombre_marches = 0 ;
tant que nombre_marches < 60
monter_une_marche
En effet, le nombre de marches reste toujours à zéro. Pour que le robot s'arrête au bout de 60 marches, il aurait fallut dire, après "monter une marche", "le nombre de marches prend la valeur n + 1" en supposant que le nombre de marche soit n.
Il s'agit ici des règles de bases en algorithmie. On imagine bien que l'algortihme définissant le comportement d'un robot complet est bien plus complexe.
Voici un exemple de programme en tant que tel pour le robot Thymio II. Ce programme lui permet d'éviter tout obstacles et de détecter le vide. Il avance continuellement.
VARIABLES/ENTRÉE
var temp
var temp2
var speed=200
var vmin=-600
var vmax=600
var l[8]
var led_state=0
var fixed
var led_pulse
timer.period[0]=20
TRAITEMENT
onevent buttons
when button.forward==1 do #augmenter la vitesse
speed=speed+50
if speed>500 then
speed=500
end
end
when button.backward==1 do #diminuer la vitesse
speed=speed-50
if speed<-300 then
speed=-300
end
end
when button.center==1 do #arrêter le robot
speed=0
motor.left.target=0
motor.right.target=0
end
call leds.top(temp, temp, 0) #les lumières s’allument
end
onevent prox
#Pour éviter les obstacles
if speed >0 then
temp=(prox.horizontal[0]*1+prox.horizontal[1]*2+prox.horizon tal[2]*3+prox.horizontal[3]*2+prox.horizontal[4]*1)
temp2=prox.horizontal[0]*-4+prox.horizontal[1]*-3+prox.horiz ontal[3]*3+prox.horizontal[4]*4
motor.left.target=speed-(temp+temp2)/(2000/speed)
motor.right.target=speed-(temp-temp2)/(2000/speed)
elseif speed < 0 then
temp=-300/speed
motor.left.target=speed+prox.horizontal[6]/temp
motor.right.target=speed+prox.horizontal[5]/temp
call math.min(motor.left.target, motor.left.target,vmax)
call math.max(motor.left.target, motor.left.target,vmin)
call math.min(motor.right.target, motor.right.target,vmax)
call math.max(motor.right.target, motor.right.target,vmin)
end
#Pour détecter le vide
if prox.ground.reflected[0]< 130 or prox.ground.reflected[1]<130 then
motor.left.target=0
motor.right.target=0
call leds.bottom.left(32,0,0)
call leds.bottom.right(32,0,0)
else
call leds.bottom.left(0,0,0)
call leds.bottom.right(0,0,0)
end
SORTIE
• La réalisation de certains problèmes nécessite la mise en place de tâches répétitives, on parle alors de boucle.
Le programme suivant, écrit en langage naturel, en contient une :
- Choisir un nombre
- Le multiplier par 1, puis 2, puis 3... jusqu'à 30.
- Afficher le résultat.
Écrit en language de calculatrice, on aboutit au programme suivant :
ENTRÉE
n est de type nombre
i est de type nombre
TRAITEMENT
Prompt n
Pour i, allant de 1 jusqu'à 30
Faire n x i
Fin Pour
SORTIE Afficher le résultat
• Tant qu'une certaine condition est vérifiée, les instructions sont répétées. La boucle s'arrête lorsque la condition est remplie. L'exemple du laybinthe s'inscrit parfaitement dans ce cas (tant que vous n'avez pas atteint la sortie, longez systématiquement le mur, ne le lâchant jamais de votre main droite).
On peut très vite faire face à des erreurs en algorithmie, par exemple lorsqu'il a été mal construit, on peut aboutir à ce que l'on appelle des boucles infinies, source de bug. La définition d'une boucle infine par wikipedia est la suivante: une boucle infinie est, en programmation informatique, une boucle dont la condition de sortie n'a pas été définie ou ne peut être satisfaite. En conséquence, la boucle ne peut se terminer qu'à l'interruption du programme qui l'utilise.
En robotique, il s'agira alors d'une boucle dont la condition ne peut être satisfaite et qui va résulter un bug dans le programme du robot.
La situation suivante crée une boucle infinie :
i=0
Tant que i < 10 :
i=1
En effet, la boucle se termine lorsque i n'est plus inférieur à 10, or l'instruction présente dans la boucle donne toujours à i la valeur 1 ; la condition d'entrée de la boucle est donc toujours vraie.
Dans l'exemple ci-dessous nous avons une boucle infinie, le robot ne s'arrêtera jamais de monter des marches car la variable qui est testée dans la condition n'est jamais incrémentée :
nombre_marches = 0 ;
tant que nombre_marches < 60
monter_une_marche
En effet, le nombre de marches reste toujours à zéro. Pour que le robot s'arrête au bout de 60 marches, il aurait fallut dire, après "monter une marche", "le nombre de marches prend la valeur n + 1" en supposant que le nombre de marche soit n.
Il s'agit ici des règles de bases en algorithmie. On imagine bien que l'algortihme définissant le comportement d'un robot complet est bien plus complexe.
Voici un exemple de programme en tant que tel pour le robot Thymio II. Ce programme lui permet d'éviter tout obstacles et de détecter le vide. Il avance continuellement.
VARIABLES/ENTRÉE
var temp
var temp2
var speed=200
var vmin=-600
var vmax=600
var l[8]
var led_state=0
var fixed
var led_pulse
timer.period[0]=20
TRAITEMENT
onevent buttons
when button.forward==1 do #augmenter la vitesse
speed=speed+50
if speed>500 then
speed=500
end
end
when button.backward==1 do #diminuer la vitesse
speed=speed-50
if speed<-300 then
speed=-300
end
end
when button.center==1 do #arrêter le robot
speed=0
motor.left.target=0
motor.right.target=0
end
call leds.top(temp, temp, 0) #les lumières s’allument
end
onevent prox
#Pour éviter les obstacles
if speed >0 then
temp=(prox.horizontal[0]*1+prox.horizontal[1]*2+prox.horizon tal[2]*3+prox.horizontal[3]*2+prox.horizontal[4]*1)
temp2=prox.horizontal[0]*-4+prox.horizontal[1]*-3+prox.horiz ontal[3]*3+prox.horizontal[4]*4
motor.left.target=speed-(temp+temp2)/(2000/speed)
motor.right.target=speed-(temp-temp2)/(2000/speed)
elseif speed < 0 then
temp=-300/speed
motor.left.target=speed+prox.horizontal[6]/temp
motor.right.target=speed+prox.horizontal[5]/temp
call math.min(motor.left.target, motor.left.target,vmax)
call math.max(motor.left.target, motor.left.target,vmin)
call math.min(motor.right.target, motor.right.target,vmax)
call math.max(motor.right.target, motor.right.target,vmin)
end
#Pour détecter le vide
if prox.ground.reflected[0]< 130 or prox.ground.reflected[1]<130 then
motor.left.target=0
motor.right.target=0
call leds.bottom.left(32,0,0)
call leds.bottom.right(32,0,0)
else
call leds.bottom.left(0,0,0)
call leds.bottom.right(0,0,0)
end
SORTIE