Algorytm - mapowanie nieznanego obszaru

bronas · Październik 23, 2011

Witam,
jestem studentem politechniki na ostatnim roku.

Jako temat mojej pracy magisterskiej wybrałem:

"Opracowanie systemu mapowania nieznanego obszaru roboczego dla grupy autonomicznych robotów mobilnych klasy e-puck"

W skrócie muszę wymyślić algorytm mapowania nieznanego terenu przez 2 i więcej robotów klasy e-puck, zaprogramować je w programie Webots, po czym określić najbardziej optymalną ilość robotów do zmapowania tego terenu w jak najkrótszym czasie.

Jeżeli chodzi o sam algorytm mam już kilka pomysłów ale narazie mój promotor nie pieje z radości. Myślałem nad czymś na zasadzie kombajnów na polu gdzie jeden jedzie koło drugiego i w taki sposób najszybciej "przeskanują" cały teren no ale na polu uprawnym nie ma tylu przeszkód;/ Promotor doradzał, że tak to powiem, opierać się na naturze:) Tak więc patrząc na zachowanie ławic ryb czy stada ptaków natrafiłem na algorytm boid. Jednak jak dla mnie jest on trochę zbyt chaotyczny no ale narazie to mój najlepszy wybór.

I w tym miejscu prosiłbym o jakąkolwiek poradę, nakierowanie na jakieś algorytmy, które by tu pasowały.

Problem mapowania nieznanego teren jaki jest wiadomo. Jeżeli chodzi o sam obszar mapowania będzie to dośc proste, prostokątne pomieszczenie z kilkoma prostokątnymi przeszkodami. I tu następny problem. Jak poradzić sobie z nie zabłądzeniem robota. Dodam, że zamierzam programować w C. Poznałem wiele metod, najprostszym sposobem wydaje się zastosowanie latarni, ale czy da się to załatwić programowo czy takie latarnie muszą być rozmieszczone fizycznie w obszarze działania. Podobnie z samą mapą. Myślałem o stworzeniu siatki pól wypełnionych cyframi od 0 do 2 gdzie 0 oznacza niesprawdzone pole, 1 - sprawdzone i puste, a 2 - sprawdzone pole z przeszkodą. Też każda podpowiedz byłaby wielce pomocna.

No i jeżeli chodzi o sam program Webots - jeżeli ktoś miał z nim styczność, chętnie skorzystałbym z każdej pomocy.

Jestem na etapie zbierania informacji, także wszystko może okazać się pomocne:)

Z góry dziękuję za każdą odpowiedź.

Pozdrawiam.