Modelarea Zborului Autonom In Formatie Folosind Algoritmi de Inspiratie Biologica

1. Introducere

Un vehicul aerian fără pilot, UAV, cunoscut și sub numele de dronă, este o aeronavă fără pilot uman la bord, al cărui zbor este controlat în mod autonom de computerele din vehicul sau este sub comanda unui pilot care se află la sol sau în altă aeronavă.

Un UAV este definit ca: vehicul aerian care nu transportă un operator uman, folosește forțe aerodinamice pentru ridicarea vehiculului, poate zbura în mod autonom sau poate fi pilotat de la distanță, poate fi consumabil sau recuperabil și poate transporta încărcătură letală sau non-letală.

Exista o gamă variată de astfel de vehicule, având forme, dimensiuni, configurații și caracteristici diferite. Inițial, UAV-urile erau aeronave simple pilotate de la distanță, dar controlul autonom este din ce in ce mai folosit. Acestea sunt utilizate predominant pentru aplicațiile militare, dar și in aplicațiile civile, momentan în număr mic, fiind într-o continuă creștere.

UAV-urile sunt adesea preferate in misiunile care sunt prea periculoase sau plictisitoare pentru aeronavele cu pilot. Datorita abilității de a îndeplini misiunile, aceste vehicule sunt promițătoare pentru îmbunătățirea securității societății.

1.1 Istoria UAV-urilor

Nikola Tesla a descris o flotă de luptă formată din vehicule aeriene fără pilot la bord în anul 1915. A urmat un progres al numărului avioanelor pilotate la distanță, incluzând și Avionul Automat Hewitt-Sperry, în timpul primului Război Mondial, dar și după acesta.

Au fost realizate mai multe în tehnologia rusă în timpul celui de-al doilea Război Mondial, fiind folosite pentru coordonarea tunurilor antiaeriene. În timpul războiului din 1973, Yom Kippur, rachetele aeriene din Egipt și Siria au provocat pagube importante avioanelor de luptă israeliene.

Astfel, Israel a dezvoltat primul UAV modern, fiind pionierul utilizării vehiculelor aeriene fără pilot, folosite pentru supravegherea în timp real. Imaginile unor ținte radar furnizate de aceste UAV-uri au ajutat Israelul pentru a neutraliza complet spațiul aerian sirian, la începutul Războiului Libanului,în 1982. Acestea se numesc drone Scout si sunt prezentate in figura de mai jos:

Figura 1 Drona Scout

Deși inteligența, supravegherea si recunoașterea rămân predominantele misiuni ale UAV-urilor, rolurile acestora s-au extins la atacul electronic, suprimarea și/sau distrugerea apărării aeriene inamice, lupte de salvare și căutare, dar și alte domenii.

Pe baza greutății brute, altitudinii operaționale deasupra nivelului solului și a rezistenței misiunii, UAV-urile pot fi clasificate în general în clase mari, mini, mici, micro și nano, ca în tabelul de mai jos:

Tabelul 1 Clasificarea UAV-urilor

UAV-urile, de obicei, se încadreaza într-una dintre cele șase categorii funcționale:

Țintă și capcană: furnizarea artileriei aeriană și de sol, o tință care simuleaza o aeronavă inamică sau o rachetă;

Lupta: capacitatea de atac în misiunile cu risc ridicat;

Logistica: UAV-urile sunt special concepute pentru operațiuni de încărcare și logistică;

Cercetare și dezvoltare: sunt folosite pentru a dezvolta în continuare tehnologiile UAV;

UAV-urile civile și comerciale: drone special concepute pentru aplicațiile civile și comercial;

1.2. Autonomia: un factor cheie

Un UAV complet autonom este capabil să zboare fără intervenția operatorului, de la decolare până la aterizare. Gradul de autonomie al UAV-urilor variază foarte mult de la zero până o la autonomie deplină.

Domeniul autonomiei dronelor este un domeniu recent, în curs de dezvoltare, beneficiind de o perspectivă mult mai largă, atât în aplicații militare, cât și civile. Tehnologia autonomiei este importantă pentru dezvoltarea UAV-urilor și se încadreaza în urmatoarele categorii:

Senzor de fuziune: combinând informații prelevate de la diferiți senzori pentru utilizarea acestora la bordul vehiculului;

Comunicații: manipularea comunicării și coordonării între mai mulți agenți, în prezența unor informații incomplete și imperfecte;

Planificarea traiectoriei: determinarea unei traiectorii optime pentru vehicul, astfel încât să îndeplinească obiectivele și constrângerile misiunii, cum ar fi obstacole sau necesarul de combustibil;

Generarea traiectoriei: determinarea unei manevre optime de control pentru a urmări un anumit traseu sau pentru a merge de la o locație la alta;

Reglementarea traiectoriei: strategiile de control specifice, necesare pentru a constrânge un vehicul în cadrul toleranței la o traiectorie;

Programarea și alocarea sarcinilor: determinarea unei distribuții optime a sarcinilor printre un grup de agenți, cu echipamente si constrângeri de timp;

Tactici de cooperare: formularea unei secvențe optime și distribuția spațială a activităților între agenți, cu scopul de a maximiza șansa de succes în orice scenariu al misiunii date;

O altă cale de a caracteriza autonomia este de a asocia funcționalitatea și gradul de dificultate situațional. Două variabile majore care faciliteaza această descompunere sunt complexitatea si incertitudinea.

Nivelurile autonomiei:

Nivelul 1: un operator uman ia toate deciziile. Sistemul nu are controlul autonom al mediului său;

Nivelul 2: vehiculul poate efectua mai multe funcții independente de controlul uman, atunci când este delegat să facă acest lucru;

Nivelul 3: sistemul poate efectua o gamă largă de activități atunci când se administrează permisiuni de nivel superior;

Nivelul 4: sistemul primește obiective de la oameni și le traduce în sarcinile care trebuie efectuate fără interacțiunea umană.

2. Calculul de inspiratie biologica

Roitul nu este despre numere, ci despre interacțiunile dintre indivizii unui grup. Roirea este privită in două moduri: interacțiunea dintre indivizii unui grup și tacticile de roit, care pot fi folosite de grupuri militare. Al doilea mod descrie acest proces: dispersate inițial, grupurile se reunesc pentru a duce la atingerea scopului, apoi se răspândesc din nou, asemanător unei tactici de război.

Termenul roi este adesea folosit pentru adunări de animale, cum sunt bancurile de pești, stolurile de păsări, colonii de furnici, termite, dar și colonii de albine care au un comportament colectiv, ceea ce conduce la o robustețe mai mare.

2.1. Cerințe tehnologice pentru comportamenul de roi

Setul minimal de tehnologii necesare pentru a activa și a reuni roiurile, este alcătuit din:

Comportamentul emergent al indivizilor care interacționează in roi;

Comportament simplu reactiv al indivizilor;

Arhitectura comportamentală a indivizilor permite comutarea cu comportamente reactive;

Detecția locală cu variabilitate individuală reactivă.

Comportament emergent

Cea mai bună metodă de a descrie comportamentul emergent este acela de a începe cu câteva exemple. Stolurile de păsări, bancurile de pești sunt exemple ale comportamentului emergent. De exemplu, bancul de pești poate fi descris ca o interacțiune între indivizi, fiecare dintre aceștia având următoarele reguli:

Directia de deplasare trebuie sa fie îndreptat către centrul masei;

Vectori aliniați;

Vecinii nu trebuie loviți.

Un alt exemplu este zborul in formație:

Trebuie să urmeze liderul;

Păstrarea altitudinii;

Vecinii nu trebuie loviți.

Comportamentele emergente au caracteristici foarte interesante pentru autonomia UAV-urilor, acestea fiind în mod inerent descentralizate, implicite, rezistente și scalabile.

Fiind descentralizate duc la eliminarea oricărei comenzi centralizate, o caracteristică care este dorită în dezvoltarea sistemului de control al UAV-urilor.

Faptul că sunt implicite elimină orice cerință de a controla în mod explicit indivizii. Rezistența este evidențiată de toleranța la imperfecțiunea și variația dintre indivizi.

Sistemele emergente sunt foarte robuste la adăugarea și scăderea membrilor, acestea putând funcționa bine în condiții de risc ridicat, ceea ce ne conduce la scalabilitate.

