C10-2 Robotique mobile

 

Soft Computing

Pendant les années 60 ont été developpées, principalement par monsieur Lofti Zadeh, des techniques de programmation qui vont sous le nom de « Soft Computing » et qui sont maintenant très utilisé. Ces techniques sont :

•  Les systèmes flous (fuzzy)

Ils utilisent des modèles précis dans un nombre fini de points et ils réalisent des transitions douces entre ces points.

• Les réseaux de neurones

 On montre au système des exemples de entrée/sortie et  le système apprend un algorithme pour calculer les sorties à des entrées inconnues

• Les systèmes stochastiques

On génére des solutions d'essai et on cherche d'arriver à la solution optimale en combinant les solutions avec des bons comportements.

Ce genre de techniques se base sur le fait que on a à traiter avec modèles qui contiennent par définition des approximation, des imprécisions et des incertitudes, qui peuvent rendre les approches plus traditionnels peu efficaces.

 

 

Les ensembles Flous

L'idée à la base des systèmes flous est celle de ensemble flou. Un ensemble flou est un ensemble pour lequel la fonction d'appartenance prend des valeurs dans l'intervalle [0,1] et pas seulement les valeurs 0 et 1 comme d'habitude. La fonction d'appartenance va définir le dégrée de appartenance de l'élément considéré à l'ensemble dont on parle.

La procédure pour construire des fonctions d'appartenance est assez simple :

1. Sélection de la variable ;

2. Identification des étiquette ;

3.   Identification des points caractéristiques de chaque étiquette ;

4. Choix de la forme de la fonction ;

5. Essai .

Chaque ensemble flou est appelé granule. Ça n'existe pas de règles général pour le nombre de granules à définir pour une variable (en général il y en a entre 3 et 7) ou sur leur distribution. Les seules propriétés qui doivent être respectées lors du choix des fonctions de appartenance sont :

 

• Propriété de couverture

Chaque possible valeur de la variable doit appartenir à au moins un granule

• Propriété de unimodalité

Pour chaque granule il y a un seul ensemble de points avec appartenance maximale

• Partition flou 

Pour chaque valeur possible de la variable la somme des dégrées d'appartenance doit être 1

 

