Dynamic Decentralized 3D Urban Coverage and Patrol with UAVs

Technische Samenvatting: Dynamische Decentrale 3D Stedelijke Dekking en Patrouille met UAV's

Probleemformulering
Het artikel behandelt de uitdaging van het coördineren van een zwerm Unmanned Aerial Vehicles (UAV's) om een coöperatieve, periodieke dekking en patrouille uit te voeren in een 3D stedelijke omgeving na natuurlijke of door de mens veroorzaakte rampen (bijv. brand, overstromingen, aardbevingen). De omgeving wordt gemodelleerd als een verzameling gebouwen die worden gerepresenteerd door rechte prisma's, waarbij het doel is om alle verticale gevels en dakoppervlakken te dekken met specifieke beeldkwaliteitseisen voor objectdetectie.

Belangrijke beperkingen en aannames zijn onder meer:

• Beperkte middelen: Er zijn onvoldoende agenten om continue dekking te bieden; daarom moet het systeem periodieke dekking bieden.
• 3D-complexiteit: Agenten moeten om obstakels heen navigeren (de gebouwen zelf) en de cameraneiging (pitch) beheren om zowel gevels als daken te kunnen bekijken.
• Systeemvereisten: De oplossing moet decentraal zijn (geen centrale controller), schaalbaar, robuust tegen het falen van agenten, aanpasbaar aan dynamische veranderingen en in staat om te opereren met een beperkte communicatiebandbreedte en -bereik (periodieke connectiviteit).
• Doelstelling: Het minimaliseren van de maximale "onproductiviteit" ($i_v$), gedefinieerd als het tijdsinterval tussen opeenvolgende bezoeken aan een specifiek gezichtspunt op het oppervlak van een gebouw.

Methodologie
De auteurs stellen een modulair, decentraal framework voor dat het probleem opdeelt in vier afzonderlijke fasen: Viewpoint Generatie, Task Generatie, Task Allocatie en Patrol Strategie.

1. Viewpoint Generatie:
   De 3D-oppervlakken van gebouwen (gevels en daken) worden gediscretiseerd in een verzameling gezichtspunten ($V$). Elk gezichtspunt vertegenwoordigt een specifieke 3D-positie en oriëntatie waar een UAV een rechthoekig gebied van het oppervlak kan vastleggen dat overeenkomt met het gezichtsveld (FOV) van de camera op een specifieke afstand ($c_d$) om een optimale resolutie voor objectdetectie te garanderen.

2. Task Generatie:
   Gezichtspunten die bij een enkel gebouw horen, worden verbonden om een gesloten pad ($H_j$) te vormen. Deze padgeneratie wordt gemodelleerd als een 3D Traveling Salesman Problem (TSP). Om de NP-harde complexiteit van het vinden van een optimale oplossing te vermijden, gebruiken de auteurs het Christofides-algoritme, een heuristiek die een padlengte garandeert die binnen 1,5 keer de optimale waarde ligt. Het pad houdt rekening met het vermijden van obstakels (bijv. niet door het gebouw zelf vliegen) met behulp van 3D-zichtbaarheidsgrafieken. Elk gebouw vormt een "taak" met een gedefinieerde capaciteit ($c_j$) voor het aantal agenten dat het kan ondersteunen.

3. Task Allocatie:
   Agenten worden toegewezen aan taken (gebouwen) met behulp van de Consensus-Based Bundle Approach (CBBA) en de uitbreiding daarvan, de Consensus-Based Grouping Algorithm (CBGA). Deze op veilingen gebaseerde, decentrale methode stelt agenten in staat om te bieden op taken op basis van een scorefunctie. De score houdt rekening met de gekwadrateerde afstand tot het gebouw en een prioriteitsfactor ($p_j$), wat heterogene taakafhandeling mogelijk maakt (bijv. het prioriteren van gebouwen met een hoge belangrijkheid of het herverdelen van agenten voor dynamische trackingtaken). Dit zorgt voor schaalbaarheid en fouttolerantie zonder dat een volledig verbonden communicatiegrafiek vereist is.

4. Patrol Strategie:
   Zodra ze aan een gesloten pad zijn toegewezen, voeren agenten een minimale, decentrale patrol strategie uit.

• Beweging: Agenten betreden het pad bij hun dichtstbijzijnde gezichtspunt en bewegen in een willekeurige richting (met de klok mee of tegen de klok in).
• Interactie: Agenten wisselen lokale statusinformatie uit (positie, huidige gezichtspuntindex, laatst bediende gezichtspunt en richting) alleen wanneer ze binnen het communicatiebereik zijn.
• "Bouncing" Mechanisme: Wanneer agenten elkaar ontmoeten (ofwel bij hetzelfde gezichtspunt of wanneer ze elkaar passeren), passen ze specifieke regels toe om van richting te veranderen ("bouncen").
  • Als twee agenten in tegengestelde richtingen naar hetzelfde gezichtspunt bewegen, bedient de dichtstbijzijnde agent dit en keert om, terwijl de verder gelegen agent onmiddellijk omkeert.
  • Als ze in dezelfde richting bewegen, keert de verder gelegen agent om om inhalen te voorkomen.
  • Als agenten de laatst bediende gezichtspunten van elkaar passeren, keren beiden om.
• Emergente Gedrag: Deze lokale interactie leidt tot een emergente oscillatie waarbij agenten het pad dynamisch verdelen. Het systeem streeft niet naar een gelijke verdeling van het pad, maar zorgt ervoor dat alle gezichtspunten periodiek worden bezocht.

Belangrijkste Bijdragen

• Modulair Framework: Het artikel introduceert een gestructureerde aanpak die de scheiding tussen coverage path planning en de patrol strategie maakt, waardoor individuele componenten onafhankelijk geoptimaliseerd of gewijzigd kunnen worden.
• Minimale Patrol Strategie: In tegenstelling tot eerdere werken die vertrouwen op globale consensus of complexe coördinatie om een continu omtrekpad te verdelen, gebruikt deze aanpak eenvoudige lokale regels ("bouncing") om periodieke dekking op discrete 3D gesloten paden te bereiken.
• 3D-Discretisering: De methode behandelt expliciet het 3D-karakter van stedelijke omgevingen door gezichtspunten te genereren voor zowel gevels als daken, rekening houdend met cameraneiging en obstakelvermijding bij de padplanning.
• Efficiëntie van Middelen: De strategie minimaliseert de computationele en communicatieve overhead, wat het geschikt maakt voor platforms met beperkte middelen die opereren in omgevingen met sporadische connectiviteit.

Simulatie Resultaten
De auteurs hebben het framework gevalideerd met behulp van een Swarm Research Simulator in een scenario met 7 gebouwen en 401 gezichtspunten.

• Setup: 100 UAV's werden toegewezen aan de 7 gebouwen. Agenten bewogen met 2 m/s en pauzeerden gedurende 3 seconden bij elk gezichtspunt.
• Prestaties: Het systeem draaide in realtime (1 Hz voor allocatie/patrol logica, 10 Hz voor UAV-dynamica). Het Christofides-algoritme nam gemiddeld 3 ms per gebouw in beslag, en het patrol-algoritme nam minder dan 2 ms per agent in beslag.
• Dekking: Over 10 experimentele runs (elk 1800 seconden) slaagde de zwerm erin om volledige dekking van alle gezichtspunten te bereiken.
• Onproductiviteit: De maximale onproductiviteit voor gezichtspunten was begrensd en convergeerde over de tijd. De resultaten toonden aan dat de minimale strategie effectief de bovengrens van de onproductiviteit beperkt en periodieke dekking garandeert zonder globale coördinatie.

Betekenis en Claims
Het artikel claimt dat de voorgestelde aanpak succesvol de multi-agent 3D stedelijke dekking opgelost heeft door gebruik te maken van emergent gedrag afgeleid van eenvoudige lokale regels. De betekenis ligt in de afweging: het systeem offert de optimaliteit van een gelijke padverdeling (die globale consensus vereist) op om een hoge schaalbaarheid, robuustheid en aanpasbaarheid in dynamische, communicatiebeperkte stedelijke omgevingen te bereiken. De auteurs stellen dat deze minimale strategie bijzonder geschikt is voor scenario's met rampenbestrijding, waarbij communicatiesignalen beperkt of sporadisch kunnen zijn, en waarbij het systeem functioneel moet blijven zelfs als individuele agenten falen of verloren gaan. Toekomstig werk wordt geïdentificeerd als het verbeteren van de viewpoint generatie om heterogene camera's en complexe occlusies te behandelen, maar de huidige bijdrage richt zich op de haalbaarheid van het decentrale patrol mechanisme in een gestructureerde 3D stedelijke setting.