Jaki algorytm powinienem wdrożyć, aby zaprogramować robota sprzątającego pomieszczenie?

W przypadku tego pytania załóż, że następujące rzeczy nie są znane:

• Rozmiar i kształt pokoju
• Lokalizacja robota
• Obecność wszelkich przeszkód

Załóżmy również, że następujące rzeczy są stałe:

• Rozmiar i kształt pokoju
• Liczba, kształt i lokalizacja wszystkich (jeśli w ogóle) przeszkód

Załóżmy, że robot ma następujące właściwości:

• Może poruszać się tylko do przodu w przyrostach jednostek bezwzględnych i obracać się w stopniach. Również operacja, która się porusza, zwróci prawdę, jeśli się powiedzie, lub fałsz, jeśli nie poruszy się z powodu przeszkody
• Racjonalnie nieograniczone źródło energii (powiedzmy, że jest to robot zasilany energią słoneczną, umieszczony na stacji kosmicznej, która cały czas jest skierowana w stronę słońca bez sufitu)
• Każdy ruch i obrót odbywa się za każdym razem z absolutną precyzją (nie martw się o niewiarygodne dane)

Na koniec rozważ następujące właściwości środowiska robota:

• Znajdując się na stacji kosmicznej bez sufitu, pokój jest bezpieczny, ale frustrująco blisko odległości od mijających komet, więc pył (i lód) stale zaśmiecają środowisko.

