SHRDLU

SHRDLU – system komputerowy z dziedziny sztucznej inteligencji służący do przetwarzania języka naturalnego, napisany przez Terry’ego Winograda w MIT Artificial Intelligence Laboratory w latach 1968–1970. SHRDLU umożliwia prostą konwersację (poprzez terminal) z użytkownikiem na temat małego świata obiektów. W pierwotnej wersji obiekty wyświetlane były na wczesnych ekranach komputerowych DEC-340 podłączonych do komputera PDP-6.

Wprowadzenie

Prawdziwy świat jest pełen odwracających uwagę i zbędnych detali, postęp w dziedzinie nauki jest natomiast osiągany poprzez sztuczne, uproszczone modele rzeczywistości (np. brak tarcia czy perfekcyjnie twarde ciała w wielu modelach fizycznych). W 1970 r. Marvin Minsky oraz Seymour Papert z MIT Artificial Intelligence Laboratory zaproponowali, by badania z dziedziny sztucznej inteligencji w podobny sposób skupiały się na rozwijaniu programów zdolnych do inteligentnego zachowania w sztucznych i prostych sytuacjach zwanych mikroświatami (ang. micro-worlds). Duża część badań skupiła się wtedy na tzw. światach bloków (ang. blocks world), które składały się z pokolorowanych bloków o różnych kształtach i rozmiarach umieszczonych na płaskiej powierzchni.

Pierwszym dużym sukcesem podejścia mikroświatów był SHRDLU napisany w ramach doktoratu przez Terry'ego Winograda na MIT(szczegóły programu zostały opublikowane w 1972 r.). Części systemu zostały napisane w językach Micro Planner oraz Lisp.

System kontroluje ramię robota operującego na wirtualnych blokach. SHRDLU odpowiada na komendy wprowadzone w naturalnym języku angielskim, takie jak „Will you please stack up both of the red blocks and either a green cube or a pyramid” (tłum. „Czy możesz ułożyć na stos oba czerwone bloki i żadnego zielonego sześcianu lub piramidy). System planuje sekwencje akcji do wykonania, a następnie w wirtualnym świecie robot przesuwa odpowiednio elementy. SHRDLU potrafi prawidłowo odpowiadać na pytania dotyczące swojego świata bloków, np. „Can a pyramid be supported by a pyramid?” (tłum. „Czy piramida może być podparta piramidą?”). SHRDLU próbuje postawić na sobie dwie piramidy i odnosi porażkę.

Cele systemu

Celem systemu SHRDLU nie jest jedynie symulacja podawanych instrukcji, lecz przede wszystkim użycie ważnych idei z dziedziny semantyki syntaktycznej i rozwiązywania problemów oraz ich interakcja w przetwarzaniu i rozumieniu języka naturalnego.

System odpowiada na pytania zadawane przez użytkownika, wykonuje polecenia oraz akceptuje informacje w interaktywnym dialogu w języku angielskim. Zrozumienie języka angielskiego wymaga zintegrowanych reguł dotyczących składni, semantyki oraz wnioskowania. Winograd wyszedł z założenia, że najlepszym sposobem na eksperymentowanie ze złożonymi modelami językowymi jest napisanie programu, który potrafi zrozumieć język w z góry określonej dziedzinie. W przypadku SHRDLU jest to robot posiadający rękę, oko oraz zdolność do manipulowania trójwymiarowymi obiektami.

W intencji autora program miał na celu:

1. być użytecznym systemem przetwarzania języka naturalnego,
2. pomóc lepiej zrozumieć czym jest język i jak łączyć ze sobą jego elementy,
3. pomóc zrozumieć czym jest inteligencja oraz jak może być ona zaimplementowana w komputerach.

Przykład działania

Poniżej przedstawiony jest przykładowy dialog w programie SHRDLU wraz z opisem wykonanych przez program czynności.

	Instrukcja	Opis
Użytkownik	PICK UP A BIG RED BLOCK.	System odpowiada „OK” dopiero wtedy, gdy wykona polecenie. Żeby podnieść czerwony blok program robot musi oczyścić drogę, czyli znaleźć miejsce dla zielonego bloku i przenieść go na bok. Następnie podnosi czerwony blok.
Komputer	OK.
Użytkownik	GRASP THE PYRAMD.
Komputer	I DON’T UNDERSTAND WHICH PYRAMID YOU MEAN.	Na ekranie są 3 piramidy. Robot nie wykonuje żadnej czynności.
Użytkownik	FIND A BLOCK WHICH IS TALLER THAN THE ONE YOU ARE HOLDING AND PUT IT INTO THE BOX.	System musi zrozumieć, co użytkownik ma na myśli przez „it” oraz „one”, a także użyć dedukcji, żeby zrozumieć, który z obiektów trzyma.
Komputer	BY „IT”, I ASSUME YOU MEAN THE BLOCK WHICH IS TALLER THAN THE ONE I AM HOLDING. OK.	Ręka robota opuszcza czerwony blok i podnosi większy niebieski.
Użytkownik	WHAT DOES THE BOX CONTAIN?
Komputer	THE BLUE PYRAMID AND THE BLUE BLOCK.
Użytkownik	HOW MANY BLOCKS ARE NOT IN THE BOX?	Program obsługuje zaprzeczenia takie jak „not” i „no”
Komputer	FOUR OF THEM.
Użytkownik	THE BLUE PIRAMID IS NICE.
Komputer	I UNDERSTAND.	Informacja jest dodawana do bazy danych.
Użytkownik	I LIKE BLOCKS WHICH ARE NOT RED, BUT I DON’T LIKE ANYTHING WHICH SUPPORTS A PYRAMID.
Komputer	I UNDERSTAND.	Zostały dodane dwa nowe twierdzenia o „liking”
Użytkownik	DO I LIKE THE BOX?
Komputer	NO.	Niebieski blok podpiera wszystko to co się w nim znajduje. Także piramidę.
Użytkownik	PUT THE BLOCK YOU ARE HOLDING BEHIND BLUE PYRAMID.
Komputer	OK.	Robot ustawia niebieski blok za niebieską piramidą, wewnątrz bloku, w którym znajduje się ta piramida.

