Roboty Mobilne

Opisane wcześniej układy dłoni - systemy oczne mogą być uważane za "roboty", ale nie mogły poruszać się ze swojej ustalonej bazy. Do tego czasu niewiele robiono na robotach mobilnych, mimo że zyskiwały one znaczącą pozycję w nauce. Wspomniałem już o "żółwiach Graya", które były wczesnymi wersjami autonomicznych robotów mobilnych. Na początku lat 60. naukowcy z Laboratorium Fizyki Stosowanej Uniwersytetu Johna Hopkinsa zbudowali robota mobilnego o nazwie "Bestia". Kontrolowany przez pokładową elektronikę i kierowany czujnikami sonarowymi, fotokomórkami i ramieniem "wyczuwającym płytę ścienną", mógł wędrować po korytarzach o białych ścianach w poszukiwaniu ciemnych wtyczek zasilania. Po znalezieniu jednego, a jeśli jego baterie byłyby słabe, podłączałby się i ładował jego baterie. System jest opisany w książce Hansa Moravca. Od połowy lat 60. kilka grup zaczęło pracować nad robotami mobilnymi, w tym AI Labs w SRI i Stanford. Zacznę od obszernego opisu Projekt robota SRI dla niego dostarczył bodźca do wynalezienia i integracji kilku ważnych technologii AI.

Shakey, robot SRI

W listopadzie 1963 r. Charles Rosen, lider badań sieci neuronowych w SRI, napisał notatkę, w której zaproponował opracowanie mobilnego "automatu", który łączyłby funkcje rozpoznawania wzorców i pamięci sieci neuronowych z programami AI wyższego poziomu { takie jak były opracowywane w MIT, Stanford, CMU i gdzie indziej. Rosen wcześniej uczestniczył w letnim kursie na UCLA na LISP prowadzonym przez Bertrama Raphaela, który kończy doktorat w SIR ,na MIT. Rosen, i inni w jego grupie natychmiast zaczęli myśleć o robotach mobilnych. Zatrudnili również Marvina Minsky′ego jako konsultanta, który miał pomagać. Minsky spędził dwa tygodnie w SRI w sierpniu 1964 roku. Zrobili pierwszą z wielu podróży do biura ARPA (w tym czasie w Pentagonie), aby wzbudzić zainteresowanie wspieraniem badań robotów mobilnych w SRI. Rozmawialiśmy również z Ruth Davis, dyrektorem Departamentu Badań i Inżynierii Obronnej (DDR i E) - biura odpowiedzialnego za wszystkie badania Departamentu EFENS. W kwietniu 1964 r. Napisali do DDR & E propozycję "Badania w inteligentnych automatach (faza I)", która, jak twierdzili, ostatecznie doprowadziły do opracowania maszyn, które będą wykonywać zadania, które obecnie uważa się za wymagające ludzkiej inteligencji. "Propozycja wraz z kilkoma wyjazdami i dyskusjami zakończyła się w listopadzie 1964 r. oświadczeniem "work" wydanym przez ówczesnego dyrektora ARPA Biuro Technik Przetwarzania Informacji, Ivan Sutherland. Fragment poniższy opisuje cele programu.



W międzyczasie Bertram Raphael ukończył studia doktoranckie MIT. Dyplom uzyskał w 1964 i objął stanowisko w UC Berkeley na rok akademicki. W kwietniu 1965 r. przyjął ofertę dołączenia do SRI, aby zapewnić naszej grupie niezbędną wiedzę specjalistyczną w zakresie sztucznej inteligencji. Po kilku projektach propozycji badań i dyskusjach z osobami w odpowiednich biurach Departamentu Obrony (skomplikowane tym, że Ivan Sutherland opuścił ARPA w tym czasie), SRI otrzymało w końcu dość duży (jak na razie) kontrakt oparty zasadniczo na pracy Sutherlanda . Datą "rozpoczęcia pracy" w projekcie, którym zarządzało ARPA przez Rome Air Development Center (RADC) w Rzymie w Nowym Jorku, był 17 marca 1966 r. Ruth Davis odegrał znaczącą rolę w zachęcaniu ARPA i RADC do kontynuacji realizacji projektu. "Łączenie" kilku różnych technologii AI było jednym z głównych wyzwań i jednym z głównych wkładów projektu automatyki SRI. Jednym z zadań była faktyczna budowa pojazdu-robota, którego działania byłyby kontrolowane przez pakiet programów. Z powodu różnych dziwactw inżynieryjnych pojazd zatrząsł się, gdy nagle się zatrzymał. Wkrótce nazwaliśmy go "Shakey", chociaż jeden z badaczy uważał to za zbyt lekceważące. [Shakey został wprowadzony do "Robot Hall of Fame" ( wraz z C-3PO między innymi) ] w 2004 r. Został również uznany jako piąty najlepszy robot wszechczasów (spośród 50) według magazynu Wired w styczniu 2006 r. Numery 2 i 4 Wireda były oficjalne, "Spirit" i "Opportunity" (roboty masrsjańskie) były numerem 3, a "Stanley" (zwycięzca 2005 roku DARPA "Grand Challenge") została uznany "robotem wszech czasów nr 1". Shakey jest teraz wystawiany w Computer History Museum w Mountain View, Kalifornia.]

