Artificial intelligence techniques in real-time robust route planning

Abstract

Usability of satellite navigation devices deteriorates drastically when the driver encounters an obstacle or makes a mistake. This is because applications used for satellite navigation are designed as decision-making systems, not decision-support systems. This is caused by using a classical approach to route planning, based on path search in a graph representing the road network. If perturbations occur during execution of a plan, it is necessary to repeat the planning procedure with updated constraints. Unfortunately, mobile devices have limited processing power, making the task time-consuming and difficult. To provide practical support for the driver in the decision-making process and give them free choice among available options, route planning should be performed in a multi-variant manner. Delivery of instructions to the driver is subject to hard real-time constraints - instructions regarding a manoeuvre at a certain junctions delivered after the car has reached it are useless. The thesis presents a solution to the problem of efficient generation, representation and execution of route plans in dynamic environments by intelligent beings. The suggested approach allows for efficient a priori generation of multi-variant plans and flexible navigation in unpredictable environments. Problem wytyczania trasy przejazdu jest praktycznym zagadnieniem, znajdującym zastosowanie od czasów pierwszych podróży dokonywanych przez człowieka. Użyteczność urządzeń służących do nawigacji satelitarnej 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 niejako 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. Aby wspomóc podejmowanie decyzji przez kierowcę i zapewnić mu wolny wybór spośród dostępnych opcji, wytyczanie trasy powinno przebiegać wielotorowo. Kierowca może wtedy 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. 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).