On peut démontrer que la robustesse (intégral de la somme de tous les erreurs dans l'espace de la mesure) d'un système floue est toujours plus grande de celle obtenue pour une partition binaire, et que cette robustesse est maximale si la règle de partition flou est respectée.

Pour les ensemble flou on peut définir les opérateurs usuels comme :

• Complément :

 

•  Union :

 

• Intersection :

 

L'utilisation de ces opérateurs permet de garantir que l'erreur maximal qu'on commit est celui qu'on a dans les fonctions d'appartenance de départ, mais on peut donner des définitions différentes (qui respectent quand même certaines conditions).

 

 

La logique flou

La logique flou est une logique prédicative du premier ordre à valeurs infinis dans [0,1].

Une logique prédicative a les mêmes propriétés de la logique propositionnelle (la logique « classique »), mais on a en plus la possibilité de définir des prédicats sur les variables et on peut utiliser des quantificateurs existentiels et universels (tels que « existe » ou « pour tous »). Un prédicat est un instrument du langage qui permet de faire des affirmation sur quelque chose. Dans ce type de logique on peut déduire la valeur de vérité d'une proposition en utilisant l'inférence (par exemple le « modus ponens »).

La logique binaire est une logique à 2 valeurs, mais on peut avoir une logique à plus valeurs, par exemple 3 (vrai 1, faux 0, indéfini 1/2) ou même infini valeurs, comme la logique flou (un continu de valeurs entre 0 et 1 compris).

Etant données ces différences entre la logique « classique » et la logique flou, c'est pas trop étonnant que certaines tautologies à lesquelles on a l'habitude ne sont plus vraies dans ce contexte. Par exemple :

• Loi du troisième exclus  : (a or not a = 1)

•  Loi de contradiction  :  (a and not a = 0)

 

Une proposition en logique flou s'exprime comme:

                        A is L

Où :

            A c'est une variable linguistique

            L est l'étiquette d'un ensemble flou

 

Une variable linguistique est définie par (X, T(X), U, G, M), où :

            X est le nom de la variable

            T(X) ensemble des valeurs linguistique de X, qui correspondent à une variable flou

            U univers du discours avec base u

            G règle syntactique pour générer l'interprétation X pour chaque valeur u

            M règle sémantique pour associer à X sa signification

 

Une proposition en logique flou est donc tu type :

                        p : X is F

où :

            X c'est un variable prenant une valeur u dans U

            F c'est un ensemble flou défini en U, qui représente un prédicat flou

La valeur de vérité de la proposition p est donnée par :

                         

Qui est compris dans [0,1].

 

A partir de ce genre de proposition on peut en peut en construire des autres. Un exemple sont les propositions qualifiées non-conditionnelles, du type :

                        p : (X is F) is S

Où :

            F est un qualificateur flou de vérité

            S est un ensemble flou

C'est aussi possible d'utiliser des modificateurs flous (du type beaucoup, peu, souvent, très etc. ). Par exemple :

            F(très a) = F(a)²

            F(peu a) = F(a)^1/2

 

 

Règles flous

Les systèmes flous utilisent des règles d'inférence pour modéliser les relations entrée/sortie et donc pour inférer connaissances nouvelles à partir de quelque fait connu.

Ces règles ont la forme :

            IF <antécédent> THEN <conséquence>

Où <antécédent> et <conséquence> sont des phrases (suites de proposition et variables en général) liées par l'opérateur AND dans le cas de <conséquence> et par les opérateurs AND, OR, NOT dans le cas de <antécédant>.

De cette façon sont réalisés les systèmes basés sur la connaissance.

Les phases des règles flou sont de type linguistique, et ont la forme :        

            (V is L)

 Où :

            V est une variable linguistique

            L est l'étiquette d'un ensemble flou

 Une interprétation (très pratique) de ce type de règles la suivante : on va établir une correspondance entre la configuration des entrées (qualitative) et la sortie souhaitée.

Ce type de règle est appelé linguistique (ou de Mamdani).

Le deuxième type de règle qui est utilisé est constitué par les règles mathématiques (ou de Takagi-Sugeno-Kosko, TSK), qui sont du type

             IF (A is LA_n)AND(B is LB_m) THEN U is f(A,B)

 Qui peut etre interpreté comme une correspondence établie entre la configuration des entrées (qualitative) et un modèle mathématique à appliquer à la valeur des entrées (mésurées) pour calculer la sortie. 

 

Un controleur flou

L'utilisation de ces règles dans un système flou se fait de la manière suivante :

•  « Fuzzyfication » des entrées

• Combinaison des dégrées d'appartenance

• Combinaison avec les poids des règles

• Agrégation des sorties des différentes règles

•  « Défuzzyfication » de la sortie ainsi calculée

Application : contrôleur flou pour évitement d'obstacles

Un exemple de utilisation de la logique flou en robotique est la navigation autonome dans un environnement inconnu avec évitement d'obstacles. Ce type d'application peut etre assez complexe et a des contraints de robustesse et vitesse qui peuvent etre satisfaits en utilisant un contrôleur flou. Un exemple de ce genre a été trouvé dans l'article  pour ce bout a été trouvé dans l'article « $,1s&s&(B. ».

Le bout est de permettre la navigation en évitant les collisions avec les obstacles d'un robot omnidirectionnel équipé avec un télémètre laser.

Pour faire ça, on utilise comme entrées la distance et la direction relevées par la télémètre de l'ostacle le plus proche au robot et comme sorties on aura la direction à suivre et la distance à parcourir. Les variables de sortie auront donc la même structure que les variables d'entrée.  

L'espace analysé par la télémètre est divisé comme dans la figure suivante :

 

La forme des ensembles flous pour la distance sont montrés dans la figure suivante :

 

La forme des ensembles flous pour la direction est montrée dans la figure suivante.

 

 

Les valeurs des paramètres des fonctions d'appartenences dépendent  de la sensibilité du télémètre utilisé, et pour cette raison le plus souvent des fois les données sont normalisés.

Une fois que on a les données relatives à l'obstacle le plus proche, on peut déterminer les degrés d'appartenance aux ensemble qu'on vient de montrer.

On applique alors les règles suivantes pour l'évitement d'obstacle :

 

IF obstacle is NEAR AND ZERO POSITIVE THEN move MEDIUM AND MEDIUM NEGATIVE

IF obstacle is MEDIUM AND ZERO POSITIVE THEN move NEAR AND MEDIUM NEGATIVE

IF obstacle is NEAR AND MEDIUM POSITIVE THEN move MEDIUM AND NEAR NEGATIVE

IF obstacle is MEDIUM AND MEDIUM POSITIVE THEN move NEAR AND MEDIUM NEGATIVE

IF obstacle is NEAR AND ZERO NEGATIVE THEN move MEDIUM AND MEDIUM POSITIVE

IF obstacle is MEDIUM AND ZERO NEGATIVE THEN move NEAR AND MEDIUM POSITIVE

IF obstacle is NEAR AND MEDIUM NEGATIVE THEN move MEDIUM AND NEAR POSITIVE

IF obstacle is MEDIUM AND MEDIUM NEGATIVE THEN move NEAR AND MEDIUM POSITIVE

 

Plus une règles activée si le chemin est libre :

 

IF obstacle is LARGE POSITIVE OR LARGE NEGATIVE OR FAR THEN move FAR AND NEAR POSITIVE AND NEAR NEGATIVE

 

On peut ajouter aussi d'autres types de règles, comme par exemple l'arriver à un certain but.

Dans l'implémentation on utilise le min pour le AND, le max pour le OR et pour l'agrégation des règles, et la méthode du centroid pour la défuzzyfication des résultats.

Avec un tel type de système, c'est possible d'obtenir des comportement très variés, en changeant tout simplement les fonctions d'appartenance, les constants de normalisations ou en ajoutant des règles supplémentaires.