Coöperatieve sturing van een zwerm onbemande vliegtuigen

Coöperatieve sturing van een zwerm onbemande vliegtuigen Christophe Wauthier

Promotor: prof. dr. ir. Robain De Keyser Begeleiders: Clara-Mihaela Ionescu, ir. Ramona Hodrea Masterproef ingediend tot het behalen van de academische graad van Master in de ingenieurswetenschappen: werktuigkunde-elektrotechniek

Vakgroep Elektrische energie, systemen en automatisering Voorzitter: prof. dr. ir. Jan Melkebeek Faculteit Ingenieurswetenschappen Academiejaar 2008-2009

Cooperative control of a swarm of unmanned aerial vehicles Christophe Wauthier Supervisor(s): Robain De Keyser, Jorge Niño Abstract— This article gives an overview of the progress that has been achieved during the last decade in cooperative control of multi-agent systems. Due to the novelty of that work area, a lot of diverse but unfinished research has been conducted. Several cooperative control methods are introduced and some shortcomings are highlighted. The article thereby focuses on the application of formation control of a swarm of unmanned aerial vehicles. Implementation of decentralized control algorithm in MATLAB and Simulink environment is done and step by step extension is carried out to meet some real-life constraints. Keywords— multi agent system, unmanned aerial vehicle, formation control, obstacle avoidance

I

I. I NTRODUCTION

N last decades, an exponential growth has taken place in research towards autonomous unmanned vehicles and their application in tasks that are characterised by repetitiveness or presence of danger. A number of succesfull methods have been presented to control a single mobile vehicle, like path following, area surveillance and pursuit. But in recent years, interest has grown in assigning multiple vehicles to a single mission. However, to achieve cooperation and coordinations between multiple agents, new concepts and theories have to be introduced. II. M ULTI AGENT SYSTEMS

Multi agent systems are every system where multiple interacting intelligent agents combine relatively simple strategies to show complex behaviour. One agent has the property to: - posses a certain autonomy, - have local knowledge, - be decentralized. Multi agent systems have alternatives in ground, naval, aerial and space applications.

IV. S IMULATION A. Implementation We introduce a decentralized control algrithm [1] that guides a formation of three co-leading UAVs along an off-line stipulated trajectory. The identical, but individual controller of every agent uses local information to determine the controller output, the angular velocity ωi (t). Therefore a desired heading is calculated that sends an agent towards a desired point. We analyse the results and check if the algorithm is resistant against real life constraints. We point out the impossibility to react on environmental changes and propose to find a solution. B. Extension To be able to avoid obstacles, we extend the algorithm and present an extra angular velocity that is calculated with real-time gathered information about the environment. The original algorithm does not take into account detours, what obliges us to create an automatic speed control loop that compensates for the extra distance. Positive results are presented. V. C ONCLUSION As almost every control method is ad hoc, it is hard to find a cooperative algorithm that is extendable over multiple diverse applications. Within one application, it is possible to develop a behaviour based control that meets real-life constraints like the presence of unexpected obstacles. Future work kan take into account more constraints or handle formations of higher dimension, even in 3D.

III. UAV SWARMS

R EFERENCES

Driven by the Global War on Terror (GWT), unmanned aerial vehicles (UAVs) have known a great evolution in recent years. But they’ve proven useful not only in military missions. More and more civil applicatins emerge where UAVs play a prominent role. However, a single UAV system is highly vulnerable, due to the single point of failure. That’s why a swarm of UAVs can not only increase the efficiency of a task, but also robustness is obtained. An in-depth study on UAV swarms in general and formation control in specific is done and a state of the art on cooperative control is formulated. We treat several modelling methods, architectures and hiërarchies.

[1] B.D.O. Anderson, B. Fidan, C. Yu and Dirk van der Walle, UAV Formation Control: Theory and Application, Recent Advances in Learning and Control, p.15-33, 2008

Inhoudsopgave

iii

Inhoudsopgave Extended abstract

ii

1

Inleiding

1

2

Multi Agent Systemen 2.1 Inleiding . . . . . . . . . . . . . . . . . 2.2 Geschiedenis van autonome systemen 2.3 Biologische parallel . . . . . . . . . . . 2.4 Voor- en nadelen . . . . . . . . . . . . 2.5 Toepassingen . . . . . . . . . . . . . .

3

4

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

3 3 4 7 7 8

UAV zwermen 3.1 Inleiding . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Geschiedenis . . . . . . . . . . . . . . . . . . . . . . . . . 3.3 Toepassingen . . . . . . . . . . . . . . . . . . . . . . . . 3.3.1 Surveillance . . . . . . . . . . . . . . . . . . . . . 3.3.2 Achtervolging . . . . . . . . . . . . . . . . . . . . 3.3.3 Formatie . . . . . . . . . . . . . . . . . . . . . . . 3.4 Modellering . . . . . . . . . . . . . . . . . . . . . . . . . 3.4.1 Toestandsmodel . . . . . . . . . . . . . . . . . . . 3.4.2 Communicatie . . . . . . . . . . . . . . . . . . . 3.4.3 Grafentheorie . . . . . . . . . . . . . . . . . . . . 3.5 Sturing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.5.1 Gecentraliseerde vs. gedecentraliseerde sturing 3.5.2 Leiderschap vs. virtueel leiderschap . . . . . . . 3.5.3 Reactieve vs. predictieve sturing . . . . . . . . . 3.5.4 Gedragsgebaseerde sturing . . . . . . . . . . . . 3.6 Tekortkomingen . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

11 11 12 14 14 14 14 15 15 16 16 18 18 18 19 19 19

Simulatie 4.1 Inleiding . . . . . . . . . . . . . . . . . . . . 4.2 Omschrijving van de situatie . . . . . . . . 4.3 Eigenschappen van de UAV en de formatie 4.4 Uitwerking van een algoritme . . . . . . . . 4.5 Implementatie . . . . . . . . . . . . . . . . . 4.5.1 Bepaling van controller frequentie . 4.5.2 MATLAB vs. Simulink . . . . . . . . 4.6 Analyse . . . . . . . . . . . . . . . . . . . . . 4.6.1 Flexibiliteit t.o.v trajectorie . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

20 20 20 22 23 24 24 30 30 30

. . . . .

. . . . .

. . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . .

. . . . . . . . .

. . . . . . . . .

Inhoudsopgave . . . . . . . . .

34 34 34 35 35 37 38 39 44

Conclusie 5.1 Samenvatting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Verder onderzoek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

45 45 46

4.7

5

4.6.2 Flexibiliteit t.o.v. formatie . . . . . . 4.6.3 Flexibiliteit t.o.v. meetfouten en ruis 4.6.4 Flexibiliteit t.o.v. omgeving . . . . . Uitbreiding . . . . . . . . . . . . . . . . . . . 4.7.1 Aanpassing van controleoutput . . . 4.7.2 Dynamisch pad . . . . . . . . . . . . 4.7.3 Snelheidsregelkring . . . . . . . . . 4.7.4 Toepassing . . . . . . . . . . . . . . . 4.7.5 Resultaat . . . . . . . . . . . . . . . .

iv . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

A MATLAB programma

47

B Simulink model

50

C Uitgebreid Simulink model

51

Bibliografie

52

Hoofdstuk 1. Inleiding

1

Hoofdstuk 1

Inleiding In afgelopen decennium is een grote interesse gegroeid in onbemande voertuigen (Autonomous Unmanned Vehicles of AUVs) en hun toepassing in diverse doeleinden. Dit omwille van hun functionaliteit bij opdrachten gekarakteriseerd door herhaling, nood aan informatiewinning of aanwezigheid van allerhande gevaar. Het behandelen van vervuilde ondergrond bij bodemsanering of zich verplaatsen in vergiftigde omgevingen zijn hier mooie voorbeelden van. Naast de aanwezigheid van gevaar zijn personeelstekort en een hoge arbeidskost invloedrijke factoren in het streven naar automatisering binnen de industrie in het algemeen en transport in het specifiek. Tal van studies werden reeds uitgevoerd betreffende het dynamisch gedrag van allerhande voertuigen, de identificatie van de betrokken deelsystemen en de ontwikkeling van aandrijfen sturingsmechanisme (Valavanis, 2007; Nino, 2007; Radu, 2008). De hedendaagse techniek laat reeds toe AUVs op individuele basis missies tot een goed eind te brengen. Echter, bij het inzetten van e´ e´ n enkele AUV wordt de uitvoering van die opdracht heel erg op de proef gesteld. Kleine fouten in de beslissing van de AUV kunnen nefaste gevolgen hebben op de tijdsduur van de opdracht en de effic¨ıentie waarmee ze uitgevoerd wordt. Bovendien betekent het falen van de AUV een totale mislukking van de missie. Daarom werd in recente jaren heel wat onderzoek gevoerd naar de mogelijkheid om meerdere voertuigen samen in te zetten bij ¨ het verwezenlijken van een gemeenschappelijke taak. Dit noemen we cooperatieve sturing van een zwerm. Uitvoeringstijd kan hierbij drastisch naar omlaag gehaald worden, samen met een reële winst in efficiëntie en robuustheid. Nieuwe concepten en denkwijzen zijn nodig om meerdere AUVs samen te laten werken, deze thesis spits zich dan ook volledig toe op deze studie. Hierbij wordt verondersteld dat op heden genoeg kennis verworven is om een alleenstaande AUV te sturen (). Waar nodig worden toegepaste theorieën wel kort uiteengezet.

Hoofdstuk 1. Inleiding

2

AUVs kunnen te land, ter zee of in de lucht worden ingezet. Elke toepassing vergt zijn eigen aangepaste voertuigen, veronderstellingen, vereenvoudigingen, modellering, etc. In een eerste deel van de thesis beschouwen we multi agent systemen in het algemeen, zonder onderscheid te maken tussen de subgroepen. In een tweede deel wordt de aandacht exclusief gevestigd ¨ op cooperatieve sturing bij onbemande vliegtuigen. Een derde deel behandelt de implementatie van een simulator voor een zwerm onbemande vliegtuig in MATLAB/Simulink omgeving. ¨ Hierbij wordt een cooperatieve sturingsmethode nader toegelicht en de resultaten besproken. Opvallend aan deze methoden is dat amper rekening gehouden wordt met praktische beperkingen die in de realiteit permanent aanwezig zijn. Er wordt een balans opgesteld van de huidige ontwikkelingen en mogelijke verbeteringen en een nieuw algoritme wordt uitgewerkt die een zwerm onbemande vliegtuigjes stuurt tijdens een specifieke missie, rekening houdend met deze waarheidsgetrouwe beperkingen.

Hoofdstuk 2. Multi Agent Systemen

3

Hoofdstuk 2

Multi Agent Systemen 2.1

Inleiding

Multi agent systeem Een multi agent systeem (MAS) is een systeem bestaande uit meerdere interagerende intelligente agenten en kan door een samenkomst van relatief simpele individuele strategieën toch complexe gedragingen vertonen. Ze kunnen worden ingezet bij het oplossen van problemen die moeilijk of onmogelijk zijn voor een individueel teamlid. Eén agent uit een MAS wordt gekarakteriseerd door drie eigenschappen: 1. Autonomie: de agenten vertonen een minimum vermogen van zelfstandig functioneren. 2. Lokale kennis: geen enkele agent bezit een globale kennis van de toestand van het systeem. 3. Decentralisatie: geen enkele agent beslist individueel wat er met het volledige systeem (of alle agenten) gebeurt. Wat juist verstaan wordt onder een agent kan ruim ge¨ınterpreteerd worden. Communicerende meetstations of een netwerk van stationaire productierobots vallen ook onder de noemer MAS. In deze thesis beperken we ons echter tot mobiele agenten. Meerdere voertuigen vormen dan een multi vehicle system (MVS) Hoewel dit het begrip agent een heel stuk insnoert, zullen we zien dat binnen deze klasse nog variatie mogelijk is. In dit hoofdstuk wordt een helikopterzicht gepresenteerd van enkele toepassingen van MASs, voorafgegaan door een korte uiteenzetting over de evolutie van simpele alleenstaande voertuigjes tot complexe zwermen.


