Simulated Nuclear Reactor - Accident Analysis

Brak lidera, brak mapy, tylko sąsiadów

Zbiór dronów poruszających się w ciasnym kształcie litery V lub obracających się w koło wygląda z zewnątrz jak choreografia, ale pozaśniętego drona nie posiada kopii tej choreografii. Każdy dron realizuje tę samą prostą regułę wykorzystując jedynie to, co widzi lub słyszy od swoich najbliższych sąsiadów – żaden centralny kontroler nie wysyła pozycji, żaden dron nie ma globalnej mapy formacji. Jest to konsensus: rodzina algorytmów rozproszonych, gdzie lokalne porozumienie między sąsiadami generuje skoordynowane zachowanie na poziomie globalnym, i tak ten demo w naszym miejscu zorganizowało się w formacje liniowe, V-kształtne, siatkowe i okrągłe.

demo na żywo · powiązana symulacja● LIVE

Uaktualnienie kanoniczne

Postępujący liniowy protokół konsensusu wymaga od każdego agenta i, aby przesunąć swoje stan x_i w kierunku średniej wartości stanów jego sąsiadów, ważonej przez stopień ich powiązania:

x_i(t+1) = x_i(t) + ε * sum_{j w N(i)} ( x_j(t) - x_i(t)) Dla lotu formacyjnego, x_i nie jest absolutną pozycją drona, ale jego pozycją względną względem wyznaczonego slotu w formacji. Każdy dron zna swój własny przesunięcie wewnątrz docelowego kształtu (slot drona nr 3 znajduje się o 2 m z tyłu i 1 m w lewo od środka skupienia stada, np.) i stosuje zasadę konsensusu do zmodyfikowanego członu błędu – różnicy między jego rzeczywistą pozycją względną a jej wymaganą pozycją względną, uśrednionej względem tego, co ich sąsiedzi zgłaszają o ich stanach. Zrowadzając ten błąd do zera wszędzie, cała stada zablokuje się w formacji, mimo że żaden dron nigdy nie obliczył kształtu jako całości.

x_i(t+1) = x_i(t) + eps * sum_{j in N(i)} ( x_j(t) - x_i(t) )

Dlaczego znaczy więcej graf komunikacyjny niż zasada

Aktualizacja powyżej działa tylko wtedy, gdy informacje mogą faktycznie dotrzeć do każdego drona, poprzez kilka połączeń. Przedstawcie rój jako graf – węzeł dla każdego drona, krawędź, jeśli dwa drony znajdują się w zasięgu komunikacji lub czujności – a odpowiednim obiektem jest laplacyana L = D - A (macierz laplasa minus macierz sąsiedztwa). Teoria konsensusu dowodzi zbieżności tylko wtedy, gdy graf jest spójny: istnieje ścieżka, bezpośrednia lub pośrednicząca, między każdym parą dronów. Algebraiczna odległość – druga najmniejsza wartość własna L, często nazywana lambda-2 lub wartością Fiedlera – kontroluje szybkość: większa lambda-2 oznacza szybszą zbieżność; graf na granicy rozdzielenia na siebie ma lambda-2 bliskie zeru i konsensus powolnie się wyłania. Kontrola formowania prawdziwego róju jest niezoddzielna od problemu topologii sieci – jeśli drony rozchodzą się, aż graf komunikacyjny ulegnie rozszczepieniu na dwie oddzielne grupy, każda grupa osiągnie własny lokalny konsensus i rój podzieli się na dwie formacje, które nigdy nie będą się zgadzać. Utrzymywanie spójności – czasem jawnie, poprzez zniekształcanie ruchu w celu uniknięcia izolacji peryferyjnego drona – jest tak samo ważna jak prawo konsensusu.

L = D - A D = diag(stopień każdego węzła) A = macierz sąsiedztwa (1, jeśli i, j mogą komunikować się, w przeciwnym razie 0) lambda_2(L) > 0 iff graf jest spójny iff konsensus zbiega się lambda_2(L) duża => szybka zbieżność; lambda_2(L) -> 0 => zbieżność utyka

L = D - A
D = diag(degree of each node)
A = adjacency matrix (1 if i, j can communicate, else 0)

lambda_2(L) > 0   iff   graph is connected  iff  consensus converges
lambda_2(L) large  => fast convergence; lambda_2(L) -> 0  => convergence stalls

Od konsensusu do kształtów: linia, V, siatka, okrąg

Zmiana formacji polega po prostu na wymianie tabeli offsetów, którą każdy dron trzyma – samo prawo konsensusu nigdy nie ulega zmianie. Formacja w kształcie litery V przypisuje każdemu dronom slot na dwóch rozchodzących się promieniach za wirtualnym punktem lidera (odzwierciedlającym formację aerodynamiczną guszczy, której używają gołębie); siatka przypisuje prostokątną kratę offsetów; okrąg przypisuje offsety pod równymi kątami wokół centroidu o stałym promieniu. Ponieważ protokoł podstawowy jest niezależny od kształtu, demo może wymieniać formacje „gorącym wstopem” i obserwować, jak rój ponownie się gromadzi, napędzany jedynie ponownym odczytaniem przez każdy dron nowego slotu i ponovieniem tej samej reguły uśredniania sąsiadów.

W rzeczywistych systemach wielodronowych dodano dwa praktyczne warstwy: termin unikający kolizji (krótko-działające odpychające pole, podobne do potencjałów używanych w planowaniu trasy dla pojedynczego drona) tak aby konsensus nigdy nie nakazywał dwóm dronom zajmowania tego samego slotu tymczasowo, oraz wariant lidera i podążającego, gdzie jeden lub kilka agentów śledzi zewnętrzną trajektorię odniesienia, a reszta stosuje zwykły konsensus do wirtualnego offsetu od lidera – przydatne, gdy cała formacja musi się przesunąć w określonym miejscu zamiast tylko samogromadzać się na miejscu.

Często zadawane pytania

Czy którykolwiek z dronów w zmowie wie o pełnym kształcie formacji?

Nie. Każdy drona zna jedynie swój własny przesunięcie względem celu w formacji oraz stany zgłoszone przez jego najbliższych sąsiadów. Kształt formacji wyłania się lokalnie dla każdego drona, minimalizując jego błąd w stosunku do tych sąsiadów – żaden drona, ani zewnętrzny kontroler, nie posiada globalnego obrazu.

Co się dzieje, jeśli graf komunikacyjny stanie się odłączony?

Konsensus zbiega się tylko do pojedynczo uzgodnionej formacji, gdy graf pozostaje połączony – musi istnieć ścieżka, nawet wieloetapowa, pomiędzy każdą parą dronów. Jeśli zmowa rozprzestrzeni się na tyle, że graf rozdzieli się na oddzielne klastry, każdy z tych klastrów zbiega się do własnego lokalnego konsensusu niezależnie, a zmowa skutecznie ulega podziale na wiele formacji.

Jak szybko zmowa zbiega się do nowej formacji?

Prędkość zbieżności jest regulowana przez algebraiczną łączność grafu komunikacyjnego – drugie najmniejsze wartości własne macierzy Laplacja, lambda-2. Gęsto połączona zmowa zbiega się szybko; słabo połączona, zwłaszcza zbliżająca się do rozszczepienia na odłącza się klastry, zbiega się powoli, ponieważ informacja potrzebuje więcej czasu na propagację przez całą grupę.

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Drone Formation Flying i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.

▶ Otwórz symulację Drone Formation Flying