Rezultatele probabilistice, comportamentele haotice, modelul problematic sunt doar câteva dintre dezavantajele comportamentelor emergente.

Comportamente individuale reactive

Majoritatea sistemelor naturale sunt reactive, doar anumite mamifere au capacitatea de a planifica, de a ajuta la supraviețuirea lor. Cele mai multe sisteme de control făcute de om reacționează la intrări sau perturbatiii externe pentru a menține o variabilă de ieșire.

Chiar și cu capacitatea noastră de a planifica, majoritatea acțiunilor umane sunt determinate de comportamente reactive.

Arhitecturi comportamentale

Comportamentele micro-reactive nu sunt singurul lucru necesar. Avem nevoie și de o modalitate de a organiza aceste comportamente micro ale indivizilor astfel încât să poată comuta automat comportamentele bazate pe intrările senzoriale.

Așa cum insectele pot trece de la căutarea hranei la construirea cuibului, UAV-urile trebuie să treacă la un comportament versatil.

Detecția locală cu variabilitate individuală reactivă

Comportamentele emergente rezultate în urma interacțiunii indivizilor funcționează ca fiind comportamente reactive in sistemul lor de control. Dar, pentru a trece la astfel de comportamente este necesar un declanșator, care este reprezentat de intrarea senzorială a fiecărui individ.

O trăsătură comună a animalelor multicelulare și a tuturor animalelor de ordin mai înalt, este abilitatea de a simți mediul în mai multe feluri. Toți senzorii ne informează cu privire la ceea ce se intâmplă în exterior, în scopul de a schimba comportamentul, adică de a urma un nou set de reguli.

Nu sunt necesare cunoștiințe la nivel global pentru a realiza această sarcină, ci doar informații acumulate din interacțiunea cu mediul local. Comportamentul emergent solicită doar informații la nivel local, deci nu au nevoie de o rază lungă de comunicare și nici măcar de o confirmare că mesajul a fost primit.

De fapt, multe dintre comportamentele emergente sunt realizate prin stigmergie, informații obținute prin interacțiunea cu mediul sau sarcina. Un exemplu, îl reprezintă o colonie de furnici și cum procedează cu feromonii. O furnica se indica, lăsând în urma ei o depunere de feromoni, atenționând-ule pe celelalte că a fost acolo. Acest lucru este folosit în rularea logisticii pentru o colonie de furnici.

Robustețea comportamentului emergent rezultă din variația performanței senzorului intre indivizi. Senzorii nu sunt perfecți, iar societatea, în general, folosește acest lucru pentru a ajuta supraviețuirea. Aceste comportamente duc la dezvoltarea sistemelor autonome de control ale UAV-urilor, folosind metode de inspirație biologică.

Pentru a folosi roirea este necesară examinarea sistemelor naturale care folosesc un comportament emergent și care conduc la analiza atribuțiilor acestora.

2.2. Caracteristicile unui roi și diferența dintre acesta și o echipă

Echipele sunt formate din membri care au propriile roluri, știu ce sunt, cunosc atribuțiile celorlalți membri. O echipa este inversul unui roi.

În tabelul de mai jos, putem observa comparația particularităților roiurilor și echipelor găsite în natura:

Tabelul 2. Comparatia caracteristicilor dintre roiuri si echipe

Temporal: Roiurile sunt formate din indivizi care pot reacționa, dar nu pot anticipa, în timp ce echipele dețin capacitatea de a anticipa, care necesita modele si planuri de bord.

Compoziția: Roiurile sunt compuse din tipuri individuale sau roluri, omogene sau eterogene limitate, iar echipele sunt foarte eterogene cu roluri distincte atribuite indivizilor.

Interrelația: Roiurile interacționează cu alți indivizi folosind reguli simple, în timp ce echipele prezintă un comportament social complicat. În plus, mesajele nu sunt direcționate către un anumit individ, ci sunt difuzate. Echipele comunică prin mesaje ce au un nivel semantic superior, de obicei adresate unui anumit individ.

Predictibilitatea: Roiurile sunt probabilistice, performanțele pot fi descrise prin distribuții, dar nu sunt deterministe. Pe de altă parte, echipele sunt deterministe cu un obiectiv cunoscut într-un anumit moment, realizat prin intermediul unui plan determinist.

Individualitatea : Roiurile își obțin robustețea datorită similitudinii indivizilor. Acest lucru asigură faptul că, în cazul în care una dintre interacțiuni eșuează sau dacă una dintre insecte se abate de la misiune, eșecul acesteia este compensat de altă insectă. Așadar, valoarea individuală este scazută. Echipele sunt formate din indivizi specializați. Pierderea unui individ poate paraliza funcțiile echipei, ceea ce ne conduce la faptul că valoarea individuală este ridicată.

Eficiența: Roiurile in natură sunt ineficiente în comparație cu modalitățile în care oamenii decid să facă aceleași lucruri. Unul dintre beneficiile teaming-ului este acela că maximizează eficiența prin utilizarea sinergetică a resurselor eterogene.

Ar trebui să ținem cont că ineficiența roiurilor nu este neapărat un dezavantaj pentru indivizi, deoarece ceea ce le lipsește la eficiență se completează cu un surplus la robustețe.

Redundanța lor poate supraviețui uzurii, în cazul în care pierderea unui singur membru al echipei ar conduce la un eșec. Ineficiența lasă loc pentru imbunătățiri în vremuri de nevoie, dar necesită mai multe resurse.

Indivizii interacționează între ei , dar nu au o imagine în ansamblu a întregii colonii. Cu toate acestea, încercările și erorile au dezvoltat comportamente simple, astfel încât să interacționeze pentru binele întregului colectiv.

2.3. Caracteristici generale ale calcului bio-inspirat

Inteligența roiurilor, ca o disciplină științifică, include domenii de cercetare cum ar fi optimizarea roiurilor sau controlul distribuit al colectivelor robotice. A luat naștere în urma descoperirilor biologice despre abilitățile incredibile ale insectelor sociale pentru a rezolva probleme complicate.

Este o formă de inteligență artificială bazată pe comportamentul colectiv al sistemelor distribuite, auto-organizate. Această expresie a fost introdusă pentru prima dată de către Gerardo Beni și Jing Wang în 1989 în contextul sistemelor celulare de roboți. O altă definiție, dată de către Bonabeau, Dorigo, Theraulaz este: “orice încercare de a proiecta algoritmi sau echipamente distribuite inspirate din comportamentul colectiv al coloniilor de insecte sociale sau alte societăți de animale”.

Sistemele bazate pe SI sunt formate din agenți ce interacționează local unii cu alții și cu mediul înconjurător. Agenții urmează reguli foarte simple și chiar dacă nu există o structură de control care să dicteze comportamentul fiecărui agent, interacțiunile locale conduc la emergența comportamentului global, complex.

Coloniile lor variază în mărimi, pornind de la câteva animale și ajungând la câteva milioane de indivizi, care prezintă comportamente fascinante, unde eficiența este combinată cu robustețea și flexibilitatea.

Exemple de astfel de comportamente complexe sunt numeroase și diverse printre insectele sociale, cum ar fi găsirea celui mai scurt drum în procesul de căutare a hranei, repartizarea sarcinilor între indivizi, construirea cuibului.

Pe de altă parte, un individ execută mereu acțiuni simple și urmează reguli simple. Complexitatea unei singure insecte, în ceea ce privește abilitățile cognitive și de comunicare, poate fi ridicată, dar insuficientă în supravegherea unui sistem mai complex. Este adesea întâlnit faptul că o singură insectă nu poate găsi o soluție eficientă la o problemă complexa, în timp ce întreaga colonie este capabilă să găsească o rezolvare foarte ușor.

S-a ajuns la concluzia că insectele individuale nu au nevoie de nici o reprezentare, hartă sau cunoștiințe explicite ale structurii globale, pe care le produc. O singură insectă nu poate evalua o situație globală, nu poate centraliza informații despre starea întregii colonii și apoi să controleze sarcinile efectuate de alți lucrători, ceea ce inseamnă că în colonie nu exista niciun supraveghetor.

