1

MSI-w7/1

Metody sztucznej inteligencji

Politechnika Śląska

Katedra Podstaw Konstrukcji Maszyn

Rok akademicki 2003/2004

Wykład 7, AiR

Elementy robotyki

Prof. dr hab. Wojciech Moczulski

Materiały dydaktyczne (na prawach rękopisu)

dla studentów Wydziału Mechanicznego Technologicznego

Wszystkie ilustracje pochodzą z S. Russel, P. Norvig, Artificial

Intelligence - A modern approach, Prentice Hall, 1995

MSI-w7/2

Pojęcie robota

• Robot to aktywny i sztuczny agent, którego

środowiskiem jest realnie istniejący świat

• Jeśli przyjąć taką definicję, nie jest robotem:

– Kawał skały
– Zwierzę
– Program komputerowy (

→

softbot

)

• Szczególnym przedmiotem zainteresowania będą

roboty autonomiczne

, podejmujące

samodzielnie

decyzje

, bazując na

sprzężeniu z otoczeniem

poprzez

posiadane sensory

MSI-w7/3

Rzeczywisty świat robota (1)

• Niedostępny

– Czujniki niedoskonałe
– Robot może zwykle postrzegać bodźce ze swojego

bliskiego sąsiedztwa

• Niedeterministyczny

– Koła mogą się ślizgać po podłożu
– Akumulatory mogą się rozładować
– Elementy mogą się uszkodzić
– Nie wiadomo, czy dana akcja zakończy się sukcesem

MSI-w7/4

Rzeczywisty świat robota (2)

• Nieepizodyczny

– Wyniki akcji zmieniają się w czasie
– Robot musi rozwiązywać sekwencyjne problemy

decyzyjne i uczyć się

• Dynamiczny

– Co jest lepsze: długo się zastanawiać, czy działać

natychmiast

• Ciągły

– Nieskończenie wiele stanów
– Wymaga modyfikacji algorytmów przeszukiwania i/lub

planowania

MSI-w7/5

Zakres wykładu

• Zadania

, do których realizacji roboty się

nadają

• Niektóre specjalne

układy wykonawcze

(efektory) i

sensory

• Architektura robota

jako autonomicznego

agenta

• Wybór akcji

w ciągłej przestrzeni stanów

MSI-w7/6

Zadania wykonywane przez

roboty (1)

• Procesy wytwórcze

– Tradycyjna dziedzina zastosowania
– W 1985 r 180 000 robotów (150 000 w J, USA, F)
– Przemysł samochodowy, mikroelektronika, ...
– Przemieszczają obiekty o masie do 1 [t] z dokładnością do

2.5 [mm] w przestrzeni roboczej o R=10 [m] (1995 r.)

– Bardzo ograniczone możliwości odczuwania i adaptacji

(proste maszyny najlepiej realizują proste zadania)

– Roboty autonomiczne wciąż walczą o akceptację

2

MSI-w7/7

Zadania wykonywane przez

roboty (2)

• Gospodarka materiałowa

– Magazynowanie, transport i dostarczanie
– Różne wielkości i masy
– AGV=autonomous guided 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/8

Zadania wykonywane przez

roboty (3)

• Zadania wymagające mobilności

– Kurierzy (szpitale, biura, poczta)
– Straż bezpieczeństwa
– AUV=autonomous underwater vehicle

MSI-w7/9

Zadania wykonywane przez

roboty (4)

• Niebezpieczne środowisko

– Księżyc, planety i przestrzeń międzyplanetarna
– Środowisko radioaktywne, naprawy w reaktorach
– Naprawy instalacji chemicznych, kotłów

parowych itp.

– Zwykle operowane przez człowieka
– Często posiadają pewną autonomię (zbyt długie

opóźnienia w odpowiedzi operatora - np. Mars)

MSI-w7/10

Zadania wykonywane przez

roboty (5)

• Zdalna obecność

– Robot przedłużeniem organów i zmysłów

człowieka (prace na dnie oceanu, rozbrajanie
bomb)

