Partie Théorique
Dans cette partie nous allons tenter d'éxpliquer les résultats trouvés dans la partie précédente. Ainsi nous avons vu que les robots aspirateurs étaient séparés en trois grands types :
-Les robots aléatoires
-Les robots programmes
-Les robots fourmis
Dans cette partie nous allons donc détailler le fonctionnement de chaque catégorie
puis montrer son fonctionnement. Pour ce faire, nous allons programmer chaque
catégorie a l'aide du logiciel Python, qui nous permettra avec le module Turtle
de modéliser les trajectoires es robots. Nous allons de plus tenter de trouver un
programme encore plus performant que le modèle fourmi , à l'aide des données
collectees tout au long de la premiere partie.
Contraintes du système directionnel d'un robot aspirateur
Le système directionnel d'un robot permet
à celui-ci de se déplacer en évitant les obstacles. On définit un bon système directionnel par sa capacité à réaliser sa tache le mieux et le plus vite possible. La qualité du système directionnel du robot aspirateur dépend également beaucoup
de la mémoire qui lui est alloué. En effet, plus un système directionnel aura de mémoire, plus il pourra stocker d'informations. Dans le cas du robot fourmi, la mémoire est très
importante car le robot pourra ainsi stocker plus de coordonnés de cases sur lesquelles il est déjà passé.
Noyau principal du programme
Le programme qui modélisera les robots est composé de deux parties:
-Un noyau principal commun à tous les programmes. Les fonctions principales y sont définie.
-Une partie propre à chaque programme qui adaptera le cœur à la fonction voulue
Nous allons d'abord détailler ici le fonctionnement du cœur principal.
Coeur Principal
# -*- coding: utf-8 -*-
"""
Created on Tue Dec 29 11:13:01 2015
@author: kilian
"""
from turtle import *
from math import sin, cos, pi
import random
piece = [[0,0],[0,140],[80,140],[80,300],[280,300],[280,0]] # 712 positions pour un pas de 10
p = 10 # pas > 2
np = nz = 1 # compteurs : nb pas effectues, nb zones nettoyees
passe = [(p//2,p//2)]
def trace_piece():
shape("circle")
width(3)
down()
for i in piece:
goto(i)
goto(piece[0])
up()
def initialisation():
clear()
reset()
up()
setworldcoordinates(-2,-2,282,302)
home()
trace_piece()
goto(passe[0])
down()
left(90)
width(15)
color('yellow')
shape("circle")
shapesize(1.5,1.5,1)
speed(0)
def point_inside_polygon(x,y):
n = len(piece)
inside =False
p1x,p1y = piece[-1]
for i in range(n):
p2x,p2y = piece[i]
if y > min(p1y,p2y) and y <= max(p1y,p2y) and x <= max(p1x,p2x):
if p1y != p2y:
xinters = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
if p1x == p2x or x <= xinters:
inside = not inside
p1x,p1y = p2x,p2y
return inside
def in_passe(x,y):
for pt in passe:
if round(pt[0])==round(x) and round(pt[1])==round(y):
return True
return False
def randomn():
x, y = position()
a = (heading()*pi)/180.
possible=[]
a_faire=[]
# a gauche
xt, yt = x-p*sin(a),y+p*cos(a)
if point_inside_polygon(xt, yt):
possible.append(90)
if not in_passe(xt, yt): a_faire.append(90)
# devant
xt, yt = x+p*cos(a),y+p*sin(a)
if point_inside_polygon(xt, yt):
possible.append(0)
if not in_passe(xt, yt): a_faire.append(0)
# a droite
xt, yt = x+p*sin(a),y-p*cos(a)
if point_inside_polygon(xt, yt):
possible.append(-90)
if not in_passe(xt, yt): a_faire.append(-90)
# derriere
xt, yt = x-p*cos(a),y-p*sin(a)
if point_inside_polygon(xt, yt):
possible.append(180)
if not in_passe(xt, yt): a_faire.append(180)
return a_faire, possible
def trajet(valeur):
global np
left(valeur)
forward(p)
passe.append(position())
np += 1
if nz==int(712*0.25): # 25% de 712
print("Nb d'iterations pour 25% :", np)
color('#DFFE40')
elif nz==int(712*0.5): # 50% de 712
print("Nb d'iterations pour 50% :", np)
color('#E4FD69')
elif nz==int(712*0.7): # 70% de 712
print("Nb d'iterations pour 70% :", np)
color('#ECFAA6')
elif nz==712: # 100% de 712
print("Nb d'iterations pour 100% :", np)
return False
return True
_________________________________________________________________
Programmes
def fourmi():
global np, nz
a_faire, possible = randomn()
if len(a_faire)!=0:
i = random.choice(a_faire)
nz += 1
else:
if len(possible) > 1:
i = random.choice(possible[:-1])
else:
i = possible[0]
return i
def dirig():
global np, nz
a_faire, possible = randomn()
if len(a_faire)!=0:
i = a_faire[0]
nz += 1
else:
if len(possible) > 1:
i = random.choice(possible[:-1])
else:
i = possible[0]
return i
def aleatoire():
global np, nz
a_faire, possible = randomn()
i = random.choice(possible)
if i in a_faire:
nz += 1
return i
_________________________________________________________________
Execution
initialisation()
while trajet(dirig()):
pass
bye()
Nous allons maintenant étudier individuellement les fonctions constituant le coeur du programme
Initialisation
from turtle import *
from math import sin, cos, pi
import random
piece = [[0,0],[0,140],[80,140],[80,300],[280,300],[280,0]] # 712 positions pour un pas de 10
p = 10 # pas > 2
np = nz = 1 # compteurs : nb pas effectues, nb zones nettoyees
passe = [(p//2,p//2)]
def trace_piece():
shape("circle")
width(3)
down()
for i in piece:
goto(i)
goto(piece[0])
up()
def initialisation():
clear()
reset()
up()
setworldcoordinates(-2,-2,282,302)
home()
trace_piece()
goto(passe[0])
down()
left(90)
width(15)
color('yellow')
shape("circle")
shapesize(1.5,1.5,1)
speed(0)
def point_inside_polygon(x,y):
n = len(piece)
inside =False
p1x,p1y = piece[-1]
for i in range(n):
p2x,p2y = piece[i]
if y > min(p1y,p2y) and y <= max(p1y,p2y) and x <= max(p1x,p2x):
if p1y != p2y:
xinters = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
if p1x == p2x or x <= xinters:
inside = not inside
p1x,p1y = p2x,p2y
return inside
Dans la première partie de ce code on initialise les paramètres et les packages qui vont être utilisés dans le programme. Le package Turtle permet de tracer des figures géométriques dans Python, les fonctions sin, cos et pi du package Math permettent d'utiliser les cosinus, sinus et le nombre et la fonction random permet d'intégrer de l'aléatoire dans les programmes. On initialise également la pièce avec ses coordonnées, passe, une liste contenant les points par lesquels le robot est déjà passé, p le pas de déplacement du robot, et des compteurs pour mesurer l’efficacité des programmes. La première fonction du programme trace les contours de la pièce. Pour ce faire elle utilise une boucle tournant autant de fois qu'il y a de coordonnées dans la liste "piece". Pour chaque boucle elle trace une ligne reliant le couple de coordonnées actuel au précédent. La deuxième fonction initialise des paramètres généraux comme la vitesse, le point de départ, la couleur du tracé, etc ...
def point_inside_polygon(x,y):
n = len(piece)
inside =False
p1x,p1y = piece[-1]
for i in range(n):
p2x,p2y = piece[i]
if y > min(p1y,p2y) and y <= max(p1y,p2y) and x <= max(p1x,p2x):
if p1y != p2y:
xinters = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
if p1x == p2x or x <= xinters:
inside = not inside
p1x,p1y = p2x,p2y
return inside
La fonction point-inside-polygon
Cliquez pour agrandir
Diapo explicatif
La fonction point_inside_polygon est une des fonctions les plus importantes du programme. Elle permet de déterminer si un point est dans un polygone et dans notre cas si la tortue est dans la pièce. Nous nous sommes inspiré du code du site www.ariel.com en C et nous l'avons adapté en Python.
Pour déterminer si un point est dans le polygone la fonction effectue d'abord une boucle pour les deux premiers points. Une fois celle-ci finie, on garde le deuxième point qui devient alors premier et on récupère un nouveau point de la liste et on recommence ce processus jusqu'à ce que tous les points soient passés premier et deuxième une fois. Dans la fonction on regarde tout d'abord si l'ordonnée du robot est comprise entre celle des deux points et si le la plus grande abscisse des points est supèrieure à celle du robot. Si toutes les conditions sont réunies, on passe aux tests suivants, sinon la boucle est finie et la position de l'indicateur booléen "inside" reste identique. Dans la deuxième étape on compare la position du premier point et à celle d'un point imaginaire définit par $(y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x$ si l'abscice du premier point est inferieure ou égale à celle de l'autre, la valeur booléenne "inside" change.
Au bout de toutes les boucles, la fonction renvoie la valeur de inside
La fonction in-passe
def in_passe(x,y):
for pt in passe:
if round(pt[0])==round(x) and round(pt[1])==round(y):
return True
return False
La fonction in-passe permet de déterminer si le robot est déja passé par un point. La fonction regarde si les coordonnées sont déja dans la liste "passe" et si oui elle renvoie la valeur booléenne 1.
Le noyau
def randomn():
x, y = position()
a = (heading()*pi)/180.
possible=[]
a_faire=[]
# a gauche
xt, yt = x-p*sin(a),y+p*cos(a)
if point_inside_polygon(xt, yt):
possible.append(90)
if not in_passe(xt, yt): a_faire.append(90)
# devant
xt, yt = x+p*cos(a),y+p*sin(a)
if point_inside_polygon(xt, yt):
possible.append(0)
if not in_passe(xt, yt): a_faire.append(0)
# a droite
xt, yt = x+p*sin(a),y-p*cos(a)
if point_inside_polygon(xt, yt):
possible.append(-90)
if not in_passe(xt, yt): a_faire.append(-90)
# derriere
xt, yt = x-p*cos(a),y-p*sin(a)
if point_inside_polygon(xt, yt):
possible.append(180)
if not in_passe(xt, yt): a_faire.append(180)
return a_faire, possible
Cette fonction est le cœur du programme, c'est elle qui va retourner les cases possibles et celles d'entre elles par lesquelles le robot n'est pas encore passé. Il teste les différentes directions dans un ordre précis. En effet les robots fourmi et aléatoire utilisent une fonction random alors que le robot dirigé utilise un ordre précis. C'est cet ordre qui est respecté dans la fonction cœur.
La fonction trajet
def trajet(valeur):
global np
left(valeur)
forward(p)
passe.append(position())
np += 1
if nz==int(712*0.25): # 25% de 712
print("Nb d'iterations pour 25% :", np)
color('#DFFE40')
elif nz==int(712*0.5): # 50% de 712
print("Nb d'iterations pour 50% :", np)
color('#E4FD69')
elif nz==int(712*0.7): # 70% de 712
print("Nb d'iterations pour 70% :", np)
color('#ECFAA6')
elif nz==712: # 100% de 712
print("Nb d'iterations pour 100% :", np)
return False
return True
La fonction trajet va exécuter le programme. Le robot tourne d'un certain angle: "valeur" puis avance de la valeur indiquée par le pas (10 par défaut). Le programme vérifie également l'avancement du nettoyage. La pièce que nous utilisons est en effet composée de 712 cases. Le programme incrémente les cases sur lesquelles il n'est pas encore passé et les compare à 712. La couleur du tracé change quand il atteint les paliers 25%, 50% et 70%, la valeur que nous avons fixé comme minimale pour un robot aspirateur.
Le robot aléatoire
Introduction
Bon nombre de robots aspirateurs d'entrée de gamme utilisent ce fonctionnement. En effet il
utilise très peu de ressources (mémoire, stockage) et est assez facile à programmer. Néanmoins
il est souvent peu performant car il peu lui arriver de repasser plusieurs fois au même endroit.
(Déplacement d'un robot aléatoire)
Fonctionnement
Le fonctionnement de ce type de robot est très simple, à chaque unité de déplacement, le robot recalcule aléatoirement sa position. Ainsi le robot pourra revenir sur ces pas et on peut très bien imaginer qu'il tourne sur une boucle infinie ce qui rend la durée de son trajet aléatoire. Cependant ce système ne nécessite peu de capteurs et de mémoire ce qui rend ce robot peu onéreux ce qui explique qu'il se trouve souvent parmi les modèles d'entrée de gamme.
(Déplacement d'un robot aléatoire)
Le Programme
def aleatoire():
global np, nz
a_faire, possible = randomn()
i = random.choice(possible)
if i in a_faire:
nz += 1
return i
Dans ce programme qui utilise la liste "possible" transmise à la fonction par le noyau, on tire aléatoirement un angle de la liste "possible" qui sera renvoyé à la fonction trajet. La fonction regarde également si le robot est déjà passé par cette case pour pouvoir contabiliser les cases parcourues. Comme on peut le voir si dessous.
Le robot programmé
Introduction
Longtemps considéré comme le plus performant des systèmes directionnels, il est très fiable quand à l'arrivée à destination. Cependant en plus de son coté gourmand en mémoire, il peut prendre beaucoup de temps à arriver et dans le cas d'une pièce contenant beaucoup de meubles, l'adaptation à la pièce peut être très difficile, menaçant de faire «planter» gentiment le robot comme on le dit si bien en langage informatique.
Fonctionnement
Le fonctionnement du robot dit programmé est très simple. Il va avancer jusqu'au mur et va ensuite effectuer une rotation à 90 degrés avancer de 1 unité et ensuite refaire la même rotation dans le sens inverse. et c'est reparti pour un tour !! Ce programme est bouclé et s'arrête dès que le robot rejoins le coin opposé. Ce qui différencie les différents robots de cette catégorie c'est leur capacité à éviter les obstacles. Ce sont les robots qui se démocratisent de plus en plus. On notera que peu d'évolutions affectent ce type de robots, car leur fonctionnement reste toujours identique.
de nombreuses adaptation de ce modèle existent également, comme le robot tournant en spirales ou celui qui effectue des tours.
Le Programme
def dirig():
global np, nz
a_faire, possible = randomn()
if len(a_faire)!=0:
i = a_faire[0]
nz += 1
else:
if len(possible) > 1:
i = random.choice(possible[:-1])
else:
i = possible[0]
return i
Du fait que la liste renvoyée par le noyau soit déja rangée dans le bon ordre, le programme va simplement renvoyer le premier élément de la liste. Si toutefois la liste est vide il va prendre un élément de la liste "possible" si possible différent de 180, ce qui permet de ne pas revenir en arrière.
Le robot fourmi
Fonctionnement
Alors que les deux systèmes vus précédemment ont certains points négatifs, le robot fourmi se veut juste milieu entre ces deux systèmes.
Il nécessite plus de mémoire et de stockage, coûte donc plus cher que les deux autres modèles mais avec la démocratisation des composants, ce système est de plus en plus présent chez les robots qui se veulent haut de gamme.
Fonctionnement
Le robot aspirateur fourmi va enregistrer continuellement sa position ce qui lui permettra de s'arranger pour ne pas repasser aux endroits de la pièce où il est déja passé. Parmi les autres possibilités le robot va en choisir une aléatoirement.
Le Programme
def fourmi():
global np, nz
a_faire, possible = randomn()
if len(a_faire)!=0:
i = random.choice(a_faire)
nz += 1
else:
if len(possible) > 1:
i = random.choice(possible[:-1])
else:
i = possible[0]
return i
Le robot va simplement choisir une direction aléatoirement si possible dans la liste "a-faire", sinon dans la liste "possible" toutefois en retournant en arrière qu'en dèrnière possibilité.
Ouverture
Bilan
Dans cette partie nous avons vu que tous les systèmes directionnels se valent
dans le sens que chacun d’eux s’adapte mieux à certains types de pièces. Ainsi
le robot aléatoire par exemple s’adapte très bien aux surfaces arrondies alors
que le robot linéaire s’adapte mieux aux pièces rectangulaires même si elles sont
grandes. Le robot fourmi est un compromis entre les deux systèmes car son côté
aléatoire mais dirigé lui permet une polyvalence que les autres robots n’ont pas.
Cependant ce robot a tendance a se perdre si la surface a parcourir est trop
grande car il a une marge d’erreurs relativement importante.
Nos idées
Dans cette partie nous avons vu les points positifs et les points négatifs
des systèmes directionnels du marché. Nous avons pensé qu’à la suite de notre
étude nous pourrions proposer un système de robot qui répond aux critères.
Cahier des charges
Le robot que nous voulons créer doit répondre à certains critères que nous allons définir ici :
– Fonctionner dans tous types de pièces
– Ne pas être gourmand en mémoire et en stockage
– Ne pas nécessiter énormément de capteurs
– Parcourir au moins 70 % de la pièce
– Être rapide
Nous allons dans la prochaine partie élaborer un système directionnel qui ,nous l’espérons alliera les caractéristiques vues précédemment et le recréer à l’aide d’une carte Arduino.
Modélisation de notre modèle
Nous avons tout d'abord décidés de modéliser notre robot sous Python pour comparer son fonctionnement à celui des autres.
Le Programme
def our():
global np, nz
global droite, enrot
a_faire, possible = randomn()
if 0 in possible and not enrot:
i = 0
else:
if droite and -90 in possible:
i = -90
elif not droite and 90 in possible:
i = 90
else:
i = random.choice(possible)
enrot = not enrot
if not enrot:
droite = not droite
if i in a_faire:
nz += 1
return i
Ce système est assez simple sur son principe : Le robot détermine d'abord si il peut avancer. Si il ne peut pas, il va déterminer son sens de rotation avec la valeur booléenne droite. Il bouclera cette fonction de rotation deux fois car il doit effectuer une rotation à 180° composée de deux rotations à 90° et d'un petit déplacement vers l'avant. Si aucun choix n'est possible, le robot va se rediriger aléatoirement.