2.2

4

Geschiedenis van autonome systemen

Het ontstaan van autonome voertuigen of zogeheten mobiele robots gebeurde in de loop van voorgaande eeuwen op een heel geleidelijke manier. Reeds voor het begin van de christelijke jaartelling, werd onderzoek gedaan en discussie gevoerd over de mogelijkheid van autonome werktuigen. Vooral de Grieken waren gefascineerd door alles wat functioneerde zonder externe aandrijving. Zo bouwde de Griekse wiskundige Archytas, grondlegger van de wiskundige mechanica en vriend van Plato, reeds in 350 B.C. een mechanische houten vogel die zichzelf voorstuwde met behulp van stoom. In diezelfde tijd filosofeerde ook Aristoteles over de creatie van autonome entiteiten die arbeiders en slaven overbodig zouden maken. Verder werd in die tijd reeds gretig gebruik gemaakt van de waterklok of clepsydra. Toen al toonden wijzers een relatief nauwkeurig tijdstip, aangedreven door een continue stroom van water uit een reservoir (figuur 2.1).

Figuur 2.1: schematische voorstelling van een waterklok

In 1495 slaagde Leonardo Da Vinci erin een gepantserde pop met een inwendig mechanisme levensechte bewegingen te laten uitvoeren (figuur 2.2(a)). Deze eerste automaat werd wel enkel om entertainment redenen gebruikt. De titel van eerste robotbouwer dient Da Vinci te delen met Jacques de Vaucanson. Deze Franse uitvinder en instrumentenbouwer bouwde in 1738 een levensgrote mechanische pop die twaalf verschillende liedjes op fluit kon spelen. Wereldberoemd werd hij wat later met de creatie van een mechanische eend, die kon zwemmen, met de vleugels slaan en voedsel eten (figuur 2.2(b)).


(a) de robot van Leonardo Da Vinci

5

(b) de eend van Jacques de Vaucanson

Figuur 2.2: de voorlopers van de moderne robot

In de daaropvolgende eeuwen werd stilaan meer vorm gegeven aan autonome of op afstand bestuurde machines: In 1801 werd de ponskaart uitgevonden door Joseph Jacquard. Deze vormde de basis in de ontwerpen van Charles Babbage. Hij trachtte een rekenmachine te bouwen die logaritmische en trigonometrische functies benaderde aan de hand van benaderende polynomen. Hij mislukte daarin, maar wordt op heden toch de uitvinder van de computer genoemd. Op het einde van de 19e eeuw demonstreerde Nikola Tesla een op afstand bediend bootje. In 1921 kende het woord ’robot’ zijn oorsprong uit de pen van de Tsjechische schrijver Karel Capek. Hij leidde dit woord af van het Tsjechische ’robota’ wat ’verplichte arbeid’ betekent. De term artificiële intelligentie werd in 1956 voor het eerst gebruikt in het Darthmouth Summer Research Project on Artificial Intelligence. Kort daarna werd in Massachusetts Institute of Technology (MIT) het Artificial Intelligence Laboratory opgestart. In 1962 kreeg de eerste volwaardige industriële robot vorm onder de Ultimate. De man hierachter was George Devol, stichter van het eerste robotica bedrijf Unimation en patenthouder van meer dan 40 miljoen octrooien. Deze (arm)robot werd ingezet in de productielijn van General Motors waar het een functie kreeg die door de aanwezigheid van giftige verfdampen te gevaarlijk geacht werd voor mensen. Doorheen de geschiedenis is dit zonder twijfel de grootste motivatie om onderzoek te verrichten naar autonome mechanismen. De daaropvolgende jaren werden gekenmerkt door de ontwikkeling van meer complexe en verfijnde machines. Ze worden gebruikt in de meest uiteenlopende takken; van de ruimtevaartsector tot de speelgoedwinkels, van high-tech toepassingen tot alledaagse huishoudtoestellen.


6

Het is in de late jaren ’80 dat professor aan MIT Rodney Brooks met zijn studenten een reeks identieke rollende en stappende robots bouwt en onderzoek start naar distributed mobile robotics of verdeelde mobiele robotica. Verdeeld mobiele robotica verdeling binnen een systeem betekent meestal dat meerdere geografisch gespreide gebruikers het systeem uitmaken of dat een uit te voeren taak over meerdere units gespreid kan worden om de performantie of fouttolerantie van het systeem te verhogen. Binnen een verdeeld systeem is communicatie heel belangrijk, deze zorgt ervoor dat informatie over alle units verzonden wordt of dat deelsystemen onderling synchroniseren. Toegepast op mobiele robotica betekent verdeeldheid onder andere het toewijzen van deeltaken aan verschillende agenten, het plannen van een missie of het opstellen van een hiërarchie binnen de groep. In het daarop volgende decennium kende de robotica enkele hoogtepunten. Zo landde in 1997 NASA’s Pathfinder op Mars en werd het autonome robotsysteem Sojourner in gebruik genomen. Het feit dat in hetzelfde jaar de computer Deep Blue de grootmeester Kasparov in een schaakpartij verslaat, heeft weinig te maken met robotica, maar toont wel dat artificiële intelligentie stilaan de kop op stak. Ook op het vlak van verdeelde robotica boekt de wetenschap vooruitgang, want in 1993 wordt RoboCup opgericht. Robocup Een internationale competitie waarin teams van robots het opnemen tegen elkaar in allerhande wedstrijden. Zo wordt onderzoek naar artificiële intelligentie en verdeelde robotica gepromoot. Bij oprichting luidde het officiële doel: ”tegen het midden van de 21e eeuw in staat zijn een team van volledig autonome humano¨ıde robots te laten winnen van de meest recente winnaars van de wereldbeker voetbal en dit volgens de regels vooropgesteld door de FIFA”. In 1997 gaan de eerste RoboCup games van start. Initieel bestaat er enkel een voetbalcompetitie voor rollende robots, op heden bestaan ook reddings- en danswedstrijden voor zowel rollende als humano¨ıde robots.

Figuur 2.3: Een speelveld in de Robocup competitie


2.3

7

Biologische parallel

De motivatie om studies uit te voeren in verband met multi agent systems stamt uit het gedrag binnen zelf-organiserende zwermen die in de natuur talrijk aanwezig zijn. In een school van vissen of een troep vogels is groepsgedrag cruciaal bij het collectief verplaatsen maar ook om zich te beschermen tegen een aanval van roofdieren. Ook een kudde wild vertoont complex collectief gedrag bij het migreren, zoals toekennen van leiderschap of behouden van formaties. Deze komen tot stand door individuele beslissingen en acties van de dieren, gebaseerd op observaties van de directe omgeving en het gedrag van buren om zo globale functionaliteit te bereiken.

(a) een zwerm vogels in formatie

(b) een georganiseerde school vissen

Figuur 2.4: Voorbeelden van samenwerking in de natuur

Regeltechnische wetenschappers en ingenieurs, geboeid door dit biologisch fenomeen, werden ge¨ınteresseerd in het ontwikkelen van een artificieel analogon. Groepen van autonome voertuigen, geëquipeerd met meet-, reken- en communicatieapparatuur kunnen zo gebruikt worden bij het uitvoeren van een variëteit aan ruimtelijk verdeelde opdrachten zoals search and rescue, toezicht, exploratie en synchrone levering van lading, om maar een paar van de vele mogelijkheden op te sommen.

2.4

Voor- en nadelen

Er zijn tal van voordelen waarom de voorkeur gegeven wordt een probleem op te lossen met behulp van verdeelde robotica (Parker, 1998) + Economisch: Het is goedkoper meerdere robots te bouwen die elk e´ e´ n taak uitoefenen dan e´ e´ n enkele multi-functionele robot te ontwikkelen. + Robuustheid: een verdeeld systeem is immuun voor het wegvallen van e´ e´ n agent, e´ e´ n enkele robot natuurlijk wel. + Geografische verdeeldheid: verschillende robots kunnen op verschillende plaatsen tegelijk aanwezig zijn, werkend aan verschillende taken. + Performantie: e´ e´ n enkele robot binnen de groep beschikt over meer kennis door het delen van sensoreninformatie. Zo kan een object tijdens identificatie op eenzelfde moment


8

vanuit meerdere hoeken bekeken worden en kan een zwaar object door meerdere agenten gedragen of geduwd worden. + Veiligheid: mensenlevens worden gespaard als gevaarlijke en complexe taken door een groep robots kan uitgevoerd worden. Natuurlijk zijn er niet enkel de voordelen, er zijn ook overwegingen die een snelle ontwikkeling van MASs in de weg staan: ¨ ¨ - Coordinatie en cooperatie zijn niet altijd makkelijk te bekomen, een enkele agent kampt niet met dit probleem. - Verschillende agenten kunnen elkaar hinderen bij het uitvoeren van een taak.

2.5

Toepassingen

Zoals in sectie 2.1 reeds aangehaald werd, is een MAS een heel ruim begrip. Toepassingen spreiden zich dan ook over alle denkbare sectoren van de industrie. Zelfs wanneer we ons beperken tot mobiele agenten (MVS) blijft er ruimte voor interpretatie. Het grootste onderscheid kan gemaakt worden door de omgeving waarin de mobiele robots zich verplaatsen. Te land Dit is hoogst waarschijnlijk de categorie die het meest geassocieerd wordt met robotica. Het algemene beeld van een robot bij het grote publiek is namelijk deze van een mensachtige machine of humanoid (figuur 2.5(a)). Er bestaat inderdaad onderzoek naar tweevoetige robots die zich voortbewegen als een mens, maar de grootste nadruk hierbij ligt eerder nog op het streven naar stabiliteit dan op praktisch gebruik. Onbemande grondvoertuigen (Unmanned Ground Vehicle of UGV) zijn daarom meestal van de rollende soort, vooral bij gebruik in groep (figuur 2.5(b)).

(a) een humanoid robot

(b) een rollende UGV

Figuur 2.5: Onderscheid tussen humanoids en rollende UGVs


9

Ter zee Water is geen makkelijk medium om zich in of op te verplaatsen. Niet enkel zijn de traagheidskrachten uitgesproken aanwezig tijdens manoeuvreren, ook moet er meestal rekening gehouden worden met permanente stroming en deinig, die de navigatie en sturing van een onbemand schip (Unmanned Surface Vehicle of USV) bemoeilijkt. Onder water Onbemande onderwatervaartuigen (Unmanned Underwater Vehicle of UUV) zijn niet zomaar een uitbreiding op vorige klasse. De mogelijkheid van zich in drie dimensies te kunnen bewegen opent nieuwe perspectieven, maar verplicht ons daarvoor aangepaste sturing te ontwikkelen. In de lucht Het luchtruim is een zeer interessant werkgebied bij het verkennen van mogelijkheden voor onbemande voertuigen. De open ruimte biedt eerst en vooral de beste communicatiemogelijkheden tussen agenten, want nabijheid van storende objecten of interferentie, die op grond en in het water wel voorkomen, zijn er niet. Overigens is bij breuk, botsing of andere problemen, de afloop meestal fataal voor betrokken personen, wat het luchtruim tot gevaarlijk werkgebied maakt en de interesse in onbemande vliegtuigen (Unmanned Aerial Vehicle of UAV) doet toenemen. Een volgend hoofdstuk spitst zich volledig toe op deze tak van MASs. In de ruimte In de ruimte zijn sinds het begin van het ruimtevaartstijdperk, op een miniem aantal uitzonderingen na, alle voertuigen vanop afstand en door computers bestuurd. Wel wor¨ den op heden meer en meer cooperatieve methodes ontwikkeld om bijvoorbeeld dataverkeer tussen meerdere satellieten te optimaliseren. ¨ We overlopen enkele van de vele mogelijke toepassingen van cooperatieve sturing waar op heden intensief ondezoek naar gebeurt. Box pushing Het is moeilijk voor e´ e´ n enkele agent om een groot en zwaar voorwerp gecontroleerd te verplaatsen. De samenwerking tussen meerdere agenten laat dit vlotter verlopen. Hoewel deze toepassing niet onmiddelijk in de praktijk toegepast wordt, vormt ze wel de basis ¨ proefomgeving bij het onderzoek naar cooperatieve sturingsmethodes. Formatie De natuur leert ons dat zich verplaatsen in groep tal van voordelen oplevert. Vogels die in formatie vliegen sparen bijvoorbeeld energie uit door het gebruik maken van de upwash die de vleugels van een voorganger genereren. Robots in groep kunnen ook een grotere antenne vormen dan een individuele agent, wat de gevoeligheid van een groep vergroot. Verder kunnen verschillende agenten zich toespitsen op verschillende taken, zo dient niet iedere voertuig volgeladen te worden met allerhande meetapparatuur. Surveillance of search and rescue Het uitkammen van een gebied op zoek naar een verstekeling of het waken over een grote regio, twee taken die in groep veel efficiënter uit te voeren vallen.


