Artificial Intelligence Techniques in Real-Time Robust Route Planning
Metody sztucznej inteligencji dla planowania odpornych tras w czasie rzeczywistym

mgr inż. Sebastian Ernst

Promotor: Prof. dr hab. inż. Antoni Ligęza – Akademia Górniczo-Hutnicza
Dyscyplina: Informatyka

Problem wytyczania trasy przejazdu jest praktycznym zagadnieniem, znajdującym zastosowanie od czasów pierwszych podróży dokonywanych przez człowieka. Przed epoką komputerów, do ręcznego rozwiązywania tego problemu służyły mapy; rozwiązania informatyczne pozwoliły na automatyzację tego procesu. Pierwotne aplikacje wspierające planowania trasy używane były przed rozpoczęciem podróży.

Osiągnięcia ostatnich lat, dzięki rozwojowi technologii mobilnych i udostępnieniu systemu pozycjonowania GPS, pozwoliły na bardziej czynne wspieranie nawigacji. Urządzenia i aplikacje służące do tzw. nawigacji satelitarnej są szeroko dostępne i stały się bardzo popularne.

Użyteczność takich urządzeń spada drastycznie gdy kierowca napotyka na przeszkodę w wykonaniu planu lub popełnia błąd. Dzieje się tak, gdyż aplikacje stosowane do nawigacji projektowane są jako systemy podejmujące decyzje, a nie jako systemy wspierające podejmowanie decyzji przez kierowcę. Jest to uwarunkowane stosowaniem klasycznego podejścia do planowania trasy, polegającego na wytyczaniu ścieżki w grafie reprezentującym sieć dróg.

W przypadku zaburzenia podczas wykonywania planu wytyczonego przez urządzenie, wymagane jest ponowne przeprowadzenie procedury wytyczania ścieżki dla nowych ograniczeń. Niestety, stosowane urządzenia posiadają ograniczoną moc obliczeniową. Dodatkowe utrudnienie stanowi fakt, że sygnał o zaburzenia dociera do urządzenia z opóźnieniem spowodowanym długim (1-2 sek.) okresem odnawiania informacji o położeniu i dużym błędem, którym jest ona obarczona.

Aby wspomóc podejmowanie decyzji przez kierowcę i zapewnić mu wolny wybór spośród dostępnych opcji, wytyczanie trasy powinno przebiegać wielotorowo. Złożoność takiego problemu jest jednakże jeszcze większa niż złożoność problemu wytyczania ścieżki. Jest to widoczne szczególnie w przypadku wytyczania trasy w dużych miastach, o skomplikowanej strukturze sieci ulic - kierowca może wykorzystać obserwacje sytuacji drogowej i świadomie wybrać rozwiązanie alternatywne.

Dostarczenie instrukcji do kierowcy podlega ograniczeniom czasu rzeczywistego - instrukcje dotyczące manewru na określonym skrzyżowaniu, a dostarczone po jego przejechaniu, stają się bezużyteczne. Charakterystyka ruchu ulicznego często nie pozwala przy tym na zatrzymanie się i poczekanie na zakończenie obliczeń.

Niniejsza praca rozwiązuje problem efektywnego generowania, reprezentacji i wykonywania planów przejazdu w środowisku dynamicznym poprzez wprowadzenie paradygmatu odpornego planowania tras (ang. robust route planning).

Proponowane podejście pozwala na efektywne generowanie wielowariantowych planów a priori oraz elastyczną nawigację w trudnych do przewidzenia środowiskach. Wykorzystane zostały techniki sztucznej inteligencji, takie jak algorytmy wyszukiwania, kompilacja wiedzy i granularyzacja. Pozwoliło to na wytyczanie i reprezentację planów odpornych, przystosowanych do wykonania pod ograniczeniami czasu rzeczywistego.

Pełna wersja autoreferatu ernst-autoreferat.pdf.

1. Knowledge representation for intelligent and error-prone execution of robust granular plans. A conceptual study / Sebastian ERNST, Antoni LIGĘZA / FLAIRS-22: Proceedings of the 22nd International FLAIRS Conference, 19–21 May 2009, Florida, USA
2. Adaptive granular planning for robust plan generation under uncertain traffic conditions / Sebastian ERNST, Antoni LIGĘZA / Systems Science, ISSN 0137-1223. — 2008 vol. 34 no. 1 s. 77–83 (6,0 punktów)
3. Improvement of route-planning systems using intelligent and knowledge-based methods / Sebastian ERNST, Antoni LIGĘZA / Knowledge acquisition and management, Publishing House of the Wrocław University of Economics, 2008 (7,0 punktów)
4. A rule-based approach to robust granular planning / Sebastian ERNST, Antoni LIGĘZA / International Multiconference on Computer Science and Information Technology, October 20–22, 2008, Wisła
5. Kompilacja wiedzy dla wspomagania inteligentnego wykonania odpornych planów granularnych — [Knowledge compilation for intelligent execution support of robust granular plans] / Sebastian ERNST, Antoni LIGĘZA / Inżynieria wiedzy i systemy ekspertowe / red. Adam Grzech [et al.]. — Warszawa : Akademicka Oficyna Wydawnicza EXIT, 2009 (3,0 punktów)

Pełny wykaz publikacji dostępny na stronie BPP AGH.