Robot dans un labyrinthe

**afaf06** · 04/01/2008, 16h12

bonjour, on aurait besoin d'aide pour réaliser un projet sur un robot qui se deplace dans un labyrinthe, le but du projet est de le sortir en effectuant le minimum de pas possible. pour celà, il est equipé d'un podomètre, ainsi que d'un capteur indiquant dans quelle direction le robot regarde (sachant qu'il connait les 4points cardinaux).
le robot doit tourner d'un quart de tour à droite à chaque fois qu'il est face à un mur, sinon si face à lui il y a un vide, il avance d'un pas, et le podomètre s'incremente + 1.
si quelqu'un peut nous aider, on a dejà la base 0 du projet, ainsi que quelques idées d'améliorations.
merci d'avance (sauvez nous la vie!!!!)
PS: le projet est à rendre le 12janvier 2008

**Trap D** · 04/01/2008, 17h00

Tel que tu décris la progression du robot, il n'y a pas vraiment de possibilités de choix, il trouvera la sortie, mais ce n'est pas forcément le plus court chemin. Il peut même se retrouver à son point de départ, si par hasard, le bon chemin est à gauche et non pas à droite. Peut-être n'as tu pas énoncé toutes les règles ?

**afaf06** · 04/01/2008, 18h48

en effet, si le robot se trouve à un point où par exemple sur les trois chemins possibles il en a dejà emprunté 2, il est obligé d'emprunter le troisième. et puis en général le robot prend forccement le chemin à sa droite, sauf donc s il l'a dejà emprunté il tourne encore d un quart de tour.
il nous manque les fonctions "tourner", "avancer" "boussole", et eventuellement "podomètre" à inserer dans la base 0.
je vous envoie la base 0 de projet, ça pourra peut etre vous eclairer un peu plus:

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
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
(define base '(
             ((mur sud) (tourner))
             ((mur ouest) (tourner))
             ((mur nord) (tourner))
             ((mur est) (tourner))
             ((vide sud) (avance))
             ((vide ouest) (avance))
             ((vide nord) (avance))
             ((vide est) (avance))
          )
             )
(define (decide etat percept)
  (evolue etat percept base) )
(define (evolue etat percept rules)
  (if (null? rules) etat
      (let* ( (first (car rules))
             (reste (cdr rules))
             (ok    (element etat percept first))
             )
        (if ok (nextstate first) (evolue etat percept reste)))
      )
  )