10

Identificatie Bij het identificeren van een onbekend object heeft een alleenstaande robot het nadeel slechts e´ e´ n invalshoek te hebben. Meerdere agenten bieden een hogere zekerheid op het correct identificeren of classificeren van een vreemd voorwerp. Rendez-vous Het samenbrengen van meerdere voertuigen op eenzelfde lokatie op hetzelfde tijdstip kent zijn toepassing in militaire operaties waar een maximaal verrassingseffect verkregen wordt bij gelijktijdige aanvallen (Ren & Beard, 2005; Murray, 2006). Mobiele sensor netwerken De studie van het zodanig positioneren van meerdere mobiele sensoren om een maximum hoeveelheid aan informatie te verzamelen. Een concreet voorbeeld hiervan is het Autonomous Oceaan Sampling Network (AOSN) (Murray, 2006). Een netwerk, bestaande uit een verzameling autonome voertuigen, waarin iedere agent zijn beweging aanpast aan informatie die hijzelf of andere leden van de groep ontvangen. Een ander voorbeeld is de Terrestrial Planet Finder (TPF), meerdere microsatellieten die e´ e´ n virtuele satelliet vormen en gebruik makend van lichtinterferentie verafgelegen sterren en planeten kunnen waarnemen. Transportsystemen Op plaatsen waar veel voertuigen bijeen komen is er meestal verlies van efficiëntie en natuurlijk een groeiende kans op botsingen. De personen die deze voertuigen besturen zijn daar meestal zelf de oorzaak van. Intelligente autosnelwegen, waar interactie tussen individuele voertuigen een veiliger verloop biedt, zijn dan ook interessante onderzoeksvelden (Swaroop, 1997). Ook air traffic control kan van deze mogelijkheid gebruik maken. Mapping Wanneer een plan of schematische weergave gewenst is van een onbekend gebied; zal de samenwerking tussen meerdere voertuigen, verspreid in dat gebied, een snellere en nauwkeurigere oplossing geven. Huishouden of entertainment De AIBO robot-hond van Sony of het Furby speelgoed zijn enkele voorbeelden van robots die de mogelijkheid bezitten te interageren met zijn omgeving of soortgenoten. De recente ontwikkelingen in domotica zetten verschillende huishoudtoestellen in verbinding met elkaar om een gedeelde taak te volbrengen. Zo worden bij het aanzetten van de DVD-speler, ook het televisietoestel en het Dolby Surround Systeem op actief geplaatst.

Hoofdstuk 3. UAV zwermen

11

Hoofdstuk 3

UAV zwermen 3.1

Inleiding

Een onbemand vliegtuig (Unmanned Aerial Vehicle of UAV) is een vliegtuig die geen piloot of andere bemanning aan boord heeft. Het voertuig kan van op afstand via radiogestuurde controle bestuurd worden of kan autonoom functioneren. Net zoals andere voertuigen is het mogelijk meerdere UAVs samen te laten werken bij het volbrengen van een missie die een individueel vliegtuig niet of minder efficiënt kan uitvoeren. Soms wordt als benaming niet UAV maar UAS (Unmanned Aircraft System) gebruikt, omdat het volledige systeem vaak uit meerdere vliegtuigen bestaat en soms zelfs een ondersteunend basisstation op de grond omvat. In dit hoofdstuk overlopen we de evolutie van UAVs en bekijken in welke toepassingen deze ¨ reeds -eventueel in groep- gebruikt worden. Nadien wordt ingegaan op wat cooperatieve sturing van een zwerm UAVs juist betekent. Hierbij komen uiteenlopende architecturen, hiërarchieën en restricties in de communicatie aan bod. Verder wordt ge¨ıntroduceerd welke methodes be¨ staan om groepen onbemande vliegtuigen te modelleren en cooperatief te sturen. Ten slotte wordt behandeld welke de grootste tekortkomingen zijn van huidige technieken en mogelijke verbeteringen worden aangeduid. Meestal vallen alle onderwerpen door te trekken over de volledige lijn van MVSs. UAVs vormen dan ook een louter praktisch voorbeeld van deze overkoepelende groep.


3.2

12

Geschiedenis

Reeds vroeg in de geschiedenis werden allerhande vliegende objecten ontworpen en gebouwd die niet aan boord zelf bestuurd werden, meestal enkel voor recreatieve doeleinden. De eerste UAV met een duidelijk omschreven functie was Aerial Target, ontworpen door H.P. Folland en A.M. Low (figuur 3.1(a)). Het radiogestuurde vliegtuigje, waarvan de bouw startte in 1916, diende als doelwit bij het testen van luchtafweer. Dit was echter een dekmantel voor een Brits project die onderzoek deed naar het gebruik van radiosignalen bij het sturen van geleide projectielen. Ook tijdens het interbellum en zelfs tijdens en na W.O. II bleef bij het gebruiken van UAVs de controle voornamelijk beperkt tot radiosturing, terwijl jet motoren de voornaamste aandrijving werd. Een uitzondering hierop was de LARYNX (figuur 3.1(b)), een onbemand vliegtuig, gebouwd in 1927, die de basisprincipes van een automatische piloot hanteerde en gebruikt werd als primitieve kruisraket, maar door gebrek aan accuraatheid verdere doorbraak mistte. Op een eerste generatie ’autonome’ UAVs was het wachten tot de Vietnam oorlog, waar ze ingezet werden bij het verkennen van voorop liggend gebied. Uitgerust met videoapparatuur vlogen ze in rechte lijn of beschreven een constante cirkel terwijl de omgeving opgenomen werd en dit tot een brandstoftekort hen gebood te landen. Door de simpele aard van deze toestellen werden ze ’drones’ genoemd.

(a) een replica van de Aerial Target

(b) LARYNX, een primitieve kruisraket

Figuur 3.1:

De evolutie naar grotere autonomie ging hand in hand met de ontwikkelingen op het vlak van: - Sensoren: gevoeligere sensoren bieden meer nauwkeurige gegevens. - Communicatie: tussen verschillende apparatuur binnen e´ e´ n vliegtuig of tussen verschillende agenten dient informatie verstuurd te worden. - Optimalisatie: bij het berekenen van een pad die voorgeschreven verwachtingen invult maar ook aan beperkingen gehoorzaamt. - Planning en taakverdeling: het optimaal toewijzen van deeltaken om met een beperkt aantal resources een gegeven taak te volbrengen. De exponentiële groei van bovenstaande onderzoeksvelden bij de aanvang van het computertijdperk op het einde van de 20e eeuw zorgde voor een versnelling in de vooruitgang van UAVs. De grootste groei ontstond echter steeds in oorlogstijden, vooral dan in het laatste decennium door de strijd tegen terrorisme in Afghanistan en Irak, de onbemande vliegtuigen


13

hebben immers geen last van het woeste landschap en de immense droogte die heerst in die gebieden. Naast het feit dat zo geen mensenlevens geriskeerd worden, gaat men ook politiek ingewikkelde en schandalige situaties, zoals neergeschoten vliegtuigen en gegijzelde militairen, uit de weg. De MQ-1 Predator, weergegeven in figuur 3.2, werd reeds in 1995 in gebruik genomen, onder andere tijdens missies boven Bosnië. Bijna 15 jaar later bewijst deze UAV nog steeds zijn dienst, weliswaar voorzien van alle nieuwste updates. Deze vliegtuigen worden wel meestal nog vanop aftand bestuurd, soms zelfs vanuit grondbasissen aan de andere kant van de wereld.

Figuur 3.2: de MQ-1 Predator, in dienst sinds 1995

Wat de toekomst betreft is de stap naar volledig gebruik van onbemande vliegtuigen niet heel ver weg meer is. Het ziet er naar uit dat de USAF Joint Strike Fighter en de Eurofighter Typhoon de laatste generatie militaire gevechtsvliegtuigen zijn die een piloot aan boord hebben.


3.3

14

Toepassingen

In sectie 2.5 werd reeds overlopen welke de voornaamste praktische toepassingen zijn voor het gebruik van MASs. Voor ieder van de vermelde voorbeelden kan wel een variant gevonden worden voor een groep UAVs. We gaan hier nog even dieper in op enkele enkele toepassingen, typisch voor een UAV zwerm. Tot voorheen werden UAVs vooral voor militaire doeleinden gebruikt, het is dan ook niet te verwonderen dat de meeste van de toepassingen militair getint zijn, of tenminste daar hun oorsprong kennen.

3.3.1

Surveillance

Een gebied moet bewaakt worden en is te groot om door e´ e´ n enkele UAV behandeld te worden. Daarom kan een groep aangewezen worden die zijn geografische verspreidheid gebruikt om efficiënter op te treden. Efficëntie maximaliseren stemt hier overeen met het minimaliseren van de uitvoertijd. Bij een opgegeven gebied wil dit zeggen dat er naar minimale sensor overlap gestreefd wordt, een reeds bezocht stuk bezoeken is namelijk tijdverlies. Een techniek voor een niet-overlappende lus in een te observeren gebied te vinden, is het Spanning Tree Coverage (STC) algoritme (Jones et al., 2007) en kan zowel offline als in real-time toegepast worden. De uitbreiding van STC voor een multi-vehicle area surveillance is een heel recente studie. Meestal wordt verondersteld dat de agenten van op verschillende plaatsen starten, maar hetzelfde trajectorie volgen. Bij het bepalen van de gespannen boom moet dan rekening gehouden worden met de startposite van de UAVs, want de vorm van deze boom bepaalt in grote mate de verkenningsduur. Samengevat is het STC algoritme rekenkundig efficiënt, garandeert volledige bedekking van het gebied en genereert moeilijk te voorspellen trajectories, wat gewenst is bij militaire doeleinden.

3.3.2

Achtervolging

Het achtervolgen van dynamische doelen is een zeer uitdagende studie, zeker wannneer het vluchtende doel een zekere vorm van intelligentie toegewezen krijgt. Multiplayer differential game theory (Jones et al., 2007) wordt gebruikt om het gedrag van volgers en ontsnappers te modelleren en complexe aanpakken, zoals het oplossen van de Hamilton-Jacobi vergelijking of het opstellen van een cellular-search model (Yatsenko et al., 2007) bestaan om een achtervolging te optimaliseren.

3.3.3

Formatie

De meest voor de hand liggende uitbreiding van individuele opdrachten naar die in groep is het vormen van een formatie. Het volbrengen van de opdracht bestaat dan uit twee luiken: het eigenlijk doel blijft hetzelfde, maar ook moet iedere UAV een vaste relatieve positie behouden ¨ ten opzichte van e´ e´ n of meerdere teamleden. Cooperatieve sturing betekent dan dat aan beide verwachtingen voldaan wordt. Het constant houden van een inter agent distance kan op symmetrische of asymmetrische manier gebeuren. In het eerste geval wordt moeite gedaan door beide agenten om de gewente posities in te nemen of constante afstand te behouden. De onderliggende graaf (sectie 3.4.3) is


15

dan ongerichte. Het mag als triviaal beschouwd worden dat bij streven naar formatie niet all niet alle, maar slechts enkele onderlinge afstanden constant moeten gehouden worden om de volledige vorm en dimensie van de formatie gegarandeerd wordt. Voorwaarden voor zogenaamde stijfheid, worden bestudeerd in rigid graph theorie (zie 3.4.3). Bij asymmetrische sturing streeft slechts e´ e´ n van agenten uit een agentenpaar actief de gewenste positie of afstand na, wat een onderliggende gerichte graaf impliceert. Aangezien deze aanduidt dat informatie slechts in e´ e´ n richting gestuurd hoeft te worden, betekent dit een drastische vermindering van de communicatie complexiteit.

