Intelligence artificielle dans un labyrinthe

Intelligence artificielle dans un labyrinthe - C - Programmation

Marsh Posté le 21-03-2006 à 23:15:18    

Bonjour à tous,
 
 
Je suis en train de réaliser une application en c, la partie graphique est réalisée avec sdl. Un robot doit se deplacement de facon autonome dans une piece (un labyrinthe) ou il y a des murs et divers obstacles. J'ai codé la génération du labyrinthe et le déplacement du robot mais je bloque sur l'intelligence artificielle.
 
En effet mon robot utilise une stratégie "vers la gauche" c'est a dire qu'il se déplace dans une direction tant qu'il le peut et quand il est bloqué (par un mur par exemple) il effectue diverses rotations (vers la gauche) jusqu'a pouvoir se deplacer dans une direction. Il tient compte aussi de la priorité c'est a dire qu'il passera en priorité dans un chemin qu'il n'a pas emprunté auparavant.
 
Mon problème est que le robot doit explorer TOUTE la salle et cela en un minimum de temps. J'ai regardé des algorithmes de pathfing comme celui de dijstra ou le A* mais j'ai l'impression que je fais fausse route ... car ces algorithmes sont utilisés pour trouver les chemins les plus court et non pas parcourir tout en ensemble ?
 
Pourriez vous m'aider  :jap: !
Merci d'avance!

Reply

Marsh Posté le 21-03-2006 à 23:15:18   

Reply

Marsh Posté le 22-03-2006 à 00:21:40    

bah solution super bourine :  
Dans une liste, tu mets toutes les salles de ton labyrinthe, et tu fais un parcours entre ton robot et la pièce, tu dépille, et tu continue comme ça, jusqu'a ne plus avoir de pièce dans ta liste.
 
spa génial mais bon  [:petrus75]


---------------
my flick r - Just Tab it !
Reply

Marsh Posté le 22-03-2006 à 00:39:56    

j'y avait justement pensé a chaque case on empile ses voisines mais je ne suis pas convaincu que ca va bien marcher... car on va totu de meme repasser par certaines cases un bon nombre de fois non?  
Mais est ce que c'est la seule solution personne ne connait des algorithmes permettant de resoudre ce problème?

Reply

Marsh Posté le 22-03-2006 à 01:10:08    

algo de couverture de sommet dans un graphe,
algo du voyageur de commerce

Reply

Marsh Posté le 22-03-2006 à 01:23:40    

Si tu ne connais pas à l avance le labyrinthe, mais que les salles sont de même taille, ton idée de dijstra c est mieux.
 
Tu est obligé de tester tous les murs du labyrinthe, soit avec le robot, soit avec la carte (salles adjacentes déjà explorées), mais c est avec un algo de plus court chemin seulement que tu peut te déplacer d un bout à l autre du labyrinthe de façon efficace.

Reply

Marsh Posté le 22-03-2006 à 10:26:45    

Les solutions de nargy seront très efficaces.
Sinon il existe une solution tout bête qui marche (sauf dans le cas de murs orphelins), c'est de suivre le mur qu'on a à droite.

Reply

Marsh Posté le 22-03-2006 à 10:36:26    

rital_5_4 a écrit :

J'ai codé la génération du labyrinthe et le déplacement du robot mais je bloque sur l'intelligence artificielle.


Quel rapport avec le langage C ? Il y a une section ALGO sur ce site.
 


---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/
Reply

Marsh Posté le 22-03-2006 à 11:16:39    

Théorie des graphes;
 
plus d'explications:
http://www.vieartificielle.com/art [...] php?id=161

Reply

Marsh Posté le 22-03-2006 à 11:24:21    

J ai essayé de formaliser un peu le problème.
 
D abord il s agit d une structure de graphe, dans tous les cas, aussi on a le choix entre 3 types d algos:
- parcours non cyclique: O(n)
- plus courts chemin: O(n*n)
- couverture de sommet: O(n^n)
 
Si on considère que l on ne peut connaître que la place des murs, on ne connait pas par avance ni la géométrie des salles, ni la disposition du labyrinthe:
le graphe est composé de:
- les coins
- les murs
Il y a exactement 2 murs pour 1 coin (car les murs ont une épaisseur):

Code :
  1. +-----------+
  2. |           |
  3. |    +---+  |
  4. |    |   |  |
  5. +----+   +--+


Le seul algo possible est celui du tournant à gauche.
 
