Čo ponúkame - Najlepšie výsledky

Na jednotkovom kruhu sa nachádza určitý počet brán. Na kruhu sú umiestnené dva autonómne mobilné roboty. Roboty majú maximálnu rýchlosť 1, bezdrôtovo medzi sebou komunikujú. Každý robot má k dispozícii mapu domény vrátane brán, vie, aká je jeho vzdialenosť od druhého robota, nepozná však svoju vlastnú počiatočnú polohu na doméne. Cieľom evakuačného problému je nájsť algoritmus, ktorý v najhoršom možnom prípade minimalizuje čas potrebný pre oba roboty na dosiahnutie brány a opustenie domény.

 

Riešitelia uvažujú o dvoch variantoch tohto problému, v závislosti od toho, či roboty majú kontrolu nad počiatočnou vzájomnou vzdialenosťou. Ukázali, že ak je počiatočná vzdialenosť medzi robotmi vstupným údajom (čiže nie je pod ich kontrolou), existujú jednoduché algoritmy na dosiahnutie optimálneho času evakuácie v prípade, že: a) na štarte sú roboty tesne vedľa seba, pričom rozmiestnenie výstupných brán je ľubovoľné; b) všetky brány sú rovnomerne rozmiestnené alebo tesne vedľa seba, a roboti majú ľubovoľné štartovacie pozície.

 

K ďalším výsledkom patrí dolný a horný odhad pre prípad ľubovoľného rozmiestnenia brán a ľubovoľných štartovacích pozícií robotov. Pre model, v ktorom si roboty na štarte môžu vybrať vzájomnú vzdialenosť (so znalosťou, ale bez kontroly vzájomných pozícií brán), riešitelia navrhli prirodzenú triedu algoritmov parametrizovaných najväčšou vzdialenosťou medzi ľubovoľnými dvomi bránami.