– Roboty militarne (samoloty, szpiegi, ...)

• Zwiększenie możliwości człowieka

– Zastąpienie amputowanych organów
– Siatkówka, zmysł dotyku

MSI-w7/11

Najważniejsze podzespoły

• Robot ma:

– Sztywny

korpus

(body)

– Więzy

(links) [sztywne]

– Połączenia

(joints)

– Końcowe elementy wykonawcze

(end effectors)

stosowane do oddziaływania na środowisko

MSI-w7/12

Elementy wykonawcze

• Oddziałują na środowisko

pod kontrolą układu

sterowania robota

• Wyposażone w

siłowniki/serwomechanizmy

(jeden

dla każdego stopnia swobody) zamieniające
komendy programowe w fizyczny ruch

• Stosowane do:

– Zmiany pozycji robota (

lokomocja

)

– Przemieszczania innych obiektów w środowisku

(

manipulacja

)

3

MSI-w7/13

Lokomocja

• Roboty kroczące
• Roboty jeżdżące

MSI-w7/14

Lokomocja - roboty kroczące

• Stateczne statycznie:

• Można zatrzymać w

każdej chwili (nie
upadną)

• Bardzo wolne

przemieszczanie się

• Zużywają

nieefektywnie energię

• Stateczne dynamicznie

• Skaczące

MSI-w7/15

Lokomocja - roboty jeżdżące (1)

• Podwozie kołowe, gąsienicowe, ...

• Proste w budowie
• Bardziej efektywne niż nogi
• Podparcie statyczne
• Łatwiejsze do sterowania

MSI-w7/16

Lokomocja - roboty jeżdżące (2)

Robot na podwoziu 4-
kołowym ma 3 stopnie
swobody (pozycja x-y,
kierunek), lecz w małej
skali tylko 2!!

MSI-w7/17

Lokomocja - roboty jeżdżące (3)

• Roboty

holonomiczne (układ bez poślizgu)

– Liczba stopni swobody równa sterowalnej liczbie

stopni swobody

– Budowa możliwa, lecz nieopłacalna

• 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/18

Manipulowanie (1)

• Realizowane przez

manipulatory

• Większość manipulatorów wykonuje

– albo

ruch obrotowy

(R)

– albo

ruch postępowy

(P)

4

MSI-w7/19

Manipulowanie (2)

MSI-w7/20

Manipulowanie (3)

MSI-w7/21

Manipulowanie:

Końcowy mechanizm wykonawczy

• Oddziaływuje

bezpośrednio na
obiekty otoczenia

• Narzędzia

:

– Śrubokręt
– Automat spawalniczy
– Pistolet malarski
– . . .

• Chwytaki

MSI-w7/22

Sensory: Identyfikacja stanu robota

• Do określania położenia więzów:

– Stosowane kodery (encoder)
– Dużo większa dokładność niż w przypadku

człowieka

• Do określania zmiany położenia robota

mobilnego:

– Odometria (pomiar obrotu koła;

poślizgi

!!)

– GPS

MSI-w7/23

Pomiar siły

• Stosuje się czujniki siły
• Pomiar dla 6 stopni swobody, pomiędzy

manipulatorem a końcowym układem
wykonawczym

• Umożliwia ruch wzdłuż powierzchni przy

utrzymaniu kontaktu ze stałym naciskiem
(compliant motion)

MSI-w7/24

Odczuwanie dotyku

• „Palce” z elastycznego materiału
• Dokonywany pomiar ugięcia (przez macierz

czujników)

• Dotyk określany metodami podobnymi do

rozpoznawania obrazów

5

MSI-w7/25

Sonar

• SOund Navigation and Ranging = nawigacja

i określanie zasięgu za pomocą dźwięku

• Dostarcza użytecznej informacji o obiektach

bardzo blisko robota

• Umożliwia awaryjne zapobieżenie kolizjom
• Efektywny w przypadku omijania przeszkód
• Mało przydatny do opracowywania mapy

(szeroka wiązka dźwięku)

MSI-w7/26

Sensory i systemy wizyjne (1)

