Discussion :

[rouliow]

Bonjour,

J'ai un problème en IA que je dois réalisé en Lisp. J'ai une boite fermé ou il y a des block à l'interieur, et des choses à nettoyer. J'ai des capteur qui detecte les murs et les saletés. Le but et que mon robot puissent tout nettoyer le plus rapidement possible.

Le problème c'est que le robot part d'une origine et ne connait pas son environnement(pas les dimensions et ne sais pas ou sont les blocs et les saletés) alors il faut etre capable de lui allimenter sa base de connaissance et de lui faire prendre des décisions.

La solution que j'ai pensé pour arriver à parcourir toutes les cases serait de créer des regles:
Afin de toujours aller sur une case inexploré, et d'appliquer des regles de priorités comme d'habord essayer d'aller en haut, si c'est pas possible a droite etc(afin que le robot sache ou aller). Si toutes les cases autour de lui ont été visités, le faire retourner en arriere jusqu'a la derniere case ou on a fait un choix et qu'il etait possible de visiter une case inexploré. Si le robot ne peut pas attendre une case comme si elle etait bloqué par des murs, considérer que les cases ont été visités(car il ne peut rien faire a coze des obstacles)
Quand toutes les cases sont visitées retouner à l'orgine.

Il y a t'il une façon élégente de résoudre ce problème ? Si vous avez des idées d'algo je suis preneur.

Merci

ps : Pour plus d'info (http://www.cs.waikato.ac.nz/~bernhar...apter2_6pp.pdf)

[rouliow]

Pour illuster le probleme, le but est de nettoyer les saletés, de revenir a sa position initial tout en ne connaissant pas l'environement

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
   !---!---!---!---!---!---!
 5 ! # ! # ! # ! # ! # ! # !
   !---!---!---!---!---!---!
 4 ! # !   !   !   !   ! # !
   !---!---!---!---!---!---!
 3 ! # ! * ! # !   !   ! # !
   !---!---!---!---!---!---!
 2 ! # ! * !   ! # !   ! # !
   !---!---!---!---!---!---!
 1 ! # ! A ! # ! * !   ! # !
   !---!---!---!---!---!---!
 0 ! # ! # ! # ! # ! # ! # !
   !---!---!---!---!---!---!
     0   1   2   3   4   5

Figure 1: Example of an environment in the vacuum-agents world, # represents obstacles, * is dirt and A is the name of the agent.

[ToTo13]

Bonjour,

est ce que ton robot est capable de mesurer ses déplacement ?
- J'aurai tendance à faire partir ton robot tout droit jusqu'à ce qu'il rencontre un obstacle.
- Ensuite, on le fait rester le plus à gauche (ou droite) possible.
- Mais on note en permanence sa direction et son avancement (vitesse, distance parcourue).
- On obtiens ainsi une carte du contour de la pièce dans laquelle il se trouve.
- En cartographiant ainsi, on calcule lorsque l'on est revenu à un point déjà visité.
- Ensuite, on peut lancer le robot dans une direction afin qu'il nettoie les partie intérieures.

[rouliow]

Il peut mesurer ses deplacement, si je lui fournit cette fonctionnalité .

Je comptais enregistrer la position des cellules qu'il a visité (X1,Y1 X2,Y1) etc et essayé de lui faire visiter de nouvelles region quand il se retrouve bloqué.

Merci de ta réponse, ca revient un peu a ce que je voulais faire.

Bon allé j'apprend le lisp et je m'y met.

Merci

[ToTo13]

Bonjour,

je suis d'accord de lui faire visiter des cellules, mais dans la réalité, chaque cellule a une taille infiniment petite, je dirai même ponctuelle.

[ZZelle]

Bonjour,

est ce que ton robot est capable de mesurer ses déplacement ?
- J'aurai tendance à faire partir ton robot tout droit jusqu'à ce qu'il rencontre un obstacle.
- Ensuite, on le fait rester le plus à gauche (ou droite) possible.
- Mais on note en permanence sa direction et son avancement (vitesse, distance parcourue).
- On obtiens ainsi une carte du contour de la pièce dans laquelle il se trouve.
- En cartographiant ainsi, on calcule lorsque l'on est revenu à un point déjà visité.
- Ensuite, on peut lancer le robot dans une direction afin qu'il nettoie les partie intérieures.

Cette stratégie pose un petit problème si la pièce contient un mur intérieur (genre un pilier). Par contre la stratégie de Rouliow fonctionne dans ce genre de situation (dans la mesure où on arrive à découper la surface pavage avec des pavés de la taille du robot) mais est certainement moins optimale.

[Veovis]

L'algorithme utilisé pour ce genre de probléme est le POMDP (Partially Observable Markov Decision Process). Pour comprendre le principe des POMDP, une page vraiment bien faite : http://www.cassandra.org/pomdp/index.shtml