Shakey miał wbudowaną kamerę telewizyjną do robienia zdjęć otoczenie, laserowy dalmierz (triangulujący, nie określający czasu) do wykrywania jego odległości od ścian i innych obiektów oraz wykrywacze guzów przypominające kocie wąsy. Środowiskiem Shakeya była kolekcja "pokoi" drzwiami, ale oddzielonych niskimi ścianami, które moglibyśmy wygodnie zobaczyć, ale Shakey nie. Niektóre pokoje zawierały duże obiekty. Większość programów, które opracowaliśmy w celu kontrolowania Shakey, działała na komputerze DEC PDP-10. Między PDP-10 a samym pojazdem mobilnym znajdował się komputer peryferyjny PDP-15 (do obsługi dolnej poziom komunikacji i poleceń do sprzętu pokładowego) oraz dwukierunkowe łącze radiowe i wideo. Programy PDP-10 były zorganizowane w tak zwanej hierarchii "trójwarstwowej". Programy na najniższym poziomie napędzały wszystkie silniki i przechwycone informacje sensoryczne. Programy na poziomie pośrednim nadzorowały prymitywne działania, takie jak przejście do wyznaczonej pozycji, a także przetwarzały obrazy wizualne z kamery telewizyjnej Shakeya. Planowanie bardziej złożonych działań, wymagających wykonania sekwencji pośredniej Działania na tym samym poziomie były wykonywane przez programy na najwyższym poziomie hierarchii. Projekt Shakey obejmował integrację kilku nowych wynalazków w technikach wyszukiwania, w solidnej kontroli działań, w planowaniu i nauce oraz w wizji. Wiele z tych pomysłów jest dziś powszechnie używanych.

A*: Nowa heurystyczna metoda wyszukiwania

Jednym z pierwszych problemów, które rozważano, było zaplanowanie sekwencji "punktów nawigacyjnych", których Shakey mógł użyć podczas nawigacji z miejsca na miejsce. Aby ominąć pojedynczą przeszkodę leżącą między pozycją początkową a pozycją bramkową, Shakey powinien najpierw skierować się w stronę punktu w pobliżu okludującej granicy przeszkody, a następnie skierować się prosto w kierunku niezakłóconego końcowego punktu bramkowego. Sytuacja staje się jednak bardziej skomplikowana, jeśli środowisko jest wypełnione wieloma przeszkodami i szukaliśmy ogólnego rozwiązania tego trudniejszego problemu. Shakey zachował informacje o położeniu przeszkód i własnej pozycji w modelu siatki takim jak ten pokazany poniżej