3.4

Modellering

Een formatie van UAVs is een systeem opgedeeld in deelsystemen, die elk voorgesteld kunnen worden door een toestandsmodel, het totale systeem bereikt dan zijn formatie door communicatie tussen en synchronisatie van die deelsystemen, daarom is het nodig een model op te stellen van het netwerk met behulp van grafentheorie.

3.4.1

Toestandsmodel

Ieder fysisch systeem, gehoorzamend aan dynamische wetten, kan beschreven worden door een toestandsmodel (3.1). Dit wiskundig model drukt uit hoe vooropgestelde toestandsvariabelen en systeemuitgangen zich gedragen in functie van de systeemingangen en dit aan de hand van eerste orde differentiaalvergelijkingen. Bij ieder vlieguig binnen een zwerm hoort dus een toestandsmodel.  x(t) ˙ = f (x(t), u(t)) x(t) ∈ Rm , u(t) ∈ Rn (3.1) y(t) = h(x(t)) x(t) en u(t) zijn respectievelijk de toestands- en en sturingsvector van het deelsysteem. f (x(t), u(t)) is een gladde vectorfunctie die de dynamica van het systeem omvat. De uitgangsvector y(t) kan vrij gekozen worden, maar bevat meestal de te sturen toestandsvariabelen. Een groep van n UAVs kan gemodelleerd worden in e´ e´ n toestandsmodel met toestandsvector x(t) = [x1 (t)T x2 (t)T . . . xn (t)T ]T

(3.2)

met xi (t) (i = 1 . . . n) de toestandsvector van de i-de agent. Een analoge redenering geldt voor de sturings- en uitgangvector. Het sturen van een systeem betekent het bepalen van de sturingsvector u(t). Bij een alleenstaand systeem zal deze afhankelijk zijn van eigen toestandsvariabelen, systeemuitgangen of ¨ zelf verkregen meetgegevens. Bij cooperatieve sturing zal deze ook functie zijn van informatie, verkregen van andere agenten uit de groep, als resultaat van onderlinge communicatie.


3.4.2

16

Communicatie

Al sinds de oorsprong van verdeelde robotica wordt intensief studie gevoerd naar het communicatieve aspect in multi robot systemen. Communicatie tussen robots kan opgedeeld worden in twee categorieën ((Klein, 2005)): • Expliciete communicatie: robots zenden en ontvangen rechtstreeks nuttige informatie van andere robots in het team. • Impliciete communicatie: robots leiden informatie af uit de veranderingen die aanwezig zijn in de omgeving of winnen informatie als neveneffect uit de acties van andere teamleden. Al snel werd ondervonden dat zelfs een minieme informatie-uitwisseling binnen een groep grote voordelen kan opleveren. Recent wordt dan ook meer bestudeerd wat de nodige communicatie in een MAS is om een bepaalde robuustheid en betrouwbaarheid te verzekeren in de aanwezigheid van fouttoleranties op de communicatie (Fax & Murray, 2004). Om te bestuderen hoe communicatie tot stand komt binnen een groep of hoe informatie gedeeld, kan inzicht verworven worden in de grafentheorie.

3.4.3

Grafentheorie

Bij het bestuderen en analyseren van allerhande netwerken is het onontbeerlijk gebruik te maken van grafentheorie. Deze biedt een abstracte presentatie van een verzameling objecten die het netwerk uitmaken en de eventuele interconnecties. De eigenschappen van zo’n graaf helpen conclusies te trekken in verband met het netwerk en oplossingen te formuleren, het wiskundig vraagstuk ’De zeven bruggen van Koningsbergen’ is hier e´ e´ n van de oudste en meest gekende voorbeeld van. Ook bij de aanvang van de studie in verband met gedecentralizeerde sturing in de jaren ’70, werd al snel gebruik gemaakt van graaftheoretische ideeën bij het voorstelling van een multi agent system. Hoewel hieromtrend reeds genoeg informatie te vinden is in de literatuur (Ilaya et al., 2008; Ren et al., 2008; Ren & Sorensen, 2008; Fax & Murray, 2004), wordt toch kort ingegaan op de basis van de grafentheorie en de toepassing op multi agent systems. Een gerichte graaf G = (V, E) bestaat uit een eindige en niet-ledige verzameling knopen V = (Vi , i ∈ I), die elk een agent van het netwerk voorstellen en een verzameling geordende paren E ⊂ V 2 , die we takken noemen. Een tak (i, j) in een gerichte graaf betekent dat knoop Vj informatie ontvangt van knoop Vi en niet noodzakelijk omgekeerd. Vi definieren we als de ouderknoop en Vj als de kindknoop. Een ongerichte graaf is een speciaal geval van een gerichte graaf waarbij voor elk geordend paar (i, j) ∈ E ook (j, i) ∈ E. We noemen een graaf ’compleet’ als (i, j) ∈ E, ∀i, j ∈ I, i 6= j. Een gericht pad binnen de graaf G is een opeenvolging van takken (Ai1 , Ai2 ), (Ai2 , Ai3 ), . . .. Een graaf noemen we sterk verbonden wanneer er een gericht pad bestaat van Ai naar Aj en van Aj naar Ai , ∀i, j ∈ I, i 6= j. Een gerichte boom is een gerichte graaf waar iedere knoop juist e´ e´ n ouderknoop bezit, met uizondering van e´ e´ n knoop. Deze noemen we de wortel van de boom en vanuit deze knoop vertrekt een gericht pad naar


17

elke andere knoop van de graaf. Een gespannen boom van een gerichte graaf is een gerichte boom die alle knopen van die graaf bevat. We zeggen dat een graaf een gespannen boom bevat wanneer een deelverzameling van alle takken een gespannen boom vormen. De matrix A = (aij ) ∈ n × n is de matrixvoorstelling van de gerichte graaf G = Λ(A) en is gedefiniëerd door aii = 0 en aij > 0 ⇔ (i, j) ∈ E. Wanneer aij waarden aanneemt verschillend van 0 of 1, noemen we de graaf gewogen. A = (aij ) wordt ook wel de bogenmatrix genoemd. Voor de bogenmatrix van een gewogen ongerichte graaf geldt logischerwijs: aij = aji , ∀i 6= j. De Laplaciaan van een graaf is de matrix L = lij , met P lii = i6=j aij lij = −aij , i 6= j Hieruit leiden we af dat lij ≤ 0, i 6= j en

Pn

j=1 lij

(3.3)

= 0, i = 1 . . . n.

De Laplaciaan van een ongerichte graaf is symmetrisch positief definiet, van een gerichte graaf niet. Wel geldt voor beide dat 0 steeds een eigenwaarde van de Laplaciaan is met 1 (kolomvector) als eigenvector. Andere eigenwaarden zijn bij een ongerichte graaf altijd positief. Bij een gerichte graaf bezitten ze allemaal een positief reëel deel. Als en slechts als 0 een enkelvoudige eigenwaarde is van L, bevat de gerichte graaf een gespannen boom. Een graaf wordt rigid of stijf genoemd wanneer de enige mogelijke bewegingen binnen de graaf een translatie of rotatie van de volledige graaf zijn. Er bestaan verschillende hulpmiddelen om stijfheid van een graaf te analyseren. Er kan een stijfheidsmatrix opgesteld worden waarbij de dimensie en de rang informatie verschaffen in verband met de stijfheid. Een andere methode is het theorema van Laman (Anderson et al., 2008). Verder is een graaf minimaal stijf wanneer het wegnemen van eender welke tak een verlies van stijfheid betekent. Een nodige voorwaarde hiervoor is dat |E| = 2|V | − 3. Een minimale stijve formatie van UAV’s biedt geen weerstand tegen het wegvallen van een sensor of communicatieve link. In de praktijk zal dus steeds een zeker robuustheid gewenst zijn. (Fax & Murray, 2004) gaat dieper in op de besluiten die kunnen getrokken worden aan de hand van karakteristieken van de Laplaciaan. (Ren & Beard, 2005) bestudeert het bekomen tot consensus als de graaf dynamisch is, wat wil zeggen dat de verzameling van takken verandert in de tijd. (Yu et al., 2007) behandelt het modelleren van formaties in 3 dimensies.


3.5

18

Sturing

Eens een model opgesteld van het systeem kan tot een nadere beschrijving van de sturing ¨ overgagaan worden. Cooperatieve sturing is een heel ruim begrip. Iedere berekening van controlevectoren u(t) wordt met de term ’sturing’ bestempeld. Als u(t) daarenboven functie is ¨ van toestandsvariabelen van andere agenten, is de sturing ’cooperatief’. Hoe de sturingsvector bekomen wordt staat dus vrij en dit kan op verschillende manieren.

3.5.1

Gecentraliseerde vs. gedecentraliseerde sturing

Beschouwen we de graaf G = (V, E) die de zwerm UAVs voorstelt, dan stroomt informatie van agent Ai naar agent Aj als (i, j) ∈ E. We noemen agent Ai een buur van agent Aj . De verzameling buren van een agent Aj noemen we Ni . Per definitie is een sturingsstrategie gecentraliseerd als ui (t) = f (xj | j 6∈ Ni )

(3.4)

Met andere woorden, de sturingsvector is afhankelijk van toestandsvariabelen van een agent die geen buur is van Ai . Bij een gedecentraliseerde sturing daarentegen geldt ui (t) = f (xj | j ∈ Ni )

(3.5)

¨ Bij een gecentraliseerde sturing gebeurt de cooperative controle dus niet in de agent zelf, maar op een locatie waar alle informatie van het systeem beschikbaar is. Dit kan in een grondstation zijn of in een agent die buur is van alle teamleden. Deze situatie is echter niet realistisch en bovendien uiterst kwetsbaar, het mis functioneren van de centrale unit betekent compleet verlies van controle. Decentralisatie biedt robuustheid, maar door onvolledige kennis van het systeem, zijn sturingen sub-optimaal.

3.5.2

Leiderschap vs. virtueel leiderschap

Een zwerm die gemodelleerd wordt als een gerichte boom (sectie 3.4.3) voldoet aan het leidervolger type. De leider of de wortel, voert een taak uit zonder daarbij rekening te houden met de rest van de groep. Iedere andere UAV ontvangt informatie van e´ e´ n agent waarop beslissingen gebaseerd worden, zo worden leider-volger paren gevormd. De communicatie en rekenintensiteit wordt zo tot een minimum herleidt. Hetzelfde nadeel als bij gecentraliseerde sturing steekt wel de kop op. Het falen van e´ e´ n agent heeft zijn invloed verder in de keten (Shao et al., 2007; Swaroop, 1997). Een virtuele leider is een fictief punt binnen de groep die zich als leider gedraagt, dit kan het massamiddelpunt zijn van de groep of de locatie van een agent. Alle agenten zijn dan volgers


19

van die fictieve leider zodat wederom robuustheid ingebouwd wordt. Een nadeel aan deze aanpak is wel dat de virtuele leider zelf geen beslissingen kan nemen en bijgevolg niet kan inspelen op externe invloeden (zie 4.6).

3.5.3

Reactieve vs. predictieve sturing

In laatste jaren is een merkbare verschuiving opgetreden van reactieve naar predictieve sturing. Bij de eerste methode worden huidige en vorige metingen gebruikt bij het berekenen van de optimale sturing. De klassieke P(ID)-regelaar is hier een perfect voorbeeld van. Predictieve methodes zijn een meer geavanceerde techniek. Hierbij wordt vooraf een benaderend model van het te sturen systeem opgesteld door systeemidentificatie. Aan de hand hiervan en met kennis van de huidige toestand wordt een schatting gemaakt van toekomstige toestanden en uitgangen. De sturing is dan een iteratief proces waarin een kostenfunctie wordt opgesteld en een controleinput wordt gezocht die deze functie over een korte tijdspanne minimaliseert. Deze uitkomst wordt dan ogenblikkelijk toegepast op het echte systeem (Wise, 2006; Cai et al., 2007; Radu, 2008).

