Metody sztucznej inteligencji
Pojęcie robota
Politechnika ÅšlÄ…ska
" Robot to aktywny i sztuczny agent, którego
Katedra Podstaw Konstrukcji Maszyn
środowiskiem jest realnie istniejący świat
Rok akademicki 2003/2004
" Jeśli przyjąć taką definicję, nie jest robotem:
Wykład 7, AiR
 Kawał skały
 ZwierzÄ™
Elementy robotyki
 Program komputerowy ( softbot)
Prof. dr hab. Wojciech Moczulski
" Szczególnym przedmiotem zainteresowania będą
Materiały dydaktyczne (na prawach rękopisu)
roboty autonomiczne, podejmujÄ…ce samodzielnie
dla studentów Wydziału Mechanicznego Technologicznego
decyzje, bazując na sprzężeniu z otoczeniem
Wszystkie ilustracje pochodzÄ… z S. Russel, P. Norvig, Artificial
poprzez posiadane sensory
Intelligence - A modern approach, Prentice Hall, 1995
MSI-w7/1 MSI-w7/2
Rzeczywisty świat robota (1) Rzeczywisty świat robota (2)
" Nieepizodyczny
" Niedostępny
 Wyniki akcji zmieniajÄ… siÄ™ w czasie
 Czujniki niedoskonałe
 Robot musi rozwiązywać sekwencyjne problemy
 Robot może zwykle postrzegać bodz
ce ze swojego
decyzyjne i uczyć się
bliskiego sÄ…siedztwa
" Dynamiczny
" Niedeterministyczny
 Co jest lepsze: długo się zastanawiać, czy działać
 Koła mogą się ślizgać po podłożu
natychmiast
 Akumulatory mogą się rozładować
" Ciągły
 Elementy mogą się uszkodzić
 Nieskończenie wiele stanów
 Nie wiadomo, czy dana akcja zakończy się sukcesem
 Wymaga modyfikacji algorytmów przeszukiwania i/lub
planowania
MSI-w7/3 MSI-w7/4
Zadania wykonywane przez
Zakres wykładu
roboty (1)
" Procesy wytwórcze
" Zadania, do których realizacji roboty się
 Tradycyjna dziedzina zastosowania
nadajÄ…
 W 1985 r 180 000 robotów (150 000 w J, USA, F)
" Niektóre specjalne układy wykonawcze
 Przemysł samochodowy, mikroelektronika, ...
(efektory) i sensory
 Przemieszczają obiekty o masie do 1 [t] z dokładnością do
2.5 [mm] w przestrzeni roboczej o R=10 [m] (1995 r.)
" Architektura robota jako autonomicznego
 Bardzo ograniczone możliwości odczuwania i adaptacji
agenta
(proste maszyny najlepiej realizujÄ… proste zadania)
" Wybór akcji w ciągłej przestrzeni stanów
 Roboty autonomiczne wciąż walczą o akceptację
MSI-w7/5 MSI-w7/6
Zadania wykonywane przez Zadania wykonywane przez
roboty (2) roboty (3)
" Gospodarka materiałowa
" Zadania wymagające mobilności
 Magazynowanie, transport i dostarczanie
 Kurierzy (szpitale, biura, poczta)
 Różne wielkości i masy
 Straż bezpieczeństwa
 AGV=autonomous guided vehicle
 AUV=autonomous underwater vehicle
 Wyzwanie przyszłości: obchodzenie się z
żywnością (różne wielkości, kształty, tekstury, )
" Inne - np. strzyżenie owiec w Australii (140
mln owiec!!)
MSI-w7/7 MSI-w7/8
Zadania wykonywane przez Zadania wykonywane przez
roboty (4) roboty (5)
" Niebezpieczne środowisko " Zdalna obecność
 Księżyc, planety i przestrzeń międzyplanetarna  Robot przedłużeniem organów i zmysłów
człowieka (prace na dnie oceanu, rozbrajanie
 Åšrodowisko radioaktywne, naprawy w reaktorach
bomb)
 Naprawy instalacji chemicznych, kotłów
 Roboty militarne (samoloty, szpiegi, ...)
parowych itp.
" Zwiększenie możliwości człowieka
 Zwykle operowane przez człowieka
 Często posiadają pewną autonomię (zbyt długie  Zastąpienie amputowanych organów
opóz
nienia w odpowiedzi operatora - np. Mars)
 Siatkówka, zmysł dotyku
