PoliArdo-Algoritmi rešavanja lavirinta

PoliArdo, projekat na kom rade učenici srednje škole Politehnika-škola za nove tehnologije, prošle godine je sa verzijom PoliArdo v1.0 postigao izvanredne rezultate na takmičenju u programiranju robota (učesnici Katarina Perendić i Danijel Končar), a ove godine ide se korak dalje-štampa robota na 3D štampaču, upotreba koračnih motora umesto DC motora kao i mnoge druge inovacije. Novi robot, PoliArdo v2.0, priprema se za takmičenje koje će se održati u aprilu 2017., a pripremaju ga Danijel Končar i Nikola Starčević kao naslednici Arduino sekcije.

poliardo1_v1-0

PoliArdo v1.0

PoliArdo v2.0 (priprema)

Na šta nas asocira reč „lavirint“?

Prva stvar koja nas asocira “lavirint” je sam izgled lavirinta koji ima puno zidova, hodnika, izlaz, prepreke i još mnogo toga. Zatim “Mit o lavirintu” i čudovištu u njemu. Dakle, drevne civilizacije su znale za postojanje lavirinta kao i algoritme za prolaz kroz njega. Postoji mnogo različitih algoritama, a mi ćemo vam predstaviti jedan koji se u praksi najčešće koristi.

Algoritam praćenja zida predstavlja jedan od najpoznatijih algoritama za pronalaženje izlaza iz lavirinta, a takođe je poznat kao “pravilo leve ruke” i “pravilo desne ruke”. Ukoliko je lavirint povezan, odnosno ako su svi njegovi zidovi međusobno spojeni, ili ako su spojeni sa spoljnom granicom lavirinta, tada ako robot (čovek) unutar lavirinta, prateći jednu stranu zida tokom celog prolaska kroz lavirint, sigurno dolazi do izlaza iz lavirinta, ako izlaz uopšte postoji, u suprotnom robot (čovek) se vraća na ulaz u lavirint i pritom obilazi svaku putanju u lavirintu barem jednom.

lavirint

Sada smo videli ideju prolaska kroz lavirint, ali još uvek ne znamo šta su to roboti.

Robot je mašina koju je čovek napravio da bi radila ono za šta je naučena odnosno isprogramirana. Postoje razne vrste robota. Mi ćemo za ovaj zadatak koristiti edukativnog robota u obliku vozila. Pošto robot nema ruke da bi mogao prođe kroz lavirint prateći upustva koje smo naveli, na njemu moraju da se nalaze senzori, odnosno čula robota koja bi mu vraćala informacije iz prostora. Najjednostavnije rešenje je da se na robota ugrade ultrazvučni senzori koji rade po principu radara. Oni šalju ultrazvučni signal ka zidu, on se odbija i vraća kao povratna informacija o udaljenosti zida. Time robot može da prati zid sve dok ne naiđe na neko skretanje odnosno raskrsnicu. Tada robot prima informaciju da je zid nestao i da mora da skrene na određenu stranu.

senzor

ultrazvučni senzor

Robot je sposoban da prati jedan zid uz pomoć senzora, ali postavlja se pitanje šta ako robot dođe u slepu ulicu. U tom slučaju on mora da se okrene. To znači da mora da ima još jedan senzor ispred sebe koji bi mu govorio o preprekama ispred njega.

Naravno, ultrazvučni senzor može da zameni i odredjeni broj infracrvenih dioda koje takođe vraćaju informacije robotu iz okoline. Robot, pošto ne zna kakav je lavirint, mora da prodje kroz sve njegove delove da bi došao do izlaza. Sada možemo da proširimo naš algoritam za rešavanje lavirinta na taj način što ćemo robotu programski da pamtimo kada je skrenuo, uleteo u slepu ulicu, vratio se i to preračunati u najkraći put. Tako da robot prilikom drugog puštanja sa istog mesta moze da prođe kroz lavirint najkraćim putem. On u memoriji ima preračunate vrednosti kao što su npr: skretanje levo ili desno, preskakanje dve raskrsnice sve dok ne dođe do izlaza. Ovako prolaženje kroz lavirint naziva se programsko jer robot ima zadatu putanju.

kolor-sensor

kolor senzor

Dok robot prvi put prolazi kroz lavirint on ujedno uči i snalazi se u prostoru i time unapređujemo razvijanje veštačke inteligencije.

Šta mislite o ovome?

Ostavite komentar