De fapt, o colonie de insecte sociale este mai degrabă ca un sistem descentralizat format din indivizi autonomi și care urmează reguli stimul-răspuns simple. Regulile care guvernează interacțiunile dintre insecte, se execută numai în conformitate cu informațiile locale. Aceste interacțiuni asigură propagarea informației prin colonie și organizează activitatea fiecărui individ.

Datorită acestor rețele de interacțiune sofisticate, insectele sociale pot rezolva mai multe tipuri de probleme și pot răspunde provocărilor externe într-un mod foarte flexibil și robust. În spatele acestei organizații stau ascunse mai multe mecanisme, care permit membrilor să facă față situațiilor incerte și să găsească soluții pentru probleme complexe. Cercetătorii numesc acest lucru auto-organizare.

Auto-organizarea este un ansamblu de mecanisme dinamice unde apar structuri la nivelul global al unui sistem de interacțiuni între componentele sale de nivel inferior, fără a fi codificate în mod explicit la nivel individual. Se bazează pe patru elemente de bază:

Feedback-ul pozitiv (amplificarea): Aceasta reprezintă adesea baza morfogenezei la insectele sociale, rezultând executarea unui comportamen simplu, care promovează crearea unor structuri. Exemple de feedback pozitiv cuprinde recrutarea și consolidarea. Un bun exemplu este considerat drumul către o sursă de hrană, care creează condițiile pentru apariția unui traseu de rețea la nivel global.

Feedback-ul negativ (pentru contrabalansare și stabilizare): Se contrabalansează feedback-ul pozitiv și ajută la stabilizarea modelul colectiv. La cautarea hranei de către furnici, se pot prezenta unele forme de feedback negativ.

Amplificarea fluctuațiilor (dezordine,erori): apar comportamente colective, deși insectele sociale sunt cunoscute pentru efectuarea acțiunilor stocastice.

Interacțiuni multiple: auto-organizarea necesită adesea densitate minimă a toleranței comune a indivizilor. În plus, indivizii ar trebui să poată face uz de rezultatele propriilor activități, precum și de activitățile altora.

Auto-organizarea este, de asemenea, caracterizată prin câteva proprietăți cheie:

Dinamică: Așa cum s-a menționat mai sus, producția de structuri, precum și persistența acestora necesită interacțiuni permanente între membrii coloniei și mediul lor. Aceste interacțiuni promovează feedback-ul pozitiv care creează structurile colective și acționează pentru subzistență împotriva feedback-ului negativ care tinde să le elimine.

Proprietăți emergente: prezintă proprietăți care sunt mai complexe decât simpla contribuție a fiecărui agent. Acestea rezultă din combinația neliniară a interacțiunilor dintre membrii coloniei.

Bifurcații: o bifurcație este apariția unor noi soluții stabile atunci când unii parametri ai sistemului se schimba. Acest lucru corespunde unei modificări calitative ale comportamentului colectiv.

Multi-stabil: Multi-stabilitatea înseamnă că, pentru un anumit set de parametri, sistemul poate ajunge la diferite stări stabile în funcție de condițiile inițiale și de fluctuațiile aleatorii.

Organizarea comportamentelor colective a insectelor sociale poate fi înțeleasă ca o combinație de patru funcții: coordonare, cooperare, deliberare și colaborare. Acestea susțin procesarea informațiilor coloniei în două moduri:

Coordonarea și forma de colaborare cu structurile spațiale, temporale și sociale care rezultă în urma activitații coloniei. Funcția de coordonare reglează densitatea spațio-temporală dintre indivizi, în timp ce funcția de colaborare reglează alocarea activităților lor.

Cooperarea și deliberarea furnizează instrumente pentru colonie, ca aceasta să poată face față provocărilor mediului. Funcția deliberare reprezintă mecanismele care susțin deciziile coloniei, în timp ce funcția de cooperare este alcătuită din mecanismele care depășesc limitele indivizilor.

Împreună, aceste patru funcții contribuie la realizarea diferitelor misiuni colective ale coloniei.

2.3.1. Algoritmi de inspirație biologică

Prin simularea comportamentului colectiv al sistemului descentralizat, s-au dezvoltat mai multe proceduri de optimizare, care pot fi numite algoritmi de inspirație biologică.

Tehnicile de optimizare inspirate din comportamentul colectiv au devenit din ce în ce mai populare, in ultimul deceniu. Acestea sunt caracterizate printr-un mod de lucru descentralizat care imită comportamentul de roi al insectelor sociale, stoluri de pasări, bancuri de pești.

Avantajele acestora comparativ cu tehnicile tradiționale, sunt robustețea si flexibilitatea. Aceste proprietați fac din „inteligența roiurilor” un model de proiectare de succes pentru algoritmii care se confruntă cu cele mai complexe probleme.

Principalele tehnici de optimizare sunt:

Optimizarea coloniei de furnici;

Optimizarea ansamblului de particule;

Colonia artificiala a albinelor;

Evolutia diferențiala.

2.3.1.1. Optimizarea coloniei de furnici

La diferite specii de furnici, există mereu indivizi care pot lasa un feromon pe sol in timpul parcurgerii unui traseu. Feromonii sunt substanțe chimice care atrag alte furnici. Depunând acest feromon, furnicile creează un traseu pentru a marca drumul de la mușuroi la hrană.

Mai multe specii de furnici sunt capabile de a exploata traseele cu feromoni, pentru a determina cel mai scurt drum către sursa de hrană.

Figura 2 Mușuroi de furnici

Deneubourg și colegii săi au folosit un pod cu două ramificații între un mușuroi de furnici și o sursă de hrană, pentru a studia comportamentul furnicilor. Aceștia au facut mai multe experimente, dar cel mai interesant este acela în care o ramificație este mai mare decat cealaltă.

La început, furnicile au fost lasate să se miste între mușuroi și sursă de hrană , iar numărul de furnici care au ales oricare dintre cele două ramuri s-a observat în timp. În final, s-a putut observa că cele mai multe furnici au ales ramificația cea mai scurtă.

Rezultatul poate fi explicat după cum urmează. Când un proces începe, nu există feromoni pe niciuna dintre cele două ramuri. Prin urmare, furnicile nu au nici o preferință și aleg una dintre cele două. Deoarece una dintre ramificații este mai scurtă și alta mai lungă, furnicile care o aleg pe cea scurtă sunt primele care ajung la hrană și se intorc la mușuroi.

Dar când trebuie să aleagă între ramificații, nivelul de feromoni de pe ramura scurtă influențează decizia furnicilor. Așadar, va fi utilizată de majoritatea furnicilor, datorită gradului ridicat de feromoni.

Figura 3 traseul furnicilor către hrană

2.3.1.2. Optimizarea ansamblului de particule

Primul program referitor la ansamblul de particule a fost determinat prin modificarea simulării unui stol de păsări. În anii 1980, două grupuri distincte de cercetători au implementat modele similare ale dinamicii unui stol de păsări.

Reynolds (1987) a vrut să prezinte pe calculator, animații ale unui stol de păsări, concluzionând că stolul ar putea fi simulat folosind trei reguli:

Separarea – Dacă o entitate este prea aproape de alta, atunci se departează de aceasta;

Alinierea – Deplasarea unei entități în rând cu vecinii, dacă se află la o distanță optimă de aceștia;

Coeziunea – Deplasarea către vecini atunci când este prea departe de aceștia.

Figura 4. Regulile de deplasare a păsărilor

Heppner, un biolog, a făcut filme tridimensionale ale stolurilor de păsări și a studiat cu atenție dinamica mișcărilor acestora.

Modelul, deși a fost dezvoltat independent de cel al lui Reynolds, conținea cele trei reguli esențiale, dar și atracția pentru așezarea pe crengile copacilor. În cele din urmă, stolurile s-au așezat.

Figura 5. Stol de păsări

Autorul a experimentat cu aceste modele de stoluri și a adăugat înca o caracteristică, cu rezultate surprinzătoare. A fost adăugat „vectorul lan de porumb”, care în primul program a fost doar un punct bidimensional.

Punctul a fost considerat pentru simularea hranei, iar păsările vedeau hrana și cel mai important, cele care zburau puteau observa alte păsări cum roiau în jurul țintei. Așadar, membrii stolului erau atrași de pozițiile altor indivizi care se aflau în apropierea hranei.

