Travelling All the Time

Written by Petr Brož

Petr Brož

University of West Bohemia

Seminar in Czech
March 4, 2009 at 9:30
University of West Bohemia, UK417

Abstract

(download in PDF)

Problematice hledání cest byla věnována značná pozornost již od samého počátku vědní disciplíny teorie grafů. V dnešní době proto existuje nespočet algoritmů k jejímu řešení. Vzhledem k původnímu kontextu úlohy ale většina těchto algoritmů předpokládá, že prostředí, nad kterým pracují, je neměnné a předem známé. Je zřejmé, že pro účely moderních aplikací s proměnným prostředím (např. virtuální realita, počítačové hry) tak může být použití konvenčních metod velmi obtížné, pokud vůbec možné.

Tato úvaha vedla k zahájení výzkumu v oblasti hledání cest v proměnném prostředí s pomocí dynamických struktur pro dělení prostoru. V rámci semináře bude popsáno konkrétní řešení, které využívá regulární triangulaci a pseudooptimální algoritmus hledání cest pro bezkolizní navigaci mezi obalovými koulemi překážek, které mohou přibývat, ubývat, měnit svůj tvar, pozici apod. V druhé části semináře pak bude nastíněn další směr vývoje tohoto systému, především lokální navigace pomocí potenciálového pole.