MSI-w7/9 MSI-w7/10
Najważniejsze podzespoły Elementy wykonawcze
" Oddziałują na środowisko pod kontrolą układu
" Robot ma:
sterowania robota
 Sztywny korpus (body)
" Wyposażone w siłowniki/serwomechanizmy (jeden
 Więzy (links) [sztywne]
dla każdego stopnia swobody) zamieniające
 Połączenia (joints)
komendy programowe w fizyczny ruch
 Końcowe elementy wykonawcze (end effectors)
" Stosowane do:
stosowane do oddziaływania na środowisko
 Zmiany pozycji robota (lokomocja)
 Przemieszczania innych obiektów w środowisku
(manipulacja)
MSI-w7/11 MSI-w7/12
Lokomocja Lokomocja - roboty kroczÄ…ce
" Stateczne statycznie:
" Roboty kroczÄ…ce
" Można zatrzymać w
" Roboty jeżdżące
każdej chwili (nie
upadnÄ…)
" Bardzo wolne
przemieszczanie siÄ™
" Zużywają
nieefektywnie energiÄ™
" Stateczne dynamicznie
" SkaczÄ…ce
MSI-w7/13 MSI-w7/14
Lokomocja - roboty jeżdżące (1) Lokomocja - roboty jeżdżące (2)
" Podwozie kołowe, gąsienicowe, ...
Robot na podwoziu 4-
kołowym ma 3 stopnie
" Proste w budowie
swobody (pozycja x-y,
" Bardziej efektywne niż nogi
kierunek), lecz w małej
skali tylko 2!!
" Podparcie statyczne
" A
atwiejsze do sterowania
MSI-w7/15 MSI-w7/16
Lokomocja - roboty jeżdżące (3) Manipulowanie (1)
" Roboty holonomiczne (układ bez poślizgu)
" Realizowane przez manipulatory
 Liczba stopni swobody równa sterowalnej liczbie
" Większość manipulatorów wykonuje
stopni swobody
 albo ruch obrotowy (R)
 Budowa możliwa, lecz nieopłacalna
 albo ruch postępowy (P)
" Roboty nieholonomiczne (auto z przyczepami)
 Im większa różnica w liczbie stopni swobody, tym
trudniej sterować
 Dużo prostsze z punktu widzenia układu
mechanicznego
MSI-w7/17 MSI-w7/18
Manipulowanie (2) Manipulowanie (3)
MSI-w7/19 MSI-w7/20
Manipulowanie:
Sensory: Identyfikacja stanu robota
Końcowy mechanizm wykonawczy
" Oddziaływuje
" Do określania położenia więzów:
bezpośrednio na
 Stosowane kodery (encoder)
obiekty otoczenia
 Dużo większa dokładność niż w przypadku
" Narzędzia:
człowieka
 Śrubokręt
" Do określania zmiany położenia robota
 Automat spawalniczy
mobilnego:
 Pistolet malarski
 Odometria (pomiar obrotu koła; poślizgi!!)
 . . .
 GPS
" Chwytaki
MSI-w7/21 MSI-w7/22
Pomiar siły Odczuwanie dotyku
" Stosuje się czujniki siły "  Palce z elastycznego materiału
" Pomiar dla 6 stopni swobody, pomiędzy " Dokonywany pomiar ugięcia (przez macierz
manipulatorem a końcowym układem czujników)
wykonawczym
" Dotyk określany metodami podobnymi do
" Umożliwia ruch wzdłuż powierzchni przy rozpoznawania obrazów
utrzymaniu kontaktu ze stałym naciskiem
(compliant motion)
MSI-w7/23 MSI-w7/24
Sonar Sensory i systemy wizyjne (1)
" Systemy wizyjne ogólnego przeznaczenia mają
" SOund Navigation and Ranging = nawigacja
nadal bardzo ograniczone możliwości
i określanie zasięgu za pomocą dz
więku
" Skuteczne systemy wizyjne budowane sÄ… gdy jest
" Dostarcza użytecznej informacji o obiektach
ograniczona lista zadań, które ma wykonywać robot
bardzo blisko robota
(np. zakłada się, że przeszkody są płaskie),
" Umożliwia awaryjne zapobieżenie kolizjom
" Robot może oświetlać otoczenie światłem o
określonej długości fali (podczerwień, ...)
" Efektywny w przypadku omijania przeszkód
" Specjalne systemy czujników mogą być stosowane
" Mało przydatny do opracowywania mapy
do dokładnych pomiarów geometrii obiektów
(szeroka wiÄ…zka dz
więku)
MSI-w7/25 MSI-w7/26
Sensory i systemy wizyjne (2) Sensory i systemy wizyjne (3)
MSI-w7/27 MSI-w7/28
Architektury robotów Architektura klasyczna
" Poszukiwanie ścieżek i przemieszczanie robota
" Określają sposób organizacji działań,
realizowano przez podprogramy działań
mających na celu określanie akcji na
pośredniego poziomu (Intermediate-Level
podstawie percepcji
Action=ILA)
" Podobne do problemu projektowania agenta
" ILA składa się ze złożonych procedur działań
w najtrudniejszym wariancie (ze względu
niskiego poziomu (Low-Level Action=LLA)
na własności środowiska):
do sterowania układem robota
 Duża objętość danych wejściowych