Primele experimente au fost șocante. Stolul s-a îndreptat, imediat, spre același punct ca și când erau aspirate. Acel prim algoritm a operat astfel:

Fiecare pasăre evaluează distanța până la lanul de porumb;

Fiecare pasăre identifică anumiți vecini, care erau în apropiere;

Fiecare pasăre a identificat care dintre vecini erau mai aproape de țintă și când s-a întamplat aceasta;

Dacă poziția sa era în dreapta celui mai bun punct precedent, se deplasa o anumită mulțime la stânga sau se muta la dreapta;

Dacă poziția era în dreapta celui mai bun punct al unui vecin, muta mulțimea la stânga, în caz contrar la dreapta.

Figura 6. Stol de păsări

Algoritmul dezvoltat de Kennedy si Eberhart conține un concept foarte simplu și modele care pot fi implementate în câteva linii de cod. Sunt necesari operatori matematici primitivi și este convenabil, din punct de vedere computațional, în materie de memorie și viteză.

2.3.1.3. Colonia artificială a albinelor

Un comportament de roi interesant, în natură, este acela al roiurilor de albine care alocă sarcini în mod dinamic și se adaptează la schimbările mediului într-un mod inteligent.

Albinele au amintiri fotografice, sisteme de navigare și aptitudini de luare a deciziilor de grup în procesul de selectare a așezării cuibului. Pot îndeplini sarcini ca matcă și supravegherea puietului, de a stoca, extrage și distribui miere și polen, de a comunica și a căuta hrană. Aceste caracteristici sunt stimulente în modelarea comportamentelor inteligente ale albinelor.

Căutarea hranei este cea mai importantă sarcină în stup. Multe studii s-au concentrat pe acest comportament și ce tipuri de informații l-ar afecta.

Procesul începe cu plecarea unei albine în căutarea unei surse pentru a aduna nectar. După ce a găsit o floare, aceasta extrage nectarul și îl depozitează în stomac.

În funcție de numărul florilor și de distanța dintre acestea și stup, stomacul unei albine ajunge la saturație în 30-120 min, iar mierea este produsă în urma secreției unei enzime din stomacul acesteia, care acționează asupra nectarului colectat.

Ajunsă la stup, albina descărcă nectarul în celulele goale ale fagurelui și sunt adăugate substanțe în plus pentru a evita fermentarea și atacurile bacteriene. Celulele pline cu miere și enzime sunt acoperite cu ceară.

Figura 7. Traseul albinelor spre hrană

După ce a lăsat nectarul, albina efectuează anumite mișcări specifice în zona fagurelui pentru a distribui informația legată de sursa de hrană.

În timpul dansului, celelalte albine o ating cu antenele pentru a învăța mirosul și gustul sursei de hrană. Aceasta se mișcă în diferite zone ale fagurelui pentru a recruta mai mulți indivizi.

Sunt diferite tipuri de dans, în funcție de distanța de la stup la hrană: dans în cerc, bâțâit, tremur. Dacă distanța de la hrană până la stup este mai mică de 100 m, acestea se mișcă în cerc, iar dacă distanță este mai mare, albinele se bâțăie.

Figura 7. Dansul albinelor

O colonie de albine este nevoită să își împartă forța de muncă la câți indivizi sunt, fiind specializate în efectuarea sarcinilor în stup. Cu toate acestea, există un semn de întrebare în legătură cu factorii ce influențează specializarea albinelor, cum ar fi vârsta lor, hormonii.

Algoritmul virtual al albinelor a fost dezvoltat de Yang în anul 2005, pentru a rezolva funcțiile numerice ale optimizării. În acest model, un roi virtual de albine este generat, având o mișcare aleatorie.

Acestea interacționează între ele în momentul găsirii nectarului. Sursele de nectar corespund valorilor active ale funcției. Soluția problemei optimizării poate fi obținută datorită interacțiunilor între indivizi.

Algoritmul albinelor a fost descris de Pham, în anul 2006, și simula comportamentul albinelor în procesul de căutare a hranei. În versiunea de bază, algoritmul realizează un fel de căutare, care poate fi folosită în optimizarea combinatorie și funcțională.

Algoritmul stupului, care a avut la bază comunicarea dintre albine în interiorul acestuia, a fost propus de Wedde în anul 2004 și aplicat pe traseul rețelelor. Astfel, albinele traversează regiuni ale rețelei numite zone de căutare a hranei. Pe parcursul acestui traseu, informații legate de starea rețelei sunt oferite pentru a actualiza tabele locale de informații.

Figura 8. Algoritmul stupului

Optimizarea coloniei de albine a fost descrisa de Teodorovic și Dell'Orco in anul 2005, acesta fiind cel mai studiat si aplicat algoritm in rezolvarea problemelor din lumea reala.

2.3.1.4. Evoluția diferențială

Fiecare specie a trebuit să permită adaptarea structurii lor fizice pentru a se potrivi mediilor în care trăiesc și pentru a-și mări durata de viață. Prin simularea relației de bază dintre optimizare și evoluție biologică, o ramură importantă a inteligenței artificiale, au fost dezvoltate tehnici de calcul evolutive, pentru a rezolva problemele complexe de optimizare. Calculul evolutiv are la bază progresul iterativ, cum ar fi creșterea sau dezvoltarea într-o populație.

Această populație este selectată pentru o căutare aleatorie ghidată folosind prelucrarea paralelă pentru a obține rezultatul dorit. Modelul de calcul al tehnicilor evolutive datează din anii 1950, când au fost utilizate principiile Darwiniene pentru rezolvarea problemelor de origine automată.

Tehnicile de calcul evolutive implică algoritmi de optimizare metaeuristici. În general, programul include programarea evolutivă, strategiile de evoluție, algoritmul genetic și programarea genetică.

Algoritmul evoluției diferențiale a apărut ca o formă de calcul evolutivă în urmă cu un deceniu. Primul articol despre acest algoritm a apărut ca un raport tehnic, scris de Storn și Price în anul 1995. Un an mai târziu, succesul acestuia a fost demonstrat la Primul Concurs Internațional privind Optimizarea Evolutivă în luna mai 1996.

2.4. Inteligența bio-inspirată

2.4.1. Obținerea unei capacități autonome ridicate

În timp ce progresele tehnologice recente au permis dezvoltarea sistemelor de vehicule fără pilot și implementările recente au demonstrat beneficiile UAV-urilor, atât în aplicațiile militare cât și civile, avantajul deplin al acestor sisteme va fi utilizat atunci când acestea pot funcționa autonom.

Astăzi, UAV-urile nu sunt folosite doar în comunicații, meteorologie, agricultură, geologie, transport, dar de asemenea au o utilizare pe scară largă în monitorizarea și supravegherea intelingentă, interferența artificială, comunicații militare, suprimarea apărării aeriene.

Ultimul scop în dezvoltarea tehnologiei autonomiei UAV-urilor este de a înlocui pilotul uman, ceea ce conduce la construirea unui sistem complet autonom. Caracteristica specială a unui sistem autonom este de a fi un scop în situații imprevizibile.

Această capacitate este o îmbunătățire importantă în capabilitate comparativ cu capacitățile sistemelor automate. Un sistem autonom este capabil să ia o decizii pe bază unui set de reguli și/sau limitări. Acesta este capabil să determine ce informații sunt importante în luarea unei decizii.

Capabilitățile autonome au fost activate de progresele făcute în domeniul informaticii (analog și digital), inteligență artificială, științe cognitive și comportamentale, dar și tehnologii de comunicare.

Pentru a atinge aceste capabilități autonome în mediul sistemului fără pilot, îmbunătățirea este esențială la algoritmii avansați care oferă capacități de luare a deciziilor robuste, integrarea automată a informațiilor extrem de disparate, iar construcția computațională să se ocupe de seturi de date cu imprecizie, contradicție și incertitudine.

Dinamica, auto-organizarea, coordonarea, robustețea puternică, dar și alte caracteristici apărute în procesul inteligenței bio-inspirate pot îndeplini cerințele UAV-urilor în medii de luptă complicate. Inteligența bio-inspirată poate oferi un mod promițător de a face față situației complicate pentru UAV-uri, sporind astfel capacitatea autonomă a acestora.

2.4.2. Îmbunătățirea flexibilității și a robusteței

