Formbildning (eller mönsterbildning) är ett grundläggande distribuerat problem för system av beräknings mobila enheter. Intensivt studerad för system av autonoma mobila robotar, har det nyligen undersökts i sfären av programmerbar materia, där enheter antas vara små och med kraftigt begränsade kapaciteter. Nämligen har det studerats i den geometriska Amoebot-modellen, där de anonyma enheterna, som kallas partiklar, arbetar med en sexkantig tessellation av planet och har begränsad beräkningskraft (de har konstant minne), strikt lokal interaktion och kommunikationskapacitet (endast med partiklar i angränsande noder i nätet), och begränsad motorisk kapacitet (från en rutnät nod till en tom angränsande nod); deras aktivering kontrolleras av en kontradiktorisk schemaläggare. Nyligen genomförda undersökningar har visat hur partiklarna, från en välstrukturerad konfiguration där partiklarna bildar en (inte nödvändigtvis fullständig) triangel, kan bilda en stor klass av former. Detta resultat har fastställts enligt flera antaganden: överenskommelse om medurs riktning (dvs. chirality), en sekventiell aktivering schema, och randomisering (dvs., partiklar kan vända mynt för att välja en ledare). I detta papper får vi flera resultat som, bland annat, ger en karakterisering av vilka former kan bildas deterministiskt med utgångspunkt från någon helt enkelt ansluten inledande konfiguration av n partiklar. Karaktäriseringen är konstruktiv: vi ger en universell form formation algoritm som, för varje genomförbar par av former (S 0, S F ), gör det möjligt för partiklarna att bilda den slutliga formen S F (given i ingång) med början från den ursprungliga formen S 0, okänd för partiklarna. Den slutliga konfigurationen kommer att vara en lämplig skalad kopia av S F beroende på n. Om randomisering är tillåten, då alla inmatningsform kan bildas från någon inledande (enkelt ansluten) form av vår algoritm, förutsatt att det finns tillräckligt med partiklar. Vår algoritm fungerar utan chiralitet, vilket bevisar att chiralitet är beräkningsmässigt irrelevant för formbildning. Dessutom fungerar det under en stark kontradiktorisk schemaläggare, inte nödvändigtvis sekventiell. Vi tar också hänsyn till komplexiteten i formbildning både i fråga om antalet rundor och det totala antalet rörelser som utförs av partiklar som utför en universell formformationsalgoritm. Vi visar att vår lösning har en komplexitet av O(n 2 ) rundor och rörelser: detta antal drag är också asymptotiskt värsta-fall optimal.
En universal formationsalgoritm i Amöebot-modellen beskrevs av Di Luna et al. Hoppa över det.
Shape formation by programmable particles
{'venue': 'Distributed Computing', 'journal': 'Distributed Computing', 'mag_field_of_study': ['Computer Science', 'Engineering']}