Lego og Labyrinter

Toke Høiland-Jørgensen, Morten Brandrup, Mads Hald Jørgensen & Thomas Petersen Bluhme

Studenteropgave: Semesterprojekt

Abstrakt

Vi har undersøgt hvilken algoritme der er den mest hensigtsmæssige, såvel teoretisk som praktisk, at anvende til at afsøge en labyrint. Derudover har vi undersøgt hvilke praktiske problemer der er ved at konstruere og programmere en Legorobot så den kan omsætte en fysisk labyrint til en form, som de valgte algoritmer kan bruge til at afsøge den og hvordan disse problemer kan afhjælpes. For at gøre dette har vi bygget en Legorobot, og programmeret den til at køre rundt i en fysisk labyrint. Vi har undersøgt algoritmerne Random Mouse, Not So Random Mouse, Tremaux's Algoritme og Recursive Backtracker. Algoritmerne er vurderet ud fra to kriterier: simplicitet og effektivitet. Vi har fundet at Random Mouse er den mest simple, efterfulgt af Not So Random Mouse, Recursive Backtracker og Tremaux's algoritme. Recursive Backtracker og Tremaux's algoritme er de mest effektive, hvor Recursive Backtracker er en smule bedre i den praktiske afprøvning. Vi har vægtet effektivitetskriteriet tungest, og konkluderer derfor at Recursive Backtracker er den mest hensigtsmæssige algoritme. Under konstruktionen har vi identificeret en række praktiske problemer og deres løsninger. Disse problemer involverer kalibrering af robotten, kørsel til midten af kryds, fantommålinger pga. unøjagtige sensorer, genkendelse af løkker i labyrinten samt problemer med crashes af den benyttede open source LeJOS-firmware.

UddannelserBasis - Naturvidenskabelig Bacheloruddannelse, (Bachelor uddannelse) Basis
SprogDansk
Udgivelsesdato20 jun. 2008
VejledereTorben Braüner

Emneord

  • kortlægning
  • afsøgning
  • lego
  • java
  • tremaux
  • labyrinter
  • lejos
  • algoritmer
  • lol