Inteligentne
Systemy Robotyczne (ISR)
- Informacje
- Plan wykładu
- Laboratorium
- Literatura
Informacje:
Wykład z
przedmiotu ISR składa się z dwóch części:
- pierwszej prowadzonej przez prof.
C. Zielińskiego
- drugiej prowadzonej przez W.
Szynkiewicza
Plan
wykładu:
Część pierwsza:
- Metody programowania robotów. Ogólne
wprowadzenie.
Programowanie a struktura układu sterowania. Metody off-line
i on-line.
Klasyfikacja języków programowania robotów.
- Programowe struktury ramowe. Przegląd
zagadnień i
struktur tego typu. Sposoby przetwarzania programowych struktur
ramowych i języków programowania.
- Systemy wieloagentowe. Struktura
agenta, formalizacja
opisu działania agenta za pomocą funkcji przejścia. Efektory.
Receptory. Ontologie.
- Systemy behawioralne.
Dekompozycja sekwencyjna i
równoległa. Selekcja zachowań wykorzystująca predykaty.
Transformacja
systemów synchronicznych w zdarzeniowe.
- Systemy behawioralne. Zachowania
elementarne i złozone.
Agenty deterministyczne i niedeterministyczne.
- Hybrydowe systemy deliberatywno-behawioralne.
- Systemy rozmyte. Zbiory rozmyte,
wykorzystanie do
sterowania agentów upostaciowionych.
- Środowisko MRROC++. Wprowadzenie.
Sposoby
wykorzystania MRROC++ do budowy systemów wielorobotowych.
Część druga:
- Autonomiczna nawigacja robota mobilnego. Pojęcie
robota
autonomicznego. Sformułowanie zadań: samo-lokalizacji robota,
planowania ścieżki ruchu, konstruowania map otoczenia, wykrywania i
unikania kolizji, sterowania. Źródła niepewności w
nawigacji. Reprezentacje środowiska. Podstawowe pojęcia
matematyczne: rozkład
prawdopodobieństwa, prawdopodobieństwo warunkowe, reguła Bayesa,
zmienne losowe, procesy stochastyczne, łańcuchy Markowa.
- Samo-lokalizacja robota. Podział i
omówienie wybranych podejść i metod lokalizacji.
Podejście probabilistyczne wykorzystujące łańcuchy Markowa (filtr
Bayesa): wersja topologiczna i geometryczna (siatkowa). Model czujnika
i model działania (akcji) robota, model środowiska (siatki zajętości,
drzewa binarne, czwórkowe, itp.).
- Metody losowe w zadaniu samo-lokalizacji. Algorytmy
Monte Carlo, filtry cząsteczkowe. Porównanie podejść do
problemu samo-lokalizacji robota.
- Budowa mapy otoczenia - mapowanie. Problemy
tworzenia mapy jako wewnętrznej reprezentacji otoczenia robota. Mapy
geometryczne
i topologiczne, hybrydowe. Wykorzystanie i interpretacja danych z
czujników. Wybrane metody i algorytmy tworzenia map
środowiska.
Estymacja prawdopodobieństwa aposteriori (siatki
zajętości, rozszerzony filtr Kalmana), metoda największej
wiarygodności.
- Jednoczesna samo-lokalizacja i budowanie mapy
- Simultaneous Localization and Mapping
(SLAM). Algorytm FastSLAM. Podejście z zastosowaniem filtru
Kalmana.
- Planowanie ścieżki ruchu robota.
Sformułowanie problemu
planowania. Przeszukiwanie dyskretnej i ciągłej przestrzeni stanu.
Metody i algorytmy planowania ścieżki ruchu (geometryczne i
topologiczne): metoda propagacji fali, metoda diagramu Woronoia, metoda
grafu widoczności, metoda elastycznej wstęgi, metoda sztucznych
pól potencjałowych. Metody probabilistyczne planowania
ścieżek.
- Unikanie kolizji. Przykładowe
algorytmy unikania kolizji.
Laboratorium:
Zadania
powinny być wykonywane przez
zespoły 2 osobowe. Można wybrać jeden z dwóch
rodzajów ćwiczeń
laboratoryjnych:
- Zadania
polegające na implementacji algorytmów i komputerowej symulacji
ich działania (maksymalna punktacja - 35 pkt.).
- Zadania eksperymentalne
polegające na wykorzystaniu
sprzętu (maksymalna punktacja - 45 pkt.).
Przykładowe zadania
przygotowane przez prof. C. Zielińskiego (sem. letni 2004/2005)
- Sterowanie reaktywne robotem mobilnym.
- Sterowanie robotem mobilnym z wykorzystaniem
pól
potencjałowych.
- Poszukiwanie drogi w labiryncie.
- Budowa gniazda przez rój robotów.
Literatura do
powyższych
zadań:
C. Zieliński. Formal
approach to the design of robot programming frameworks: the behavioural
control case. BULLETIN OF THE POLISH ACADEMY OF SCIENCES
TECHNICAL SCIENCES Vol. 53, No. 1, 2005.
Przykładowe zadania
przygotowane przez W. Szynkiewicza (sem. letni 2004/2005)
- Algorytm lokalizacji robota - podejście markowowskie.
- Lokalizacja robota z wykorzystaniem algorytmu filtru
cząsteczkowego - podejście Monte Carlo.
- Tworzenie mapy hybrydowej (geometryczno-topologicznej) na
podstawie odczytów z czujników.
- Algorytm RRT (Rapidly-exploring Random Tree) planowania
ścieżki
ruchu robota moblinego.
- Algorytm PRM-SBL planowania ścieżki ruchu robota.
Literatura i materiały pomocnicze:
- A.
Arleo, J. del R. Millan, and D. Floreano: Efficient Learning
of
Variable-resolution Cognitive Maps for Autonomous Indoor Navigation. IEEE
Trans.
on Robotics and Automation, Vol.19, No. 6, pp. 990-1000, (1999).
- Artificial
Intelligence and Mobile Robots, Ed. D. Kortenkamp, R. P.
Bonasso,
R. Murphy, MIT Press, 1998.
- I.
Dulęba: Metody
i
algorytmy planowania ruchu robotów mobilnych i
manipulacyjnych,
Akademicka Oficyna Wydawnicza Exit, 2001.
- D.
Fox, W. Burgard, and S. Thrun:
Markov localization for mobile robots in dynamic environments.
Artificial Intelligence. 11:391--427, 1999.
- D.
Fox, S. Thrun, W. Burgard, and F. Dellaert.
Particle filters for mobile robot localization. In A. Doucet,
N.
DeFreitas, and N. Gordon, editors, Sequential Monte Carlo Methods in
Practice. 2000.
- D.
Fox. Adapting
the sample size in particle filters through KLD-sampling. International
Journal of Robotics Research,
22(12):985-1003, 2003.
- S. M. LaValle and J. J. Kuffner, Jr.: Randomized
Kinodynamic Planning. International Journal of Robotics
Research,
Vol. 20, No. 5, pp.379-400, May 2001.
- S. M. LaValle and J. J. Kuffner, Jr.: Rapidly-Exploring
Random Trees: Progress and Prospects. In A. Bicchi, H. I.
Christensen, and D. Prattichizzo, editors, Control Problems in
Robotics, p. 19-37. Springer-Verlag, Berlin, 2002.
- G. Sanchez and J.C. Latombe: On
delaying Collision Checking in PRM Planning - Application to
Multi-Robot
Coordination. Int. J. of Robotics Research, 21(1):5-26,
January 2002.
- L.
E. Kavraki, P. Svestka, J. C. Latombe, and M. Overmars: Probabilistic
roadmaps for path planning in high-dimensional configuration spaces.
IEEE Transactions on Robotics and Automation, 12(4):566-580, 1996.
- S.
Russell, P. Norvig: Artificial Intelligence: A Modern Approach,
Prentice Hall; 2nd edition, 2002.
- S. Thrun, 1998.
A Framework for Programming Embedded Systems: Initial Design and
Results. Technical Report CMU-CS-98-142, Carnegie Mellon
University, Pittsburgh, PA
- S.
Thrun, D. Fox, and W. Burgard, 1998.
A
Probabilistic Approach to Concurrent Mapping and Localization for
Mobile Robots. Machine Learning 31, 29--53 and Autonomous
Robots 5,
253--271, (joint issue).
- S. Thrun, 1999.
Learning Metric-Topological Maps for Indoor Mobile Robot Navigation.
Artificial Intelligence 99(1), 21--71.
- S. Thrun, J. Langford, and D. Fox, 1999.
Monte
Carlo Hidden Markov Models: Learning Non-Parametric Models of Partially
Observable Stochastic Processes. In Proceedings of ICML-99.
- S. Thrun, D. Fox, and W. Burgard.
Monte Carlo Localization With Mixture Proposal Distribution.
In
Proceedings of the AAAI National Conference on Artificial Intelligence,
Austin, TX, 2000.
AAAI.
- S. Thrun, D. Fox, W. Burgard, and F. Dellaert.
Robust Monte Carlo Localization for Mobile Robots .
Artificial Intelligence 128, 2001, pp. 99-141.
- S.
Thrun, M. Beetz, M. Bennewitz, W. Burgard, A.B. Cremers, F. Dellaert,
D. Fox, D. Haehnel, C. Rosenberg, N. Roy, J. Schulte, and D. Schulz.
Probabilistic Algorithms and the Interactive Museum Tour-Guide Robot
Minerva. International Journal of Robotics Research, 19(11): 972--999, 2000.
- S. Thrun, M. Montemerlo, D. Koller, B. Wegbreit,
J. Nieto, and E. Nebot. FastSLAM: An
Efficient Solution to the Simultaneous Localization And Mapping
Problem with Unknown Data Association.
- S. Thrun, W. Burgard, and D. Fox. Probabilistic Robotics.
The MIT Press, 2005.
- Biblioteka procedur numerycznych
"Numerical Recipes in C."
- C. Zieliński. Formal approach to the design of
robot programming frameworks: the behavioural
control case. BULLETIN OF THE POLISH ACADEMY OF SCIENCES. TECHNICAL
SCIENCES Vol. 53, No. 1, 2005.
E-mail:
W.Szynkiewicz.(et).ia.pw.edu.pl