Poproszono mnie o znacznie prostszą wersję tego pytania (pokój jest prostokątem i nie ma żadnych przeszkód, jak możesz się nad nim poruszać, gwarantując, że możesz przejechać każdą część przynajmniej raz) i po tym, jak zacząłem zastanawiać się, jak byś do niego podszedł, gdybyś nie mógł nie gwarantuje kształtu ani obecności przeszkód. Zacząłem patrzeć na to z algorytmem Dijkstry , ale jestem zafascynowany tym, jak inni podchodzą do tego (lub czy istnieje dobrze przyjęta odpowiedź? (Jak robi to Roomba?)

O ile mi wiadomo, ten problem nie został „rozwiązany”.

Formalnie jest to problem z zasięgiem online. Pokrycie, ponieważ musimy pokryć każdy punkt na podłodze, a także online, ponieważ nie mamy dostępu offline do mapy. Jeśli interesują Cię najnowsze wyniki, sugeruję, byś poszukał „ robotycznych algorytmów pokrycia online ”, być może w Google Scholar (istnieje wiele wspaniałych wyników). Oprócz bardzo kolorowego (re) postu @ embedded.kyle dodam kilka szczegółów (postaram się również szybko znaleźć kilka prostych wyników):

• Dijkstra's zapewni ci ścieżkę, ale niekoniecznie zasięg. Na przykład, w jaki sposób określasz Dijkstry, że musisz odwiedzić każdy punkt na wykresie, zamiast odwiedzać jeden punkt tak szybko, jak to możliwe? Możesz uruchomić wszystkie pary najkrótszych ścieżek, ale jakie są punkty? Nie masz mapy.

• Takie algorytmy online są często nazywane algorytmami „błędów”, ponieważ wyglądają jak robaki wędrujące po danym obszarze, wpadające na coś, a następnie wędrujące trochę wokół niego.

• Bez przeszkód i prostokątnego pokoju, a zakładając, że zaczniesz na granicy, optymalna jest ścieżka bulwarofonu (droga wołu).

Zabawne, że rolnicy robili to od zawsze, prawda? http://en.wikipedia.org/wiki/Boustrophedon . Można to rozszerzyć na pomieszczenia z przeszkodami, znajdując z grubsza prostokątny obszar wolny od przeszkód. Howie Choset trochę nad tym pracował .

• $\pi*d^2$$d$
• To ogromny, fascynujący obszar. Przepraszam, nie mogę przedstawić lepszego podsumowania!

Największym problemem jest to, że nie masz mapy. Bez mapy jesteś ograniczony do prostych działań, takich jak podążanie obwodu i poruszanie się wzdłuż ścieżki (jak wspomniana spirala). Istnieją więc roboty, które budują mapę podczas czyszczenia, rozkładają odwzorowany obszar na kształty, a następnie pokrywają każdy kształt, aby zapewnić pokrycie. Zobacz: http://mintcleaner.com/

Robot Roomba zaczyna się spiralnie, dopóki nie trafi w coś, a następnie wykonuje zamiatanie po obwodzie. Potem odbija się. Roomba jest de facto standardem w domowych robotycznych odkurzaczach, myślę, że można to nazwać „przyjętym rozwiązaniem”. Ale z własnego doświadczenia (posiadam dwa) zdecydowanie można poprawić.

Z tego, jak działają rzeczy :

Z wywiadu z Nancy Dussault Smith, wiceprezesem ds. Komunikacji marketingowej w iRobot:

Kiedy się zacznie, zauważysz spiralny wzór, będzie on spiralnie przewijał się na coraz większym obszarze, aż uderzy w obiekt. Kiedy znajdzie przedmiot, będzie podążał wzdłuż krawędzi tego obiektu przez pewien czas, a następnie zacznie się kręcić, próbując obliczyć największą odległość, jaką może przebyć, nie uderzając w inny obiekt, a to pomaga mu wyliczyć jak duża jest ta przestrzeń, ale jeśli będzie trwać zbyt długo, nie uderzając o ścianę, zacznie znów kręcić się spiralnie, ponieważ pokazuje, że znajduje się na szeroko otwartej przestrzeni, i ciągle to oblicza i wymyśla.

Podobnie jest z czujnikami brudu pod spodem, gdy jeden z tych czujników zostanie wyzwolony, zmienia swoje zachowanie, aby pokryć ten obszar. Następnie wyruszy w poszukiwaniu innego brudnego obszaru na prostej ścieżce. Sposób, w jaki te różne wzory nakładają się na siebie, wiemy, że jest to najbardziej skuteczny sposób na pokrycie pokoju.

Wybrane przez nas wzorce i sposób, w jaki algorytm został pierwotnie opracowany, opierały się na algorytmach behawioralnych zrodzonych z MIT badających zwierzęta oraz o tym, jak chodzą w poszukiwaniu żywności. Kiedy patrzysz, jak mrówki i pszczoły wychodzą, a one przeszukują obszary, tego rodzaju zasięg i wymyślenie tego wszystkiego wynika z tych badań. Oczywiście nie jest to dokładne, nie mówię, że jesteśmy pszczołami miodnymi, ale to zrozumienie, jak szukać obszaru w naturze, jest podstawą rozwoju naszej technologii adaptacyjnej.

Niektóre zdjęcia Roombas z długimi czasami ekspozycji z diodami LED ilustrują, jak to działa w praktyce:

Neato stosuje podejście zorganizowane. Używając SLAM i zderzaków, mapuje „bieżący” pokój, najpierw obwód, a następnie stosuje algorytm do czyszczenia tak skutecznie, jak to możliwe. Nigdy nie miałem Roomby, ale biorąc pod uwagę to, co przeczytałem o jego algorytmie, nigdy nie przeszedłbym z neato.

Laserowy dalmierz w neato jest często kannabilizowany dla robotyki, ponieważ jest opłacalnym czujnikiem dla algorytmów SLAM.

Gdybym otrzymał twoje zadanie, najpierw znajdę odpowiednią implementację SLAM , w oparciu o posiadany sprzęt.

Następnie użyłbym algorytmu planowania CNC ISLAND Motion . Z mojego doświadczenia wynika, że ​​są one bardzo skuteczne w pokonywaniu dowolnego obszaru przy najmniejszej ilości ruchu.

Pierwszą rzeczą, którą musisz ustalić, jest cel robota - nie do końca jasne w swoim pytaniu. Robot musi wykonać dwa główne zadania: odkryć kształt obszaru, który można wyczyścić, a następnie go wyczyścić.

Ale czy ilość brudu jest stała? Czy brud jest stale dodawany? Czy Twoim celem jest zminimalizowanie średniego czasu pozostawania brudu na podłodze, czy średniego czasu? Czy celem jest utrzymanie podłogi w równej czystości? A może wystarczy raz wyczyścić tak szybko, jak to możliwe? Czy istnieją wzorce gromadzenia się brudu, które można zmierzyć i wykorzystać na swoją korzyść w osiąganiu celu?

Odpowiedź na te pytania pomoże wskazać wybrany algorytm. W przypadku robota robota Roomba nauczenie się dokładnego układu pomieszczenia może nie mieć sensu, ponieważ meble (takie jak krzesła wokół stołu), ludzie i inne przeszkody poruszają się bardzo często. Jednak w twoim przypadku może być lepiej zbadać przestrzeń, aby zbudować pełną mapę (pewną kombinację wzoru kosiarki do trawy ze znajdowaniem krawędzi), a następnie użyć tej mapy, aby obliczyć najkrótszą ścieżkę przez przestrzeń (termin to „zasięg”, i jest na to kilka sposobów, np. algorytm drzewa opinającego .

Jeszcze jedną rzeczą, o którą musisz się martwić, jest sposób dyskretyzacji przestrzeni, w której się znajdujesz. Ponieważ możesz poruszać się w dowolnym kierunku - nawet przy liczbach całkowitych i jednostkach odległości całkowitej - pozycje X i Y mogą mieć ułamek wartości. Musisz zdecydować, w jaki sposób reprezentować przeszkody na tej mapie, bez rozrastania się do nieskończonej liczby punktów danych.

Nie jestem pewien, czy nadal go potrzebujesz, ale dla tych, którzy akurat google w tym wątku, stworzyłem jedną prostą wersję algorytmu.

Zasadniczo próbuje zbudować mapę obszaru podczas czyszczenia i używa mapy, aby znaleźć najbliższy niezapisany węzeł (część pokoju). Jeśli nie można go znaleźć, oznacza to, że pokój jest sprzątany (lub nieoczyszczone części są niedostępne dla robota).

Może być wolniejszy niż inny algorytm, ale może zagwarantować zasięg niezależnie od pozycji początkowej, kierunku i przeszkód.

https://github.com/dungba88/cleaner_robot

AKTUALIZACJA: Stworzyłem tutaj wersję demo i porównuję ją z cofającym się DFS. Mimo że moim algorytmem jest O (N ^ 2), jest on znacznie bardziej zoptymalizowany pod względem liczby ruchów i obrotów.

http://jenova.dungba.org/cleaner/showdown

Patrząc na prostszy problem, o który zostałeś poproszony - prostokątny pokój bez przeszkód i przynajmniej raz wyczyść każdą część .

Rozwiązaniem jest znalezienie rogu pokoju, a znalezienie rogu nie będzie dużym problemem. Gdy to zostanie osiągnięte, po prostu idź spiralną ścieżką do centrum pokoju.