Metody symulacyjne w wielokrokowych Grach Obronnych Stackelberga w kontekście bezpieczeństwa publicznego

Opracowane metody algorytmiczne

Ze względu na złożoność obliczeniową (NP-trudność) wyznaczania Równowagi Stackelberga w grach wielokrokowych, prace badawcze odeszły od klasycznych metod dokładnych opartych na programowaniu liniowym (MILP) na rzecz skalowalnych metaheurystyk. W ramach projektu zaproponowano i przebadano szereg unikalnych podejść:

• Algorytmy oparte na Monte Carlo Tree Search (MCTS): Zaproponowano metody (Mixed-UCT, O2UCT), które wykorzystują przeszukiwanie drzew gry metodą Monte Carlo do estymacji optymalnych strategii mieszanych. Dzięki iteracyjnemu próbkowaniu przestrzeni strategii atakującego oraz zastosowaniu podejścia typu "double-oracle", rozwiązania te pozwalają na efektywne wyznaczanie strategii w grach o sumie ogólnej.


• Podejście Ewolucyjne i Memetyczne: Zaprojektowano generyczne algorytmy ewolucyjne (EASG), służące do ewolucji populacji strategii obrońcy. Metody te zostały rozszerzone o obsługę gier z sygnalizacją (EASGS), gdzie uwzględniono wykorzystanie dronów i sensorów oraz niepewność detekcji. Wprowadzono również algorytmy memetyczne, wzbogacające ewolucję o lokalną optymalizację strategii w celu podniesienia jakości rozwiązań.


• Koewolucja Strategii: Stworzono systemy koewolucyjne (CoEvoSG), w których jednocześnie ewoluują dwie konkurujące populacje: strategii obrońcy i strategii atakującego. Zastosowanie mechanizmu "Hall of Fame" opartego na Równowadze Nasha pozwoliło na stabilizację procesu uczenia i szybszą konwergencję, eliminując konieczność kosztownego przeszukiwania całej przestrzeni odpowiedzi przeciwnika.


• Neuroewolucja: Opracowano metody wykorzystujące sieci neuronowe do oceny jakości strategii (NESG, DNESG). Sieci te, trenowane na danych historycznych, pełnią rolę modeli zastępczych (surrogate models), umożliwiając błyskawiczne porównywanie strategii w turniejach ewolucyjnych bez konieczności przeprowadzania pełnych symulacji gry. Podejście to pozwala na aproksymację modelu decyzyjnego atakującego bez wiedzy a priori o jego preferencjach.


• Modelowanie Ograniczonej Racjonalności: Przeanalizowano scenariusze, w których przeciwnik nie zachowuje się w sposób idealnie racjonalny. Do algorytmów optymalizacyjnych zintegrowano modele psychologiczne, takie jak Teoria Zakotwiczenia (Anchoring Theory), Teoria Perspektywy (Prospect Theory). Przeprowadzone eksperymenty z udziałem ludzi potwierdziły, że strategie wygenerowane z uwzględnieniem tych błędów poznawczych (np. przy użyciu wariantu ATSGL dla metod MILP lub odpowiednich wariantów metod heurystycznych) pozwalają obrońcy osiągać wyższe wyniki w starciu z rzeczywistymi przeciwnikami.


• Rozszerzona Przestrzeń Decyzyjna (ADSO): Zaproponowano metodę optymalizacji w rozszerzonej przestrzeni decyzyjnej, wykorzystującą zmienne binarne do sterowania rzadkością (sparsity) rozwiązań. Podejście to umożliwia generowanie bardziej zwartych strategii obronnych, co znacząco poprawia skalowalność obliczeniową w bardzo dużych instancjach gier.

Wyniki i zastosowania

Zrealizowane eksperymenty wykazały, że proponowane metody metaheurystyczne oferują bliską liniowej skalowalność czasową oraz niemal stałe zużycie pamięci, co stanowi znaczącą przewagę nad wykładniczą złożonością klasycznych solverów. Dzięki temu algorytmy te umożliwiają rozwiązywanie gier o rozmiarach i horyzoncie czasowym, które dotychczas były nieosiągalne dla metod dokładnych.

Metody zweryfikowano na różnorodnych scenariuszach, w tym:

• Ochrona infrastruktury fizycznej (gry typu Warehouse Games, Search Games).
• Cyberbezpieczeństwo (gry typu FlipIt, Deep Packet Inspection).
• Ochrona zasobów naturalnych (Green Security Games) z wykorzystaniem patroli i systemów ostrzegania.
• Ochrona celów ruchomych (np. promów pasażerskich).