3.5.4

Gedragsgebaseerde sturing

Gedragsgebaseerde sturing laat een groot deel van de analyse, betrokken in vorige methodes vallen, en gaat uit van simpele gedragsalgoritmes (Ilaya et al., 2008). Deze eenvoudige maar efficiënte manier van sturen kent zijn oorsprong in de biologie, waar bestudeerd werd hoe een school vissen of een zwerm bijen zich verplaatsten. Elke lid van de groep gebruikt slechts lokale informatie bij het volgen van simpele gedragsregels. De meeste commmunicate gebeurt dan ook op impliciete wijze (sectie 3.4.2).

3.6

Tekortkomingen

Groepsgedragingen modelleren en controlleren is een heel complexe taak. Omdat in iedere situatie andere aspecten van belang zijn, is het moeilijk e´ e´ n sluitende sturingsmethode te ontwikkelen die voor meerdere opdrachten kan gebruikt worden. Iedere methode is daarom uiterst si¨ tuatiegericht. Bovendien staat cooperatieve sturing nog in zijn kinderschoenen. De vereenvoudigingen zijn meestal te simplistisch en onrealistisch. In de praktijk komen veel beperkingen ¨ voor die cooperatie bemoeilijken. Voorbeelden hiervan zijn meetruis en foutieve communicatie, maar ook onverwachte veranderingen in de omgeving. In een volgend hoofdstuk wordt onderzocht hoe flexibel sturingsalgoritmes zijn en hoe ze uitgebreid kunnen worden om ook bij levensechte beperkingen te blijven functioneren.

Hoofdstuk 4. Simulatie

20

Hoofdstuk 4

Simulatie 4.1

Inleiding

In dit hoofdstuk wordt een specifieke situatie voor ogen gehouden en een sturingsalgoritme ge¨ıntroduceerd. We kijken naar welke eigenschappen zo een algoritme bezit en wat mogelijke verschillen zijn. Wanneer een algoritme onmiddellijk ge¨ımplementeerd wordt in de vliegtuigen is er geen marge voor mislukking. Het falen van het algoritme betekent immers het verlies van e´ e´ n of meerdere UAVs. Ook zou op die manier optimaliseren van een sturingsmethode een tijdsconsumerende taak zijn. Daarom is het van primordiaal belang om tijdens de ontwikkelingfase software simulaties uit te voeren. Zo kan op een veilige manier aan foutopsporing en -reductie gedaan worden of stap voor stap een algoritme geoptimaliseerd worden zonder hardware in gevaar te brengen. In dit eindwerk worden Matlab en de Simulink omgeving gebruikt bij het opstellen, simuleren en evalueren van algoritmes. Algoritme Een algoritme is een reeks van instructies die ervoor zorgt dat vanuit een gegeven begintoestand een strikt omschreven doel bereikt wordt. In de toepassing van een zwerm UAVs vertaalt dit zich in een iteratief proces van logische beslissingen die de agenten in de zwerm dienen te nemen. M.a.w. een algoritme bepaalt een opgelegd denkproces voor de UAV. Om robuust en efficiënt te zijn dient in een algoritme bijgevolg rekening gehouden te worden met alle mogelijk scenario’s die kunnen optreden.

4.2

Omschrijving van de situatie

We kiezen ervoor een algoritme te ontwikkelen die een kleine groep vliegtuigen in staat stelt een onbekend gebied te verkennen. Hierbij wordt het massamiddelpunt van de groep als virtuele leider vooropgesteld en opgedragen dat deze een off-line berekend trajectorie volgt. Verder is het de bedoeling dat de UAVs een vooraf bepaalde formatie aanhouden. De keuze hiervoor is tweeërlei: • Sturingsalgoritmes voor een zwerm UAVs zijn ad hoc en moeilijk over verschillende situaties heen te veralgemenen. Het in formatie een gebied verkennen is dan de toepassing die nog het meest flexibiliteit bezit en toelaat om met e´ e´ nzelfde algoritme verschillende


21