" Do planowania zastosowano algorytm STRIPS
 Potrzeba szybkiej reakcji w niektórych
sytuacjach
MSI-w7/29 MSI-w7/30
Architektura klasyczna: Przykład System planowania
" (ILA): przemieść robota z miejsca X do miejsca Y
" Działa wg algorytmu STREPS
 (LLA): zaplanuj ścieżkę stosując algorytm A*
" Układ dowodzenia twierdzeń efektywnie
 (LLA): przemieść robota wzdłuż zaplanowanej ścieżki,
generujÄ…cy sekwencje akcji
korygując tę ścieżkę podczas ruchu
" Wyniki planowania kompilowane w ogólne
 (LLA): zaktualizuj wewnętrzny model świata
makro-operatory (CBR - ułatwia rozwiązanie
 (LLA): gdy rośnie niepewność położenia, wyślij rozkaz
do systemu wizyjnego w celu określenia nowej pozycji
podobnych problemów w przyszłości)
robota
" Realizuje najkrótszą podsekwencję planu
" System ILA/LLA zapewniał stosunkowo jasny i
prowadzącą do celu i której warunki wstępne są
niezawodny ciÄ…g akcji dla systemu planowania
spełnione
MSI-w7/31 MSI-w7/32
Situated automaton (2):
Situated automaton (1)
Opracowywanie
" Bazuje na koncepcji automatu skończonego: " Generowanie poprzez autonomiczny proces
kompilacji
 Na wejścia podawane sygnały z sensorów,
stosowanych do odbierania bodz
ców z otoczenia
" Manualny proces projektowania oparty na
 Wyjścia podłączone są do układów
dekompozycji ze względu na różne
wykonawczych robota
zachowania, którymi robot powinien się
" Bardzo efektywna implementacja agenta
wykazywać
odruchowego ze stanem wewnętrznym
MSI-w7/33 MSI-w7/34
Situated automaton (3) Situated automaton (3)
" Sposoby reprezentacji wiedzy:
 Formalna reprezentacja wiedzy przez
projektantów robota
 Wiedza zawarta w architekturze agenta
" Kompilator generuje automat skończony,
którego stany wewnętrzne odpowiadają
" Wszystkie obliczenia wykonywane przez sieci ze
zdaniom logicznym dotyczącym środowiska
sprzężeniem do przodu
" Czas obliczeń bardzo krótki
MSI-w7/35 MSI-w7/36
" Nie wymaga jawnej reprezentacji wiedzy
Bazowanie na zachowaniach (1) Bazowanie na zachowaniach (2)
" Dekompozycja na moduły realizujące
odpowiednie zachowania (omijanie
przeszkody, podążanie wzdłuż ściany, ...)
" Każdy moduł ma dostęp do sygnałów z
sensorów i może wysyłać sygnały do
układów wykonawczych
" Zachowania sÄ… zorganizowane w hierarchie
MSI-w7/37 MSI-w7/38
Podstawy analizy przestrzeni
Bazowanie na zachowaniach (3)
konfiguracji (1)
" Przestrzeń stanów:
" Wyeliminowanie jako podstawy scentralizowanej,
 opisuje wszystkie możliwe konfiguracje otoczenia
kompletnej reprezentacji stanów otoczenia (co jest
(włącznie z elementami robota)
bardzo kosztowne)
 jest ciągła - konfiguracje elementów robota i lokalizacje
