i

Aktuální číslo:

2020/6

Téma měsíce:

Léky pro budoucnost

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

 |  1. 6. 2020
 |  Vesmír 99, 352, 2020/6

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.

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.

Nyní vidíte 28 % článku. Co dál:

Jsem předplatitel, mám plný přístup
Jsem návštěvník
Chci si přečíst celé číslo
Předplatným pomůžete zajistit budoucnost Vesmíru. Více o předplatném
OBORY A KLÍČOVÁ SLOVA: Informatika

O autorovi

Pavel Surynek

Doc. RNDr. Pavel Surynek, Ph.D., (*1979) vystudoval Matematicko-fyzikální fakultu Univerzity Karlovy. Působil na Univerzitě v Kobe v Laboratoři inteligentní informatiky a v Centru výzkumu umělé inteligence při Národním institutu pokročilé průmyslové vědy a technologií (AIST) v Japonsku. Ve vědecké a pedagogické práci v současnosti pokračuje na Fakultě informačních technologií ČVUT. Zabývá se umělou inteligencí, speciálně heuristickým prohledáváním, splnitelností, multiagentními systémy a řešením úloh z robotiky.
Surynek Pavel

Doporučujeme

Paradoxy infekce způsobené SARS-CoV-2

Paradoxy infekce způsobené SARS-CoV-2

Jiří Beneš, Ladislav Machala  |  1. 6. 2020
Přestože řada otázek čeká na vysvětlení, vědci rychle skládají obraz infekce novým virem.
Potíže s hrochy

Potíže s hrochy uzamčeno

Pavel Hošek  |  1. 6. 2020
Hroši, ač tvorové obojživelní, údajně neumějí plavat. Opravdu neumějí? A pokud ne, jak mohli v minulosti proniknout na rozmanité ostrovy, na nichž...
Kauza nedokonané vraždy

Kauza nedokonané vraždy

Tomáš Grim  |  1. 6. 2020
Horké léto roku 1985. V domácnosti na periferii Břeclavi se odehrává lítý boj. Dvě oběti na životech jsou v podobných případech standardem. I...

Předplatným pomůžete zajistit budoucnost Vesmíru

Tištěná i elektronická
verze časopisu
Digitální archiv
od roku 1994
Speciální nabídka
pro školy a studenty

 

Objednat předplatné