Hledání statického objektu ve známém prostředí

Problém mobilního hledání obecně spočívá v nalezení jednoho nebo více cílů v daném prostředí pomocí jednoho nebo několika mobilních senzorů. My předpokládáme jeden statický objekt, který je, neznámo kam, umístěn dovnitř známého 2D polygonálního prostředí a chceme ho nalézt s pomocí jediného mobilního robotu v průměru co nejrychleji. Robot je vybaven senzorem s 360° rozhledem a omezeným dosahem viditelnosti, který po celou dobu hledání snímá okolí. U robotu se předpokládá schopnost rozpoznat objekt zájmu pokud se vyskytuje v jeho zorném poli. Jádrem problému je tedy naplánovat co nejeefektivnější strategii hledání. V diplomové práci Jana Mikuly navrhneme a implementujeme novou metodu pro tento problém a experimentálně ověříme její vlastnosti. V obecné rovině problém řešíme standardně a to rozdělením na diskretizaci a optimalizaci. Obě části našeho řešení jsou nicméně inovativní. Navrhujeme nový způsob, jak diskretizovat prostředí s využitím řešení souvisejícího, tzv. hlídačova problému. Zavádíme také obecnou metaheuristiku produkující efektivní plány pro několik diskrétních modelů původního problému. Nová metaheuristika, která bere v úvahu omezený výpočetní čas, je nejprve navržena pro nejjednodušší model — problém cestujícího doručovatele — a to pomocí obecné metodiky založené na vyhodnocení distribuce výpočetního času z mnoha běhů. Testována na několika sadách standardních instancí používaných komunitou z operačního výzkumu, naše metaheuristika výrazně překonává současný nejlepší přístup z literatury v experimentech s omezením na výpočetní čas v rozmezí od 1 do 100 sekund. Dále poskytuje konkurenceschopné výsledky v tradičním smyslu a v experimentech s danou cílovou kvalitou řešení, která odpovídá nejlepšímu známému řešení zhoršenému přibližně o 1 %. Metaheuristika je dále rozšířena tak, aby lépe modelovala problém mobilního hledání, a to zohledněním úsilí potřebného k otáčení robota, snímání na cestě mezi lokacemi a dalších reálných aspektů problému. Navrhovaná diskretizace a metaheuristika společně produkují efektivní strategie pro mobilní hledání, jak ukazují naše vlastní idealizované simulace a také experimenty v realistickém prostředí robotického simulátoru. V reálném životě lze naše řešení použít například jako efektivní plánovač v krizovém scénáři, kde mobilní robot nebo jiný druh agenta hledá oběti po nějaké katastrofě.