" Stan wewnętrzny potrzebny jedynie do śledzenia
obiektów w przestrzeni fizycznej są określone we
współrzędnych rzeczywistych
tych stanów otoczenia, które są niedostępne dla
" Przestrzeń konfiguracji C dla robota o k stopniach
czujników, ale są potrzebne do wyboru akcji w
swobody: zbiór wszystkich punktów, których
każdym zachowaniu
współrzędnymi są wartości opisujące położenia
" Do reprezentowania stanu wewnętrznego czasem
wszystkich więzów robota:
wystarczy mało pamięci, nawet dla złożonych zadań
q = [q1,K, qk ]
MSI-w7/39 MSI-w7/40
Podstawy analizy przestrzeni Podstawy analizy przestrzeni
konfiguracji (2) konfiguracji (3)
" Przeszkoda w przestrzeni konfiguracji O to
Robot może poruszać
siÄ™ bezpiecznie, bo
podzbiór C , w którym jakikolwiek element
istnieje ciągła ścieżka
robota uderza o cokolwiek (o obiekty
pomiędzy punktami
środowiska, inny element robota) całkowicie leżąca w F
" F=C - O jest wolną przestrzenią, w której
robot może bezpiecznie się poruszać.
MSI-w7/41 MSI-w7/42
Uogólniona przestrzeń konfiguracji (1) Uogólniona przestrzeń konfiguracji (2)
" E- przestrzeń wszystkich możliwych
" Przestrzeń konfiguracji, w której stan innych
konfiguracji obiektów innych niż robot
obiektów jest uwzględniony jako część
 Gdy do opisu wystarczy m parametrów
konfiguracji:
Ä… = [Ä…1,K,Ä…m]
, przestrzeń E jest m-wymiarowa
 Inne obiekty mogą być ruchome
" W= C × E jest przestrzeniÄ… (k+m)-wymiarowÄ…
 Kształty innych obiektów mogą się zmieniać:
wszystkich możliwych konfiguracji w świecie
" Obiekty posiadające więzy mechaniczne (nożyczki)
" Jeśli w rozwiązywanym zadaniu występuje
" Obiekty deformowalne (łańcuch, papier, ...)
więcej robotów, utworzyć super-robota (jeden
" Szczególnie przydatna w planowaniu montażu
wektor opisuje konfiguracjÄ™ wszystkich
MSI-w7/43 robotów) MSI-w7/44
Uogólniona przestrzeń konfiguracji (3) Podejście warstwowe
" Kartki książki, na każdej
" Ruchy obiektów bez pomocy robota (ślizganie się
nieco inna pozycja
obiektu po powierzchni stołu, ...) - NIELEGALNE
ruchomego obiektu (b-
" W przestrzeni W jest (k+m) stopni swobody:
nowa współrzędna)
 tylko k sterowalnych (można zmieniać konfigurację
" Dla każdej wartości b
robota)
(stałe przeszkody) jest
 konfiguracje obiektów zmieniają się tylko po akcji robota określone F
" Transit motion - wewnÄ…trz
" (k+m) - wymiarowa przestrzeń ze sterowaniem
kartki
wzdłuż dwóch typów dróg:
" Transfer motion - ruch
 Ścieżki przejścia samego robota (transit paths)
Manipulator o 2 członach
pomiędzy kartkami
 Ścieżki, po których robot przemieszcza obiekt (transfer
w przestrzeni roboczej z ruchomÄ…
paths)
przeszkodÄ…
MSI-w7/45 MSI-w7/46
Planowanie w przypadku n
Planowanie nawigacji i ruchu
ruchomych obiektów
" Podział W na skończoną liczbę małych
" Dekompozycja komórkowa (cell
stanów - abstrahowanie (planowanie logiczne) decomposition)
" Wpierw planowanie ruchów obiektów, potem " Szkieletyzacja (skeletonization)
ruchu robota (klasyczny sposób planowania
" Planowanie z ograniczonym błędem
montażu)
(bounded-error planning)
" Ograniczenie ruchów obiektów (podejście
" Nawigacja bazujÄ…ca na punktach
LMT; sparametryzowana rodzina ruchów
orientacyjnych (landmark-based navigation)
obiektów - np. po prostych)
" Algorytmy działania bezpośredniego (online)
MSI-w7/47 MSI-w7/48
Dekompozycja komórkowa (1) Dekompozycja komórkowa (2)
" Podziel F na proste, połączone komórki
(dekompozycja)
" Określ, które komórki sąsiadują ze sobą i zbuduj
graf sÄ…siedztwa
" Określ, w których komórkach leżą punkty: startu i
docelowy, a następnie w grafie sąsiedztwa wyszukaj
ścieżkę pomiędzy tymi komórkami
" Dla wyszukanego ciągu komórek oblicz ścieżkę
wewnątrz komórki, łączącą punkty graniczące z
sąsiednimi komórkami, przez które przechodzi
ścieżka
MSI-w7/49 MSI-w7/50
Dekompozycja komórkowa (3) Metoda szkieletyzacji (1)
" Redukuje przestrzeń konfiguracji w
" Podejście rozumne, lecz niekompletne
jednowymiarowy podzbiór (szkielet)
" Otrzymuje się bezpieczną ścieżkę
" Szkielet jest siecią o skończonej liczbie
" Nie zawsze da siÄ™ znalez
ć ścieżkę, nawet
łuków, w której ścieżki wyszukiwane są z
jeśli istnieje
zastosowaniem metod przeszukiwania
" Są inne sposoby dekompozycji, usuwające grafów
te wady
" Gdy start i cel nie są węzłami szkieletu,
trzeba jedynie określić sposób dojścia do
jakiegoś węzła szkieletu
MSI-w7/51 MSI-w7/52
Metoda szkieletyzacji (2) Metoda szkieletyzacji (3)
" By planowanie było kompletne, muszą być " Grafy widzialności (visibility graphs)
spełnione wymagania:
" Diagramy Voronoi
 Gdy S jest szkieletem w wolnej przestrzeni F ,