• Systemy wizyjne ogólnego przeznaczenia mają

nadal

bardzo ograniczone możliwości

• Skuteczne systemy wizyjne budowane są

gdy jest

ograniczona lista zadań

, które ma wykonywać robot

(np. zakłada się, że przeszkody są płaskie),

• Robot może oświetlać otoczenie światłem o

określonej długości fali (podczerwień, ...)

• Specjalne systemy czujników

mogą być stosowane

do dokładnych pomiarów geometrii obiektów

MSI-w7/27

Sensory i systemy wizyjne (2)

MSI-w7/28

Sensory i systemy wizyjne (3)

MSI-w7/29

Architektury robotów

• Określają sposób organizacji działań,

mających na celu

określanie akcji na

podstawie percepcji

• Podobne do problemu projektowania agenta

w najtrudniejszym wariancie (ze względu
na własności środowiska):

– Duża objętość danych wejściowych
– Potrzeba szybkiej reakcji w niektórych

sytuacjach

MSI-w7/30

Architektura klasyczna

• Poszukiwanie ścieżek i przemieszczanie robota

realizowano przez podprogramy

działań

pośredniego poziomu

(Intermediate-Level

Action=

ILA

)

• ILA składa się ze złożonych procedur

działań

niskiego poziomu

(Low-Level Action=

LLA

)

do sterowania układem robota

• Do planowania zastosowano algorytm

STRIPS

6

MSI-w7/31

Architektura klasyczna: Przykład

• (ILA): przemieść robota z miejsca X do miejsca Y

– (LLA): zaplanuj ścieżkę stosując algorytm A*
– (LLA): przemieść robota wzdłuż zaplanowanej ścieżki,

korygując tę ścieżkę podczas ruchu

– (LLA): zaktualizuj wewnętrzny model świata
– (LLA): gdy rośnie niepewność położenia, wyślij rozkaz

do systemu wizyjnego w celu określenia nowej pozycji

robota

• System ILA/LLA zapewniał stosunkowo jasny i

niezawodny ciąg akcji dla systemu planowania

MSI-w7/32

System planowania

• Działa wg algorytmu STREPS

• Układ dowodzenia twierdzeń

efektywnie

generujący

sekwencje akcji

• Wyniki planowania kompilowane w

ogólne

makro-operatory

(CBR - ułatwia rozwiązanie

podobnych problemów w przyszłości)

• Realizuje

najkrótszą podsekwencję planu

prowadzącą do celu

i której warunki wstępne są

spełnione

MSI-w7/33

Situated automaton (1)

• Bazuje na koncepcji automatu skończonego:

– Na wejścia podawane sygnały z sensorów,

stosowanych do odbierania bodźców z otoczenia

– Wyjścia podłączone są do układów

wykonawczych robota

• Bardzo efektywna implementacja agenta

odruchowego ze stanem wewnętrznym

MSI-w7/34

Situated automaton (2):

Opracowywanie

• Generowanie poprzez

autonomiczny proces

kompilacji

• Manualny proces projektowania oparty na

dekompozycji

ze względu na różne

zachowania, którymi robot powinien się
wykazywać

MSI-w7/35

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ą
zdaniom logicznym dotyczącym środowiska

MSI-w7/36

Situated automaton (3)

• Wszystkie obliczenia wykonywane przez sieci ze

sprzężeniem do przodu

• Czas obliczeń bardzo krótki
• Nie wymaga jawnej reprezentacji wiedzy

7

MSI-w7/37

Bazowanie na zachowaniach (1)

• 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/38

Bazowanie na zachowaniach (2)

MSI-w7/39

Bazowanie na zachowaniach (3)

• Wyeliminowanie jako podstawy scentralizowanej,

kompletnej reprezentacji stanów otoczenia (co jest
bardzo kosztowne)

• Stan wewnętrzny potrzebny jedynie do śledzenia

tych stanów otoczenia, które są niedostępne dla
czujników, ale są potrzebne do wyboru akcji w
każdym zachowaniu

