Navigační hlavolamy

V mnoha velkoskladech zásilkových společností spěchají armády robotů (obr. 1) od jednoho regálu k druhému. Počítače je navigují tak, aby byly co nejrychlejší a nesrazily se. Nakládají a převážejí zboží na místa, kde je lidé převezmou, zabalí a odešlou zákazníkům. Naskládat zboží do krabice ještě stále umějí lépe a rychleji lidé. Je však asi jen otázkou času, kdy i to roboty zvládnou.

Není třeba říkat, kolik pracovníků tak společnosti nemusejí zaměstnat a kolik nachozených kilometrů robotičtí skladníci ušetří těm (snad šťastnějším) zaměstnaným. Roboty jsou naprogramovány tak, aby vše k zabalení přivezly přesně včas. Nikdy nic nehledají, vždy přesně vědí, kde se co nachází – vlastně to nevědí ony, ale počítač, který je řídí a má přehled o všech těch milionech užitečných i zbytečných věcí, po kterých zákazníci touží. Intenzita a hustota robotické dopravy ve velkoskladu si nezadá s automobilovou dopravou v přeplněném velkoměstě. I když se z mnoha důvodů roboty pohybují podstatně pomaleji než automobily, srážka mezi nimi by i tak znamenala vážnou komplikaci a nejspíš i zásah lidského personálu, o jehož zaměstnávání společnost nestojí. Možná překvapí, že robotický provoz je plynulý a žádné dopravní zácpy nevznikají. Roboty si totiž neplánují trasu samy, nýbrž ji centrálně určuje důmyslný algoritmus, který má dokonalý přehled o tom, kam má který robot namířeno. Centrální algoritmus tak najde pro každý robot trasu s ohledem na všechny ostatní roboty. Přednost mají roboty, které musejí přepravit zboží nejdříve. Takto si běžný automobilista obvykle trasu neplánuje, protože o úmyslech ostatních řidičů nemá ponětí a nezbývá mu nic jiného než vyrazit naslepo a snažit se dorazit do cíle podle vlastního uvážení co nejrychleji nebo nejbezpečněji. Nevyrazí trasou B kvůli tomu, že v blízkém okamžiku chce někdo jiný, kdo více spěchá, jet trasou A, i když existují aplikace, které by takové plánování trasy do jisté míry umožnily. Díváme-li se na věc z hlediska multiagentních systémů, pak automobilisté sice zpravidla respektují dopravní předpisy, ale jinak příliš nespolupracují, někdy se chovají až sobecky či soutěživě, zatímco roboty ve velkoskladu dokonale spolupracují, jako by jim šlo o blaho společnosti, pro kterou pracují.

Jak ale řešit či aspoň nějak matematicky uchopit úlohu nalezení tras (v umělé inteligenci se hovoří spíše o hledání cest – angl. pathfinding) pro mnoho robotů současně tak, aby mezi nimi nedošlo ke kolizi?