Ett optimeringsproblem som naturligt uppstår i studien av svärmrobotar är Freeze-Tag Problem (FTP) av hur man väcker en uppsättning av "sömn" robotar, genom att ha en väckt robot flytta till sina platser. När en robot väl är vaken kan den hjälpa till att väcka andra slumrande robotar. Målet är att alla robotar ska vakna så tidigt som möjligt. Medan FTP har viss likhet med problem från områden i combinatorial optimering såsom routing, sändning, schemaläggning, och täcker, dess algoritmiska egenskaper är förvånansvärt olika. Vi tar hänsyn till både scenarier på grafer och i geometriska miljöer. I grafer sover robotar på hörn och det finns en längdfunktion på kanterna. Vakna robotar färdas längs kanter, med tid beroende på kant längd. För de flesta scenarier, vi anser att offline-versionen av problemet, där varje vaken robot vet positionen för alla andra robotar. Vi bevisar att problemet är NP-hård, även för specialfallet med stjärngrafer. Vi etablerar också hårdhet approximation, visar att det är NP-hård att få en approximationsfaktor bättre än 5 3, även för grafer av begränsad grad. Dessa nedre gränser kompletteras med flera positiva algoritmiska resultat, inklusive: • Vi visar att den naturliga giriga strategin på stjärngrafer har en tight värsta-fall prestanda på 7 3 och ger ett polynom-tids approximationsschema (PTAS) för stjärngrafer. • Vi ger en enkel O(log )-konkurrenskraftig online-algoritm för grafer med maximal grad och lokalt avgränsade kantvikter. • Vi ger en PTAS, kör i nästan linjär tid, för geometriskt inbäddade fall.
Problemet med nätverksbildning är nära relaterat till Freeze-Tag-problemet REF.
The Freeze-Tag Problem: How to Wake Up a Swarm of Robots
{'venue': 'Algorithmica', 'journal': 'Algorithmica', 'mag_field_of_study': ['Mathematics', 'Computer Science']}