Si on considère que l on connait par avance la géométrie des salles, par exemple elles ont toutes la même taille:

Code :
  1. O OOOOOOO
  2. O   O   O
  3. O * O O O
  4. O   O O O
  5. O * O O O
  6. O     O O
  7. OOOOOOO O


alors on est pas obligé de parcourrir tous les murs, on peut faire des supposition sur les salles adjacentes. Par exemple les mur marqués dune astérisque: quand on découvre un couloir on est pas obligé de le traverser si on a déjà exploré la salle à l autre bout.
Dans ce cas on peut utiliser un algo de plus court chemin.
 
Si on connait le labyrinthe à l avance, on peut utiliser un algo de couverture de sommet.
 
Dans le cas particulier du robot, il me semble que tu te trouve dans le cas n°1, mais tu peut te trouver dans le cas n°2 sans faire de supposition sur la géométrie des salles. Le robot, lorsqu il détecte un mur, a une précision. Il ne peut détecter des murs trop petits (même s il bloque dessus) ou des passages trop petits. Tu mesure la précision de mesure de ton robot, et alors tu te trouve dans le cas n°2: tu peut diviser le labyrinthe en carrés de taille égale à la précision. Le robot se met alors à parcourrir le labyrinthe en optimisant les trajectoires, et peut choisir le plus court chemin entre une zone explorée et non explorée.
 
Reste à traiter le cas particulier du mur trop petit sur lequel le robot bloque: dans ce cas tu agrandi le mur sur ta carte de carrés pour le représenter, et tu maintient une deuxième carte avec les position exactes mesurées.
 

Code :
  1. OO  OOOOOOOOO
  2. OO    OO    O
  3. O  OO O  O OO
  4. OO    O  O  O
  5. OO  O O  OO O
  6. OOO     OOO O
  7. OOOOOOOOOOO O


Message édité par nargy le 22-03-2006 à 11:25:04
Reply

Marsh Posté le 22-03-2006 à 12:26:48    

Merci à tous!

Citation :

Si on considère que l on ne peut connaître que la place des murs, on ne connait pas par avance ni la géométrie des salles


C'est le cas ici en fait le labyrinthe et générer de facon aléatoire et le robot ne connait pas le labyrinthe il l'explore case par case
 

Citation :

Si tu ne connais pas à l avance le labyrinthe, mais que les salles sont de même taille


Les salles ou plutot les pieces ont en effet toutes la meme taille et en fait chaque piece (case) peut avoir une cloison en haut en bas a gauche et a droite. L'ensemble des pieces formant le labyrinthe.
 
Je vais regarder tout ca cette apres midi je vous tiens au courant. Merci.


Message édité par rital_5_4 le 22-03-2006 à 12:30:30
Reply

Marsh Posté le 22-03-2006 à 12:26:48   

Reply

Marsh Posté le 30-05-2012 à 14:28:37    

Bonjour,
 
Je me permets de vous contacter au Sujet de votre post : Intelligence artificielle dans un labyrinthe.
Je suis actuellement en école d’ingénieur et j'ai le même projet à réaliser a quelques détails près qui sont que le robot peut se déplacer en diagonale et qu'il doit trouver la sortie en un minimum de coup.
Ayant redigé un code assez complexe et plutot long je voulais savoir si il vous été possible de m'envoyer vos sources (code source C) ou tout simplement de m'aider si vous  
en avez le temps.
 
Cordialement Hakim.
 

Reply

Marsh Posté le 30-05-2012 à 16:57:54    

Utilise le A*, c'est le plus optimisé je pense.
T'as des exemples sur le net, nous on ne peut te donner du code tout fait, par contre on est là pour t'aider.


---------------
Perhaps you don't deserve to breathe
Reply

Marsh Posté le 11-03-2016 à 11:25:01    

Bonjour, je viens juste de commencer le même travail que toi avec un robot a base d'arduino, mais j'arrive pas a trouvé une solution de parcours de toute la  labyrinthe en enregistrant les chemins non parcourus  :??:  :??:  :??:  :??:  :??:

Reply

Marsh Posté le 11-03-2016 à 11:26:43    

Bonjour, je viens juste de commencer le même travail que toi avec un robot a base d'arduino, mais j'arrive pas a trouvé une solution de parcours de toute la  labyrinthe en enregistrant les chemins non parcourus  :??:  :??:  :??:  :??:  :??:

Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed