Читать книгу Jak myślą inteligentne maszyny - Sean Gerrish - Страница 19

Być może kiedy byliście dziećmi, graliście w grę, w której udawało się, że podłoga w salonie jest tak naprawdę gorącą lawą. Celem uczestników było odnalezienie drogi w pokoju, unikając kontaktu z podłogą (czyli lawą), o ile istniała taka możliwość. Humvee miał przed sobą to samo zadanie, mianowicie musiał dotrzeć z bieżącej pozycji do następnego punktu mapy, z tą różnicą, że zamiast lawy musiał omijać niebezpieczne rejony pustyni.

Nie możemy jednak powiedzieć mu po prostu: znajdź odpowiednią drogę. Pamiętajmy, że kiedy Vaucanson projektował Flecistę, musiał wyposażyć figurę w instrukcje określające najmniejszą nawet czynność, dzięki czemu Flecista wypracował w końcu umiejętność gry na flecie. W tym przypadku jest podobnie: kiedy programujemy komputer, tak by odnalazł on odpowiednią drogę, musimy przedstawić mu jasną sekwencję kroków, dzięki którym będzie on w stanie odnaleźć ją samodzielnie. Te kroki przypominają przepis kulinarny, przy czym tutaj musimy wyraźnie opisać najdrobniejszy nawet detal.

Gdybyśmy mieli opisać formalnie proces, w ramach którego odnajdujemy drogę w wypełnionym lawą salonie, wyglądałoby to prawdopodobnie następująco. Po pierwsze, określilibyśmy w umyśle koszt wykonania kroku po danej powierzchni lub obiektach w salonie mniej więcej tak:

Tabela 2.1

Typ teren	„Koszt” jednego kroku
Dywan (lawa)	1
Stół	0,5 (mama będzie zła, ale lawa to jednak nie jest)
Kanapa	0
Śpiący pies lub kot	10

Następnie zaplanowalibyśmy drogę przez salon, szacując, która kombinacja kroków doprowadziłaby nas na drugi koniec pokoju najmniejszym możliwym kosztem. Zauważmy, że ujęliśmy problem odnalezienia odpowiedniej drogi w pojęciach minimalizacji funkcji (kosztu drogi). Jest to rzecz ważna, ponieważ uchwyciliśmy problem w kategoriach, na których dobrze znają się komputery. Nie radzą sobie z luźnym planowaniem drogi w złożonym środowisku, ale akurat w minimalizacji funkcji są niezłe. Koncept ten będzie co jakiś czas powracał w niniejszej książce.

W rajdzie, w którym wziął udział Humvee, liczył się czas, tak więc Red Team przypisał każdej komórce mapy o wymiarach metr na metr określony w sześciostopniowej skali koszt, który odzwierciedlał spodziewany czas, jaki zajmie pojazdowi przejechanie bezpiecznie jednego metra. Trudny teren uplasował się wyżej na skali kosztu niż teren łatwy, ponieważ po tym pierwszym Humvee musiałby poruszać się wolniej. Zespół przyznał specjalne kary tym częściom terenu, które były nieutwardzone, gdzie brakowało danych GPS, stromych i nierównych, a także tym komórkom mapy, które znajdowały się zbyt daleko od korytarza określonego współrzędnymi GPS. Dysponując już mapą z kosztem przypisanym każdej kwadratowej komórce, zespół musiał wyznaczyć odpowiednią drogę.

W przypadku znanej metody wyszukiwania ścieżki za pomocą algorytmu Dijkstry komputer wyszukuje ścieżkę przez podnoszenie „granicy” wyszukiwania z punktu startowego¹³. Program wykonuje pętlę, przesuwając nieco granicę wraz z każdym uruchomieniem pętli, dopóki granica nie osiągnie punktu docelowego. Wraz z podnoszeniem granicy przez program powoli zwiększa się koszt, który program skłonny jest ponosić za dotarcie do jakiegokolwiek punktu w ramach granicy; tak więc ilekroć rozciąga granicę, zawierając w niej kolejny punkt, ów nowy punkt lokuje się na krawędzi tego, ile program jest skłonny zapłacić. Z rozciągania granicy w taki sposób płynie taka oto korzyść, że można dzięki niemu prowadzić wyszukiwanie wśród najbardziej obiecujących tras – takich jak płaskie drogi, którym przypisany jest niski koszt – na długo przedtem, zanim przystąpi się do wyszukiwania w obrębie trudnych tras, na przykład trudnego terenu pozbawionego dróg.

W momencie gdy osiągnięty zostanie punkt docelowy – w przypadku samochodu autonomicznego jest to cel podróży – komputer wie już, że ścieżka istnieje, i zna także jej koszt. O ile komputer przechowuje dane na temat rozmieszczenia granic na mapie, może sprawnie cofnąć się i znaleźć najkrótszą ścieżkę do punktu docelowego. Ilustracje 2.3a, 2.3b i 2.3c ukazują, jak wygląda zarówno najkrótsza ścieżka, jak i granica wyszukiwania.

Informatycy i robotycy poświęcili wiele lat na badanie tego typu algorytmów i wiedzą, w jaki sposób w ułamku sekundy odnaleźć ścieżkę o najniższym koszcie na obszernych mapach. Jeśli zaś rozwiązaniem nie musi być najlepsza możliwa ścieżka, a jedynie ścieżka wystarczająco dobra, zajmuje im to jeszcze mniej czasu. Kiedy już zespół Red Team za pomocą algorytmu zaplanował trasę pojazdu, Humvee był gotowy do startu.

Ilustracja 2.3a. Przykładowa mapa. Ciemne odcienie oznaczają wyższy koszt podróży

Ilustracja 2.3b. „Granica” wyszukiwania w różnych iteracjach algorytmu Dijkstry

Ilustracja 2.3c. Optymalna ścieżka wiodąca przez mapę

(a) Mapa z czterema różnymi rodzajami terenu. Każda komórka siatki odpowiada metrowi kwadratowemu i przyjmuje jeden z czterech kolorów oznaczających określony typ terenu. Ciemniejsze odcienie powiązane są z wyższym kosztem i niełatwo jest je przebyć. Pozycja startu i pozycja mety zaznaczone są – odpowiednio – po lewej stronie i u góry ilustracji. Zaczynając od najjaśniejszego, a kończąc na najciemniejszym odcieniu, czas potrzebny na przebycie komórki wynosi 1, 3, 9, 18 sekund na metr; (b) Wybrane algorytmy wyszukiwania uruchomione przez podniesienie „granicy” wyszukiwania z punktu startowego. Każda granica reprezentowana jest przez linię konturu; ukazuje ona, jaki dystans przejedzie samochód w 175, 350, 525 i 700 sekund; (c) Po zakończeniu pracy algorytmu na mapie naniesiona jest najbardziej odpowiednia ścieżka wiodąca przez siatkę kosztu. W tym przypadku ścieżka utrzymuje się z reguły na jasnym terenie, po którym samochód może przejechać szybciej