(Aby uzyskać wymaganą dokładność, komórki siatki zostały rozłożone na mniejsze komórki w pobliżu obiektów. Myślę, że było to jedno z pierwszych zastosowań adaptacyjnego rozkładu komórek w planowaniu ruchu robota i jest obecnie powszechnie stosowaną techniką.) Weźmy na przykład pod uwagę problem z nawigacją, w którym Shakey jest w pozycji R i musi podróżować do G (gdzie R i G są oznaczone zacienionymi kwadratami). Może użyć komputerowej reprezentacji modelu siatki do zaplanowania trasy przed rozpoczęciem podróży - ale jak? Mapa pokazuje pozycje trzech obiektów, których należy unikać. Obliczenie lokalizacji niektórych kandydujących punktów orientacyjnych w pobliżu rogów obiektów nie jest trudne. (Punkty te muszą być wystarczająco daleko od rogów, aby Shakey nie wpadł na przedmioty.) Punkty trasy są oznaczone zacienionymi gwiazdami i oznaczone "A", "B" i tak dalej przez "K." Korzystając z technik znanych obecnie w grafice komputerowej, nietrudno jest również obliczyć, które punkty nawigacyjne są osiągalne, korzystając z pozbawionej przeszkód prostej linii z dowolnego innego punktu nawigacyjnego oraz od R. i G. Patrząc w ten sposób, problem nawigacji Shakeya jest problemem wyszukiwania, podobnym do tych, o których wspominałem wcześniej. Oto, w jaki sposób można zbudować drzewo wyszukiwania, a następnie wyszukać najkrótszą ścieżkę od R do G. Po pierwsze, ponieważ do A i F można bezpośrednio dotrzeć pozbawionymi przeszkód, prostymi ścieżkami z R, są one ustawione jako potomek bezpośredni "wezłów" R w drzewie wyszukiwania. Kontynuujemy proces obliczania węzłów potomnych (wzdłuż ścieżek prostych bez przeszkód) z każdego z A i F i tak dalej, aż do drzewa zostanie dodane G. Następnie jest to prosta kwestia, aby zidentyfikować najkrótszą drogę od R do G. Kilka metod przeszukiwania drzew (i ich bardziej ogólnych kuzynów, wykresów) było już używanych w połowie lat 60. XX w. Jednym z argumentów przemawiających za tymi znanymi metodami było zagwarantowanie do znalezienia najkrótszych ścieżek używanych do rozwiązania problemów nawigacyjnych Shakeya. Mogą one jednak być niewykonalne obliczeniowo w przypadku trudnych problemów. Oczywiście rozwiązywanie prostych problemów z nawigacją (takich jak na schemacie) nie wymaga dużego wyszukiwania, więc każda metoda wyszukiwania szybko rozwiązuj takie problemy, ale opanowane metodami ogólnymi, które skutecznie działałyby na większe, trudniejsze problemy. Znałem heurystyczną metodę wyszukiwania zaproponowaną przez J. Dorana i Donalda Michie do rozwiązania ośmioczęściowej układanki z przesuwanymi kafelkami. Przypisali wartość liczbową do każdego węzła w drzewie wyszukiwania, w oparciu o szacunkową trudność osiągnięcia celu z tego węzła. Węzłem o najniższym wyniku był ten, który został wybrany obok generowanych potomków. Uznałem, że dobrym "heurystycznym" oszacowaniem trudności w dostaniu się z pozycji punktu drogi do celu (przed dalszym szukaniem dalej) byłaby "odległość linii lotniczej", ignorując wszelkie przeszkody pośrednie, od tej pozycji do celu. Zasugerowałem, abyśmy wykorzystali tę ocenę jako wynik odpowiedniego węzła w drzewie wyszukiwania. Bertram Raphael, który wówczas kierował pracą nad Shakey, zauważył, że lepszą wartością dla wyniku byłaby suma odległości przebytej tak daleko od pozycji początkowej plus moje heurystyczne oszacowanie, jak daleko robot musiał się posunąć. Raphael i ja opisaliśmy ten pomysł Peterowi Hartowi, który niedawno uzyskał stopień doktora. ze Stanford i dołączył do naszej grupy w SRI. Hart wspomina "wracając do domu tego dnia, siedząc na określonym krześle i wpatrując się w ścianę przez ponad godzinę, i dochodząc do wniosku", że jeśli oszacowanie pozostałej odległości (cokolwiek by to było) nigdy nie było większe niż faktyczna pozostała odległość, to zastosowanie takiego oszacowania w naszym nowym schemacie punktacji zawsze znajdowałoby ścieżkę mającą jak najkrótszą odległość do bramki. (Oczywiście, moja heurystyczna odległość linii lotniczej spełniła bardziej ogólny stan Hart'a.) Ponadto, pomyślał, że taka procedura wygeneruje drzewa wyszukiwania nie większe niż jakiekolwiek inne procedury, które gwarantowałyby również najkrótsze ścieżki i które wykorzystywałyby oceny heurystyczne nie lepiej niż nasz. Razem Hart, Raphael byli w stanie stworzyć na to dowody ,twierdzi, a wynikowy proces wyszukiwania nazwali "A*". ("A" dotyczyło algorytmu, a "*" oznaczało jego szczególną właściwość znalezienia najkrótszych ścieżek. Myślę, że Hart i Raphael wykonali większość ciężkiego podnoszenia przy opracowywaniu dowodów.) Kiedy ścieżki wiążą się z kosztami, które zależą od więcej niż tylko odległość, a gdy takie koszty (a nie odległości) są uwzględniane przy obliczaniu wyników, A* gwarantuje ścieżki o najniższych kosztach. Uwzględnienie oszacowania pozostałej odległości (lub kosztu) do celu przyczynia się do poszukiwania w ogólnym kierunku celu. Uwzględnienie dotychczasowego dystansu (lub kosztu) zapewnia, że proces wyszukiwania nie będzie na zawsze prowadzony obiecującymi, ale być może daremnymi ścieżkami i będzie w stanie "przecinać" przeszkody. A* został przedłużony na wiele sposobów {szczególnie Richarda Korfa, aby uczynić go bardziej praktycznym, gdy pamięć komputera jest ograniczona. Obecnie A* jest używany w wielu aplikacjach, w tym w parsowaniu języka naturalnego, obliczaniu wskazówek dojazdu i interaktywnych grach komputerowych.

Solidne wykonanie akcji

Algorytm A* został osadzony w programach Shakey′a do nawigacji z jednego miejsca do drugiego w pomieszczeniu zawierającym przeszkody i do popychania obiektu z jednego miejsca do drugiego. Programy nawigacyjne wraz z innymi zajmowały środkowy poziom w hierarchii programów Shakeya. Te programy na poziomie średnim zostały zaprojektowane tak, aby osiągnąć określone cele, takie jak na przykład postawienie obiektu przed wejściem. Byli również dość solidni w tym, że "próbowali" nawet w obliczu nieprzewidzianych trudności. Na przykład, jeśli obiekt, który został popchnięty, przypadkowo ześlizgnął się z przedniego "paska popychającego", program pchający zauważył ten problem (poprzez wbudowane czujniki kontaktowe na pasku popychającym) i przestawiono Shakey, aby mógł ponownie połączyć obiekt i kontynuować pchanie. Myśląc o tym, jak osiągnąć tę wytrzymałość, zainspirowały mnie zarówno urządzenia TOTE Millera, Galantera i Pribrama, jak i idea homeostazy. (Przypomnij sobie, że jednostka TOTE do wbijania gwoździ wali, dopóki gwóźdź nie zostanie całkowicie wbity, a systemy homeostatyczne podejmują działania w celu przywrócenia ich stabilności w obliczu postrzeganych zakłóceń środowiska.) Chciałem, aby programy na średnim poziomie szukały i wykonały akcję, która była zarówno "najbliższa" realizacji ich celów, i która faktycznie mogłaby zostać wykonana w obecnej sytuacji. Jeśli wykonanie tej akcji doprowadziłoby do sytuacji, w której, zgodnie z przewidywaniami, można by wykonać akcję jeszcze bliższą osiągnięcia celu, dobrze, program na średnim poziomie przynajmniej robił postępy. Jeśli nie, lub coś nieoczekiwanego spowodowałoby niepowodzenie, następna akcja zostałaby wykonana w celu powrotu na właściwe tory. Opracowaliśmy z Richardem Dudą format zwany "tabelami Markowa" do pisania programów na poziomie pośrednim posiadających tę właściwość "próbowania"

STRIPS: Nowa metoda planowania

Programy na średnim poziomie mogą wykonywać szereg prostych zadań, takich jak przenoszenie Shakey z jednego miejsca do drugiego w tym samym pokoju, pchanie przedmiotów i przenoszenie Shakey przez drzwi do sąsiedniego pokoju. Jednak przejście do jakiegoś odległego pokoju i popchnięcie tam jakiegoś obiektu w wyznaczone miejsce wymagałoby połączenia sekwencji kilku programów na średnim poziomie. Tak jak ludzie czasami tworzą, a następnie wykonują plany wykonania swoich zadań, chcieliśmy, aby Shakey był w stanie opracować plan działań, a następnie wykonać plan. Plan składałby się z listy programów do wykonania. Informacje potrzebne do planowania zostały zapisane w tak zwanym "modelu aksjomatycznym". Ten model zawierał logiczne stwierdzenia w języku rachunku predykatów (o którym mówiłem wcześniej). Na przykład położenie Shakeya było reprezentowane przez instrukcję taką jak AT (ROBOT, 7,5), fakt , że Box1 jest przesuwalny, było reprezentowane przez instrukcję PUSHABLE (BOX1), a fakt, że między drzwiami R1 i R2 istniało przejście o nazwie D1, reprezentowane było przez JOINSROOMS (D1, R1, R2). Model aksjomatów miał prawie dwieście takich stwierdzeń i był podstawą zdolności rozumowania i planowania Shakeya. Pierwsza próba budowy planów Shakey wykorzystywała system dedukcji QA3 i rachunek sytuacji. Poprosilibyśmy QA3 o udowodnienie (przy użyciu wersji modelu aksjomat), że istniała sytuacja, w której cel Shakeya (na przykład przebywanie w odległym pokoju) był prawdziwy. Wynik odliczenia (jeśli się powiedzie) nazwałby tę sytuację kategorią działania na średnim poziomie do wykonania. Wykorzystanie rachunku sytuacyjnego do planowania, jak zestawiać działania średniego szczebla, przy użyciu logicznych instrukcji opisujących wpływ tych działań na sytuacje. Musieliśmy nie tylko opisać, w jaki sposób akcja na średnim poziomie zmieniła pewne rzeczy w świecie, ale musieliśmy również stwierdzić, że nie zmieniło to wielu rzeczy. Na przykład, gdy Shakey pchnął obiekt, pozycja tego obiektu w powstałej sytuacji została zmieniona, ale pozycje wszystkich innych obiektów nie. To, że większość rzeczy w świecie Shakeya nie uległo zmianie, musiało zostać wyraźnie przedstawione jako logiczne stwierdzenia, a co gorsza, uzasadnione przez QA3. Trudność ta, zwana "problemem z ramką", była przedmiotem wielu badań w AI, a wiele prób było złagodzić, jeśli nie rozwiązać. Z powodu problemu z ramką QA3 można było wykorzystać za wykorzystanie najprostszych dwu- lub trzyetapowych planów. Każda próba generowania planów znacznie dłużej wyczerpałoby pamięć komputera. Problem z rachunkiem sytuacji (tak jak go wówczas używano) polegał na tym, że zakładano, że wszystkie rzeczy mogą się zmienić, chyba że zostanie wyraźnie stwierdzone, że się nie zmieniły. Uznałem, że lepszą konwencją byłoby założenie, że wszystkie rzeczy pozostały niezmienione, chyba że wyraźnie stwierdzono, że się zmieniły. Aby zastosować taką konwencję, zaproponowałem inny sposób aktualizacji zbioru instrukcji logicznych opisujących sytuację. Pomysłem było to, że pewne fakty, w szczególności te, które miały miejsce przed wykonaniem czynności, ale które mogą nie zostać utrzymane, powinny zostać usunięte, a niektóre nowe fakty, mianowicie te spowodowane przez wykonanie czynności, powinny zostać dodane. Wszystkie inne fakty (te, które nie zostaną przeznaczone do usunięcia), należy po prostu skopiować do zbioru opisującego nową sytuację. Oprócz opisania w ten sposób skutków akcji, każdy opis akcji miałby warunek wstępny, to znaczy stwierdzenie, co musiało być prawdziwe w sytuacji, aby móc wykonać akcję w tej sytuacji. (Rok wcześniej doktorant Carl Mewitt na MIT opracowywał język programowania robotów o nazwie PLANNER, który miał mechanizmy dla podobnych rodzajów aktualizacji. Na przykład, aby opisać efekty programu goto (( X1, Y1), (X2, Y2)) w celu przeniesienia Shakey z pewnej pozycji (X1, Y1) na jakąś pozycję (X2, Y2), należy usunąć logiczną instrukcję AT (ROBOT, X1, Y1), dodać instrukcję AT (ROBOT, X2, Y2) i zachowaj wszystkie pozostałe instrukcje. Oczywiście, aby wykonać goto ((X1, Y1), (X2, Y2)), Shakey musiałby już być w pozycji (X1, Y1); to znaczy model aksjomatowy musiał zawierać warunek wstępny AT (ROBOT, X1, Y1) lub przynajmniej zawierać stwierdzenia, z których można udowodnić AT (ROBOT, X1, Y1).

Mniej więcej w tym czasie (1969) Richard Fikes właśnie ukończył doktorat. Pracuj pod kierunkiem Allena Newella w Carnegie i dołączył do grupy w SRI. W rozprawie Fikes′a badano nowe sposoby rozwiązywania problemów przy użyciu procedur zamiast logiki, jak w QA3. Razem z Fikes pracowaliśmy nad zaprojektowaniem systemu planowania, który używał warunków wstępnych, usuwał listy i dodawał listy (wszystkie wyrażone jako logiczne instrukcje) do opisania działań. Fikes zasugerował, że wykonując poszukiwanie sekwencji działań spełniających cele, system powinien użyć heurystycznej analizy "means-ends" centralnej dla Newell, Shaw i ogólnego problemu rozwiązywania problemów (GPS) Newella, Shawa i Simona. zaczynałby od zidentyfikowania tych akcji, których listy dodania zawierały instrukcje, które pomogły ustalić warunek celu. Warunki wstępne tych działań byłyby ustalone jako podzadania, a ten proces rozumowania wstecznego trwałby do momentu znalezienia sekwencji działań, która przekształci początkową sytuacja w jedną spełniającą cel. Około roku 1970 Fikes zakończyło programowanie (w LISP) nowym systemem planowania. Nazwaliśmy go STRIPS, akronimem Solvera Problemford Research Institute. Po jego zakończeniu STRIPS zastąpił QA3 jako system Shakey do generowania planów działania. Typowe plany składające się z około sześciu działań na średnim poziomie można wygenerować na PDP-10 w ciągu około dwóch minut. Sam system planowania STRIPS h jako droga do bardziej wydajnych planistów AI, ale wielu z nich nadal opisuje działania w kategoriach tak zwanych "operatorów STRIPS" (czasami "reguł STRIPS"), które składają się z warunków wstępnych, usuń listy i dodaj listy.

Uczenie się i wykonywanie planów

To jedna rzecz, aby zrobić plan, a zupełnie inna, aby go właściwie wykonać. Chcieliśmy też móc zapisać plany już opracowane przez STRIPS do ewentualnego wykorzystania w przyszłości. Udało się stworzyć strukturę zwaną "tabelą trójkątów" do reprezentowania planów, która była przydatna nie tylko do wykonywania planów, ale także do ich zapisywania. (John Munson początkowo zasugerował pogrupowanie warunków i efektów działań robota w trójkątny stół. Około 1970 roku Munson, Richard Fikes, Peter Hart opracowali formalizm tabeli trójkątów do reprezentowania planów składających się z operatorów STRIPS.) Tabela trójkątów warunki wstępne i skutki każdego działania w planie, aby mógł on śledzić, czy plan był prawidłowo wykonywany. Działania w planach wygenerowanych przez STRIPS miały określone wartości dla swoich parametrów. Na przykład, jeśli jakieś działanie goto było częścią planu, rzeczywiste współrzędne miejsca zostały użyte do nazwania miejsca, z którego miał się udać Shakey, i miejsca, do którego miało się udać, być może goto ((3,7), (8,14 )). Chociaż możemy chcieć zapisać plan, który zawierałby ten konkretny goto jako komponent, bardziej ogólnie stosowany plan miałby komponent goto z niespecyficznymi parametrami, które można by zastąpić konkretnymi w zależności od konkretnego celu. Chcielibyśmy uogólnić coś takiego jak goto ((3,7), (8,14)), na przykład goto ((x1, y1), (x2, y2)). Nie można nie chcąc nie chcąc zamieniać stałych na zmienne, ale należy upewnić się, że wszelkie takie uogólnienia skutkują wykonalnymi i wykonalnymi planami dla wszystkich wartości zmiennych. Byli w stanie wymyślić procedurę, która dała prawidłowe uogólnienia, i te uogólnione plany były reprezentowane w tabeli trójkątów. Po wygenerowaniu, uogólnieniu i przedstawieniu planu w tabeli trójkątów ogólny program wykonawczy Shakey, zwany "PLANEX", nadzorował jego wykonanie. W środowisku, w którym działał Shakey, wykonanie planu czasami się załamywało, ale PLANEX, korzystając z tabeli trójkątów, mógł zdecydować, jak przywrócić Shakey z powrotem do pierwotnego celu. PLANEX zapewnił ten sam rodzaj "ciągłej" odporności na planowanie wykonania, co tabele Markowa dawały do wykonywania akcji na średnim poziomie.

Procedury wizji Shakey′a

Środowisko Shakeya składało się z podłogi, po której się poruszał, ścian ograniczających pokoje, drzwi między pokojami i dużych prostoliniowych przedmiotów na podłodze w niektórych pokojach. Dołożono wszelkich starań, aby Shakey "łatwo widział". Ciemna listwa przypodłogowa oddzieliła jasną podłogę od jasnych ścian. Obiekty pomalowano na różne odcienie czerwieni, które wydawały się ciemne dla kamery vidicon i jasne dla dalmierza laserowego na podczerwień. Mimo to przetwarzanie wizualne wciąż stanowiło trudne problemy. Zamiast próbować przeprowadzić pełną analizę scen wizualnych, nasza praca koncentrowała się na wykorzystaniu wizji do uzyskania określonych informacji, których Shakey potrzebował do wykonania swoich zadań. Informacje te obejmowały lokalizację Shakey oraz obecność i lokalizację obiektów {rodzaj informacji, która była wymagana przez działania na średnim poziomie. Procedury wizualne służące do gromadzenia tych informacji zostały wbudowane w programy do wykonywania tych działań. W tych procedurach wykorzystywano znane właściwości środowiska Shakey. Wykorzystując fakt, że obiekty, podłoga i ściana zawierały płaszczyzny raczej stałego oświetlenia, Claude Brice i Claude Fennema w naszej grupie opracowali procedury przetwarzania obrazu, które identyfikowały regiony o jednolitej intensywności na obrazie. Ponieważ oświetlenie na jednej płaszczyźnie, powiedzmy twarz obiektu, może zmieniać się stopniowo w całym regionie, rutynowa regionalizacja jako pierwsza identyfikuje raczej małe regiony. Zostały one następnie scalone ponad granicami regionu na obrazie, jeśli zmiana intensywności na granicy nie była zbyt duża. Ostatecznie obraz zostanie podzielony na kilka dużych regionów, które wykonały rozsądną robotę, reprezentując samoloty na scenie. Granice tych regionów można by następnie wytyczyć za pomocą odcinków prostych. Inną rutyną wizji była możliwość bezpośredniej identyfikacji segmentów prostych na obrazie. Richard Duda i Peter Hart opracowali metodę wykonania tego w oparciu o nowoczesną formę "transformacji Hougha". Po wykryciu krawędzi podczas przetwarzania zidentyfikowano lokalizacje i kierunki małych odcinków linii, transformacji Hougha użyto do skonstruowania dłuższych linii, które były statystycznie najbardziej prawdopodobne, biorąc pod uwagę małe odcinki linii jako dowód. Zarówno nding regionu, jak i wykrywanie linii zastosowano w różnych obszarach widzenia procedury dla działań na średnim poziomie. Jedna z tych procedur, zwana obloc, została użyta do określenia położenia obiektu, którego położenie było znane z grubsza. Zdjęcia pokazują ramkę, jak to wygląda jako obraz telewizyjny z kamery Shakeya i dwa etapy przetwarzania obloka.



Z obszarów odpowiadających pudełku i podłodze (i biorąc pod uwagę fakt, że Shakey jest na tej samej podłodze co pudełko), proste obliczenia geometryczne mogłyby dodać pudełko i jego lokalizację do modeli Shakey. Shakey zwykle śledził swoją lokalizację, licząc martwe rachunki (licząc obroty kół), ale szacunki te stopniowo akumulowały błędy. Kiedy Shakey zdecydował, że powinien zaktualizować swoją lokalizację, użył innej procedury wizji, zwanej picloc. Pobliski "punkt orientacyjny", taki jak róg pokoju, został użyty do aktualizacji pozycji Shakey w odniesieniu do punktu orientacyjnego. Zdjęcia na ryc. 12.7 pokazują, w jaki sposób obloc śledzi listwę przypodłogową i znajduje obszary odpowiadające ścianom i podłodze.



Ostatnie zdjęcie pokazuje rozbieżność między przewidywaną przez Shakey lokalizacją rogu (na podstawie oszacowania własnej lokalizacji przez Shakey) a faktyczną lokalizacją na podstawie pikloku. Ta rozbieżność została wykorzystana do skorygowania oszacowania pozycji Shakey. Zanim Shakey rozpoczął prostoliniowy ruch w pokoju, w którym obecność przeszkód może nie być znana, użył procedury zwanej clearpath, aby ustalić, czy jego ścieżka jest wolna. Ta procedura sprawdzała obraz swojej ścieżki na lub (w kształcie trapezu) pod kątem zmian jasności, które mogą wskazywać na obecność przeszkody. Oceniając wydajność wizualną Shakey, należy zauważyć, że był naprawdę bardzo prymitywny i z zastrzeżeniem wielu błędów - nawet w specjalnie zaprojektowanym środowisku Shakey. Jak podaje jeden raport: "Regiony, które chcemy zachować odrębność {takie jak dwie ściany spotykające się w rogu - są często łączone, a fragmenty znaczących regionów, które powinny zostać scalone, są zbyt często trzymane oddzielnie." Jeśli chodzi na przykład o clearpath, ten sam raport zauważa, że "cienie i odbicia mogą nadal powodować fałszywe alarmy, a jedynym rozwiązaniem niektórych z tych problemów jest wykonanie dokładniejszej analizy sceny". Niemniej jednak wizja odegrała ważną rolę w ogólnej wydajności Shakey, a wiele technik przetwarzania wizualnego opracowanych podczas projektu Shakey jest nadal używanych (z późniejszymi ulepszeniami)

Niektóre eksperymenty z Shakey

Aby zilustrować metody planowania i realizacji Shakey oraz metody uczenia się w działaniu, stworzono zadanie, w którym Shakey miał przepchnąć określone okno przed określonymi drzwiami w nieprzylegającym pokoju. Aby to zrobić, Shakey musiał użyć STRIPS, aby zaplanować podróż do tego pokoju, a następnie pchnąć pudełko. Przed rozpoczęciem realizacji planu Shakey zapisał go w uogólnionej formie opisanej wcześniej. Podczas realizacji planu ustalono, że Shakey napotka nieoczekiwaną przeszkodę. Ilustrując swoją solidną procedurę wykonywania planu, Shakey był w stanie znaleźć inną wersję uogólnionego planu, który poprowadziłby go nieco inną drogą do docelowego pomieszczenia, w którym mógłby kontynuować. Jednym z badaczy pracujących nad projektem Shakey był L. Stephen Coles, który niedawno uzyskał stopień doktora. dyplom pod kierunkiem Herb Simon na Carnegie Mellon University zajmujący się przetwarzaniem języka naturalnego. Coles chciał dać Shakeyowi zadania określone w języku angielskim. Opracował parser i system analizy semantycznej, który tłumaczy proste angielskie polecenia na logiczne instrukcje dla STRIPS. Na przykład, wspomniane zadanie wypychania pudełka zostało dla Shakey po angielsku postawione w następujący sposób:

Użyj BOX2, aby zablokować drzwi DPDPCLK z pokoju RCLK.

(BOX2, DPDPCLK i RCLK były nazwami, których Shakey używał do identyfikacji danego pudełka, drzwi i pokoju. Byliśmy zobowiązani do używania nazw Shakey do wykonywania zadań do wykonania.) Program Colesa o nazwie ENGROB, przetłumaczony to angielskie polecenie do spełniony jest następujący warunek (wyrażony w języku rachunek predykatów):

ZABLOKOWANE (DPDPCLK, RCLK, BOX2)

Warunek ten został następnie przekazany STRIPS, aby opracować plan jego osiągnięcia. Coles był również zainteresowany tym, aby Shakey rozwiązał problemy wymagające pośredniego rozumowania. Założył eksperyment, w którym Shakey miał zepchnąć pudło z podwyższonej platformy. Aby to zrobić, musiałby się zorientować, że będzie musiał zepchnąć rampę na platformę, zwinąć rampę, a następnie pchnąć pudło. To zadanie zostało powierzone Shakey po angielsku jako "Push box, który jest na platformie na podłogę". Zadanie zostało pomyślnie wykonane i opisane w jednym z raportów technicznych Shakey. Zadanie "zepchnięcia pudełka z platformy" było sposobem Colesa na pokazanie, że Shakey może rozwiązać problemy takie jak problem z małpami i bananami. Problem ten, rozsławiony przez Johna McCarthy′ego jako przykład rozumowania dedukcyjnego, dotyczył małpy, pudełka i niektóre z bananów wiszących poza zasięgiem. Małpa miała być w stanie zrozumieć, że aby zdobyć banany, musiałby wepchnąć pudełko pod banany, wspiąć się na pudełko, a następnie złapać banany. Mówi się, że McCarthy słyszał, jak Karl Lashley podczas sympozjum Caltech Hixon w 1948 r. Opisuje podobny problem z demonstrowaniem inteligentnego rozwiązywania problemów przez szympansy. Jedną z osób, które były pod wrażeniem Shakey, był Bill Gates, który później był współzałożycielem Microsoft. Widział Shakey lm w 1972 roku jako gimnazjalista i pojechał z Seattle do SRI (wraz z Paulem Allenem, który był drugim współzałożycielem Microsoftu), aby się przyjrzeć. Według jednego ze źródeł był "szczególnie podekscytowany tym, że Shakey porusza się po okolicy, żeby mógł wejść na rampę"

Shakey wpada w kłopoty z finansowaniem

Shakey był pierwszym systemem robotów posiadającym umiejętności planowania, rozumowania i uczenia się; postrzegać otoczenie za pomocą czujników wizyjnych, zasięgowych i dotykowych; i do monitorowania realizacji swoich planów. Być może było to nieco przed czasem. Potrzebne byłoby znacznie więcej badań (i ogólnie postęp w technologii komputerowej), zanim praktyczne zastosowania robotów o takich umiejętnościach byłyby możliwe. W jednym z raportów o Shakey′u wspomniano o niektórych ograniczających założeniach przyjętych w tym czasie przez projekty badawcze robotów:

"Zazwyczaj środowisko problemowe [dla robota] jest nudnym rodzajem miejsca, w którym pojedynczy robot jest jedynym czynnikiem zmieniającym - nawet czas stoi w miejscu, dopóki robot się nie poruszy. Sam robot łatwo się myli; nie można podać drugiego problemu, dopóki nie rozwiąże pierwszego, nawet jeśli oba problemy mogą być powiązane w jakiś intymny sposób. Wreszcie, większość systemów robotów nie może jeszcze wygenerować planów zawierających wyraźne instrukcje warunkowe lub pętle."

Mimo że badacze SRI mieli wielkie plany kontynuowania pracy nad Shakey, DARPA odmówiła, a projekt zakończył się w 1972 r. Zakończenie to było niefortunne, ponieważ prace nad planowaniem, widzeniem, uczeniem się i ich integracją z systemami robotów osiągnęły wiele rozmach i entuzjazm wśród badaczy SRI. Ponadto badano kilka nowych pomysłów dotyczących planowania i percepcji wizualnej. Wiele z nich zostało szczegółowo opisanych w końcowym raporcie dla projektu Shakey. Spośród tych pomysłów szczególnie ważna była technika konstruowania planów w sposób hierarchiczny. Aby to zrobić, najpierw musi zostać utworzony ogólny plan składający się tylko z działań wysokiego poziomu. Taki plan można znaleźć przy znacznie mniejszym wyszukiwaniu niż jeden składający się ze wszystkich potrzebnych działań na najniższym poziomie. Na przykład plan uzyskania pracy może potrzebować tylko decyzji o jeździe metrem lub kierowaniu samochodem. Stopniowo plan wysokiego poziomu musi być coraz bardziej szczegółowo dopracowany, aż do podjęcia działań na najniższym poziomie (np. jaki zestaw kluczy samochodowych powinien zostać wykorzystany) w końcu zostałby zaatakowany. Student Stanford, pracujący w SRI, Earl Sacerdoti, zaproponował dwie nowatorskie metody planowania hierarchicznego. Po pierwsze (w ramach pracy magisterskiej) zaprogramował system który nazwał ABSTRIPS. Składał się on z szeregu aplikacji STRIPS {począwszy od łatwego do skomponowania planu, który ignorował wszystkie oprócz najważniejszych warunków wstępnych operatora. Rezultatem była seria coraz bardziej szczegółowych planów, których kulminacją był plan, który można faktycznie zrealizować. Dla jego doktoratu, podczas pracy Sacerdoti opracował potężniejszy system planowania hierarchicznego, który nazwał NOAH (ang. Nets of Action Hierarchies). W przeciwieństwie do ABSTRIPS, których operatory akcji były na tym samym poziomie szczegółowości (choć z warunkami, które można selektywnie zignorować), NOAH zastosował operatory akcji na kilku poziomach szczegółowości. Każdy operator jest wyposażony w specyfikacje, w jaki sposób mogą zostać opracowane przez operatorów na niższym poziomie szczegółowości. Co więcej, przedstawienie planu przez NOAH, w formie Sacerdoti zwanej "siecią proceduralną", "pozwoliło na nieokreśloność co do kolejności wykonywania kroków planu na jednym poziomie. To" opóźnione zobowiązanie "dotyczące zamówienia pozwoliło na bardziej szczegółowe kroki opracowania nieuporządkowanych planów na jednym poziomie, które mają być przeplatane na niższym poziomie, często z konsekwentną poprawą ogólnej wydajności. Sacerdoti liczył na wykorzystanie swoich pomysłów dotyczących planowania hierarchicznego w projekcie Shakey, więc on i reszta z SRI byli bardzo rozczarowani że DARPA nie zamierza wesprzeć kolejnego projektu (podstawowe badania nad robotami były jedną z ofiar nacisku DARPA na prace nad aplikacjami, które rozpoczęły się na początku lat 70.). Jednak udało nam się namówić DARPA na projekt, który miał oczywiste znaczenie wojskowe, ale nadal pozwalał nam kontynuować prace nad automatycznym planowaniem, wizją i realizacją planu. Co ciekawe, projekt był właściwie kontynuacją badań nad Shakiem ale z człowiekiem wykonującym zaplanowane zadania zamiast robota. Nazwano to "projektem konsultanta komputerowego (CBC)".Sacerdoti i badacze SRI nie byli sami w rozpoznawaniu i znaczeniu planowania hierarchicznego. W ramach swojego doktoratu pracując na uniwersytecie w Edynburgu, Austin Tate opracowywał sieciowy system planowania o nazwie INTERPLAN. W latach 1975 i 1976, wspierany przez British Science Research Council, Tate i koledzy z badań operacyjnych stworzyli hierarchicznego planistę o nazwie NONLIN . Planista wziął swoją nazwę od faktu, że podobnie jak NOAH, niektóre kroki planu pozostały nieuporządkowane, dopóki nie zostały opracowane na niższych poziomach hierarchii. Inne systemy planowania wyrosły z tradycji NOAH i NONLIN. Jednym z nich był interaktywny system generowania i wykonywania planu SIPE-2 opracowany przez Davida E. Wilkinsa z SRI International35. Kolejnym był O-PLAN opracowany przez Tate i współpracowników z Artiialial Intelligence Applications Institute (AIAI) na University of Edynburg Te systemy zostały szeroko stosowane, rozszerzone i stosowane.

Wózek Stanforda

Na początku lat 60. James Adams, absolwent inżynierii mechanicznej w Stanford (a później profesor Stanford), zaczął eksperymentować z czterokołowym wózkiem mobilnym z kamerą telewizyjną i łączem radiowym. Lester Earnest napisał (w swojej historii kilku projektów wykorzystujących ten wózek) "

Między innymi Adams pokazał w swojej rozprawie, że z opóźnieniem komunikacji odpowiadającym podróży w obie strony na Księżyc (około 2 sekund) pojazdu nie da się niezawodnie kontrolować jeśli podróżuje z prędkością większą niż około 0,2 km / h (0,3 km / h). "

Po tym jak Earnest dołączył do Stanford AI Laboratory, on i Rodney Schmidt, doktor inżynierii elektrycznej, otrzymał ulepszoną wersję wózka, aby "podążać za białą linią o wysokim kontraście [na drodze wokół laboratorium] w kontrolowanych warunkach oświetleniowych z prędkością około 0,8 mil na godzinę (1,3 km / h)". Inni absolwenci AI również eksperymentowali z wózkiem od czasu do czasu na początku lat siedemdziesiątych. Kiedy Hans Moravec przyjechał do Stanford, aby kontynuować doktorat studiując nawigację wizualną, rozpoczął pracę z wózkiem, "ale doznał niepowodzenia w październiku 1973 r., kiedy wózek spadł z rampy zjazdowej pod kontrolą ręczną i skończył z kwasem akumulatorowym w całej elektronice". W 1979 roku Moravec dostał odnowiony wózek, teraz wyposażony w system wizyjny stereo, do przejścia przez zagracony pokój bez interwencji człowieka. Ale robiło to bardzo powoli. Według Moravca system był niezawodny dla krótkich serii, ale powolny. "Wózek poruszał się 1 m co 10-15 minut kołysząc się na boki. Po przejechaniu z metr zatrzymał się, zrobił kilka zdjęć i długo o nich myślał. Potem zaplanował nową ścieżkę, wykonał jej trochę i znów się zatrzymał. Z powodzeniem przejechał wózek przez kilka 20-metrowych torów (każdy zajmuje około 5 godzin) na tyle skomplikowanych, że wymagało to trzech lub czterech unikanie skrętów; w innych próbach zawiodło w odkrywaniu sposobów. Wraz z Shakey'em wózek Stanforda znajduje się w Muzeum Historii Komputerów w Mountain View w Kalifornii. Były one prekursorami długiej linii pojazdów-robotów