Proprietățile cele mai importante ale modelelor auto-organizate sunt robustețea, capacitatea unui sistem de a funcționa fără eșec în cadrul unui larg domeniu de condiții, și flexibilitatea, capacitatea unui sistem de a se adapta rapid la nou, diferit, sau schimbarea cerințelor.

Robustețea rezultă din multitudinea de interacțiuni dintre indivizii care aparțin coloniei. Acest lucru asigură faptul că, în cazul în care una dintre interacțiuni eșuează sau dacă una dintre insecte ratează misiunea, eșecul lor este compensat rapid de alte insecte. Aceasta promovează, de asemenea, stabilitatea modelelor produse, întrucât comportamentele individuale sunt în mare parte probabilistice.

Flexibilitatea sistemelor auto-organizate este bine ilustrată prin capacitatea insectelor sociale de a adapta comportamentele colective la medii schimbătoare și colonii de diferite dimensiuni. Aceste adaptări pot avea loc fără nici o modificare a regulilor comportamentale la nivel de individ.

Prezența eterogenizarii mediului poate modula comportamentul unei insecte și conduce comportamentul coloniei către o anumită soluție.

Toate aceste modulații comportamentale oferă posibiliatea unei colonii de a dezvolta o gamă largă de comportamente colective. Datorită sensibilității indivizilor la variație, fie declanșată de mediu sau de colonie, aceasta este capabilă să perceapă aceste schimbări și reacționează corespunzător în aproape orice situație.

Pentru a opera în medii complexe și incerte, UAV-urile trebuie să simtă și să înțeleagă mediul. Această capacitate implică faptul că UAV-urile trebuie să creeze un model al mediului care îl înconjoară, prin tehnologia de fuziune a datelor multisenzoriale și transformarea acestora în informații semnificative care susțin un proces de luare a deciziilor.

În timp ce robustețea este necesară la schimbările mediului, în viitor trebuie să existe capacitatea de a se adapta și de a învăța de la mediul operațional. Această adaptare trebuie să se întâmple suficient de rapid pentru a oferi beneficii pe baza deciziei buclă a adversarului, iar autonomia trebuie să fie implementată în așa fel încât aceste lecții pot fi împărțite cu alte sisteme autonome, care nu s-au confruntat cu această situație.

Cu toate acestea, chiar și într-un mediu ostil, dinamic, nestructurat și incert, acest proces nu trebuie să afecteze negativ siguranța, fiabilitatea sau capacitatea de a colabora cu alți operatori sau alte sisteme autonome.

2.4.3. Controlul cooperativ al UAV-urilor

În ultimii ani, o schimbare importantă a avut loc în domeniul autonomiei UAV-urilor, deoarece cercetătorii au început să studieze problemele care implică mai multe UAV-uri și nu unul singur.

Sistemele militare moderne sunt din ce în ce mai sofisticate, fiind formate dintr-un amestec de vehicule cu și fără pilot, care sunt folosite în medii de luptă complexe. Soluțiile tradiționale implică o atribuire a resurselor centralizate, urmate de o execuție descentralizată.

Este ușor de înțeles că un grup de UAV-uri este mult mai eficient, decât unul sigur, deoarece volumul de muncă este împărțit între membrii grupului. Acestea pot fi echipate pentru diferite funcții ale misiunii, chiar dacă este vorba despre supraveghere și recunoaștere sau evaluarea pagubelor luptei.

Misiunile de supraveghere pot fi finalizate rapid prin acoperirea unei suprafețe mai mari a zonei de căutare, atunci când grupul este răspândit. De asemenea oferă redundanță pentru a asigura că misiunea este finalizată. Dacă unul dintre UAV-uri este distrus de inamic sau cade din cauza unor probleme de natură mecanică, restul grupului poate termina misiunea. Având mai multe UAV-uri atribuite unei misiuni, cu siguranță probabilitatea de succes crește.

Una dintre cele mai simple probleme de control este cea a zborului în formație: mai multe vehicule vor zbura într-o formație, ansamblu ce va fi stabilit cu ajutorul locațiilor relative ale vehiculului din apropiere.

O modalitatea de a aborda problema controlului formației de zbor este formularea acesteia ca o optimizare. Un aspect important care apare în controlul formației este cel al stabilității, în care perturbațiile cresc datorită dispersării lor printr-un sistem de vehicule.

Ca urmare a acestui accent pus pe sistemul format din mai multe UAV-uri, coordonarea acestora a primit o atenție semnificativă. În scopul de a atinge obiectivul dorit, trebuie să se decidă care UAV ar trebui să aibă sarcină de căutare, clasificare, atac și altele. Acest lucru este necesar chiar și pentru grupurile mici de UAV-uri, dar și importanța de alocare a resurselor crește o dată cu mărimea, complexitatea și capacitatea echipei.

Există două tipuri de probleme pentru alocarea resurselor: statice și dinamice. Alocarea resurselor în mod static înseamnă că atribuirea se face la un moment dat, astfel încât UAV-urile sunt angajate, în timp ce în cazul dinamic, resursele pot fi realocate în momentul în care variația câmpului de luptă este luată în considerare.

Una dintre aplicațiile care motivează folosirea mai multor UAV-uri și prezintă multe proocari pentru inginerii de sistem, atât din punct de vedere teoretic și practic. Misiunea este inițiată de un individ instruit foarte puțin care desenează un traseu pe o hartă digitală, generând o urmă pe pamanat continuă și precisă, ca senzorii aerieni să o urmărească. Apoi acest traseu de la sol este transmis prin rețea flotei de vehicule aeriene fără pilot, fiind echipată cu senzori vizuali complementari.

Un algoritm de optimizare generează autonom traiectorii de zbor fezabile care maximizează o acoperire cât mai bună a traseelor și avantaje ale capacității senzorilor, ale câmpului vizual, a rezoluției. Flota de vehicule aeriene fără pilot începe drumul de căutare. În timpul acestei faze, informația obținută de la senzorii montați pe bordul UAV-ului este împărtășită prin rețea și preluată de utilizatorii aflați la distanță. Detectarea dispozitivului exploziv poate fi făcută de la distanță pe teren, pe baza imaginilor și a datelor furnizate în rețea.

Așa cum s-a explicat, punctele forte ale comportamentului de roi sunt în executarea sarcinilor reactive, a sarcinilor simple, folosind mai mulți agenți și robustețea de uzură. În plus stabilitatea comportamentului emergent se bazează pe imperfecțiunea senzorilor. După cum arată istoria, sistemele simple autonome au folosit cu succes comportamentele emergente. Comportamentele emergente au caracteristici foarte interesante pentru includerea în autonomia UAV-urilor:

Inerent descentralizate: Se elimină necesitatea pentru orice comandă centralizată, o caracteristică dorită pentru dezvoltarea sistemului de control distribuit al UAV-urilor;

Inerent implicite: Se elimină orice necesitate de a controla în mod explicit indivizii;

Rezistente în mod inerent: Este permisă imperfecțiunea și diversitatea între indivizi;

Inerent scalabil: Sistemele emergente sunt foarte robuste la adăugarea și scăderea numărului de membri, astfel încat sistemele să poată funcționa bine în situații de risc.

Comportamentul emergent are și dezavantaje, cum ar fi:

Rezultatele sunt probabilistice;

Executarea este nedeterministă;

Comportamentele haotice sunt posibile;

Proiectarea este problematică.

3. Evoluția diferențială

3.1. Inspirația biologică

Cercetătorii au căutat în natură inspirație, astfel încât să poată aborda problemele de calcul complexe. Optimizarea este prezentă în procesele naturale. De exemplu, fiecare specie a trebuit să își adapteze structura fizică în funcție de mediu, abilitățile de supraviețuire fiind întărite.Relația de bază dintre optimizare și evoluția biologică a condus la dezvoltarea unei paradigme importante în inteligența computațională.

Calculul evolutiv folosește progresul iterativ, cum ar fi creșterea sau dezvoltarea unei populații. Această populație este selectată cu ajutorul unei căutări aleatorii. Modelul evolutiv al tehnicilor de calcul datează din anii 1950, datorită folosirii principiilor Darwiniene.

