For the purpose of exploring how a computer can navigate through a maze, this project examines how a robot’s surroundings can be interpreted, mapped and navigated through, by applying common maze solving algorithms. The execution of the project involves infrared sensors used to interpret a controlled environment, consisting of a twodimensional board with paths. Movement and navigation decisions will be made possible by two DCmotorized wheels mounted on a platform, two simple computers and two maze solving algorithms. The interpretation of the maze is done with infrared sensors by applying commonly used line following techniques, with some adjustments to care for the projects specific application. A single board computer with support for analog input is used for the line following and interpretation of crossroads. In addition with having another single board computer, with support for high level programming languages, a suitable data structure can be built for the purpose of the mapping. From this decisions regarding navigation will be made. The algorithm for mapping the maze and the decision making is implemented using Python 2. An experiment is performed to investigate the time consumption regarding two different algorithms, Wall follower and Trémaux. The implemented theories are discussed and the used algorithms are described thoroughly in this report. From the results, it can be understood that the Trémaux algorithm showed different results every test run, as it should. But the conclusion comes from the mean value of the time consumption. It shows that Trémaux was more effective than the Wall follower algorithm, with varying time differences of up to a couple of minutes. / I syfte att utforska hur en dator kan navigera i en labyrint undersöker detta projekt hur en omgivning kan kartläggas. Själva utförandet av projektet går ut på att bygga en robot som med hjälp av ljuskänsliga sensorer tolkar en kontrollerad miljö byggd med en platta med definierade vägar. Därefter navigerar den utifrån tolkningen med hjälp av DCmotorstyrda hjul monterade på en plattform, två simpla datorer och två olika labyrintlösande algoritmer. Tolkningen av labyrinten görs med hjälp av infraröda sensorer genom att använda vanliga linjeföljartekniker, med några justeringar för att passa just detta problem. En enkortsdator med stöd för analoga indata används för linjeföljandet och för tolkningen av vägkorsningar. Med ytterligare hjälp av en enkortsdator som stödjer högnivåspråk byggs en lämplig datastruktur för kartläggandet av labyrinten upp. Denna används sedan för att fatta beslut angående navigering. Själva algoritmen för kartläggandet och beslutsfattning implementeras i Python 2. Ett experiment görs i syfte att undersöka tidskonsumtionen angående två olika algoritmer, Wall follower och Trémaux. I denna rapport beskrivs och diskuteras även de använda teorierna kring algoritmerna utförligt. Från resultaten visar det sig att Trémaux algoritmen får olika tider varje testkörning, så som den bör göra. Men slutsatsen dras från medelvärdena av tidskonsumptionerna. Det som kan tas från resultaten är att Trémaux är mer effektiv än Wall follower med denna implementation, med varierande tidsskillnader upp till ett antal minuter.
| Identifer | oai:union.ndltd.org:UPSALLA1/oai:DiVA.org:kth-192069 |
| Date | January 2016 |
| Creators | REBECCA, WIKSTRÖM, MARTIN, SJÖGREN |
| Publisher | KTH, Maskinkonstruktion (Inst.) |
| Source Sets | DiVA Archive at Upsalla University |
| Language | English |
| Detected Language | Swedish |
| Type | Student thesis, info:eu-repo/semantics/bachelorThesis, text |
| Format | application/pdf |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | MMKB 2016:22 MDAB083 |
Page generated in 0.0028 seconds