(define (element x y rule)
  (let ( (condition (car rule)) )
    (or (equal? x 'avance)
        (and (elem? x condition) (elem? y condition)))))


(define (elem? x l)
  (cond ((null? l) #f)
        ((equal? x (car l)) #t)
        (else (elem? x (cdr l)))))

(define (nextstate rule)
  (caadr rule))


(define (evolution cstate listE)
  (if (null? listE) cstate
      (evolution (decide cstate (car listE)) (cdr listE))))

**+Guilhem** · 04/01/2008, 19h55

Trap D a raison, il va trouver le bon chemin mais ce ne sera (sûrement) pas le plus court.

Pourquoi ne pas calculer d'abord le plus court chemin PUIS faire avancer le robot ?

P.S. : Utilise la balise [CODE] quand tu mets du code, sinon c'est illisible.

**afaf06** · 04/01/2008, 19h55

pitié il faut que vous nous aidiez... on est vraiment dans la merde

**afaf06** · 04/01/2008, 19h57

oui on y a pensé aussi, mais le problème c'est qu'on est tellement nulles en programation que d'abord on est pas capables de le faire, et en plus le prof le saurai si notre projet est compliqué qu'on s'est faites aidé!!!
vous pouvez nous aider????

**Garulfo** · 05/01/2008, 00h07

Envoyé par afaf06

oui on y a pensé aussi, mais le problème c'est qu'on est tellement nulles en programation que d'abord on est pas capables de le faire, et en plus le prof le saurai si notre projet est compliqué qu'on s'est faites aidé!!!
vous pouvez nous aider????

Ton problème n'a rien à voir avec la programmation. C'est encore un problème d'algorithmie. Tu n'as pas d'algorithme correct : tu ne peux espérer en faire un programme.

Commence pas chercher l'algorithme (dans le forum idoine si tu veux) puis quand tu auras un problème pour le coder en Scheme, tu pourras venir demander de l'aide ici.

De plus si ton but est de leurrer ton prof, tu n'es pas prêt d'obtenir de l'aide de ma part. Se faire aider n'est pas grave si tu comprends et que tu fais ta part des choses. Par contre plagier (faire passer pour soi, ce qui est aux autres) c'est grave. Il serait peut être intéressant d'en parler à ton prof en premier non ?

**afaf06** · 05/01/2008, 13h04

bien sûr qu'on comprend ce qu'on fait et qu'on essaie de faire qqc, le problème c'est qu'au bout de 3mois de programmation à frequence de 1h30 par semaine, on ne se sent pas vraiment capables de faire grand chose, surtout la syntaxe... on a fait les fonctions qui nous manque, le problème c'est que c'était mal ecrit, donc faux... merci pour ton encouragement

alex_pi · 05/01/2008, 13h31

Il est impossible, avec une vision locale du labyrinthe de déterminer un chemin optimal. Exemple

Code :

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

1
2
3
4
5
6
7
8

  1             2
 | |           | |
 | |           | |
 | |           | |
 | |___________| |
 |_______R_______|

Maintenant tu peux mettre la sortie en 1 ou en 2, et un long couloir de l'autre. Le robot, depuis sa position ne peux pas choisir. Il est donc impossible d'avoir un algo qui donne le meilleur résultat dans tous les cas.

De plus, si tu n'a pas d'assurance qu'il n'y a pas de cycle dans ton labyrinthe et que tu ne peux pas mettre de marque (poser un petit caillou ou une fleche...), je ne pense pas qu'il existe d'algorithme déterministe qui fonctionnera.

Bref, je confirme ce qui a été dit plus haut, avant de crier à l'aide sur un forum Scheme, prend un papier, un crayon, dessine des labyrinthe, et demande toi quel *algorithme* tu peux appliquer pour sortir de ton labyrinthe avec une vision locale des murs (dans le cas de l'absence de cylcle, il existe une méthode très connue, ça ne devrait vraiment pas poser de problème !)

**Garulfo** · 06/01/2008, 04h07

Envoyé par afaf06

bien sûr qu'on comprend ce qu'on fait et qu'on essaie de faire qqc, le problème c'est qu'au bout de 3mois de programmation à frequence de 1h30 par semaine, on ne se sent pas vraiment capables de faire grand chose, surtout la syntaxe... on a fait les fonctions qui nous manque, le problème c'est que c'était mal ecrit, donc faux... merci pour ton encouragement

Qui a dit que vous ne comprenez pas ce que vous faites ? Ce n'est pas ce que j'ai dit. Où est votre conception ? Mais où est l'algorithme ?

Je suis convaincu que vous n'avez pas une bonne conception. Vous devriez commencer par là. Une fois que vous avez cet algorithme, ce sera beaucoup plus facile. Allez donc poser la question dans la partie sur les algorithmes.

Puis après, le codage se fera aisément.

Au passage, 1h30 par semaine pendant 3 mois, c'est ridicule (sans être nullement offensant). Ça fait seulement, 18h. En général je demande au moins 5h/semaine à mes étudiants. Et les sessions durent 15 semaines, i.e. 75h de travail personnel. Certains petits projets dans le cadre demandent environ 18h par semaine par personne.

alex_pi · 06/01/2008, 11h06

Envoyé par Garulfo

Au passage, 1h30 par semaine pendant 3 mois, c'est ridicule (sans être nullement offensant). Ça fait seulement, 18h. En général je demande au moins 5h/semaine à mes étudiants. Et les sessions durent 15 semaines, i.e. 75h de travail personnel. Certains petits projets dans le cadre demandent environ 18h par semaine par personne.

Je pense justement qu'il dit qu'il n'a eu que ça comme cours, qu'il trouve aussi que c'est très peu, et que c'est pour ça qu'il a du mal, àmha

**Trap D** · 06/01/2008, 11h45

Envoyé par alex_pi

Je pense justement qu'il dit qu'il n'a eu que ça comme cours, qu'il trouve aussi que c'est très peu, et que c'est pour ça qu'il a du mal, àmha

Je pense que c'est "elle"

oui on y a pensé aussi, mais le problème c'est qu'on est tellement nulles en programation que d'abord on est pas capables de le faire, et en plus le prof le saurai si notre projet est compliqué qu'on s'est faites aidé!!!
vous pouvez nous aider????

Ceic dit sans être offensant le moins du monde.