gebieden aan te doen. Voor gelijkaardige gebieden is het soms mogelijk hetzelfde offline trajectorie te gebruiken, maar meestal wordt dit opnieuw opgesteld, aangepast aan de specifieke wensen. Dit is namelijk niet de meest rekenintensieve taak van het geheel, er dient enkel rekening gehouden te worden met de kinematische beperkingen van de UAVs, zoals maximale snelheid of turn rate. • Een goed sturingsalgoritme moet makkelijk op te schalen zijn. Dit wil zeggen dat de communicatie binnen een groep niet lineair mag stijgen met het aantal agenten. Het is relatief gemakkelijk om een formatie initieel te laten bestaan uit weinig agenten en zo reeds kwalitatieve besluiten te trekken in verband met het algoritme. Later worden dan stelselmatig agenten aan de formatie toegevoegd, zonder dat de eigenschappen van het algoritme verloren gaan. We introduceren een algoritme (Anderson et al., 2008) waarin een tweedimensionaal gebied verkend wordt door een niet-hiërarchische formatie van drie autonome UAVs. De vliegtuigen worden verwacht een constante onderlinge afstand te houden terwijl een virtuele leider in het massamiddelpunt een voorgeschreven pad volgt. Hierbij wordt verondersteld dat de UAVs tijdens het uitoefenen van de taak een constante snelheid aanhouden. De formatie start in het midden van een te verkennen zone en het pad van de virtuele leider vormt een Archimedische ¯ en in relatie ¨ spiraal. Deze kan geformuleerd worden in tijdsafhankelijke poolcoordinaten (r, θ) ¯ r sin θ). ¯ ¨ staan met de carthesische coordinaten (x, y) = (r cos θ, r(t) = bφ(t) ¯ θ(t) = φ(t) (mod 2π)

(4.1)

Hierin is b is een karakteristiek van de spiraal die beschrijft hoeveel de straal per omwenteling toeneemt. φ(t) is een monotoon stijgende functie die voldoet aan φ(0) = 0 en limx→∞ = ∞ en afhankelijk is van de (constante) snelheid van de UAVs b volgens de differentiaalvergelijking ˙ =p φ(t)

vc (bφ(t))2 + b2

(4.2)

Het controle algoritme betreft een gedecentraliseerde, niet-hiërarchische en asymmetrische sturing met gebruik van lokale informatie. Met andere woorden, de identieke, maar individuele sturing van elke agent bepaalt acties op basis van onvolledige informatie over het systeem. Ieder vliegtuig kent naast zijn eigen positie en richting ook de positie van e´ e´ n andere agent uit de groep en probeert als enige van dat paar de onderlinge afstand constant te houden. De volgorde is gekozen zodat die informatiestroom een cyclus vormt. Door het behouden van de gewenste onderlinge afstanden wordt formatie gegarandeerd. Verder is ook het te volgen trajectorie in de UAVs geprogrammeerd.


4.3

22

Eigenschappen van de UAV en de formatie

De UAV in de toepassing is de Aerosonde (figuur 4.1), ontwikkeld door Insitu en gebouwd door Aerosonde Ltd. De UAV is aangedreven door een verbrandingsmotor die 1.28 kW (1.74 pk) ontwikkelt. Aan boord is plaats voor een kleine computer en enkele meteorologische meetinstrumenten. Verder is een GPS ontvanger voorzien voor navigatie.

(a)

(b)

Figuur 4.1: Een afbeelding en een schematische schets van de Aerosonde

De Aerosonde heeft in zijn bestaan sinds 1998 reeds meerdere missies succesvol tot een eind gebracht. Zo slaagde een eerste generatie van de UAV er in, als eerste onbemande vliegtuig in de geschiedenis, een vlucht van 3 270 km over de Atlantische Oceaan te volbrengen. Verder werden ze al meermaals ingezet bij het penetreren van tropische cyclonen, een taak die logischerwijs niet weggelegd is voor bemande vliegtuigen. De voornaamste karakteristieken van de Aerosonde, zoals die gebruikt wordt in deze toepassing, zijn te vinden in tabel 4.1. Lengte Draagwijdte Hoogte Vleugeloppervlak Gewicht Bereik Plafond vnom vmax ωmax

1.7 m 2.9 m 0.6 m 0.57 m2 13.1 kg 3000 km 4500 m 32 m/s (115 km/u) 40 m/s (144 km/u) 0.08 rad/s

Tabel 4.1: Algemene karakteristieken van de Aerosonde

De formatie die we beogen is een gelijkzijdige driehoek met zijde d = 3000 m. De virtuele leider √ in het massamiddelpunt staat op een gelijke afstand d = dc / 3 tot de verschillende agenten.


23

Figuur 4.2 verduidelijkt deze situatie.

Figuur 4.2: Schematische voorstelling van de formatie

4.4

Uitwerking van een algoritme

Aangenomen wordt dat de UAVs zich met een constante snelheid vc = vnom in het vlak bewegen. De kinematica voor ieder van de agenten hiervoor is x˙ i (t) = vc cos(θi (t) y˙ i (t) = vc sin(θi (t) θ˙i (t) = ωi (t)

(4.3)

pi = (xi (t), yi (t)) is de positie en θi (t) en ωi (t) zijn respectievelijk de richting en de hoeksnelheid van agent Ai (i ∈{1,2,3}) op tijdstip t. De controller van agent Ai gebruikt als individuele sturingsingangen de locaties pi (t),pj (t) en p(t). Dit zijn respectievelijk de posities van zichzelf, de agent Aj die hij volgt en verwachtte positie van de de virtuele leider A0 . De te controleren systeeminput is ωi . Die tracht de richting van de UAVs naar een gewenste waarde te brengen met de PI-regelaar Z t ωi (t) = θ˙i (t) = kP [θid (t) − θi (t)] + kI [θid (t) − θi (t)] dt (4.4) t0

θid (t) is de gewenste richting die als volgt wordt bepaald: - Vooreerst zoeken we het punt pid (t), die op afstand d van pj (t) en op astand dc van p(t) ligt. pid (t) = arg min {kp − pi (t)k | p ∈ C(p(t), dc ) ∩ C(pj (t), d)} (4.5) waar C(m, r) de notatie is van een cirkel met middelpunt m en straal r. We veronderstellen in eerste instantie dat het punt pid (t) bestaat. - θid (t) is dan

 ∠(p (t) − p (t)) i id θid (t) = ∠(p (t) − p (t − ∆)) id

i

if |eij | > i else

(4.6)

In woorden: de gewenste richting voor een UAV is deze van zijn huidige positie naar het dichtste snijpunt van de twee circkels C(p(t), dc ) en C(pj (t), d) als de separatiefout eij de tolerantieterm overschrijdt. Zoniet is phiid (t) evenwijdig met de richting waarin pid beweegt. ∆ is daarom een vaste delay-term.


24

Wanneer de UAVs perfect hun snelheid aanhouden, zullen de twee cirkels uit (4.5) steeds een snijpunt hebben. Om het hoofd te bieden aan afwijkende situaties, die we later in dit hoofdstuk zullen beschouwen, passen we aan.   ∠(pi (t) − p(t)) if kp(t) − pi (t)k < d − dc     ∠(p(t) − p (t)) if kp(t) − pi (t)k > d + dc i θid (t) = (4.7)   ∠(pid (t) − pi (t)) if |eij | > i     ∠(p (t) − pi (t − ∆)) else id

Hierin wordt geboden dat het vliegtuig Ai zich verwijderd van p(t) wanneer het te dicht bij de virtuele leider komt en richting p(t) vliegt wanneer het zich te ver van de virtuele leider bevindt.

4.5 4.5.1

Implementatie Bepaling van controller frequentie

Het beoogde systeem is hybride, wat betekent dat de continue dynamica of kinematica van de de UAVs gecombineerd worden met discrete dynamica van de controller. Aangezien deze thesis zich enkel concentreert op sturing op strategisch niveau, wordt de dynamica van alle inner loops verwaarloosd. De vliegtuigjes zijn verondersteld stapsgewijs van turn rate te kunnen veranderen, alsook bewegen de sturingsactuatoren zonder overgangsverschijnsel. We schrijven dit als τuav = τact = 0 (4.8) Deze vereenvoudiging is aanvaardbaar wanneer de tijdschaal van de sturing groot genoeg is. Het is belangrijk hiermee rekening te houden bij het kiezen van de controller frequentie. Een voldoende hoge frequentie is nodig om de fout op de te volgen richting te beperken. Bij hogere frequenties echter stijgt de rekenintensiteit en vallen de dynamica van het vliegtuig en de actuatoren niet meer te verwaarlozen. Een compromis sluiten is nodig. Een eerste stap in de simulatie is daarom het afwegen van de toegestane fout tegen het schenden van de vereenvoudiging (4.8).


25

Sample frequentie: 0.33 Hz Wanneer de sample periode te groot of de frequentie te klein gekozen wordt slagen de vliegtuigen er niet in de vooropgestelde spiraal te volgen alsook de formatie gaat verloren.

(a)

(b)

Figuur 4.3: sample periode 3 s

In een beginfase lijkt de formatie stand te houden en ook de virtuele leider volgt het pad op een treffelijke manier. Verder in deze thesis zoeken we een verklaring waarom deze situatie niet stabiel blijkt te zijn.


26

Sample frequentie: 0.5 Hz Bij kleinere frequenties wordt de formatie wel behouden terwijl de virtuele leider de Archimedische spiraal doorloopt. De fout op dit trajectorie of de onderlinge afstanden hebben logischerwijs een omgekeerd evenredig verband met de controller frequentie.

(a)

(b)

Figuur 4.4: sampleperiode 2 s


27

(a)

(b)

Figuur 4.5: sampleperiode 1 s

Sample frequentie: 1 Hz


28

(a)

(b)

Figuur 4.6: sample periode 0.5 s



29

(a)

(b)

Figuur 4.7: sample periode 0.25 s



30

Ovezicht Figuren 4.4 tot 4.7 tonen de simulatie van de eerste 700 s van de missie en dit voor verschillende waarden van de controller frequentie. Tabel 4.2 geeft een overzicht van de rmswaarden van de fout op het trajectorie epath en op de onderlinge afstanden eij . sample freq. [Hz]

epath [m]

eij [m]

0.5 1 2 4

101.10 33.51 11.86 3.955

88.78 48.86 23.53 5.462

Tabel 4.2: rms-waarden van de fout op epath en eij

De tijdsconstante in de dynamica van sturingsactuators bedraagt doorgaans enkele milliseconden. Bij het hanteren van bovenstaande controller frequentie mag die zonder schroom verwaarloosd worden. Het kiezen voor nog grotere controller frequenties leidt misschien wel tot een verdere reductie van de fout, maar in de praktijk zijn zo’n grote nauwkeurigheiden niet geëist. Bovendien stijgt de rekenintensiteit van het algoritme lineair met de controller frequentie zodat deze niet te groot gekozen mag worden. In het verder verloop van de thesis wordt een frequentie van 2 Hz of dus een periode van 0.5 s verondersteld.

4.5.2

MATLAB vs. Simulink

¨ Deze eerste simulatie werd bekomen na implementatie van het cooperatieve sturingsalgoritme in een MATLAB programma die terug te vinden is in bijlage A. De for-lus wijst op het iteratieve karakter van het algoritme. Een tweede mogelijkheid om het systeem te simuleren is het bouwen van een model in Simulink. Dit is een toolbox binnen Matlab die het via een Graphical User interface mogelijk maakt dynamische modellen grafisch voor te stellen. Hierbij wordt gebruik gemaakt van een uitgebreide bibliotheek aan voorgeprogrammeerde functieblokken. Hoewel in een Matlab programma duidelijker te zien is wat de opeenvolgende stappen of beslissingen in het algoritme zijn, geniet modelleren in Simulink de voorkeur. Deelsystemen en eventuele (terug)koppelingen zijn hierin immers makkelijk te onderscheiden. In bijlage B wordt het Simulink model en zijn deelsystemen nader toegelicht.

4.6

Analyse

Voorgesteld algoritme behandelt een groep vliegtuigen in een zeer specifieke situatie. In wat ¨ volgt evalueren we hoe dezelfde cooperatieve sturingsmethode flexibel staat tegenover afwijkende situaties. We maken kwalitatieve besluiten en ontwikkelen een nieuw algoritme die weerstand biedt aan zulks situatieveranderingen.

4.6.1

Flexibiliteit t.o.v trajectorie

De Archimedische spiraal is e´ e´ n mogelijk pad die de formatie van UAVs kan volgen. We onderzoeken of ook andere trajectories in aanmerking komen voor het toepassen van vooropgesteld


31

algoritme. Hierbij beperken we ons tot gladde paden die de kinematica van de UAVs niet schenden. Veronderstellend dat een gladde functie gezien kan worden als een opeenvolging van cirkelbogen, volstaat het te controleren of de formatie iedere cirkelboog kan volgen. Intu¨ıtief hebben we hier reeds een antwoord op klaar. De Archimedische spiraal is niets meer dan een functie met monotoon stijgende kromtestraal. Als deze kan gevolgd worden, kunnen ook andere gladde functies als trajectorie gebruikt worden. We zien dit bevestigd in figuur 4.8 tot 4.11 waar de formatie langsheen cirkelbogen van verschillende straal gestuurd wordt.

Figuur 4.8: Cirkelboog met straal 5000 m


32




33


We besluiten dat het mogelijk is een willekeurig trajectorie te volgen terwijl formatie behouden blijft. Dit trajectorie moet echter wel voldoen aan de beperkingen op de kinematica van de UAVs. Bij wijze van voorbeeld testen we dit op een willekeurig pad (figuur 4.12).

Figuur 4.12: Volgen van willekeurig traject


4.6.2

34

Flexibiliteit t.o.v. formatie

In (Anderson et al., 2008) is gewenst dat de vliegtuigen in formatie op relatief grote afstand van elkaar blijven. Dit teneinde een accurate lokalisatie van doelen op de grond te verkrijgen. In andere toepassingen kan het zijn dat de vliegtuigen veel dichter bij elkaar dienen te blijven. Dit biedt voor het beschouwde algoritme geen probleem.

Figuur 4.13: Traject volgen in kleinere formatie

4.6.3

Flexibiliteit t.o.v. meetfouten en ruis

Een foutloze meting is nooit mogelijk en ook het aansturen van actuatoren gebeurt niet op een perfecte manier. Steeds hebben we te maken met ruis. In het Simulink model bouwen we Gaussiaanse onzekerheden in voor de meting van positie en van richting en besluiten na simulatie dat voldoende kleine variaties in het ruis de missie niet verstoren. Om nauwkeurige meetgegevens te verkrijgen in de aanwezigheid van ruis bestaan bovendien technieken zoals het toepassen van Kalman filters of Monte Carlo methodes. Hiervoor verwijzen we naar de literatuur (lit verw)

4.6.4

Flexibiliteit t.o.v. omgeving

Er werd aangetoond dat huidig sturingsalgoritme een ruime variëteit aan a priori vastgelegde paden kan volgen. Kennis in verband met de omgeving speelt hierin wel een cruciale rol. Wanneer reeds op voorhand statische obstakels of te ontwijken zones gekend zijn, is het mogelijk de off-line trajectorie in functie hiervan aan te passen. In de praktijk is dit jammer genoeg haast nooit het geval. Aanwezigheid van dynamische of onverwachte obstakels kunnen nefast zijn voor de UAVs. Het algoritme in zijn huidige vorm stelt de volledige formatie of de individuele


35

UAVs niet in staat correct te reageren op veranderingen in de omgeving. We zoeken daarom naar een mogelijkheid tot verbetering.

4.7

Uitbreiding

Het behandelde gedragsgebaseerde algoritme bewijst zijn dienst in de situatie waarvoor het ontworpen is: het volgen van een willekeurig, maar off-line bepaald trajectorie zonder onzekerheden in de omgeving, metingen of aansturingen. In dit hoofdstuk wordt een nieuw sturing ontworpen die wel bestand is tegen deze onverwachte gebeurtenissen. Hierbij concentreren we ons op het ontwijken van obstakels.

4.7.1

Aanpassing van controleoutput

Uit sectie 4.4 leren we dat ωi de systeeminput is die door de PI-regelaar gecontroleerd wordt. Deze zorgt ervoor dat de richting van iedere UAV convergeert naar een wenswaarde die hem naar het punt brengt op afstand d van een te volgen agent en op afstand dc van de virtuele leider in het massamiddelpunt. Hierbij wordt geen rekening gehouden met de eventuele aanwezigheid van obstakels. We voegen aan de regelaar een extra term ωobst toe, die aan de hand van real-time verkregen informatie in verband met obstakels, de hoeksnelheid van de systeeminput ω wijzigt. Hierbij nemen we in acht dat • Een UAV wegens de beperkingen op zijn hoeksnelheid op de hoogte moet zijn van de aanwezige obstakels in een voldoende groot gebied rondom zich. • Een UAV sneller dient weg te draaien van een nabij obstakel dan van een verafgelegen. • Een UAV niet te snel mag beslissen weg te draaien van een obstakel. Het kan immers zijn dat het originele algoritme daar reeds voor zorgt. • Een UAV enkel dient weg te draaien van een obstakel als hij er naar toe vliegt en niet als het obstakel zich verwijdert. • Een UAV sneller dient weg te draaien hoe sneller het vliegtuig het obstakel nadert. en stellen voorop dat het dubbele van de maximale hoeksnelheid bereikt wordt wanneer de UAV op 400m recht naar het obstakel vliegt. De keuze om twee keer voor de maximale hoeksnelheid te kiezen volgt uit het feit dat een vliegtuig dat bij het volgen van zijn gewenste richting gevraagd wordt maximaal naar links te draaien ook in staat moet zijn naar rechts te draaien bij het uitwijken voor een obstakel. De veiligheidszone van 400m is de straal van de kleinst mogelijke draaicirkel van de UAV. rmin = vnom /ωmax = 400 m

(4.9)


36

We besluiten: ωobst

  − θobst − θi 2ωmax rmin cos(θobst − θi ) kθobst − θi k dobst =  0

if dobst < 500m

(4.10)

else

waarin dobst en φobst respectievelijk de afstand en de richting van agent Ai tot het obstakel zijn. We gaan ervan uit dat de UAVs 500m ver kunnen ’zien’ Hoewel met de invoering van deze aangepaste systeeminput het botsen met obstakels vermeden wordt, biedt dit geen waterdichte oplossing voor ons probleem. Namelijk: • Het trajectorie dat het massamiddelpunt dient te volgen is tijdsafhankelijk. Dit houdt in dat op ieder tijdstip t een gewenste positie p(t) = (x(t), y(t)) van de virtuele agent voor ogen gehouden wordt. Deze opeenvolging van punten wordt a priori in de UAV geprogrammeerd en houdt geen rekening met eventuele obstakels onderweg. • Wanneer de bijkomende ωobst een UAV ertoe dwingt zijn originele richting te wijzigen om een collisie te vermijden, zullen ook de andere agenten hierop reageren. De huidige positie van e´ e´ n agent bepaalt namelijk de gewenste positie een andere. • Bij een geslaagd manoeuvre rond een obstakel zullen alle agenten in meer of mindere mate extra afstand afgelegd hebben die niet in het volgen van het trajectorie begrepen zat. Ondertussen heeft de gewenste positie van het massamiddelpunt zich wel verder verplaatst. Conclusie: door de tijdsafhankelijkheid van de gewenste trajectorie wordt er geen rekening gehouden met eventuele omwegen die UAVs afleggen bij het manoeuvreren. Aangezien die achterstand niet in te halen valt is het onmogelijk voor de virtuele agent om zijn gewenste positie in te nemen. En hoewel de aard van het algoritme er voor kan zorgen dat de formatie hersteld wordt, zal het massamiddelpunt niet het gewenste pad volgen.

Dit zien we verduidelijkt in figuur 4.14 Het algoritme stuurt de UAV naar die posities zodat formatie behouden blijft, maar de achterstand van de virtuele leider op zijn referentiepad resulteert in het weglopen van de formatie. In feite trachten de UAVs afstand goed te maken door als het ware een hoek af te snijden. Bij paden met een grote kromtestraal is dit echter onbegonnen werk: de formatie komt niet terug naar zijn gewenste pad.


37

Figuur 4.14: Onstabiliteit van het algoritme in aanwezigheid van obstakels

Om diezelfde reden leidt een te kleine controller frequentie (sectie 4.5.1) ook tot falen van de opdracht. We stellen twee manieren voor om dit probleem op te lossen en bekijken welke haalbaar is in deze situatie.

4.7.2

Dynamisch pad

Het idee achter het volgen van een dynamisch pad is dat in de buurt van een geometrisch traject gebleven wordt en niet noodzakelijk dichtbij een a priori gespecificeerd punt. Met andere woorden, de vorm van het pad ligt vast, maar de snelheid waarmee dit pad doorlopen wordt niet. Deze wordt bepaald in functie van een fout-terugkoppeling, in dit geval de afstand van de virtuele leider op gewenste positie. Hiervoor moet de referentiebaan geparametriseerd worden. p(t) = (x(s(t), y(s(t))) (4.11)

dp(s

Waar s ∈ R een functie is van de tijd en de baan glad is a.s.a.

ds 6= 0 voor alle s De snelheid s˙ waarmee het dynamisch pad doorlopen wordt is dan s˙ = vc e−a δ(t) waar vc de constante snelheid is van de UAVs, a > 0 en δ(t) = kp0 (t) − p(t)k. Dit zorgt ervoor dat het trajectorie bij wijze van spreken wacht op de virtuele leider.

(4.12)


38

Het grote struikelblok van deze methode is dat iedere agent op ieder ogenblik de positie van de virtuele leider p0 (t) moet kennen om te berekenen hoe die zijn referentiebaan evolueert. Die positie is functie van de posities van alle agenten in het systeem. p0 (t) =

i=1 pi (t)

P3

3

(4.13)

Hoewel het in de beoogde situatie weinig moeite vergt communicatie te voorzien tussen drie individuele agenten, ligt dat anders bij zwermen van een grotere schaal. Bovendien is het in strijd met de eigenschap van gedragsgebaseerde sturing dat enkel lokale informatie gebruikt wordt bij het nemen van individuele beslissingen.

4.7.3

Snelheidsregelkring

Een simpele maar efficiënte manier om achterlopen van de virtuele leider tegen te gaan, is het inbouwen van een individuele en onafhankelijke snelheidsregelkring per UAV. We ontwikkelen de mogelijkheid om de snelheid van een UAV in beperkte mate en voor een korte tijd te laten stijgen. Hierbij mag natuurlijk enkel gebruik gemaakt worden van de beschikbare informatie. Expliciete informatie: - De eigen positie pi (t) en richting θi - De positie van e´ e´ n andere agent pj (t) - De gewenste positie van de virtuele leider p0 (t) Impliciete informatie: - De positie van het punt pid (zie (4.5)) - De richting θid en de afstand ρid van pi naar pid Uit simulatie leren we dat bij afwezigheid van obstakels afstanden ρi d < 100 m gangbaar zijn en niet noodzakelijk leiden tot verlies van formatie. We stellen voorop dat bij waarden van ρid ≥ ρcrit = 100 m de snelheid van de agent Ai kan opgedreven worden volgens ρd − ρcrit τv v = vnom + (vrec − vnom ) e −

(4.14)

vnom is de snelheid die in ongehinderde toestand aangehouden wordt en vrec de maximale snelheid die mag gevlogen worden tijdens het recupereren van achterstand. Ten slotte is τv een karakteristiek die bepaalt hoe snel v stijgt met stijgende ρid .


39

Figuur 4.15 toont het verloop van deze snelheidsvariatie in functie van rhoid voor vnom = 32 m/s, vrec = 35 m/s en τv = 200 m.

Figuur 4.15:

4.7.4

Toepassing

Obstakels kunnen van uiteenlopende aard zijn: - Statisch of dynamisch - Variabele vorm - Variabele grootte In deze thesis beschouwen we steeds cirkelvormige obstakels. Verder wordt onderscheid gemaakt tussen twee klassen: - Obstakels die het pad van hoogstens e´ e´ n UAV tegelijk storen. Dit is het geval wanneer de obstakels relatief klein zijn ten opzichte van de formatie. Hierbij is een individueel uitwijkmanoeuvre voldoende. - Obstakels die meerdere UAVs in de formatie tegelijk stoort. Dit is het geval wanneer de obstakels relatief groot zijn ten opzicht van de formatie en hiervoor is een collectief uitwijkmanoeuvre nodig. Figuur 4.16 toont een voorbeeld uit elk van deze klassen. Beide obstakels zijn even groot, maar relatief ten opzichte van de schaal van de formatie, is er een duidelijk verschil.


40

(a)

(b)

Figuur 4.16: De twee beschouwde klassen van obstakels

De voornaamste zorg is nu het bepalen van de snelheid vrec . Bij het nemen van deze beslissing zijn meerdere aspecten van belang. - Het opdrijven van de snelheid tijdens of na het ontwijken van obstakels gaat natuurlijk gepaard met een energiekost. Hoewel in de praktijk steeds een regelkring voor de snelheid voorzien is ni de sturing van een UAV, is toch aangewezen voorzichtig om te springen met die mogelijkheid en ze tot een minimum te beperken. - Echter, het is economischer om de UAV gedurende een korte periode snel achterstand te laten inhalen dan aan een lagere snelheid de achtervolging lang te rekken. - Verder zullen UAVs die in een omgeving opereren met een grote waarschijnlijkheid aan obstakels, over een grotere recuperatiesnelheid dienen te bezitten dan wanneer obstakels maar uitzonderlijk voorkomen. Eén aanpak is om tot een besluit te komen is het opstellen van een totale kostenfunctie, waarin zowel rekening gehouden wordt met de kost van versnellen, penalisatie op achterstand en een onzekerheid over aanwezig obstakels. Het is een complexe zaak om die te vinden die te vinden.


41

Een tweede aanpak is het schatten van de gemiddelde omweg die een UAV zal maken en vrec hierop begroten. Een voorbeeld: het offline berekende trajectorie is x km en de kruissnelheid van de UAVs bedraagd vnom m/s.. Een schatting in verband met mogelijke obstakels vertelt ons dat δxkm omweg een reële bovengrens is. vrec kan dan vrec = vnom (1 +

δx ) x

(4.15)

veronderseld worden. Tabel 4.3 geeft enkele concrete bedragen op voor vrec , met vnom = 32m/s. δx x 5% 10% 15% 20% 25%

vrec 33.6 m/s 35.2 m/s 36.7 m/s 38.4 m/s 40 m/s

Tabel 4.3: Een overzicht van vrec in functie van de relatieve omweg

In wat volgt bekijken we het verschil in prestaties van de formatie voor verschillende inhaalsnelheden. De twee variabelen die we daarbij bestuderen zijn: - De afstand van de virtuele leider p0 (t) tot diens referentiepositie p(t) - Een grootheid die aangeeft hoezeer de formatie behouden blijft. Deze kiezen we als: ef orm (t) =

1X |kpi (t) − pj (t)k − d| 2 i6=j

(4.16)

= |kp1 (t) − p2 (t)k − d| + |kp2 (t) − p3 (t)k − d| + |kp3 (t) − p1 (t)k − d| Of in woorden, de som van de absolute waarden van de fouten op de onderlinge afstanden. epath is enkel gelijk aan nul als de formatie perfect gevormd is.


42

Stabiliteit van het algoritme en dus ook van de missie gaat hand in hand met de deze van bovenstaande grootheden. Herhalen we de situatie van figuur 4.14, dan merken we dat de formatie herstelt maar de achterstand niet (figuur 4.17).

Figuur 4.17: Achterstand van virtuele leider en fout op formatie bij constante snelheid


43

Kleine obstakel We veronderstellen de aanwezigheid van het obstakel uit figuur 4.16(a).

(a)

(b)

Figuur 4.18: De inhaalprestaties bij een individueel uitwijkmanoeuvre

Zonder het toepassen van de snelheidsregelkring verliezen de UAVs na ca. 275 s de formatie en reeds bij een kleine snelheidsverhoging wordt dit tenietgedaan. Hoe hoger de recuperatiesnelheid, hoe rapper de formatie hersteld wordt. Grote objecten We doen hetzelfde, maar nu bij het obstakel uit figuur 4.16(b)

(a)

(b)

Figuur 4.19: De inhaalprestaties bij een collecltief uitwijkmanoeuvre

We kunnen besluiten dat verhogen van de recuperatiesnelheid weinig tot geen invloed heeft op het herstellen van de formatie. Het inlopen van achterstand daarentegen wel natuurlijk.


4.7.5

44

Resultaat

Bij wijze van finaal resultaat kijken we hoe een formatie het ervan af brengt in een gebied, volgezaaid met obstakels. Hierbij stellen we vrec = 37 m/s voorop.

(a)

(b)

Figuur 4.20: Ontwijken van meerdere obstakels

Omdat het niet makkelijk te zien is waar de UAVs zich ten opzichte van elkaar bevinden, bekijken we ook het verloop van de onderlinge afstanden. Dit om te controleren of botsing tussen verschillende UAVs vermeden wordt.

Figuur 4.21: Onderlinge afstand tussen UAVs

De UAVs komen op geen enkel moment gevaarlijk dicht bij elkaar in de buurt. Simulatie toont aan dat het nieuwe algoritme, mits toevoeging van een snelheidsregelkring, in staat is om zowel obstakels te vermijden als formatie te herstellen en het te volgen trajectorie te hervatten.

Hoofdstuk 5. Conclusie

45

Hoofdstuk 5

Conclusie 5.1

Samenvatting

Reeds meer en meer worden onbemande voertuigen ingezet in opdrachten die te ’dull, dirty and dangereous’ zijn voor menselijke tussenkomst. Dit is vooral van toepassing bij militaire missies, in civiele doeleinden zijn streven naar veiligheid, maar ook drukking van arbeidskost en gemakzucht de grootste drijfveren in onderzoek naar autonome voertuigen. Deze thesis start met een overzicht te bieden hoe autonome systemen in de geschiedenis evolueerden en welke praktische toepassingen op heden reeds bestaan. In afgelopen jaren is interesse gegroeid om deze autonome voertuigen te laten samen werken in groep. Niet enkel om tijd te besparen of efficiëntie van een opdracht te laten stijgen, ook om robuustheid te bieden aan het systeem. Deze thesis concentreert zich op een zwerm UAVs ¨ en in het specifiek op het behouden van een stijve formatie. Hiervoor is een cooperatieve sturing nodig die de relatieve posities van de UAVs controleert, maar ondertussen ook de globale opdracht tot een goed einde brengt. In een tweede hoofdstuk bespreekt de thesis de verschillende methodes die zich hiertoe lenen, rekening houdend met de communicatiemogelijkheden, hieärchieën en architecturen binnen de zwerm. We besluiten dat een sturing steeds situatiegericht is en moeilijk voor uiteenlopende toepassingen gebruikt kan worden. Daarom werken we in een volgend hoofstuk een concrete situatie uit waarin een kleine formatie een offline berekend trajectorie volgt. We testen het gedragsgebaseerde sturingsalgoritme op flexibiliteit ten opzichte van externe invloeden en zien in dat de grootste tekortkoming zich voordoet bij onzekerheid van de omgeving. Er wordt gezocht naar een mogelijkheid om in real-time op onverwachte veranderingen in de omgeving te reageren. Een toegevoegde regelaar voor het ontwijken van objecten wordt gecombineerd met een snelheidsregelkring. Deze laatste zorgt ervoor dat de formatie opgelopen achterstand kan recupereren. Simulatie van dit nieuw algoritme zorgt voor positieve resultaten.

Hoofdstuk 5. Conclusie

5.2

46

Verder onderzoek

Bij het beschouwen van een groep onbemande voertuigen in het algemeen en UAVs in het specifiek wordt veelal een sterk vereenvoudigd model opgesteld, zoals ook hier. De dynamica van de sturingsactuatoren en van de UAVs werd verwaarloosd en ruisloze metingen en sturingen werden verondersteld. Rekening houden met deze levensechte imperfecties is een volgende stap in het uitbreiden van het vereenvoudigd model naar een complexer, maar waarheidsgetrouwer model. Hoewel door gebruik te maken van gedragsgebaseerde sturing opschaling naar grotere formaties gemakkelijker wordt, dient hier nog expliciet onderzoek naar gevoerd te worden. Bij het verspreiden van informatie binnen een grote of sterk gespreide groep, dient rekening gehouden te worden met communicatiebereik, -vertraging en ruis. Bovendien zijn UAVs niet beperkt tot verplaatsingen in het horizontale vlak. De uitbreiding naar drie dimensies gaat gepaard met een verdubbeling van de vrijheidsgraden en werkt een complexer systeem, en dus ook complexere sturing, in de hand.

Bijlage A. MATLAB programma

Bijlage A

MATLAB programma De implementatie van het origineel algoritme in een MATLAB programma.

1 2 3 4

%Wauthier Christophe Masterthesis 2008-2009 %Cooperative control of a UAV-swarm %MATLAB Implementation of control algorithm %3 agents Ai, center of mass C follows spiral S

5 6 7 8 9

clear all close all clc global vc d dc duur b

∆

delay epsilon kp ki

10 11

tic %starts timer

12 13 14 15 16

vc=32; d=3000; dc=d/sqrt(3); duur=700;

%UAV speed %desired inter agent distance %desired distance agent - CM %simulation time

17 18 19 20 21 22

%declaration of spiral A b=6000/2/pi; ∆=0.25; %sample time t=([0:∆:duur])'; %time vector T=length(t); %length of time vector

23 24 25 26 27 28 29

%controller parameters delay=1; epsilon=30; kp=5; ki=0.0005; w_max=0.08;

%max turn rate of UAV's

30 31 32 33 34 35

%initial value of archimedean spiral S S_xi=[0]; %polecoord angle S_r=[0]; %polecoord radius S_x=S_r*cos(S_xi); %absis S_y=S_r*sin(S_xi); %ordinate

47

Bijlage A. MATLAB programma

36 37 38 39 40 41 42

%initial state of 3 agents and center of mass C A_x=d*[0 1/2 -1/2]; %absis A_y=dc*[1 -1/2 -1/2]; %sordinate A_phi=[0 0 0]; %heading C_x=mean(A_x); %absis of C C_y=mean(A_y); %ordinate of C

43 44 45 46 47 48 49 50 51

w=[0 0 0]; error=[0 0 0]; e_path=[0]; Ad_x=A_x; Ad_y=A_y; e_j=[0 0 0]; e_c=[0 0 0]; Ad_phi=[0 0 0];

%initial turn rate of agents %error of desired heading vs real heading %error of desired path vs real path %initial desired position=real position %error in interagent distance %error in distance between agent and desired position of C %initial desired heading

52 53 54 55

%start of algorithm after ∆ seconds flying with initial condiitios for i=2:T i %displays the evolution of time

56 57 58 59 60 61 62

%compute position of archimedean spiral = desired position of C S_xi(i)=S_xi(i-1)+vc*∆/sqrt((b*S_xi(i-1))ˆ2+bˆ2); S_r(i)=b*S_xi(i); S_theta(i)=mod(S_xi(i),2*pi); S_x(i)=S_r(i)*cos(S_xi(i)); S_y(i)=S_r(i)*sin(S_xi(i));

63 64 65 66 67 68

%compute real position of agents and C A_x(i,:)=A_x(i-1,:)+vc*∆*cos(A_phi(i-1,:)+w(i-1)*∆/2); A_y(i,:)=A_y(i-1,:)+vc*∆*sin(A_phi(i-1,:)+w(i-1)*∆/2); C_x(i)=mean(A_x(i,:)); C_y(i)=mean(A_y(i,:));

69 70 71

%compute the error of the virtual agent to his path e_path(i)=min(sqrt((C_x(i)-S_x).ˆ2+(C_y(i)-S_y).ˆ2));

72 73 74 75 76 77

%compute new turn rate for each agent for k=1:3 %search closest point on the two circles = desired position [Ad_x(i,k),Ad_y(i,k)]=snijpunt(A_x(i,k),A_y(i,k),... A_x(i,mod(k,3)+1),A_y(i,mod(k,3)+1),S_x(i),S_y(i));

78 79 80 81 82 83

%calculate the errors and the corresponding desired heading e_j(i,k)=sqrt((A_x(i,k)-A_x(i,mod(k,3)+1)).ˆ2+... (A_y(i,k)-A_y(i,mod(k,3)+1)).ˆ2)-d; e_c(i,k)=sqrt((A_x(i,k)-C_x(i)).ˆ2+... (A_y(i,k)-C_y(i)).ˆ2)-dc;

84 85 86 87 88

if (e_j(i,k)>epsilon) Ad_phi(i,k)=atan2((Ad_y(i,k)-A_y(i,k)),(Ad_x(i,k)-A_x(i,k))); else Ad_phi(i,k)=atan2((Ad_y(i,k)-Ad_y(i-delay,k)),... (Ad_x(i,k)-Ad_x(i-delay,k)));

48

Bijlage A. MATLAB programma end

89 90

%apply the PI controller with constraints on turn rate error_temp=mod(Ad_phi(i,k)-A_phi(i-1,k),2*pi); if error_temp
91 92 93 94 95 96 97

w_temp=kp*error(i,k)+ki*sum(error(:,k)); if abs(w_temp)<w_max w(i,k)=w_temp; else w(i,k)=sign(w_temp)*w_max; end A_phi(i,k)=A_phi(i-1,k)+∆*w(i,k);

98 99 100 101 102 103

end

104 105

end

106 107 108 109

%rms values of the errors fout1=sqrt(mean(e_path.ˆ2)); fout2=mean(sqrt(mean(e_j.ˆ2)));

110 111

1

chrono=toc;

%ends timer

%Calculates the position of p_id: the intersection of two circles

2 3 4

function [snij_x snij_y]=snijpunt(Ax1,Ay1,Ax2,Ay2,Sx,Sy) global d dc

5 6 7 8 9 10 11 12 13 14 15 16

afst_A_S=norm([Ax1 Ay1]-[Sx Sy]); if afst_A_Sd+dc snij_x=Sx; snij_y=Sy; else syms x y [x y]=solve((x-Ax2)ˆ2+(y-Ay2)ˆ2-dˆ2,(x-Sx)ˆ2+(y-Sy)ˆ2-dcˆ2); X=double(x); Y=double(y);

17

afst_temp=sqrt((Ax1-X).ˆ2+(Ay1-Y).ˆ2); [minim,pos]=min(afst_temp); snij_x=X(pos); snij_y=Y(pos);

18 19 20 21 22 23

end end

49

Bijlage B. Simulink model

Bijlage B

Simulink model

Figuur B.1: De implementatie van het origineel algoritme in een Simulink model

50

Bijlage C. Uitgebreid Simulink model

Bijlage C

Uitgebreid Simulink model

Figuur C.1: De implementatie van het nieuw algoritme in een Simulink model

51

Bibliografie

52

Bibliografie V. Adolfsson (2001). The State of the Art in Distributed Mobile Robotics. Master’s thesis, Blekinge Institute of Technology. B. D. Anderson, B. Fidan, C. Yu & D. van der Walle (2008). Uav formation control: Theory and application. W. Cai, L. Weng, R. Zhang, Z. Zhang & Y. Song (2007). Virtual leader based formation control of multiple unmanned ground vehicles (ugvs): Control design, simulation and real-time experiment. Advances in Cooperative Control and Optimization, pp. 221–230. P. Chandler, M. Pachter, D. Swaroop, J. Fowler, J. Howlett, S. Rasmussen, C. Schumacher & K. Nygard (2002). Complexity in uav cooperative control. Proceedings of the American Control conference, pp. 1831–1836. J. Fax & R. Murray (2004). Information flow and cooperative control of vehicle formations. IEEE Transactions on Automatic control, 49:1465–1476. F. Giulietti, M. Innocenti, M. Napolitano & L. Pollini (2005). Dynamic and control issues of formation flight. Aerospace Science and Technology, 9(1):65 – 71. ISSN 1270-9638. O. Ilaya, C. Bill & M. Evans (2008). Control design for unmanned aerial vehicle swarming. Proceedings of the Institution of Mechanical Engineers, Part G: Journal of Aerospace Engineering, 222:549–567. P. Jones, B. Ludington, J. Reimann & G. Vachtsenavos (2007). Intelleligent control of unmanned aerial vehicles for improved autonomy. European Journal of Control, 13:320–333. I. Kaminer, O. Yakimenko, V. Dobrokhodov, M. Lizarraga & A. Pascoal (2004). Cooperative control of small uavs for naval applications. D. Klein (2005). Controlled Collective Motion for Multivehicle Trajectory Tracking. Master’s thesis, University of Washington. T. Lam, editor (2009). Aerial Vehicles. In-Tech. K. Mathia, G. Lafferriere & T. Titensor (2007). Cooperative control of uav platoons - a prototype. Euro UAV 2007 Conference and Exhibition. T. McGeer (1999). Laima: the first atlantic crossing by unmanned aircraft.

Bibliografie

53

A. Mitrache (2007). Unmanned Aerial Vehicle Control Design. Master’s thesis, University of Ghent. R. Murray (2006). Recente research in cooperative control of multi-vehicle systems. Journal of Dynamic Systems, Measurement and Control. J. Nino (2007). Model Identification of a Micro Air Vehicle. Master’s thesis, University of Ghent. L. Parker (1998). Alliance: An architecture for fault tolerant multirobot cooperation. IEEE Transactions on Robotics and Automation, 14:220–240. M. Radu (2008). Unmanned Aerial Vehicles: Trajectory Tracking Control. Master’s thesis, University of Ghent. W. Ren & R. Beard (2005). Consensus seeking in multiagent systems under dynamically changing interaction topologies. IEEE Transactions on Automatic Control, 50:665–661. W. Ren, H. Chao, W. Bourgeous, N. Sorensen & Y.Chen (2008). Experimental validation of consensus algorithms for multivehichle cooperative control. IEEE Transactions on Automatic Control, 16:745–752. W. Ren & N. Sorensen (2008). Distributed coordination architecture for mulri-robot formation control. Robotics and Autonomous Systems, 56:324–333. D. Schoenwald (2000). Auvs: in space, air water and on the ground. IEEE Control Systems Magazine, 20:15–18. J. Shao, G. Xie & L. Wang (2007). Leader-following formation control of multiple mobile vehicles. IET Control Theory Applications, 1:545–552. R. Skjetne, I. Ihle & T. Fossen (2003). Formation control by synchronising multiple maneuvering systems. D. Stipanovic, G. Inalhan, R. Teo & C. Tomlin (2004). Decentralized overlapping control of a formation of unmanned aerial vehicles. Automatica, 40:1285–1296. D. Swaroop (1997). String stability of interconnected systems: an application to platooning in automated highway systems. K. Valavanis, editor (2007). Advances in Unmanned Aerial Vehicles: State of the Art and the Road to Autonomy. Springer. R. Wise (2006). Uav control and guidance for autonomous cooperative tracking of a moving target. V. Yatsenko, M. Hirsch & P. Pardalos (2007). Cooperative control of multiple agents and search strategy. Advances in Cooperative Control and Optimization, pp. 231–263. C. Yu, J. Hendrickx, B. fidan, B. Anderson & V. Blondel (2007). Three and higher dimensional autonomous formations: Rigidity, persistence and structural persistence. Automatica, 43:387– 402.

Bibliografie

54

H. Yuan, V. Gottesman, M. Falash, Z. Qu, E. Pollak & J. Chunyu (2007). Cooperative formation flying in autonomous unmanned air systems with application to training. Advances in Cooperative Control and Optimization, pp. 203–219.

Coöperatieve sturing van een zwerm onbemande vliegtuigen

Recommend Documents