Vi inför ett nytt problem inom området mobila robotar, som vi kallar spridning. I detta problem, n robotar placeras i en n node graf godtyckligt och måste samordna med varandra för att nå en slutlig konfiguration så att exakt en robot är vid varje nod. Vi studerar detta problem genom linserna för att minimera minnet som krävs av varje robot och för att minimera antalet rundor som krävs för att uppnå spridning. Dispersion är av intresse på grund av dess relation till problemen med spridning på en graf, prospektering med hjälp av mobila robotar, och belastning balansering på en graf. Dessutom har spridning en omedelbar verklig tillämpning på grund av sitt förhållande till problemet med laddning av elbilar, eftersom varje bil kan betraktas som en robot och laddningsstationer och vägarna ansluter dem noder respektive kanter av en graf. Eftersom laddning är en kostsam affär i förhållande till resor, vill vi fördela dessa bilar bland de olika tillgängliga laddningspunkter där kommunikationen bör begränsas till samverkan mellan bil och bil. Vi ger lägre gränser på både det minne som krävs för robotar för att uppnå dispersion och den minsta körtiden för att uppnå dispersion på någon typ av graf. Vi analyserar sedan avvägningarna mellan tid och minne för olika typer av grafer. Vi tillhandahåller tidsoptimala och minnesoptimala algoritmer för flera typer av grafer och visar kraften i ett litet minne när det gäller körtid.
Dispersion via mobila robotar introducerades i REF, där författarna studerade kompromisser mellan körtid och minne som krävs av varje robot för olika typer av statiska grafer.
Dispersion of Mobile Robots: A Study of Memory-Time Trade-offs
{'venue': "ICDCN '18", 'journal': None, 'mag_field_of_study': ['Computer Science']}