Intelligence artificielle

Un article de Wikibot.

L'intelligence artificielle regroupe l'ensemble des disciplines s'intéressant à la reproduction par des machines de mécanismes de raisonnement intelligent.

Sommaire 1 Présentation 1.1 Introduction 1.2 L’IA en tant que discipline 1.3 L’IA en robotique 1.4 Conclusion partielle 2 Techniques d'intelligence artificielle 3 Application 3.1 Analyse du comportement d'un robot : approche déterministe 3.2 Analyse du comportement d'un robot : approche non déterministe 3.3 Tendre vers un véritable comportement intelligent : l'apprentissage artificiel

Présentation

Introduction

Intelligence Artificielle (IA), le mot résonne dans la tête et attire fébrilement quelques amateurs de la robotique sans que ceux-ci franchissent le pas… Qu’est ce que c’est que l’IA et à quoi cela peut-il bien servir dans un robot ?

L’IA (terme utilisé lors d’une conférence fondatrice de la discipline : "The Dartmouth summer research project on Artificial Intelligence" organisé par McCarthy -également fondateur du "MIT Lab"- en 1956. Toutefois ce terme est sujet à polémique et n'est pratiquement utilisé que dans le milieu des jeux videos et de la robotique.) est une discipline de l’informatique qui cherche à représenter la connaissance humaine et à formaliser le raisonnement de façon à obtenir des algorithmes qui simulent (en partie) la réflexion humaine. Par extension elle est aussi devenue une discipline qui cherche à simuler par les moyens de l’informatique des mécanismes cognitifs et neuronaux.

L’IA en tant que discipline

Deux méthodologies différentes se retrouvent en IA :

• l’approche classique cherche à modéliser le raisonnement de façon symbolique. Un exemple simple est le principe du chaînage avant et de la déduction logique par une règle de la forme Si A alors B (1) (modus ponens). Ainsi si l’on dispose d’une base de règles de la forme de (1) pour modéliser des raisonnements autorisés, et d’une base de faits qui, elle, décrit la connaissance, alors il est possible d’appliquer les règles pour augmenter les connaissances de départ. Grossièrement c’est le fonctionnement d’un système expert;

• l’approche numérique ne cherche pas à expliciter clairement la connaissance ou le raisonnement. Ce sont des modèles mathématiques paramétrés sur lesquels on applique des algorithmes spécifiques (parfois des algorithmes dits d’apprentissage). Ces algorithmes ajustent les paramètres du modèle de façon créer une relation entre les entrées et les sorties de celui-ci en satisfaisant un critère quelconque (fixé à la conception). L’interprétation du modèle obtenu dépend en grande partie de l’application de départ. Une vue de l’esprit consiste à se représenter le modèle comme le résultat d’une analyse statistique des variables présentées au système (toutefois cette façon de voir n’est pas toujours exacte). Les réseaux de neurones artificiels représentent bien cette approche.

L’IA en robotique

Dès les débuts de la robotique les ingénieurs et les chercheurs ont cherché à coupler leurs robots avec les techniques de l’intelligence artificielle. L’objectif était alors de rendre les systèmes artificiels obtenus plus performants pour tout ce qui concerne leur interaction avec l’environnement. C'est une façon de rendre les machines plus autonomes.

Le champ d’application de l’IA en robotique est très vaste (et parfois loin de ce que l’on s’imagine) avec par exemple :

• l’utilisation de l’IA pour la recherche de configurations géométriques des mécanismes contraints par l’environnement (collaboration de robots, conception de sites robotiques);

• calcul d’une planification de tâche robotique ou de recherche de trajectoire (robot industriel ou robot mobile, chaque secteur d'activité avec des spécificités propres);

• élaboration de langages de programmation spécifiques aux tâches à réaliser (commande numérique, palettisation et manutention…);

• auto-apprentissage (voir le projet Cog) et réaction cohérente (par rapport à la tâche à exécuter) face à une situation inconnue;

• vision artificielle et analyse de la scène (robotique mobile et robotique industrielle : c’est un domaine d’application à lui tout seul).

La liste précédente est loin d’être exhaustive. Pour être complet nous devrions parler aussi des recherches en conscience artificielle. Mais cela reste très confidentiel et assez élitiste.

Conclusion partielle

Cette très courte introduction aura permis, nous l’espérons, au lecteur de préciser certaines idées au sujet de l’intelligence artificielle. Il est, d’un point de vue théorique, très compliqué de mettre en place un système d’intelligence artificielle qui remplisse correctement sa fonction. L’innovation dans ce domaine n’est pas forcement la chose la plus aisée. Toutefois (et à condition de rester très raisonnable dans son approche) il est toujours possible pour un amateur de robotique de réaliser de petites applications pour illustrer quelques principes de l’IA qui sont éprouvés par le milieu industriel depuis quelques années. C’est ce que nous chercherons à illustrer dans la suite.

Techniques d'intelligence artificielle

• Algorithme AStar ou A*
• Algorithmes génétiques
• Arbres de décision
• Automates à états finis ou FSM
• Logique floue
• Recuit simulé
• Réseau de neurones
• Simplex
• Systèmes multi-agents ou SMA
• Un cours de l'[ENSTA] sur les différentes techniques d'IA pour la navigation des robots : [[1]]

Application

La plupart des amateurs de robotique n'ont pas de robots disposant d'une forte puissance de calcul. On essayera donc de limiter les raisonnements de façon à ce que les résultats obtenus mènent à une réalisation pratique capable de s'exécuter sur un système à micro-contrôleur de moyenne puissance.

Cela réduit bien sûr énormément le caractère impressionnant des résultats obtenus et cela a aussi pour effet de s'écarter, parfois grandement, de l'esprit de base de ce qu'est l'Intelligence Artificielle. Toutefois d'un point de vue pédagogique il peut être intéressant d'essayer de suivre la démarche d'analyse/conception qui va suivre, ne serait-ce que pour aborder d'un autre point de vue la programmation des robots et ne pas y voir seulement une petite cuisine de programmeur. C'est aussi une bonne façon de mieux comprendre ce que l'on peut ou ne peut pas attendre d'un robot lorsqu'on utilise un paradigme de programmation classique.

Analyse du comportement d'un robot : approche déterministe

On va dans cette partie s'intéresser à une méthodologie systématique pour obtenir un code "robuste" de comportement de petit robot mobile. La formalisation théorique nous aidera à analyser ce que le système sera réellement capable de faire. Nous travaillerons sur un système très élémentaire que nous supposons :

• disposer d'un capteur de choc avant gauche;
• disposer d'un capteur de choc avant droit;
• disposer d'un moteur gauche;
• disposer d'un moteur droit.

Nous allons dans un premier temps considérer notre robot comme étant une machine à état. Nous pouvons chercher à décrire son comportement de façon littérale ; en énumérant à la suite chaque action que le robot sera capable d'accomplir et en s'imposant une formalisation des règles à découvrir. Par exemple une règle décrivant une action pourra être de la forme :

si ((le robot est dans l'état X) et (l'évènement Y vient de se produire)) alors (passer à l'état Z)

Un état pourra être une action que le robot est en train de réaliser. Un événement pourra être quelque-chose qui le fera réagir.

On peut énumérer les actions que nous souhaitons voir exécuter par le robot (la description est ici décrite en langue française, elle doit bien sûr être traduite sous la forme d'un programme) :

• A : le robot avance
• B : le robot recul puis tourne à gauche
• C : le robot recul puis fait un tour sur lui même
• D : le robot recul puis tourne à droite

A l'instar des actions nous pouvons énumérer les évènements (avec les mêmes remarques que pour les actions en ce qui concerne le code) :

• a : il ne se passe rien (sic!)
• b : le capteur droit vient d'être excité
• c : une tempo vient de passer en time out
• d : le capteur gauche et le capteur droit viennent d'être excités
• e : le capteur gauche vient d'être excité

Utilisons le motif que nous avons déjà donné pour décrire les comportements que nous souhaitons voir exécuter par notre robot :

1. si ((le robot est dans l'état A) et (l'évènement a vient de se produire)) alors (passer à l'état A)
2. si ((le robot est dans l'état A) et (l'évènement b vient de se produire)) alors (passer à l'état B)
3. si ((le robot est dans l'état A) et (l'évènement d vient de se produire)) alors (passer à l'état C)
4. si ((le robot est dans l'état A) et (l'évènement e vient de se produire)) alors (passer à l'état D)
5. si ((le robot est dans l'état B) et (l'évènement c vient de se produire)) alors (passer à l'état A)
6. si ((le robot est dans l'état C) et (l'évènement c vient de se produire)) alors (passer à l'état A)
7. si ((le robot est dans l'état D) et (l'évènement c vient de se produire)) alors (passer à l'état A)

Il est, bien sûr, possible de substituer dans une règle donnée l'un des symboles par sa description. C'est ainsi que par exemple la règle 2 peut s'interpréter de la façon suivante : Si le robot avance et qu'un choc avant droit est détecté alors le robot recul puis tourne à gauche.

Mais cette notation, si elle a l'avantage d'être assez naturelle, est plutôt lourde à manipuler. On pourra ré-écrire ces règles sous la forme plus formelle :

1. Aa-->A
2. Ab-->B
3. Ad-->C
4. Ae-->D
5. Bc-->A
6. Cc-->A
7. Dc-->A

Supposons que A est l'état initial du robot et qu'il ne se passe rien. Le robot applique la première règle. Il continue à avancer et est donc toujours dans l'état A. Puis l'évènement d intervient (choc de ses deux capteurs). Alors il n'a pas d'autres choix que d'appliquer la règle 3 : il recul pour faire demi-tour. Il se retrouve dans l'état C et au bout d'un petit moment se met à avancer. Il se retrouve donc de nouveau dans l'état A et ainsi de suite.

Nous venons donc d'appliquer les règles :

Aa-->A ; Ad-->C ; Cc-->A ... ces règles peuvent se dériver les unes des autres indéfiniment (ceci serait à démontrer, nous y reviendrons). Remarquons que la suite de caractères adc... (les évènements) suffisent a caractériser de façon non ambigu le comportement exécuté par le robot. En partie nous venons de définir ce que l'on nomme une grammaire régulière (de type linéaire à gauche). (Pour être tout à fait complet il faut y rajouter des états accepteurs. Nous choisirons comme états accepteurs les états B, C, et D. Ils seront introduits naturellement dans la suite.)

Une telle grammaire permet de définir un langage régulier. Un mot reconnu dans ce langage est une suite d'évènements qui se succèdent en partant de l'état initial à un état accepteur. Par exemple :

• • la dérivation Aa-->A ; Ad-->C ; Cc-->A ; Ab -->B reconnaît le mot adcb
  • la dérivation Aa-->A ; Ae-->D reconnaît le mot ae

Le langage ainsi défini décrit l'ensemble des comportements que le robot sera capable de suivre. Par exemple le mot adcb signifie que le robot peut avancer puis reculer et tourner à droite puis de nouveau avancer pour reculer puis tourner à gauche. Remarquons que l'ensemble des mots de ce langage est non dénombrable. Cela signifie que le robot peut avoir une infinité d'attitude bien que tous basés sur des comportements élémentaires simples.

Nous reviendrons dans la suite sur l'exploitation théorique de ce formalisme. Nous allons maintenant nous intéresser à la génération du programme qui permet d'implémenter ce comportement. Le fait que l'on soit en présence d'une grammaire régulière nous facilite l'écriture du programme du robot. En effet il existe une équivalence entre une grammaire régulière et un automate fini déterministe. Graphiquement l'automate déterministe qui correspond à la grammaire donnée ci-dessus est illustrée en figure 1 (dans la représentation utilisée le symbole '>' représente l'état initial, les états accepteurs sont représentés par des doubles cercles).

L'intérêt des automates finis déterministes, c'est qu'il est toujours possible de les transposer de façon automatique. Par exemple (en utilisant des notations évidentes) l'algorithme qui implémente l'automate décrit en figure 1 devrait suivre la démarche suivante :

Toujours executer

  Suivant ETAT

    cas A
        si evenement = a 
        alors rester dans l'etat A

        si evenement = b
        alors passer dans l'etat B

        si evenement = d
        alors passer dans l'etat C

        si evenement = e
        alors passer dans l'etat D

    cas B
        si evenement = c 
        alors passer dans l'etat A

    cas C
        si evenement = c 
        alors passer dans l'etat A

    cas D
        si evenement = c 
        alors passer dans l'etat A

Fin Toujours executer

Pour illustrer de façon plus précise comment un tel mécanisme peut être implanté dans un vrai robot, un programme a été réalisé en leJOS. LeJOS est une forme du langage java mais dédié à la programmation des robots lego MindStorms. Ce langage est par ailleurs supporté par le simulateur de robot mobile Webot 5. Ainsi le programme est le suivant (attention en cours de test, comportement étrange possible) :

import josx.platform.rcx.*;

class RobotDeterministe {
	
	public static void main(String [] args) {
		
		/* Definitions des variables */
		char ETAT;				/* les etats : valeurs A, B, C, D */
		char evt;				/* les evenements : valeurs a, b, d */
		int c;					/* tempo qui se decremente, lorsque 0 evt. c */
		int tempo;				/* variable temporaire pour 
								 * temporiser les actions */
		boolean capteurGauche;
		boolean capteurDroit;
		
		/* Definition d'un objet action */
		ActionSimpleDuRobot action = new ActionSimpleDuRobot();
		
		/* Definitions des constantes de ''temps'' */
		final int TQUART = 100;			/* tourne d'1/4 */
		final int TDEMI = 2*TQUART;		/* tourne d'1/2 */
		final int PAUSE = 300;			/* temporise entre les actions */
		final int EVTC = 50;			/* dec. avant evt. c */
		
		/* Initialisation */
		ETAT = 'A';				/* etat initial */
		evt = 'a';				/* il ne se passe rien */
		
		/* Boucle de calcul de l'automate */
		while(true) {
			
			/* scruter les capteurs pour detecter les evenements */
			capteurGauche = Sensor.S1.readBooleanValue();
			capteurDroit = Sensor.S3.readBooleanValue();
			
			/* le capteur droit vient d'etre excite */
			if((capteurDroit == true) && (capteurGauche == false))
			{	evt = 'b'; }	
			/* le capteur gauche et le capteur droit viennent 
			 * d'etre excites */
			else if((capteurDroit == true) && (capteurGauche == true))
			{	evt = 'd'; }
			/* le capteur gauche vient d'etre excite */
			else if((capteurDroit == false) && (capteurGauche == true))
			{	evt = 'e'; }
			/* il ne se passe rien */
			else
			{	evt = 'a'; }
			
			/* Mise à jour de l'etat du robot en fonction des evenements,
			 * execution de son comportement.
			 * leJOS ne supporte pas la syntaxe switch(){}. Celle-ci 
			 * est donc remplacee par des imbrications de conditions */
			 
			 /* le robot avance */
			 if(ETAT == 'A') {
			 				 	
		 		if(evt == 'a')
		 		{
		 			/* continuer a avancer */
		 			action.avance();
		 			/* rester dans l'etat A */
		 			ETAT = 'A';	
		 		}
		 		else if(evt == 'b')
		 		{	
		 			/* passer a l'etat B */
		 			ETAT = 'B';
		 		}
		 		else if(evt == 'd')
		 		{
		 			/* passer a l'etat C */	
		 			ETAT = 'C';
		 		}
		 		else if(evt == 'e')
		 		{
		 			/* passer a l'etat D */
		 			ETAT = 'D';	
		 		}	
			 }
			 /* reculer puis tourner a gauche */
			 else if(ETAT == 'B') {
			 	
		 		action.stop();
		 		action.recul();	 			
	 			/* temporiser l'action de recul */
	 			for(tempo = PAUSE; tempo == 0; tempo--);
	 			action.stop();
	 			action.tourneGauche();
	 			/* pas d'odometrie, temporiser pour faire 1/4 de tours */
	 			for(tempo = 0; tempo == TQUART; tempo++);
	 			action.stop();	 	
		 		for(c = EVTC; c <= 0; c--);	/* c == 0, passer a l'etat A */
		 		ETAT = 'A';			 
			 }
			 /* Reculer puis faire un demi tour */
			 else if(ETAT == 'C') {
			 	
			 	action.stop();
			 	action.recul();
	 			/* temporiser */
	 			for(tempo = PAUSE; tempo == 0; tempo--);
	 			action.stop();
	 			action.tourneGauche();
	 			/* pas d'odometrie, temporiser pour faire 1/4 de tours */
	 			for(tempo = 0; tempo == TDEMI; tempo++);
	 			action.stop();		 	
		 		for(c = EVTC; c <= 0; c--);	/* c == 0, passer a l'etat A */
		 		ETAT = 'A';			 
			 }
			 /* reculer puis tourner a droite */
			 else if(ETAT == 'D') {
			 	
			 	action.stop();
			 	action.recul();	 			
	 			/* temporiser */
	 			for(tempo = PAUSE; tempo == 0; tempo--);		 			
	 			action.stop();
	 			action.tourneDroite();
	 			/* pas d'odometrie, temporiser pour faire 1/4 de tours */
	 			for(tempo = 0; tempo == TQUART; tempo++);
	 			action.stop();
		 		for(c = EVTC; c <= 0; c--);	/* c == 0, passer a l'etat A */
		 		ETAT = 'A';			 	
			 }
		} /* Fin while(1) */
	}
}

class ActionSimpleDuRobot {
	
	public void avance() {
		
		Motor.A.forward();	/* moteur gauche avance */
		Motor.C.forward();	/* moteur droit avance */
	}
	
	public void recul() {
		
		Motor.A.backward();	/* moteur gauche recul */
		Motor.C.backward(); /* moteur droit recul */
	}
	
	public void stop() {
		
		Motor.A.stop();		/* stop moteur gauche */
		Motor.C.stop();		/* stop moteur droit */
	}
	
	public void tourneGauche() {
		
		Motor.A.forward();	/* moteur gauche recul */
		Motor.C.backward();	/* moteur droit avance */
	}
	
	public void tourneDroite() {

		Motor.C.forward();	/* moteur droit recul */
		Motor.A.backward();	/* moteur gauche avance */		
	}
}

Analyse du comportement d'un robot : approche non déterministe

On cherchera ici à intégrer du hasard dans l'algorithme de comportement du robot. L'objectif étant d'essayer de suivre l'idée commune qui veut que l'introduction du hasard mène à des comportements non déterministe (et intuitivement que ça nous rapproche de l'intelligence). La conclusion de cette nouvelle approche risque d'en surprendre plus d'un.

Tendre vers un véritable comportement intelligent : l'apprentissage artificiel

On s'inspirera de l'exemple donné ici en cherchant à formaliser de la même façon que ci-dessus cette nouvelle approche. Nous essaierons de donner la conviction intuitive (car cela risque d'être très complexe d'un point de vue théorique) que cette façon de voir dépasse l'approche automatique classique et nous rapproche réellement de ce que l'on peut attendre d'un système d'intelligence artificiel pour robot.