Programarea evolutivă (PE) a fost introdusă de Lawrence J. Fogel în Statele Unite ale Americii. În același timp, în Germania, I. Rechenberg și H.P. Schwefel descopereau strategiile de evoluție (ESs). După aproape un deceniu, John Henry Holland de la Universitatea din Michigan, a conceput o metodă independentă de simulare a evoluției Darwiniene, pentru a rezolvă probleme de optimizare. Acesta a numit-o algoritm genetic (GA).

De la începutul anilor 1990, aceste metode sunt numite reprezentați ai unei tehnologii, numită calcul evolutiv. De asemenea, tot de la începutul anilor 1990, a fost lansată programarea genetică (GP).

Algoritmul evoluției diferențiale (DE) a apărut ca o formă competitivă a calculului evolutiv, în urmă cu un deceniu. Primul articol despre evoluția diferențială a apărut ca un raport tehnic, scris de Storn și Price, în anul 1995.

Un an mai târziu, succesul acestui algoritm a fost demonstrat la Concursul Internațional al Optimizării, care a avut loc în colaborare cu Conferința Internațională IEE despre Calculul Evolutiv. Acest algoritm s-a clasat pe locul trei în cadrul Concursului Internațional despre Optimizarea Evolutivă, care s-a ținut în Nagoya, Japonia.

Evoluția diferențială a fost văzută ca un instrument de optimizare atractiv pentru următoarele motive:

Este mult mai simplă și mai ușor de implementat;

Deși studiile recente au arătat simplitatea acestui algoritm, evoluția diferențială prezintă performanțe mult mai bune în comparație cu alți algoritmi în rezolvarea diferitelor probleme;

Numărul parametrilor de control este mai mic.

3.2. Principiul evoluției diferențiale

3.2.1. Inițializarea vectorilor parametru

Evoluția diferențială are la bază trei operații evolutive: mutația, recombinarea și selecția. Pozițiile indivizilor sunt reprezentate de vectori, ce sunt inițializați aleatoriu în interiorul limitelor spațiului de căutare de la începutul procesului de optimizare.

Indivizii evoluează în timpul procesului de optimizare prin aplicarea mutației, recombinării și selecției. Un criteriu de oprire este determinat după construirea unei noi generații, dacă procesul de optimizare este terminat.

Ca alți algoritmi, evoluția diferențială are o mulțime de soluții. Presupunem că acea mulțime de soluții initială are NP indivizi, spațiul de căutare este D, iar vectorul soluțiilor poate fi reprezentat de , .

Există, de obicei, niște criterii de optimizare care se numesc funcția de cost sau fitness. Atunci scopul optimizării cu ajutorul evoluției diferențiale este de a găsi valorile variabilelor care minimizează fitness-ul, adica de a gasi:

(0.1)

3.2.2. Mutația

Din punct de vedere biologic, mutația înseamnă o schimbare bruscă a caracteristicilor genetice ale unui cromozom. În contextul modelului calculului evolutiv, mutația este văzută ca o schimbare cu un element aleatoriu.

În literatura evoluției diferențiale, un vector părinte care aparține aceleiași generații, se numește vector țintă, un vector mutant obținut prin operația de mutație diferențială este cunoscut sub numele de vector donator, și în final descendenții, care sunt formați din recombinarea vectorului ținta cu donatorul.

Într-una dintre cele mai simple forme ale mutației, pentru a crea vectorul donator pentru fiecare vector ținta, trei alți vectori , , sunt aleși aleatoriu. Indicii , , sunt numere întregi alese din intervalul , fiind diferiți de vectorul de bază. Acești indici sunt generați pentru fiecare vector mutant.

Acum diferența din oricare doi vectori dintre cei trei, este redimensionată de un număr scalar , care are valori în intervalul . Această diferență este adăugată celui de-al treilea vector, astfel încât rezultă vectorul donator . Procesul poate fi exprimat prin relația și figura de mai jos:

(0.2)

Figura 9. Procesul de mutație

3.2.3. Încrucișarea

Pentru a spori diversitatea mulțimii, apare o operație de încrucișare, după mutația vectorului donator. În acest fel, indivizii mulțimii sunt actualizați cu ajutorul operației de recombinare. Cu ajutorul componentelor vectorului de mutație si vectorului ținta , se poate genera vectorul . Procesul poate fi descris în ecuația de mai jos:

(0.3)

Unde numărul are valori cuprinse în intervalul , parametrul recombinării este cuprins în intervalul si este un număr întreg ales aleator din intervalul . Procesul de recombinare poate fi observat în figura de mai jos:

Figura 10. Procesul de recombinare

3.2.4. Selecția

Pentru a păstra dimensiunea mulțimii constantă în generațiile următoare, următorul pas al algoritmului este de a selecta cei mai buni vectori de țintă și probă. Apoi operația de selecție, ca un proces determinist al algoritmului, este implementată pentru a alege vectorii țintă și vectorii de probă cu cea mai mică valoare a funcției fitness, fiind exprimată ca:

(0.4)

Acest proces de selecție permite doar îmbunătățirea funcției fitness și nu deteriorarea acesteia. Operatorul de selecție garantează faptul că valoarea celei mai bune funcții nu se pierde, atunci când trece de la o generație la alta. În cazul în care noul vector de probă conduce la obținerea unei valori egale sau mai mici a funcției, înlocuiește vectorul țintă în generația următoare. Așadar, mulțimea se îmbunătățește sau rămâne la fel, dar nu se deteriorează.

3.3. Parametrii de control ai evoluției diferențiale

Există trei parametri de control principali în acest algoritm: factorul de scală al mutației, constanta de încrucișare și mărimea mulțimii . Dimensiunea populației este dată de vectorii ce se pot muta. O mărime mică a mulțimii conduce la un număr limitat de mutări, în schimb, la o mulțime mai mare, numărul de mutări crește, acestea fiind ineficiente și pot induce în eroare căutarea.

Referitor la factorul de scală și constanta de încrucișare , acestea nu pot fi stabilite intuitiv și din păcate sunt esențiale pentru garantarea funcționării algoritmului. Au fost propuse mai multe studii, unul dintre ele fiind în Lampinen și Zelinka în anul 2000.

În cadrul acestuia, după o analiză amănunțită, s-a constatat că utilizarea lui având valoarea 1, nu este bună, deoarece conduce la scăderea puterii de explorare. Analog, , , nu este o bună alegere, deoarece reduce semnificativ numărul de descendenți.

În studiul realizat de Price și Storn în anul 1997, se recomandă valori pentru cuprinse în intervalul și pentru în . Analiza din studiul lui Zielinski făcută în anul 2006, arăta că în multe cazuri, luând valori pentru și , performanțele se îmbunătățesc.

Problema alegerii parametrilor este dificilă atunci când evoluția diferențială este folosită în rezolvarea aplicațiilor reale. Așa cum s-a menționat și mai sus, o creștere a populației implică o mărire a mutărilor ineficiente, astfel alegerea corectă a lui și devine un aspect important în succesul acestui algoritm.

4. Reconfigurarea formației de UAV-uri folosind algoritmul DE bazat pe MPC

4.1. Zborul în formație

Zborul în formație este practicat de foarte mult timp , de numeroase specii de păsări, pentru beneficiile sociale și aerodinamice. Ca un subiect de cercetare interdisciplinară, zborul în formație al UAV-urilor se referă la formații cu geometrii bine stabilite. Datorită acestor formații, există anumite beneficii și anume: economisirea combustibilului, eficiența îmbunătățită în controlul traficului aerian și alocarea sarcinilor de cooperare.

Vehiculele aeriene fără pilot uman la bord se dezvoltă din ce în ce mai mult, fiind de mici dimensiuni, au greutate redusă și sunt capabile să funcționeze în mod autonom. Având aceste calități, UAV-urile au devenit indispensabile aplicațiilor moderne militare și civile.

În ultimii ani, controlul zborului în formație al UAV-urilor a devenit o temă de cercetare interdisciplinară, în timp ce zborul în formație autonom este o zonă importantă în domeniul aerospațial.

Motivația principală este reprezentată de diversitatea activităților atât militare cât și civile, unde grupurile de vehicule aeriene fără pilot oferă un cost redus și o alternativă eficientă la tehnologia existentă.

Grupurile de UAV-uri care zboară în formațiuni cu geometrii bine definite au mai multe avantaje, precum economisirea energiei atunci când forțele vortex sunt luate în considerare.