• Do reprezentowania stanu wewnętrznego czasem

wystarczy mało pamięci, nawet dla złożonych zadań

MSI-w7/40

Podstawy analizy przestrzeni

konfiguracji (1)

• Przestrzeń stanów

:

– opisuje wszystkie możliwe konfiguracje otoczenia

(włącznie z elementami robota)

– jest ciągła - konfiguracje elementów robota i lokalizacje

obiektów w przestrzeni fizycznej są określone we

współrzędnych rzeczywistych

• Przestrzeń konfiguracji

C

dla robota o k stopniach

swobody: zbiór wszystkich punktów, których

współrzędnymi są wartości opisujące położenia

wszystkich więzów robota:

[

]

k

q

q

,

,

1

K

=

q

MSI-w7/41

Podstawy analizy przestrzeni

konfiguracji (2)

• Przeszkoda w przestrzeni konfiguracji

O to

podzbiór

C

, w którym jakikolwiek element

robota uderza o cokolwiek (o obiekty
środowiska, inny element robota)

• F =

C

-

O jest wolną przestrzenią, w której

robot może bezpiecznie się poruszać.

MSI-w7/42

Podstawy analizy przestrzeni

konfiguracji (3)

Robot może poruszać
się bezpiecznie, bo
istnieje ciągła ścieżka
pomiędzy punktami
całkowicie leżąca w

F

8

MSI-w7/43

Uogólniona przestrzeń konfiguracji (1)

• Przestrzeń konfiguracji, w której stan innych

obiektów jest uwzględniony jako część
konfiguracji:

– Inne obiekty mogą być ruchome
– Kształty innych obiektów mogą się zmieniać:

• Obiekty posiadające więzy mechaniczne (nożyczki)
• Obiekty deformowalne (łańcuch, papier, ...)

• Szczególnie przydatna w planowaniu montażu

MSI-w7/44

Uogólniona przestrzeń konfiguracji (2)

• E - przestrzeń wszystkich możliwych

konfiguracji obiektów innych niż robot

– Gdy do opisu wystarczy m parametrów

, przestrzeń

E jest m-wymiarowa

• W = C × E jest przestrzenią (k+m)-wymiarową

wszystkich możliwych konfiguracji w świecie

• Jeśli w rozwiązywanym zadaniu występuje

więcej robotów, utworzyć super-robota (jeden

wektor opisuje konfigurację wszystkich

robotów)

[

]

m

α

α

,

,

1

K

=

α

MSI-w7/45

Uogólniona przestrzeń konfiguracji (3)

• Ruchy obiektów bez pomocy robota (ślizganie się

obiektu po powierzchni stołu, ...) -

NIELEGALNE

• W przestrzeni

W jest (k+m) stopni swobody:

– tylko k sterowalnych (można zmieniać konfigurację

robota)

– konfiguracje obiektów zmieniają się tylko po akcji robota

• (k+m) - wymiarowa przestrzeń ze sterowaniem

wzdłuż dwóch typów dróg:

– Ścieżki przejścia samego robota

(transit paths)

– Ścieżki, po których robot przemieszcza obiekt

(transfer

paths)

MSI-w7/46

Podejście warstwowe

• Kartki książki, na każdej

nieco inna pozycja

ruchomego obiektu (b-

nowa współrzędna)

• Dla każdej wartości b

(stałe przeszkody)

jest

określone

F

• Transit motion

- wewnątrz

kartki

• Transfer motion

- ruch

pomiędzy kartkami

Manipulator o 2 członach
w przestrzeni roboczej z ruchomą
przeszkodą

MSI-w7/47

Planowanie w przypadku n

ruchomych obiektów

• Podział

W na skończoną liczbę małych

stanów - abstrahowanie (planowanie logiczne)

• Wpierw planowanie ruchów obiektów, potem

ruchu robota (klasyczny sposób planowania
montażu)

• Ograniczenie ruchów obiektów (podejście

LMT; sparametryzowana rodzina ruchów
obiektów - np. po prostych)

MSI-w7/48

