O líných algoritmech, logice a hledání cest pro roboty

Jak přimět desetiletí propracovávané všemožné triky pracovat na hledání optimální cesty pro mobilní roboty k dosažení cíle a chytře odřezávat neperspektivní kandidáty na vyhnutí se srážkám.

Z biologického hlediska se dá říct, že lenost funguje jako ochranný mechanismus organismu proti vyčerpání. Překvapivě lenost pomáhá i ve světě počítačů a algoritmů, v umělé inteligenci při řešení robotických úloh, obzvlášť když je robotů v úloze mnoho. Počítači sice nehrozí vyčerpání, ale mohl by plýtvat drahocenným strojovým časem na zbytečnosti. U počítače, potažmo algoritmu, který na něm běží, se zdá být dobré, když není příliš snaživý a dělá jen tolik, kolik nezbytně musí. Představme si například program, který má vykonat operaci C, jestliže výsledek operace A nebo operace B je jedna, v takovém případě stačí, když zjistí, že výsledek operace A byl jedna, a už se nemusí pídit po výsledku operace B a může rovnou začít vykonávat C. To je sice hodně primitivní příklad programové lenosti, avšak je velmi užitečný, když jsou třeba operace A a B složité simulace, které trvají dlouho. Některé programovací jazyky, jako například Java nebo C++, mají podobné líné vyhodnocování výrazů přímo v definici toho, jak fungují.

Konfliktové prohledávání

Koneckonců i z pohledu společenského se zdá být určitá forma speciálně programátorské pohodlnosti prospěšná, neboť stojí za různými algoritmickými inovacemi. Pochopitelně se to nesmí přehnat, kdo má v programátorském týmu vyloženě líného programátora, ví, že to žádná výhra není. Ale je-li programátorská pohodlnost, tedy jakási tendence vyhýbat se zbytečně složitým postupům, ve správné míře namíchána s talentem, může vést k pokroku.

Multiagentní hledání cest – robot 1 má za cíl místo A, robot 2 má za cíl místo B. Pokud roboty současně vyrazí po cestách a2, a3, b3, resp. b1, c1, c2, celkově stráví na cestách 4 časové jednotky, což odpovídá jednomu z optimálních řešení.

To je případ nyní již velmi známého algoritmu pro řešení robotických navigačních úloh tzv. konfliktového prohledávání, označovaného zkratkou CBS (z anglického Conflict-based Search) [1]. Ten je bezpochyby ukázkou toho, jak nedělat věci zbytečně komplikované. Doktorand Guni Sharon na Ben Gurionově univerzitě společně se školitelem řešil úlohu známou jako multirobotické hledání cest (viz Navigační hlavolamy, Vesmír 97, 582, 2018/10). V této úloze hledáme cesty pro mobilní roboty, kde každý robot má za úkol dosáhnout svého cílového místa. Obecně se nemusí nutně jednat o roboty, ale o libovolné mobilní předměty, jejichž přemístění chceme naplánovat, nicméně s roboty v hlavní roli je úloha srozumitelnější. Roboty se obvykle pohybují všechny najednou, takže je potřeba zajistit, aby se při pohybu do cílových míst po nalezených cestách nesrazily (obr. 1). Navíc chceme v nějakém smyslu co nejlepší řešení, obvykle aby celkový součet časů, který roboty stráví na cestách, byl co nejmenší, což je veličina běžně označovaná jako cena. Informatik, který má zkušenost s řešením obtížnosti úloh, zde jistě cítí potíže, s počtem robotů totiž obtížnost exponenciálně vzrůstá. Ačkoli tedy pro nejhorší možná zadání úlohy poběží i naše nejlepší známé algoritmy dlouho, snažíme se alespoň o to, abychom jednoduchá zadání zvládali rychle, hledáme chytré adaptivní algoritmy.

Doktorand Sharon si byl zcela vědom tohoto požadavku, navíc se nevrhnul snaživě po řešení, které nabízelo rozpracování poněkud přímočaré myšlenky, která stojí za algoritmem nyní známým pod zkratkou ICTS (Increasing Cost Tree Search) a je dosti pracná na programování. Raději přemýšlel dál, až nakonec přišel s úplně jiným algoritmem, jehož naprogramování je daleko jednodušší. Konkrétně vymyslel princip líného konfliktového prohledávání. Myšlenka algoritmu je jednoduchá, přesně tak, jak geniální myšlenky bývají.

Nejprve najdeme nejkratší cestu pro každého robota tak, jako by ostatní roboty vůbec nebyly přítomny, tj. hledáme nejkratší cesty bez ohledu na možné srážky mezi roboty, jedná se tedy o jednorobotické hledání nejkratší cesty. Hledání jedné individuální nejkratší cesty je v informatice dobře prozkoumaná úloha, můžeme použít některý ze známých a navíc rychlých algoritmů, například prohledávání do šířky nebo lépe informované prohledávání. Pak řešení zkontrolujeme, jestli nedošlo ke srážce. Pakliže nikoli, máme vyhráno. Těžkou úlohu multirobotického hledání cest jsme vyřešili docela jednoduše, několikerým použitím algoritmu jednorobotického hledání nejkratší cesty. Využili jsme líného principu, optimisticky jsme vsadili na to, že úloha se neprojeví ve své plné složitosti.