Zborul în formație poate fi considerat ca o problemă complicată de control, care calculează intrările UAV-urilor de-a lungul manevrelor dificile păstrând pozițiile relative, dar și menținerea, în condiții de siguranță, a distanței dintre UAV-uri.

O formație apropiată, este numită și „formatie stransa”, deoarece distanța dintre uav-uri este mică. În acest caz, cuplarea aerodinamică este introdusă în dinamica formației.

Vehiculele care zboară într-o formație apropiată pot obține o reducere semnificativă a energiei, îmbunătățind astfel performanțele de croazieră, cum ar fi raza de acțiune și viteza. În figura de mai jos este prezentat modelul formației lider-coechipieri:

Figura 11. Lider-coechipier

Problema reconfigurării formației de UAV-uri poate fi descrisă astfel: grupul are o configurație inițială, dar și una finală. Pentru a ajunge la configurația finală, trebuie să existe anumite constrângeri, iar formația trebuie să le aibă în vedere.

Figura 12. Reconfigurarea unei formații

Această problemă poate fi recunoscută ca o problemă de control optimal cu constrângeri dinamice. Mai multe tehnici teoretice au fost dezvoltate pentru a defini poziții noi, care ulterior, vor fi ocupate de UAV-uri în formație.

Ca o problemă de control, reconfigurarea formației impune obținerea unor semnale de intrare, cum ar fi unghiul de viraj, accelerația, tracțiunea. În acest proces, UAV-urile trebuie să îndeplinească anumite condiții.

O astfel de condiție este: distanța dintre două vehicule trebuie să fie mai mare decât distanța de siguranță, dar nu mai mare decât distanța de comunicație.

4.2. Controlul predictiv bazat pe model

În ultimii ani, algoritmii de control predictiv au avut o dezvoltare considerabilă în cercetare, dar și în mediul industrial. Succesul acestuia se datorează modului de rezolvare a problemelor de control în domeniul timp.

Controlul predictiv bazat pe model ( MPC sau RHC) face parte dintr-o clasă de metode de proiectare care folosesc modelul matematic al procesului pentru obținerea unui semnal de comandă prin minimizarea unei funcții obiectiv.

În general, multe sisteme sunt inerent neliniare fiind adesea necesare în utilizarea mai multor condiții de operare. Modelele liniare sunt de cele mai multe ori inadecvate pentru a descrie dinamica procesului, așa că trebuie folosite cele neliniare.

Așadar, MPC are aceleași aplicații și pentru sistemele neliniare:

(0.5)

(0.6)

Unde (0.7)

(0.8)

Unde este vectorul de stare, iar este secvența de comandă, si reprezintă orizontul de control si predicție, existând între ele relația . este limita inferioară, iar este limita superioară.

Întregul proces de control poate fi împărțit într-o serie de intervale de optimizare, numite ferestre de rulare. Metoda MPC formează mecanismul de rulare cu buclă închisă, incluzând observația, planificarea și implementarea.

MPC tratează probleme de control global ca o serie de probleme de optimizare locale. Cu toate acestea, problema reconfigurării formației de UAV-uri este de fapt o problemă de optimizare nonlineara, care are o rezolvare dificilă, dacă se folosesc abordările tradiționale.

Principiul metodei MPC este detaliat în figura de mai jos:

Figura 13. Metoda MPC

4.3. Modelul simplificat al UAV-ului folosit pentru simularea formației

Se consideră un grup de vehicule aeriene fără pilot, având membri, care zboară la aceeași altitudine, în linie dreaptă, având dinamica de forma:

, . (0.9)

Pentru fiecare UAV al formației se definește dinamica, având urmatoarea formă:

(1.0)

(1.1)

(1.2)

(1.3)

Unde este viteza fiecărui UAV, este unghiul de poziție, iar poziția orizontală a vehiculului este dată de în sistemul de referință. Comenzile de intrare sunt date de , care conține tracțiunea și unghiul de ruliu .

este rezistența la înaintare, masa fiecarui UAV fiind reprezentată de și accelerația gravitațională este . Astfel, forma generală a dinamicii unui vehicul este:

, unde . (1.4)

Se alege unul dintre vehicule drept liderul formației, ceilalți având rolul de coechipieri. Liderul este tratat ca punct de referință, vectorul său de stare fiind reprezentat de . Timpul inițial al procesului de reconfigurare este și timpul final este .

Procesul de reconfigurare al formației este văzut ca o problemă de optimizare, deci scopul este de a găsi o acțiune de control continuă care minimizează o funcție de cost, în scopul determinării poziției finale a vehiculelor.

Ecuația funcției de cost folosită în algoritm este urmatoarea:

(1.5)

Unde reprezintă starea finală de referință a unui sistem de UAV-uri, care definește forma formației. determină starea finală a vehiculelor cu ajutorul intrării de comandă . Acestea sunt limitate de performanțele vehiculelor aeriene fără pilot. este o matrice pozitivă definită, de forma:

(1.6)

Pentru a evita accidentele dintre două UAV-uri, distanța aleasă, , trebuie să fie mai mare decât distanța anti-coliziune, :

(1.7)

Pentru a asigura comunicarea în timp real și pentru a obține schimbul de informații, trebuie să fie mai mică decât distanța de comunicare, :

(1.8)

Luând în calcul distanțele de mai sus, funcția cost poate fi rescrisă și este de forma:

(1.9)

Ca restricțiile de distanță să fie satisfacute, se ia în considerare un coeficient constant .

Pentru optimizare, s-a recurs la utilizarea funcției GA (genetic algorithm) din Matlab care are urmatoarea formă:

, (2.0)

unde se definește un set de limite, una superioară și alta inferioară. Se folosesc matrici pentru și dacă nu există limite. reprezintă funcția de fitness.

4.4. Simulări

În urma rulării programului în Matlab s-au obținut mai multe grafice ale comenzilor UAV-urilor, dar și ale funcției de cost .

Pentru a alege orizontul de timp optim, care ajută la reconfigurarea formației de vehicule, s-au experimentat mai multe variante.

Când orizontul de timp este egal cu 1 avem următorul grafic în care se observă scăderea funcției .

Pentru fiecare vehicul, înclinarea , , scade, tracțiunea, , oscilează în jurul unei singure valori. Linia verde reprezintă tracțiunea, iar linia albastră înclinarea.

În graficul de mai jos este evidențiat faptul că alegerea orizontului de timp, nu aduce nici o schimbare formației, aceasta păstrându-și aceeași formă, schimbandu-se doar traiectoria, liderul păstrandu-și aceeași poziție.

Pentru , formația tinde să respecte așezarea impusă. Se observă scăderea unghiului de înclinare, dar și faptul că valoarea tracțiunii oscilează, într-un final aceasta stabilizându-se.

Când orizontul de timp, , se poate observa scăderea funcției , a comenzii de înclinare, dar și stabilizarea tracțiunii. În acest caz, formația nu respectă așezarea finală.

Pentru , în graficele generate se poate observa scăderea valorii funcției , oscilațiile valorii comenzii de înclinare, stabilizarea comenzii de motor, dar și faptul că formația a ajuns la forma dorită.

Cazul în care este asemeni cazului de mai sus. Se observă faptul că mărirea orizontului de timp după ce s-a ales valoarea optimă, nu mai influențează așezarea vehiculelor în formație.

Alegerea orizontului de timp s-a realizat în cazul în care formația în stare finală este de tipul:

Urmatoarea simulare se va face pentru , fiind varianta cea mai bună, și va fi inversul reconfigurării prezentate mai sus. Graficele generate în acest caz sunt urmatoarele:

Se observă o scădere a comenzilor, dar și a funcției de cost.

În continuare, se va face un caz destinctiv, acesta fiind diferit de cele două simulări prezentate, liderul formației fiind în centrul acesteia:

Se poate observa o stabilizare a comenzii de motor, dar și o creștere semnificativă a comenzii de înclinare. Formația finală va fi dispusă pe verticală. Graficele rezultate în urma acestei simulări sunt:

5. Concluzii

Scopul acestei lucrări a fost determinarea unei reconfigurări optime a unei formații de vehicule aeriene fără pilot uman la bord. La baza acesteia au stat algoritmii de inspirație biologică:

Optimizarea coloniei de furnici;

Optimizarea ansamblului de particule;

Colonia artificiala a albinelor;

Evolutia diferențiala.

S-a utilizat evoluția diferențială, deoarece este mult mai simplă și mai ușor de implementat, prezintă performanțe mult mai bune în comparație cu alți algoritmi în rezolvarea diferitelor probleme, numărul parametrilor de control este mai mic.

Procesul de reconfigurare a fost propus pentru a evita posibilele coliziuni între indivizi, existând două tipuri de distanțe de siguranța, distanța anti-coliziune și distanța de comunicare.

Folosirea acestui algoritm a condus la utilizarea metodei MPC ( model predictiv control ), care tratează problemele de control global ca o serie de probleme de optimizare locale. Cu toate acestea, problema reconfigurării formației de UAV-uri este de fapt o problemă de optimizare nonlineara.

Astfel, aceasta se transformă într-o serie de probleme de optimizare, care folosește diferite orizonturi de timp. S-a ajuns la concluzia că orizontul de timp optim în această problemă de reconfigurare are valoarea 4.

Evoluția diferențială este algoritmul ce optimizează secvențele de control pentru fiecare orizont de timp. Fezabilitatea și eficacitatea acestei metode propuse este verificată cu ajutorul mai multor experimente.

Bibliografie

Weatherington D, Deputy U (2005) Unmanned Aircraft Systems Roadmap, 2005–2030. Disponibil online: http://uav.navair.navy.mil/roadmap05/USRoadmapAug%2005.pdf

Clough BT (2002) UAV swarming? So what are those swarms, what are the implications, and how do we handle them? DTIC Document. Disponibil online: http://www.dtic.mil/dtic/tr/fulltext/u2/a405548.pdf

Newcome LR (2004) Unmanned aviation: a brief history of unmanned aerial vehicles. AIAA,

Reston

Zhang X, Duan H (2012) Differential evolution-based receding horizon control design for multi-

UAVs formation reconfiguration

Haibin Duan, Pei LiBio-inspired Computation in Unmanned Aerial Vehicles

JoséA.Guerrero, RogelioLozano, FlightFormation Control

Răzvan-Dorel CIOARGĂ, Comportament emergent în medii colaborative robotizate

Laura E. Barnes, A potential field based formation control

methodology for robot swarms

MICHAEL ANTHONY KOVACINA, SWARM ALGORITHMS:SIMULATION AND GENERATION

Paolo Gaudiano, Benjamin Shargel, Eric Bonabeau, CONTROL OF UAV SWARMS: WHAT THE BUGS CAN TEACH US

Duan H, Liu S (2010) Non-linear dual-mode receding horizon control for multiple unmanned air

vehicles formation flight based on chaotic particle swarm optimisation

Zelinski S, Koo TJ, Sastry S (2003) Optimization-based formation reconfiguration planning for

autonomous vehicles

Price K, Storn R (1997) Differential evolution–a simple evolution strategy for fast optimization

Bonabeau E, Dorigo M, Theraulaz G (1999) Swarm intelligence: from natural to artificial systems

Dorigo M (1992) Optimization, learning and natural algorithms.

Duan H (2005) Ant colony algorithms: theory and applications

Karaboga D, Basturk B (2007) A powerful and efficient algorithm for numerical function

optimization: artificial bee colony (ABC) algorithm

Kennedy J, Eberhart R (1995) Particle swarm optimization. In: Proceedings of IEEE International Conference on Neural Networks

Dorigo M, Maniezzo V, Colorni A (1996) Ant system: optimization by a colony of cooperating

agents

Duan H, Zhang Y, Liu S (2011b) Multiple UAVs/UGVs heterogeneous coordinated technique

based on Receding Horizon Control (RHC) and velocity vector control

Teodorovi´c D, Dell’Orco M (2005) Bee colony optimization–a cooperative learning approach to

complex transportation problems

Clever Algorithms: Nature-Inspired Programming Recipes Disponibil online:http://www.cleveralgorithms.com/natureinspired/swarm/ant_colony_system.html

https://en.wikipedia.org/wiki/Particle_swarm_optimization

Garnier S, Gautrais J, Theraulaz G (2007) The biological principles of swarm intelligence

Duan H, Liu S (2010b) Unmanned air/ground vehicles heterogeneous cooperative techniques:

current status and prospects

Duan H, Shao S, Su B, Zhang L (2010) New development thoughts on the bio-inspired intelligence based control for unmanned combat aerial vehicle

Anexe

S-a anexat programul în Matlab pentru . Acesta a stat la baza celor trei simulări.

Dinamica unui UAV

function xp=dinamica_uav(x,u)

ro=1.22; %densitatea la nivelul solului kg/m^3

S=2.5*0.2; % m^2;

g=9.81; % m/s^2

W=5; % masa unui uav kg

v=x(1); % m/s

psi=x(2); % rad

posx=x(3); % m

posy=x(4); % m

fi=u(1); % rad inclinarea

T=20*u(2); % comanda motor in procente (0..1)

Cx=0.1;

D=ro*v.^2/2*S*Cx;

xp=zeros(4,1);

xp(1)=(T-D)/W;

xp(2)=g*sin(fi)/v;

xp(3)=v*cos(psi);

xp(4)=v*sin(psi);

end

Reconfigurarea formației

global K_orizont N deltat DeltaX_fin Dsafe Dcom omega leader X Q v0 psi_fin

leader=1;

N=5;

K_orizont=4; % orizontul de timp

deltat=1; % s

Dsafe=20;

Dcom=200;

omega=10E6;

v0=18;

psi0=0/180*pi;

psi_fin=45/180*pi;

x0=100;

y0=100;

beta=60/180*pi; % unghiul la varf al formatiei;

Umin=[-pi/9 0.5]';

Umax=[pi/9 1]';

dist_ini=30;

dist_fin=30;

DeltaX_ini=[zeros(1,N); % starile sunt v, psi, x, y

zeros(1,N);

[0 -1 -2 -3 -4]*dist_ini*cos(psi0);

[0 -1 -2 -3 -4]*dist_ini*sin(psi0)];

X=[ones(1,N)*v0; ones(1,N)*psi0; ones(1,N)*x0; ones(1,N)*y0];

X=X+DeltaX_ini;

DeltaX_fin=[zeros(1,N);

zeros(1,N);

[cos(psi_fin) sin(psi_fin); -sin(psi_fin) cos(psi_fin)]*[dist_fin*[0 -1*sin(beta/2) 1*sin(beta/2) -2*sin(beta/2) 2*sin(beta/2)];

dist_fin*[0 -1*cos(beta/2) -1*cos(beta/2) -2*cos(beta/2) -2*cos(beta/2)]]];

Q=diag([3 5000 1 1]);

lb=[];

ub=[];

for j=1:K_orizont

for i=1:N

lb=[lb;Umin];

ub=[ub;Umax];

end

end

figure(1);

plot(X(3,:),X(4,:),'*')

axis square

axis equal

grid on

hold on

pause(0.1)

kk=0;

gata=0;

Xmem=X;

for i=1:6

mem(i).x=[];

mem(i).y=[];

end

while ~gata

[uu, J] = ga(@wraper_ga,K_orizont*N*2,[],[],[],[],lb,ub);

U=despachetare(uu, K_orizont, N);

k=1;

for i=1:N

xi=X(:,i);

uik=U(k).u(:,i);

[aux, xnew]=ode45(@wraper_uav, [0 deltat],[xi;uik]);

X(:,i)=xnew(end,1:4);

if (i==leader)

c='r';

else

c='k';

end

figure(1);

plot(xnew(:,3),xnew(:,4),c)

figure(2)

subplot(2,3,i);

mem(i).x=[mem(i).x [kk, kk+1]];

mem(i).y=[mem(i).y [uik uik]];

plot(mem(i).x,mem(i).y);

grid on

title(['UAV ' num2str(i)]);

end

figure(2)

i=6;

subplot(2,3,i)

mem(i).x=[mem(i).x [kk, kk+1]];

mem(i).y=[mem(i).y [J J]];

plot(mem(i).x, mem(i).y,'ro-');

grid on

title('J Formatie')

Xmem=X;

pause(0.1);

kk=kk+1;

gata=kk>25;

end