Organizacja systemu

Hierarchia zależności systemu SHRDLU.

System SHRDLU składa się z kilku współpracujących ze sobą programów:

• MONITOR – mały program Lisp uruchamiające pozostałe części systemu.
• INPUT – to program Lisp, który akceptuje wpisany tekst po angielsku, sprawdza słowa w słowniku, dokonuje analizy tekstowej i zwraca ciąg słów wraz z ich definicjami. Na tym ciągu słów operuje gramatyka.
• GRAMMAR – główna część systemu, odpowiedzialna za proces rozumienia. Przekazuje gramatykę do podprogramu PROGRAMMAR. Wygenerowane procedury są tłumaczone do języka Lisp.
• SEMANTICS – kolekcja programów Lisp współpracująca z GRAMMAR w celu interpretacji zdań. Każda bazowa jednostka gramatyki posiada wiele połączonych ze sobą programów.
• ANSWER – kolekcja programów Lisp, która kontroluje odpowiedzi systemu, a także zapamiętuje konwersację na potrzeby przyszłej dyskusji. Korzysta z gotowych heurystyk, aby wyprodukować poprawne zdanie w języku angielskim.
• PROGRAMMAR – system parsujący, który interpretuje gramatykę i buduje drzewo parsingu, a także posiada mechanizm eksplorowania tego drzewa. Jest napisany w Lisp.
• DICTIONARY – składa się z dwóch części: pierwsza przetrzymuje syntaktyczne własności każdego słowa, druga przetrzymuje własności semantyczne. Części te są interpretowane przez program SEMANTIC FEATURES.
• SEMANTIC FEATURES – program z listą własności używany w analizie semantycznej.
• BLOCKS – kolekcja twierdzeń Micro Plannera, która obsługuje dynamikę budowania bloków na powierzchni elementów świata.
• MOVER – zbiór reguł wyświetlania, które symulują świat robota na ekranie.
• PLANNER – system dedukcji odpowiadający z kierowanie procesem parsingu oraz dedukowanie faktów do programu BLOCKS.

Przykładowe semantyczne interpretacje reguł zawartych w SHRDLU:

Język	Znaczenie
rzeczownik	obiekt
przymiotnik	właściwość obiektu
’the’	znajdź unikalny obiekt
czasownik	akcja
’it’	ostatni temat konwersacji
znak zapytania?'	oblicz odpowiedź
przymiotnik + rzeczownik	podzbiór wszystkich elementów zbioru o podanych własnościach
czasownik + wyrażenie z rzeczownikiem	wykonaj akcję na zbiorze obiektów określonych w wyrażeniu z rzeczownikiem

Wpływ na rozwój sztucznej inteligencji

SHRDLU był pierwszym systemem sztucznej inteligencji, który wykonywał realne zadanie. Poruszał problem rozumienia języka naturalnego, z którym bardzo dobrze sobie radził w ograniczonym świecie. Kolejnym sukcesem programu była zdolność do wnioskowania informacji o swoim świecie, a także zdolność zapamiętywania nazw, twierdzeń i definicji, skojarzonych z użytkownikiem lub elementami świata. SHRDLU zapamiętywał historię swoich działań w związku z czym za pomocą dedukcji potrafił odpowiadać na pytania czy coś jest możliwe do wykonania czy nie w obecnym stanie świata.

Ogromny sukces doprowadził innych badaczy sztucznej inteligencji do nadmiernego optymizmu, utraconego niedługo potem, gdy systemy musiały zmierzyć się z bardziej rzeczywistymi problemami realnego świata, ich złożonością i niejednoznacznością. Kontynuując wysiłki nad oryginalnym SHRDLU, można było zauważyć dążenie do dostarczenia programowi znacznie większej ilości informacji, z których miał wyciągnąć wnioski, prowadząc m.in. do takich inicjatyw jak Cyc.

SHRDLU jest postrzegany historycznie jako klasyczny przykład tego, jaką trudność programiście sprawia zbudowanie semantycznej pamięci komputera oraz jak ograniczone są możliwości takich programów.

Nazwa programu

Terry Winograd w następujący sposób opisuje historię powstania nazwy dla swojego programu:

1. ETAOIN SHRDLU to najczęściej występujące litery w języku angielskim począwszy od największej częstotliwości.
2. Z tego powodu maszyny linotypowe do składu druku nie miały układu klawiszy QWERTY, lecz ułożone w kolumnach względem częstotliwości: ETAOIN w pierwszej kolumnie, SHRDLU w drugiej.
3. Linotypy nie posiadały klawisza backspace, w związku z czym trudno było usunąć linie z pomyłkami, procedura usunięcia linii była bardzo żmudna.
4. Leniwi linotypiści, kiedy popełniali błąd, zamiast usuwać linię, wypełniali ją śmieciami.
5. Najprostszymi znakami do wprowadzenia były takie ciągi znaków jak: SHRDLUSHRDLUSHRDLU
6. Winograd czytał w młodości magazyn MAD, którego autorzy, popełniając błąd drukarski, stosowali podobną zasadę.
7. Kiedy przyszło do nazwania systemu, autor próbował wymyślić jakiś akronim, ale żaden nie był dobry, więc przypominając sobie o magazynie, zdecydował się wybrać coś, co wygląda na akronim, ale nim nie jest.