" Mapy drogowe (roadmaps)
S musi mieć pojedynczy kawałek wewnątrz
każdego połączonego regionu przestrzeni F
 Dla każdego p " F musi być łatwe obliczenie
ścieżki od p do szkieletu S
MSI-w7/53 MSI-w7/54
Graf widzialności Diagram Voronoi
Linie
równej
odległości
od
przeszkód
Daje najkrótszą ścieżkę pomiędzy punktami
MSI-w7/55 MSI-w7/56
Fine-motion
Landmark-based navigation (1)
planning (FMP)
" Planowanie małych,
" Proste czujniki do lokalizacji robota
precyzyjnych ruchów (np.
" Landmark - punkt z polem wpływu
montaż)
" Seria ostrożnych ruchów
" Znane środowisko, nieznane położenie
" Ruchy  uległe
robota (znany region, w którym jest)
umożliwiające
nieniszczÄ…ce spotkania z " Nieprecyzyjne sterowanie (bardzo rozsÄ…dny
przeszkodami
model); robot może mieć żyroskop/kompas
" Uwzględnia się
" Stosuje siÄ™ projekcjÄ™ wstecznÄ…
niepewność akcji
(backprojection) uwzględniając stożek v
" Bardzo złożony problem
planowania
MSI-w7/57 MSI-w7/58
Landmark-based navigation (2) Landmark-based navigation (3)
MSI-w7/59 MSI-w7/60
Algorytm działania bezpośredniego Podsumowanie (1)
" Świat fizyczny jest niedostępny,
niedeterministyczny, nieepizodyczny i
" Bardzo prosty algorytm
dynamiczny
" Kompletny i efektywny
" Åšrodowisko nieznane
" Zastosowanie robotów spowodowało
dla robota, gdy startuje
skokowy rozwój w wielu dziedzinach
" Nie można gwarantować
" Robot składa się z korpusu, sztywnych
najkrótszej ścieżki
kończyn i więzów; charakteryzuje go liczba
stopni swobody więzów
MSI-w7/61 MSI-w7/62
Podsumowanie (2) Podsumowanie (3)
" Roboty mają sensory różnych typów: wizji,
" Metody dekompozycji komórkowej i
siły, dotyku, sonar, oraz poczucie stanu ich
szkieletyzacji umożliwiają nawigację w
 części ciała
przestrzeni konfiguracji, redukujÄ…c liczbÄ™
" W dynamicznym świecie działanie musi
wymiarów przestrzeni poszukiwania
być podejmowane szybko
" Niektóre cechy otoczenia (dokładna
" Problem przemieszczania obiektów o
lokalizacja narzędzia, sworznia) są
skomplikowanych kształtach jest złożony.
nieznane. Stosuje siÄ™ wtedy Fine-motion
Jest on rozwiÄ…zywany w przestrzeni
planning
konfiguracji
MSI-w7/63 MSI-w7/64
Podsumowanie (4)
" Niepewność dotyczy także wyników
pomiaru w dużej skali (sonar). W modelu
landmark robot posługuje się dobrze
znanymi landmarkami w celu określenia
swojego położenia.
" Gdy nie jest dostępna mapa otoczenia, robot
musi planować nawigację podczas
poruszania siÄ™. Stosuje algorytmy online,
nie zawsze dające najkrótszą ścieżkę, ale
skuteczne.
MSI-w7/65