Planowanie nawigacji i ruchu

• Dekompozycja komórkowa (cell

decomposition)

• Szkieletyzacja (skeletonization)
• Planowanie z ograniczonym błędem

(bounded-error planning)

• Nawigacja bazująca na punktach

orientacyjnych (landmark-based navigation)

• Algorytmy działania bezpośredniego (online)

9

MSI-w7/49

Dekompozycja komórkowa (1)

• 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/50

Dekompozycja komórkowa (2)

MSI-w7/51

Dekompozycja komórkowa (3)

• Podejście rozumne, lecz niekompletne
• Otrzymuje się bezpieczną ścieżkę
• Nie zawsze da się znaleźć ścieżkę, nawet

jeśli istnieje

• Są inne sposoby dekompozycji, usuwające

te wady

MSI-w7/52

Metoda szkieletyzacji (1)

• Redukuje przestrzeń konfiguracji w

jednowymiarowy podzbiór (

szkielet

)

• Szkielet jest

siecią o skończonej liczbie

łuków

, w której ścieżki wyszukiwane są z

zastosowaniem

metod przeszukiwania

grafów

• 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/53

Metoda szkieletyzacji (2)

• By planowanie było kompletne, muszą być

spełnione wymagania:

– Gdy

S jest szkieletem w wolnej przestrzeni F ,

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/54

Metoda szkieletyzacji (3)

• Grafy widzialności (visibility graphs)
• Diagramy Voronoi
• Mapy drogowe (roadmaps)

10

MSI-w7/55

Graf widzialności

Daje najkrótszą ścieżkę pomiędzy punktami

MSI-w7/56

Diagram Voronoi

Linie

równej

odległości

od

przeszkód

MSI-w7/57

Fine-motion

planning (FMP)

• Planowanie małych,

precyzyjnych ruchów (np.

montaż)

• Seria ostrożnych ruchów
• Ruchy „uległe”

umożliwiające

nieniszczące spotkania z

przeszkodami

• Uwzględnia się

niepewność akcji

• Bardzo złożony problem

planowania

MSI-w7/58

Landmark-based navigation (1)

• Proste czujniki do lokalizacji robota
• Landmark - punkt z polem wpływu
• Znane środowisko, nieznane położenie

robota (znany region, w którym jest)

• Nieprecyzyjne sterowanie (bardzo rozsądny

model); robot może mieć żyroskop/kompas

• Stosuje się projekcję wsteczną

(backprojection) uwzględniając stożek v

MSI-w7/59

Landmark-based navigation (2)

MSI-w7/60

Landmark-based navigation (3)

11

MSI-w7/61

Algorytm działania bezpośredniego

• Bardzo prosty algorytm
• Kompletny i efektywny
• Środowisko nieznane

dla robota, gdy startuje

• Nie można gwarantować

najkrótszej ścieżki

MSI-w7/62

Podsumowanie (1)

• Świat fizyczny jest niedostępny,

niedeterministyczny, nieepizodyczny i
dynamiczny

• Zastosowanie robotów spowodowało

skokowy rozwój w wielu dziedzinach

• Robot składa się z korpusu, sztywnych

kończyn i więzów; charakteryzuje go liczba
stopni swobody więzów

MSI-w7/63

Podsumowanie (2)

• Roboty mają sensory różnych typów: wizji,

siły, dotyku, sonar, oraz poczucie stanu ich

„części ciała”

• W dynamicznym świecie działanie musi

być podejmowane szybko

• Problem przemieszczania obiektów o

skomplikowanych kształtach jest złożony.

Jest on rozwiązywany w przestrzeni

konfiguracji

MSI-w7/64

Podsumowanie (3)

• Metody dekompozycji komórkowej i

szkieletyzacji umożliwiają nawigację w
przestrzeni konfiguracji, redukując liczbę
wymiarów przestrzeni poszukiwania

• Niektóre cechy otoczenia (dokładna

lokalizacja narzędzia, sworznia) są
nieznane. Stosuje się wtedy Fine-motion
planning

MSI-w7/65

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.