Change search
ReferencesLink to record
Permanent link

Direct link
Amazeobot: The construction of a maze mapping robot
KTH, School of Industrial Engineering and Management (ITM), Machine Design (Dept.).
KTH, School of Industrial Engineering and Management (ITM), Machine Design (Dept.).
2016 (English)Independent thesis Basic level (degree of Bachelor), 10 credits / 15 HE creditsStudent thesis
Abstract [en]

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.

Abstract [sv]

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.

Place, publisher, year, edition, pages
2016. , 69 p.
Series
, MMKB 2016:22 MDAB083
National Category
Mechanical Engineering
Identifiers
URN: urn:nbn:se:kth:diva-192069OAI: oai:DiVA.org:kth-192069DiVA: diva2:957846
Supervisors
Examiners
Available from: 2016-09-05 Created: 2016-09-05 Last updated: 2016-09-05Bibliographically approved

Open Access in DiVA

fulltext(2357 kB)1 downloads
File information
File name FULLTEXT01.pdfFile size 2357 kBChecksum SHA-512
488421ab94ad5b7f168f0c8c0b7efe345da491dba933ed382c4a8d6e55fe82aa8008c1be733a8a442ac832c4af7226ce503ffaa6f593b16d8ae3e666b70ea4d3
Type fulltextMimetype application/pdf

By organisation
Machine Design (Dept.)
Mechanical Engineering

Search outside of DiVA

GoogleGoogle Scholar
Total: 1 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

ReferencesLink to record
Permanent link

Direct link