1

Investete n oameni! FONDUL SOCIAL EUROPEAN Programul Operaional Sectorial Dezvoltarea Resurselor Umane 2007 2013 Axa prioritar 1 Educaie i formare profesional n sprijinul creterii economice i dezvoltrii societii bazate pe cunoatere Domeniul major de intervenie 1.5 Programe doctorale i post-doctorale n sprijinul cercetrii Titlul proiectului: Investiie n dezvoltare durabil prin burse doctorale (INED) Numrul de identificare al contractului: POSDRU/88/1.5/S/59321 Beneficiar: Universitatea Transilvania din Braov

Universitatea Transilvania din Brasov Scoala Doctorala Interdisciplinara

Centrul de cercetare: Sisteme pentru Controlul Proceselor

Ing. Ioana C. COBEANU

Strategii de coordonare n timp real a comportamentului

agenilor inteligeni mobili Real-time coordination

strategies of the intelligent mobile agents behaviour

Conductor tiinific Prof.dr.ing. Vasile COMNAC

BRASOV, 2012

2

MINISTERUL EDUCAIEI, CERCETARII, TINERETULUI I SPORTULUI UNIVERSITATEA TRANSILVANIA DIN BRAOV

BRAOV, B-DUL EROILOR NR. 29, 500036, TEL. 0040-268-413000, FAX 0040-268-410525 RECTORAT

D-lui (D-nei) ..............................................................................................................

COMPONENA Comisiei de doctorat

Numit prin ordinul Rectorului Universitii Transilvania din Braov Nr. 5364 din 29.08.2012

PREEDINTE: Prof. Univ. Dr. Ing. Sorin-Aurel MORARU

Universitatea Transilvania din Braov CONDUCTOR TIINIFIC: Prof. univ. dr. ing. Vasile COMNAC

Universitatea Transilvania din Braov REFERENI: Prof. univ. dr. ing. Clement FETIL

Universitatea Tehnic din Cluj-Napoca Prof. univ. dr. ing. Dorian COJOCARU

Universitatea din Craiova Prof. univ. dr. ing. Ioan MRGINEANU

Universitatea Transilvania din Braov Data, ora i locul susinerii publice a tezei de doctorat: 5 octombrie 2012, ora 09:00, sala V III 9, aflat la etajul 3 al corpului V al Universitii Transilvania din Braov, Str. Mihai Viteazul, nr. 5. Eventualele aprecieri sau observaii asupra coninutului lucrrii v rugm s le transmitei n timp util, pe adresa Departamentului de Automatic i Tehnologia Informaiei, Corpul V al Universitii Transilvania din Braov, Str. Mihai Viteazul, nr. 5, 500174, la numrul de fax al departamentului: 0268 418 836, sau pe adresa de email: ioana.cobeanu@unitbv.ro. Totodat v invitm s luai parte la edina public de susinere a tezei de doctorat. V mulumim.

3

CUPRINS Pg.Tez Rez. 1. INTRODUCERE .................................................................................................... 9..5

1.1 Obiectivele tezei .............................................................................................. 11 1.2 Structura tezei .................................................................................................. 12..7

2. SISTEME MULTI-AGENT .................................................................................. 15..9 2.1 Noiuni introductive ......................................................................................... 16 2.2 Arhitectura sistemelor multi-agent .................................................................... 19..9 2.3 Comunicaia n cadrul sistemelor multi-agent .................................................... 23 2.4 Domenii de utilizare ......................................................................................... 2710 2.5 Aplicaia propus ............................................................................................. 3010 2.6 Concluzii ......................................................................................................... 37

3. MODELAREA I SIMULAREA SISTEMELOR MULTI-AGENT .................... 3914 3.1 Noiuni introductive ......................................................................................... 40 3.2 Instrumente utilizate n modelarea i simularea sistemelor multi-agent ................ 40 3.3 Analiza comparativ a instrumentelor ............................................................... 4514 3.4 Platforma CoReMo .......................................................................................... 4716 3.5 Arhitectura platformei CoReMo ....................................................................... 4916 3.6 Concluzii ......................................................................................................... 55

4. PROCESAREA EVENIMENTELOR N CADRUL SISTEMELOR MULTI-AGENT .............................................................................................................................. 5718 4.1 Noiuni introductive ......................................................................................... 58 4.2 Arhitectura sistemelor bazate pe evenimente ..................................................... 5918 4.3 Procesarea evenimentelor complexe .................................................................. 6319 4.4 Evaluarea comparativ a platformelor CEP ....................................................... 6619 4.5 Utilizarea CEP n procesarea evenimentelor din cadrul sistemelor multi-agent .... 7220 4.6 Concluzii ......................................................................................................... 80

5. MODELAREA PROCESULUI DE DECIZIE ...................................................... 8324 5.1 Noiuni introductive ......................................................................................... 84 5.2 Modelul de alocare al activitilor agenilor ....................................................... 84 5.3 Procesul de decizie al agenilor inteligeni ......................................................... 9024 5.4 Concluzii ....................................................................................................... 104

6. STRATEGII DE COORDONARE N TIMP REAL ........................................... 10729 6.1 Noiuni introductive ....................................................................................... 108 6.2 Tehnici utilizate pentru realizarea coordonrii ................................................. 10929 6.3 Necesitatea coordonrii n cadrul sistemului multi-agent propus ....................... 11530 6.4 Strategia de coordonare n timp real propus ................................................... 11630 6.5 Evaluarea strategiei de coordonare .................................................................. 12233 6.6 Concluzii ....................................................................................................... 131

7. CONCLUZII ....................................................................................................... 13338 7.1 Contribuii personale ...................................................................................... 13641 7.2 Diseminarea rezultatelor ................................................................................. 13843

4

7.3 Direcii viitoare de cercetare ........................................................................... 13944 BIBLIOGRAFIE SELECTIV .............................................................................. 14144 ANEXA 1. IMPLEMENTAREA ALGORITMULUI DE DETECTARE N TIMP REAL A

INCIDENTELOR ............................................................................................... 151 ANEXA 2. IMPLEMENTAREA ALGORITMULUI DE PLANIFICARE A

COMPORTAMENTELOR AGENILOR MOBILI INTELIGENI ................ 153 ANEXA 3. IMPLEMENTAREA ALGORITMULUI DE REPLANIFICARE A

COMPORTAMENTELOR AGENILOR MOBILI INTELIGENI ................ 161 LIST DE FIGURI ................................................................................................ 167 LIST DE ABREVIERI ......................................................................................... 169 REZUMAT ............................................................................................................. 17347 ABSTRACT ........................................................................................................... 17547 CONTENT ............................................................................................................. 177 CURRICULUM VITAE ......................................................................................... 18148

CONTENT Pg. Tess. Sum. 1. INTRODUCTION .................................................................................................. 9..5

1.1 Thesis objectives ............................................................................................ 11 1.2 Thesis structure ............................................................................................... 12..7

2. MULTI-AGENT SYSTEMS ................................................................................. 15..9 2.1 Introduction ..................................................................................................... 16 2.2 Multi-agent systems architecture .................................................................... 19..9 2.3 Multi-agent systems communication ................................................................. 23 2.4 Areas of application ......................................................................................... 2710 2.5 Proposed application ........................................................................................ 3010 2.6 Conclusions ..................................................................................................... 37

3. MULTI-AGENT SYSTEMS MODELING AND SIMULATION ......................... 3914 3.1 Introduction ..................................................................................................... 40 3.2 Multi-agent systems modeling and simulation tools ........................................... 40 3.3 Tools comparison analysis ................................................................................ 4514 3.4 CoReMo Platform ............................................................................................ 4716 3.5 CoReMo platform architecture ......................................................................... 4916 3.6 Conclusions ..................................................................................................... 55

4. PROCESSING EVENTS IN MULTI-AGENT SYSTEMS ................................... 5718 4.1 Introduction ..................................................................................................... 58 4.2 Event based systems architecture .................................................................. 5918 4.3 Complex Event Processing ............................................................................... 6319 4.4 CEP platforms comparison analysis .............................................................. 6619 4.5 Using CEP for event processing in multi-agent systems ..................................... 7220 4.6 Conclusions ..................................................................................................... 80

5

5. DECISION PROCESS MODELING .................................................................... 8324 5.1 Introduction ..................................................................................................... 84 5.2 Scheduling ..................................................................................................... 84 5.3 Intelligent agents decision process ................................................................ 9024 5.4 Conclusions ................................................................................................... 104

6. REAL-TIME COORDINATION STRATEGIES ......................................... 10729 6.1 Introduction ................................................................................................... 108 6.2 Coordination techniques .............................................................................. 10929 6.3 Coordination necesity in proposed multi-agent system .............................. 11530 6.4 Proposed real-time coordination strategy ......................................................... 11630 6.5 Coordination strategy evaluation ..................................................................... 12233 6.6 Conclusions ................................................................................................... 131

7. CONCLUSIONS ................................................................................................. 13338 7.1 Personal contributions .................................................................................... 13641 7.2 Results dissemination .................................................................................... 13843 7.3 Further investigations ..................................................................................... 13944

SELECTIVE BIBLIOGRAPHY ............................................................................ 14144 APPENDIX 1. REAL-TIME DETECTION INCIDENTS ALGORITHM

IMPLEMENTATION ......................................................................................... 151 APPENDIX 2. MOBILE INTELLIGENT AGENTS PLANNING BEHAVIOUR

ALGORITHM IMPLEMENTATION ................................................................ 153 ANEXA 3. MOBILE INTELLIGENT AGENTS REPLANNING BEHAVIOUR

ALGORITHM IMPLEMENTATION ................................................................ 161 LIST OF FIGURES ................................................................................................ 167 LIST OF ABBREVIATIONS ................................................................................. 169 ABSTRACT ........................................................................................................... 17547 CONTENT ............................................................................................................. 177 CURRICULUM VITAE ......................................................................................... 18148

INTRODUCERE Aplicaiile de control fac parte din viaa fiecruia dintre noi. Ele pot fi ntlnite n cadrul

locuinelor (controlul temperaturii n camer utiliznd termostatul centralei de nclzire, controlul audio sau video n cazul sistemelor de supraveghere, etc.), pe strad (controlul traficului n intersecii, controlul modului n care sunt livrate produsele de ctre firmele de curierat, etc.), n halele industriale (controlul liniilor de producie, a modului de funcionare a roboilor, etc.), i exemplele pot continua. n cadrul acestor aplicaii se urmrete obinerea unei reacii la nivelul componentelor n timp real. De exemplu, n cazul aplicaiilor de control al traficului, n momentul detectrii unui incident, autovehiculele aflate n trafic trebuie s aib posibilitatea de a evita zona congestionat.

Complexitatea sistemelor care modeleaz aplicaiile de control depinde de numrul entitilor implicate n rezolvarea problemelor. O dat cu dezvoltarea reelelor wireless de senzori, a crescut foarte mult numrul nodurilor care pot fi conectate ntr-o reea. n acelai timp nodurile reelelor wireless pot fi rspndite pe suprafee spaiale mari. Aceast evoluie face ca

6

sistemele de control s cunoasc o cretere a complexitii, fiind necesar dezvoltarea de noi tehnologii pentru meninerea bunei funcionri a sistemelor [28].

Trendurile privind modul de dezvoltare al aplicaiilor de control sunt ca decizia s fie luat ct mai aproape de proces i ca reacia la stimuli multipli s fie realizat local.

Tehnologiile propuse n dezvoltarea sistemelor de control complexe trebuie s fac fa unor serii de provocri precum [28]: creterea flexibilitii sistemului (posibilitatea de a introduce noi entiti n sistem fr a fi necesar reproiectarea acestuia), creterea independenei fiecrei componente a sistemului, reacia componentelor n timp real, pstrarea robusteii sistemului, procesarea unui volum mare de informaii, etc..

Pentru a putea realiza provocrile enunate anterior au fost dezvoltate sistemele distribuite de control. Sistemele distribuite au fost introduse cu scopul de a elimina neajunsurile sistemelor centralizate precum dependena de o entitate decizional, entitile componente ale sistemelor centralizate nu prezint autonomie. Avantajele utilizrii controlului descentralizat sunt creterea autonomiei entitilor sistemului, buna funcionare a sistemului nu mai depinde de o unitate central.

Cercetarea realizat pe durata programului de doctorat a fost orientat pe utilizarea tehnologiei sistemelor multi-agent n dezvoltarea aplicaiilor de control. Tehnologia sistemelor multi-agent este utilizat cu succes n modelarea sistemelor distribuite. Prin construcia aplicaiilor distribuite utiliznd aceast tehnologie se mbuntete flexibilitatea sistemelor i capacitatea acestora de a rezolva situaiile neprevzute aprute n cadrul sistemului [53]. Sistemele multi-agent au cunoscut o mare rspndire n ultimii ani, fiind utilizate n aplicaii din diverse domenii. Exemple de astfel de domenii sunt: transport [47] [19], industrie [46], sntate [52] militare [43] etc.

n cadrul sistemelor multi-agent fiecare component este autonom. Agenii trebuie s decid ce operaie trebuie s execute pe baza informaiilor obinute din cadrul sistemului. n cazul sistemelor multi-agent cooperative agenii trebuie s duc la ndeplinire o sarcin global [6]. Sarcina global este mprit n subsarcini care trebuie realizate de fiecare agent. Problema care apare n aceste situaii este modul de coordonare a sarcinilor locale astfel nct s fie ndeplinit scopul global al sistemului. Aceste probleme sunt soluionate prin construcia unei strategii de coordonare. Prin realizarea coordonrii n cadrul unui sistem multi-agent se asigur faptul c fiecare subproblem a scopului global este inclus n activitatea unui agent. Agenii trebuie s i modeleze comportamentul astfel nct s poat duce la ndeplinire sarcina atribuit [29].

Coordonarea reprezint o problem foarte important n modelarea unui sistem multi-agent. n ultimii ani problema realizrii coordonrii n cadrul unui sistem multi-agent a prezentat un mare interes pentru cercettori. n lipsa unei strategii de coordonare definit n cadrul unui sistem multi-agent, ntregul sistem se comport haotic. Deciziile agenilor nu corespund strii actuale a sistemului putnd duce la apariia conflictelor ntre ageni (n momentul n care acetia vor s utilizeze aceeai resurs critic n acelai moment de timp) sau la nendeplinirea scopului la nivel local sau la nivel global.

Crearea unei strategii de coordonare n cadrul unui sistem multi-agent presupune coordonarea activitilor fiecrui agent. Pentru realizarea coordonrii au fost dezvoltate diferite tehnici, mecanisme sau protocoale. Principale tehnici utilizate n construcia coordonrii agenilor sunt prezentate n [6]. Acestea sunt tehnici bazate pe structuri organizaionale, planificarea activitilor, negociere, licitaie, sau pe percepia mediului la nivelul agenilor.

7

n alegerea unei tehnici de realizare a coordonrii ntr-un sistem multi-agent trebuie s se in cont de cerinele sistemului. Strategia de coordonare care face subiectul acestei teze are ca rol principal detectarea n timp real a situaiilor care pot influena comportamentul agenilor i luarea deciziilor la nivelul agenilor astfel nct acetia s i poat finaliza sarcinile atribuite n concordan cu noua stare a sistemului. Tehnica utilizat pentru a construi aceast strategie a fost planificarea, deoarece prin aceast tehnic se realizeaz evitarea aciunilor i interaciunilor conflictuale [6]. Prin utilizarea tehnicilor bazate pe negociere sau licitaie nu se realizeaz evitarea conflictelor i rezolvarea acestora.

Strategia de coordonare n timp real presupune procesarea unui volum mare de evenimente transmise n cadrul sistemului. Pe baza acestor evenimente trebuie s se realizeze detecia anumitor situaii neprevzute aprute n sistem. Acestea sunt acele situaii care pot afecta comportamentul agenilor mobili. Tehnologia utilizat trebuie s aib capacitatea de a procesa n timp real evenimentele, s poat asocia evenimentele cu momentul de timp la care au avut loc. Soluia propus a fost utilizarea tehnologiei CEP (Complex Event Processing). Utiliznd CEP se poate realiza detecia situaiilor neprevzute pe baza evenimentelor simple. Evenimentele simple sunt procesate n timp real i prin corelarea acestora n funcie de momentul apariiei, de informaiile coninute sunt generate evenimentele complexe. Prin evenimentele complexe este semnalat apariia unei situaii neprevzute.

Un alt aspect foarte important este modelarea procesului de decizie al agenilor. Decizia agenilor trebuie s fie generat ntr-un timp ct mai scurt, dar n acelai timp trebuie s reprezinte un rspuns ct mai apropiat de cel optim la situaia actual a sistemului. Deoarece problemele pe baza crora sunt generate deciziile sunt complexe probleme de optimizare, generarea soluiilor optime se realizeaz ntr-un timp ndelungat. Pentru modelarea procesului de decizie a fost propus spre utilizare programarea bazat pe constrngeri. Aceasta asigur o bun flexibilitate n modelarea problemelor, prin utilizarea acestei metode putndu-se rezolva probleme complexe de optimizare, putndu-se obine soluii ntr-un timp scurt care respect totalitatea constrngerilor definite nefiind neaprat cele optime. Deciziile agenilor sunt potrivite contextului actual al sistemului deoarece sunt generate ntr-un timp scurt i respect constrngerile din sistem.

Obiectivul principal al cercetrii n urma creia a fost dezvoltat teza l reprezint proiec-tarea, modelarea, implementarea i testarea unei strategii de coordonare n timp real n cadrul unui sistem multi-agent.

1.2 Structura tezei

n cadrul capitolului 1, Introducere, este prezentat importana utilizrii sistemelor multi-agent n rezolvarea aplicaiilor de control, problematicii coordonrii agenilor mobili inteligeni n cadrul sistemelor multi-agent i principalele obiective ale unei strategii de coordonare. n cadrul acestui capitol a fost enunat obiectivul principal i obiectivele specifice tezei de doctorat i structura acesteia.

Capitolul 2, Sisteme multi-agent, a avut ca prim scop scoaterea n eviden a principalelor avantaje ale utilizrii sistemelor multi-agent n modelarea i controlul a diferite aplicaii de control, tipurile de arhitecturi ale agenilor ct i ale sistemelor de acest tip i modul de realizare a schimbului de informaii n cadrul unui astfel de sistem. Un alt scop al acestui capitol este propunerea unei aplicaii de control a traficului care a fost dezvoltat cu scopul de a testa strategia de coordonare propus. Tot aici a fost prezentat i arhitectura sistemului multi-agent utilizat n modelarea i controlul acestei aplicaie i motivele alegerii fcute.

8

n vederea modelrii i simulrii sistemului multi-agent propus, n cadrul capitolului 3, Modelarea i simularea sistemelor multi-agent, este realizat o analiz comparativ a platformelor de modelare i simulare a sistemelor multi-agent. Analiza comparativ a avut ca obiect patru astfel de platforme: JADE (Java Agent Development Environment), MatSim (Multi-Agent Transport Simulation), SeSAm (Shell for Simulated Agent Systems Instrument pentru simularea sistemelor multi-agent) i Repast Simphony (REcursive Porous Agent Simulation Toolkit). Analiza comparativ a fost realizat pe baza unui set de criterii. Acesta a fost obinut n funcie de necesitile sistemului multi-agent propus. n urma analizei comparative a rezultat faptul c platforma Repast Simphony se apropie cel mai mult de necesitile simulrii sistemului propus. Sistemul multi-agent propus a fost modelat n cadrul modulului CoReMo (Constraint Responsive Mobility) Citadel al platformei CoReMo, dezvoltat n colaborare cu firma Siemens, Braov, utiliznd platforma Repast. n acest modul este realizat simularea traficului oraului Braov, la care sunt adugate componente de infrastructur specifice sistemului propus.

Pentru a putea realiza coordonarea n cadrul sistemului multi-agent care face subiectul acestei teze, a fost necesar pentru nceput soluionarea a dou probleme: modul n care sunt procesate evenimentele din cadrul sistemului multi-agent i modelarea procesului de decizie al agenilor mobili inteligeni. Astfel n capitolul 4, Procesarea evenimentelor n cadrul sistemelor multi-agent, este propus utilizarea procesrii complexe a evenimentelor aprute n cadrul sistemului multi-agent. CEP permite procesarea n timp real a unui volum mare de evenimente, poate realiza detecia anumitor situaii speciale aprute n cadrul sistemului (care pot influena comportamentul agenilor). Pentru nceput a fost realizat o analiz comparativ a platformelor CEP n urma creia a rezultat faptul c platforma Esper este potrivit cerinelor sistemului. Procesarea evenimentelor este integrat la nivelul agentului detector al incidentelor. La finalul capitolului sunt prezentate detaliat algoritmul propus pentru detectarea incidentelor n cadrul sistemului multi-agent i avantajele utilizrii tehnologiei CEP n sistemele multi-agent.

Modelarea procesului de decizie al agenilor inteligeni este abordat n capitolul 5. Modelarea procesului de decizie. n cadrul acestui capitol este propus utilizarea programrii constrngerilor pentru a modela procesul de decizie a agenilor inteligeni. Avantajele acestei abordri sunt faptul c ofer posibilitatea rezolvrii problemelor complexe de optimizare ct i o bun flexibilitate n modelarea i controlul problemelor. Sunt prezentai algoritmii integrai la nivelul agenilor inteligeni (dispecer i agenii care livreaz materialele) prin care acetia i modeleaz comportamentul n timp real. Algoritmii au fost implementai utiliznd dou metode ASP i CSP (Constraint Satisfaction Problem). n primul caz implementarea a fost realizat n sistemul DLV, iar n cea de a doua solverul Choco. La finalul capitolului au fost evideniate performanele ambelor implementri (att n cazul algoritmului de iniializare a rutelor agenilor mobili inteligeni ct i n cazul algoritmului de replanificare a rutelor agenilor mobili inteligeni) i analiza comparativ a acestora.

n capitolul 6, Strategii de coordonare n timp real, pentru nceput au fost analizate tehnicile utilizate n realizarea coordonrii. Acestea au diferite proprieti i caracteristici, fiind utile n diferite tipuri de medii i aplicaii. n cadrul acestui capitol a fost propus o nou strategie de coordonare construit utiliznd tehnica bazat pe planificare. Pe baza planului iniial agenii i modeleaz comportamentul astfel nct s urmreasc ruta iniial. n momentul detectrii unui incident n trafic, agenii trebuie s decid dac trebuie s i recalculeze ruta astfel nct acetia s i poat duce la ndeplinire sarcina atribuit. n cazul n care incidentul detectat blocheaz o strad care face parte din ruta agentului, acesta trebuie s i reconfigureze ruta. n evaluarea strategiei de coordonare s-au avut n vedere modul de obinere a controlului n

9

cadrul sistemului, costul de execuie al strategiei (performanele obinute de procesul de decizie al agenilor inteligeni), modul n care sunt evitate conflictele i alte aspecte prin care se pot urmri performanele unei strategii de coordonare.

Capitolul 7, Concluzii, prezint concluziile privind rezultatele cercetrii i au fost evideniate contribuiile personale, modul de diseminare al rezultatelor i direciile viitoare de cercetare.

Aceast tez de doctorat reprezint rezultatul cercetrilor efectuate n perioada 2009

2012 n domeniul Ingineria Sistemelor din cadrul Universitii Transilvania din Braov. Cercetarea a fost realizat n cadrul proiectului Studii doctorale pentru dezvoltare durabil (SD-DD) POSDRU/6/1.5/S/59321.

Doresc s mulumesc d-lui prof. dr. ing. Vasile COMNAC, conductorul tiinific al acestei teze de doctorat, pentru colaborarea fructuoas avut pe parcursul cercetrilor pentru elaborarea tezei de doctorat, cercetri ce au condus la multiple rezultate publicate mpreun.

Cercetrile nu ar fi putut fi dezvoltate fr suportul companiei Siemens. Platforma CoReMo, pe baza cruia au putut fi obinute rezultatele experimentale, a fost dezvoltat n cadrul centrului de cercetare al departamentului Corporate Technology, Siemens Braov, Romania. n acelai timp mulumesc ntregului colectiv din cadrul acestui departament pentru colaborarea care a avut loc pe durata celor 3 ani i pentru suportul acordat.

Mulumesc i celor din cadrul departamentului CT T CEE AT (Corporate Research and Technologies CEE Austria) pentru oportunitatea de a desfura stagiul extern n cadrul acestui departament. Mulumesc pentru noua direcie pe care au luat-o cercetrile n urma acestui stagiu, pentru suportul acordat i pentru uurina cu care am fost integrat n cadrul colectivului.

Nu n ultimul rnd a dori s mulumesc prinilor, surorii mele i pritenului meu pentru susinerea acordat pe tot parcursul studiilor doctorale, oferindu-mi suportul moral necesar.

SISTEME MULTI-AGENT Tehnologia sistemelor multi-agent este utilizat cu succes n modelarea sistemelor

distribuite. Mediul sistemelor distribuite este unul dinamic. Tehnologia utilizat pentru modelarea unui astfel de sistem trebuie s fac fa situaiilor neprevzute aprute n cadrul sistemului [52]. Prin construcia aplicaiilor utiliznd tehnologia sistemelor multi-agent se mbuntete flexibilitatea sistemelor i capacitatea acestora de a rezolva situaiile neprevzute aprute n cadrul sistemului.

Sistemele multi-agent au cunoscut o mare rspndire n ultimii ani, fiind utilizate n aplicaii din diverse domenii. Arhitectura sistemelor multi-agent difer n funcie de aplicaia n care este utilizat. La realizarea unei astfel de arhitecturi este important s se cunoasc rolul agenilor i modul n care acetia interacioneaz. Aceasta este construit n funcie de modul n care se realizeaz coordonarea agenilor. n cadrul unui sistem multi-agent trebuie s fie posibil schimbarea de informaii, astfel nct deciziile agenilor s fie luate n concordan cu necesitile ntregului sistem. 2.2 Arhitectura sistemelor multi-agent

Arhitectura unui sistem software reprezint descrierea structurii acestuia. Arhitectura reprezint primul artefact care poate fi analizat pentru a determina ct de bine dac sunt atinse atributele sistemului privind calitatea i servete ca i plan al proiectului [3]. Arhitectura unui

10

sistem multi-agent este influenat de modalitatea de coordonare utilizat n cadrul acestuia. Un sistem multi-agent este format din ageni i mediul sistemului. Prin arhitectura sistemului se stabilesc tipurile agenilor care fac parte din sistem, rolurile acestora, modul de interacionare cu ceilali ageni, legturile dintre ageni i structura fiecrui agent. 2.4 Domenii de utilizare

n literatura de specialitate au fost dezvoltate o serie de aplicaii care propun integrarea sistemelor multi-agent n diferite domenii de aplicaii [12] precum domeniul transporturilor [19] [25] [47], domeniul industriei [30] [44], domeniul sntii [45] [52] sau domeniul militar [21] [43].

2.5 Aplicaia propus Aplicaia propus face parte din domeniul transportului rutier. Aceasta reprezint o

aplicaie de control a traficului care propune detectarea n timp real a incidentelor aprute n trafic i apoi rerutarea vehiculelor astfel nct timpul petrecut de acestea n trafic s fie ct mai scurt.

Prin incidentele aprute n trafic se nelege orice eveniment care duce la un blocaj n trafic. Incidentele pot fi periodice n cazul n care au loc la un anumit interval de timp. De exemplu exist anumite intervale de timp zilnice n care fluxul autovehiculelor pe anumite strzi este mai mare dect cel normal. Pe de alt parte incidentele neprevzute sunt acele incidente care apar brusc din diferite cauze precum accidente, lucrrile la infrastructur, factori de ordin climatic. Aplicaiile de control ale traficului propun detectarea ambelor tipuri de incidente, dar cu precdere accentul este pus pe incidentele neperiodice.

Necesitatea existenei aplicaiilor de control al traficului devine esenial pentru meninerea traficului n bune condiii. Acest tip de aplicaii ajut conductorii vehiculelor s poat lua propriile decizii n funcie de condiiile traficului. Prin deciziile luate, acetia i pot scurta timpul petrecut n trafic, pot evita incidentele aprute. Deciziile trebuie s fie luate ntr-un timp ct mai scurt. Pentru aceasta este foarte important ca orice conductor de vehicul s poat avea acces la informaiile privind condiiile traficului n timp real. n acest mod vehiculele pot evita incidentele aprute n trafic precum accidente, ambuteiaje, etc. Dac informaiile privind condiiile traficului nu sunt primite ntr-un timp ct mai scurt (de ordinul a cteva secunde), acestea sunt inutile deoarece decizia luat nu mai corespunde cu starea actual a sistemului, sau acesta nu mai are timp s reacioneze (s-i modifice ruta) [10].

La fiecare moment de timp autovehiculele are nevoie de informaii legate de celelalte autovehicule care particip la trafic i informaiile primite de la componentele infrastructurii. Pentru a face posibil transmiterea acestor informaii este necesar ca fiecare main s aib dispozitive prin care s se realizeze schimbul wireless de informaii. n zilele noastre exist o multitudine de dispozitive care s realizeze comunicaia wireless ntre anumite componente precum telefoane, canale radio, computere, satelii, etc. Acestea pot fi conectate ntre ele prin utilizarea infrastructurilor informatice deja existente. Sateliii GPS (Global Positioning System) pot furniza informaii legate de poziia fiecrui vehicul aflat n trafic. Componentele infrastructurii reelei de drumuri pot fi vzute ca i AP-uri (Access Points) n cadrul unei reele WLAN (Wireless Local Area Network), n timp ce vehiculele pot fi vzute ca i CL (Clients) [9]. Informaiile pot fi transmise de la componentele infrastructurii la vehiculele din aria sa de influen.

11

Scenariul propriu-zis propus se refer la livrarea materialelor de construcie i echipamentelor la un numr de antiere distribuite ntr-un ora. Aceste antiere reprezint spaiile n construcie (staii de metrou, blocuri, strzi, etc.) aflate n ora. Materialele trebuie s fie livrate din mai multe depozite localizate n afara oraului prin utilizarea unor mini-utilitare. Livrarea materialelor trebuie fcut astfel nct acestea s fie livrate n intervalul de timp stabilit. n acelai timp rutele mini-utilitarelor trebuie s fie definite pentru ca timpul petrecut n trafic de ctre acesta s nu depeasc timpul de lucru al unei zile.

Dup generarea rutelor iniiale ale fiecrei mini-utilitare, acestea vor avea capacitatea de a i reactualiza rutele pentru a evita zonele n care sunt detectate incidente i n acelai timp intervalele de timp stabilite la nivelul antierelor s fie respectate. Detecia incidentelor n timp real trebuie realizat, aa cum a fost specificat anterior, pe baza informaiilor obinute din trafic i de la ceilali participani la trafic.

n funcie de aria care este acoperit de antiere, o companie de livrare a produselor poate utiliza unul sau mai multe depozite pentru stocarea temporar i expedierea materialelor utiliznd mini-utilitarele.

Tehnologia sistemelor multi-agent este potrivit pentru a modela scenariul prezentat n cadrul acestui subcapitol. Aplicaia prezentat este o aplicaie distribuit, fiecare vehicul care livreaz materialele trebuind s aib posibilitatea de a decide ce rut urmeaz. Ruta trebuie construit astfel nct agentul s poat livra materialele n intervalele de timp stabilite la nivelul antierelor. 2.5.1 Arhitectura sistemului multi-agent

Pentru a construi arhitectura unui sistem multi-agent trebuie definite tipurile i rolurile fiecrui agent care face parte din sistem i n acelai timp i interaciunile dintre acetia.

Arhitectura sistemului multi-agent prin care se va modela aplicaia de control al traficului este prezentat n fig. 2.7. Prin construcia acestei arhitecturi se urmrete pstrarea autonomiei entitilor sistemului prin inserarea la nivelul agenilor mobili inteligeni a unui modul de inteligen artificial [13]. Prin utilizarea acestui modul fiecare agent are capacitatea de a i adapta comportamentul n timp real n funcie de starea sistemului (mediu i ceilali ageni).

Fig. 2.7. Arhitectura sistemului multi-agent

12

2.5.1.1 Reprezentarea reelei de drumuri Reeaua de drumuri este descris printr-un graf )A,N(G , n care N reprezint nodurile

grafului (interseciile strzilor), iar A reprezint arcele grafului (strzile care compun reeaua). Fiecrui arc A)v,u( i este atribuit un cost )v,u(c . Acest cost reprezint timpul mediu de parcurgere al acelei strzi. El are o valoare pozitiv i este calculat utiliznd o funcie de cost.

n calculul costurilor se ine cont de lungimea strzii i de viteza medie cu care un vehicul se poate deplasa pe acea strad. Costul unui arc A)v,u( este calculat utiliznd urmtoarea funcie:

),(),(

),(cos vuvvul

vufmed

arct (2.1)

unde arcl reprezint lungimea strzii asociate arcului A)v,u( i medv reprezint viteza medie de parcurgere a strzii asociate arcului A)v,u( . 2.5.1.2 Tipurile i rolurile agenilor

Principalele tipuri de ageni aflai n cadrul sistemului multi-agent propus sunt: agenii mobili inteligeni numii ageni de livrare, agenii mobili reprezentai de participanii la trafic care nu livreaz materiale, agentul care detecteaz incidentele aprute n trafic i agentul dispecer care genereaz rutele iniiale ale agenilor mobili inteligeni. Aceast divizare a fost realizat pe baza principalelor roluri pe care trebuie s le ndeplineasc fiecare n cadrul sistemului multi-agent.

Agentul detector al incidentelor Detectarea incidentelor poate fi realizat la nivelul fiecrui agent mobil de livrare sau la

nivelul unui agent detector al incidentelor localizat la nivel global fr a fi necesar un agent coordonator.

Realizarea unui control distribuit ai agenilor mobili de livrare poate conduce la creterea alarmant a numrului de mesaje trimise n cadrul sistemului, putnd duce chiar la blocarea comunicaiei. Pentru a putea pstra procesul de decizie la nivelul fiecrui agent de livrare i pentru a evita blocarea comunicaiei la nivelul sistemului s-a realizat detectarea incidentelor la nivelul unui agent numit detector al incidentelor. n acest mod la nivelul agenilor mobili sunt primite doar informaiile despre incidentele care le pot afecta comportamentul, i nu informaii de la toi ceilali ageni care nu le influeneaz n nici un fel acel comportament. n acelai timp informaiile legate de trafic de la ageni sau de la componentele infrastructurii sunt trimise doar la un agent i nu la toi agenii de livrare. Agentul detector al incidentelor are rolul principal de a detecta n timp real incidentele aprute n trafic.

Agentul dispecer

Agentul dispecer are rolul de a realiza planul iniial al agenilor mobili inteligeni. Prin realizarea planului iniial se nelege stabilirea tuturor rutelor agenilor mobili inteligeni. Algoritmul de stabilire a rutelor agenilor trebuie s in cont de urmtoarele constrngeri: rutele trebuie s treac prin toate punctele de construcie unde trebuie livrate produsele, toate materialele trebuie livrate n intervalul de timp stabilit la nivelul antierelor, timpul petrecut de ageni n trafic trebuie s fie ct mai scurt, materialele se pot afla n mai multe depozite.

13

Agenii mobili participani la trafic Un agent mobil este asociat unui autovehicul participant la trafic. Rolul acestor ageni este

acela de a permite autovehiculelor aflate n trafic s funcioneze ca un grup format din entiti similare. Acetia au capacitatea de a se deplasa n cadrul reelei de drumuri, de a cunoate poziia sa n spaiu i viteza cu care se deplaseaz.

Acest tip de ageni nu au inteligen proprie, comportamentele acestora fiind selectate la iniializarea sistemului. Prin comportamentul acestora se nelege faptul c fiecare agent trebuie s ajung din punctul de plecare n punctul de destinaie prin urmrirea unei rute.

Agenii mobili inteligeni participani la trafic Spre deosebire de agenii mobili prezentai anterior acestui tip de ageni le este adugat un modul de inteligen artificial. Prin utilizarea acestui modul agenii i pot reconfigura comportamentul n timp real n funcie de starea sistemului. Arhitectura unui astfel de agent de tip deliberativ este prezentat n fig. 2.8.

Fig. 2.8. Arhitectura Agentul Mobil Inteligent

Prin pstrarea planificatorului la nivelul fiecrui agent mobil inteligent se urmrete crearea descentralizat a controlului (pstrarea deciziei la nivelul fiecrui agent inteligent). n acest fel, chiar dac detectarea incidentelor este realizat la nivel global, decizia rmne la nivelul fiecrui agent. Agenii au scopuri diferite (trebuie s livreze materiale la anumite antiere), iar modificarea comportamentului este realizat astfel nct s-i ndeplineasc scopul.

Comportamentul agenilor mobili inteligeni este modificat doar n momentul n care apare n mediu un incident care i blocheaz ruta. Aceast reconfigurare a rutelor trebuie s in cont de respectarea constrngerilor din cadrul sistemului. Cele mai importante constrngeri sunt cea a vizitrii tuturor antierelor pentru care deine materiale i cea a respectrii timpilor de sosire la fiecare antier. La acestea se adaug i faptul c se urmrete minimizarea timpului petrecut n trafic de fiecare agent.

2.5.2 Realizarea interaciunilor n cadrul sistemului multi-agent propus Modul de interaciune ntre ageni este esenial n buna funcionare a unui sistem. Fiecare

agent aflat n cadrul unui sistem multi-agent trebuie s aib acces la informaiile legate de ceilali ageni sau mediul din care fac parte pentru a putea lua deciziile legate de comportamentul su n concordan cu starea sistemului. n acest mod se poate asigura realizarea coordonrii agenilor.

Informaiile sunt transmise n cadrul sistemului sub form de evenimente. Forma evenimentelor este diferit n funcie de tipul de date pe cate le conine. Acestea pot conine date

14

despre fiecare autovehicul: poziia sa, strada pe care se afl i viteza sa, date despre incidentele aprute n trafic precum strada pe care a avut loc incidentul.

Principalele interaciuni care au loc n sistemul multi-agent propus sunt:

Interaciunea Agentului Detector al Incidentelor i agenii mobili; Transmiterea informaiilor ntre Agentului Detector al Incidentelor i agenii mobili se

realizeaz ntr-un singur sens. Informaiile sunt transmise doar de la agenii mobili la agentul detector al incidentelor. Informaiile transmise sunt evenimente simple de poziie. Aceste evenimente conin informaii legate de poziionarea fiecrui agent mobil. Pe baza acestor evenimente simple Agentului Detector al Incidentelor realizeaz detecia n timp real a incidentelor.

Interaciunea Agentului Detector al Incidentelor i agenii mobili inteligeni;

Transmiterea informaiilor ntre Agentului Detector al Incidentelor i agenii mobili inteligeni se realizeaz n ambele sensuri. Informaiile transmise de la agenii mobili la agentul detector al incidentelor sunt evenimentele simple de poziie prezentate anterior. Informaiile transmise de la agentul detector al incidentelor la agenii mobili sunt evenimentele complexe prin care agenii mobili sunt informai de detecia unui ambuteiaj pe o strad.

Interaciunea Agentului Dispecer i agenii mobili inteligeni; Transmiterea informaiilor ntre Agentului Dispecer i agenii mobili se realizeaz ntr-un

singur sens. Agentul Dispecer transmite agenilor mobili inteligeni rutele lor iniiale. Rutele sunt reprezentate sub forma unui vector n care sunt reinute punctele prin care trebuie s treac agenii.

MODELAREA I SIMULAREA SISTEMELOR MULTI-AGENT Fr a modela i simula un sistem multi-agent nu se pot urmri performanele obinute de

acesta. Prin performanele unui sistem multi-agent se pot nelege urmtoarele proprieti caracteristice: arhitectura acestuia, comportamentul ntregului sistem, i a fiecrui agent, strategiile de coordonare selectate pentru a obine o bun coordonare a agenilor, etc. Pe de alt parte prin simularea unui sistem multi-agent se pot urmri performanele obinute de diferii algoritmi i a diferitelor tehnologii utilizate pentru modelarea comportamentului agenilor.

Platforma utilizat n modelarea unui sistem multi-agent trebuie selectat n funcie de anumite criterii alese pe baza cerinelor aplicaiei care urmeaz a fi creat. n lista criteriilor trebuie s fie cuprinse toate facilitile pe care platforma le ofer utilizatorului astfel nct acesta s poat crea scenariile dorite. 3.3 Analiza comparativ a instrumentelor

Pentru a putea selecta platforma de simulare a sistemelor multi-agent care va fi utilizat n cadrul aplicaiei propuse a fost necesar selectarea criteriilor pe baza crora se va realiza analiza platformelor prezentate n acest subcapitol. Principalele criterii luate n consideraie au fost:

modul de dezvoltare al agenilor: modul n care sunt definite comportamentele agenilor, dac se pot integra module de raionare ale agenilor, dac proprietile agenilor sunt conform standardului FIPA (Foundation for Intelligent Physical Agents) [58];

comportamentele predefinite ale agenilor: dac exist funcii predefinite care realizeaz logica i comportamentul agenilor i dac se pot defini comportamente complexe;

15

accesul programatic la nivelul comportamentelor i mediului: acest criteriu este un criteriu extrem de important deoarece pentru a modela diverse comportamente, pentru a realiza schimbarea acestora n timp real n funcie de starea mediului i a celorlali ageni, trebuie ca utilizatorul s aib acces programatic la nivelul comportamentelor agenilor. Pentru a putea fi create scenarii ct mai diversificate utilizatorul trebuie s poat avea acces programatic i la nivelul mediului.

limbajul de dezvoltare: limbajul n care este programat comportamentul agenilor i mediul;

posibilitatea integrrii datelor de format GIS (Geographic Information System) n cadrul platformei: dac se pot introduce hri pe care pot fi inserai agenii mobili i modul de realizare a integrrii;

integrarea modulelor externe: tipul modulelor care pot fi integrate i n ce mod. n cazul platformei JADE [7] caracteristicile agenilor sunt n conformitate cu standardul

FIPA, pot fi integrate module de raionare n cadrul unui agent. Agenii sunt reprezentai ca i fire Java, putnd executa sarcini complexe i paralele, de unde rezult faptul ca agenii pot avea comportamente complexe la care utilizatorul are acces programatic prin interfee special create. Comunicaia agenilor este realizat utiliznd limbajul ACL_FIPA (The Foundation of Intelligent Physical Agents - Agent Communication Language). n cadrul platformei JADE se pot introduce date de format GIS i se pot integra module externe. Principalul dezavantaj al platformei JADE, pentru care s-a renunat la utilizarea acestei platforme, este ncrcarea reelei. n cazul n care n cadrul platformei sunt integrai un numr mare de ageni simularea merge extrem de greu din cauza numrului foarte mare de mesaje transmise n cadrul sistemului.

Simulatorul MatSim [60] ofer posibilitatea planificrii comportamentului agenilor. Dezavantajul pe care l prezint este faptul c nu se poate interveni n timpul execuiei simulrii asupra comportamentelor agenilor, ci doar la sfritul unei simulri pe baza rezultatelor obinute se poate replanifica activitatea acestora. Acest dezavantaj a fost esenial n eliminarea posibilitii de a utiliza acest simulator n implementarea aplicaiei. n cadrul aplicaiei este necesar necesar reconfigurarea activitilor agenilor n timp real.

Platforma SeSAm [63] dei nu deine unele caracteristici pe care un agent trebuie s le aib conform FIPA (de exemplu independen), din punctul de vedere al aplicaiei care se dorete a fi construit sunt satisfcute aspectele privind raionarea agentului. Exist funcii predefinite pentru realizarea logicii i comportamentelor agenilor ns nu se pot defini comportamente avansate. Nu ofer acces programatic la nivelul comportamentului agenilor sau mediului. Aplicaia este realizat n Java ns deoarece nu exist acces programatic la comportamentele agenilor acest lucru devine irelevant. Se pot integra n cadrul platformei date de tip GIS i se pot integra module externe. Din cauza faptului ca nu exist acces programabil la nivelul agenilor aceast platform nu poate fi utilizat n implementarea aplicaiei.

Platforma Repast Symphony [61] ca i platforma SeSAm dei nu deine unele caracteristici pe care un agent trebuie s le aib conform FIPA (de exemplu independen), aspectele privind raionarea agentului sunt satisfcute din punct de vedere al aplicaiei care se dorete a fi construit. Repast faciliteaz implementarea simpl a unor tehnologii avansate de inteligen artificial precum reele neurale, algoritmi genetici, regresii, logic fuzzy etc.. Agenii n Repast sunt implementai sub forma de obiecte Java ns nu este impus nici un fel de relaie de motenire fat de o anumit clas din platform (fa de JADE unde este impus extinderea clasei Agent). Adnotrile i programatorul permit realizarea uoar de comportamente ciclice sau

16

determinate de diferite condiii, n timp ce metodele existente n cadrul proieciilor permit implementarea uoar a relaiilor i a aciunilor de deplasare. Definirea comportamentelor se face att vizual ct i programatic (n Java, Groovy etc.). Limbajul de implementare utilizat este Java. Se pot integra n cadrul platformei date de tip GIS prin GISProjection i se pot integra module externe realizate n Java foarte simplu. De asemenea bibliotecile Repast pot fi adugate la proiecte Java deja existente. Aceasta permite vizualizare uoar a simulrii n timpul rulrii deoarece fiecare proiecie are implementat un vizualizator parametrizabil ce poate fi configurat n cadrul timpului de rulare al simulatorului. Permite colectarea i analiza uoar a datelor de simulare prin integrarea de instrumente ce pot realiza export de date ctre MatLab, Weka, Excel, etc. Datorit tuturor acestor avantaje platforma Repast a fost selectat pentru a fi utilizat n implementarea aplicaiei. 3.4 Platforma CoReMo

Platforma CoReMo a fost dezoltat n colaborare cu Siemens Braov, Romania, n cadrul centrului de cercetare al departamentului Corporate Technology. Aceasta a fost construit utiliznd instrumentul Repast Simphony i are ca baz aplicaia RepastCity [62]. Aceast aplicaie a fost dezvoltat de Nick Malleson pentru a modela un sistem multi-agent utilizat n simularea infraciunilor (furturi), agenii fiind considerai infractori. 3.5 Arhitectura platformei CoReMo Platforma CoReMo este alctuit din trei module (fig. 2.6):

CoReMo Core: n cadrul acestui modul sunt definite comportamentele de baz ale agenilor (deplasarea agenilor de la un punct de origine i un punct de destinaie) i include instrumentele utilizate n iniializarea mediului. Aplicaiile derivate ale acestui modul l utilizeaz sub form de bibliotec;

CoReMo Citadel: reprezint o extensie a modului CoReMo Core prin care se definesc comportamentele specializate ale agenilor;

CoReMo Sensor Network Processing: prin acest modul sunt inclui factorii de mediu n cadrul simulrii;

3.5.1 CoReMo Core Modulul CoReMo Core reprezint nucleul platformei CoReMo. n acest modul este

realizat simularea traficului dintr-o zon metropolitan. Oraul a crui hart a fost introdus n cadrul simulatorului n formatul GIS a fost harta oraului Braov.

Spre deosebire de modelul aplicaiei RepastCity, n modelul CoReMo au fost adugate ca i sub-contexte ale contextului oraului agenii parcai i interseciile. Sub-contextul locuinelor a fost ters din cadrul acestui context deoarece scopul acestui simulator este de a urmri traficul din cadrul zonei luate n calcul. Contextul ariilor a fost adugat deoarece harta oraului Braov este mprit ntr-o serie de zone ce prezint interes i anume: zone rezideniale, zone de afaceri, zone comerciale, zone de relaxare i zona cldirilor publice. Tot n cadrul contextului ariilor au fost adugate i sub-contextele: parcrilor i punctelor de intrare.

La fel ca i n cazul aplicaiei RepastCity fiecare sub-context are asociat o proiecie GIS prin care se stabilete locaia obiectelor. Proieciile GIS atribuie fiecrui agent o locaie spaial

),( yx i sub-contextul jonciunilor are i o proiecie a reelei drumurilor pentru a permite crearea relaiilor ntre ageni.

17

3.5.1.2 Modelarea comportamentului agenilor mobili n CoReMo Core este implementat comportamentul agenilor mobili. Acetia reprezint

autovehiculele aflate n trafic. Comportamentul acestuia definete deplasarea acestuia dintr-un punct de start ctre un punct destinaie. Deplasarea trebuie s se realizeze numai pe drumurile definite pe harta oraului. Punctele de start i destinaie reprezint parcrile de unde pleac agentul i unde trebuie sa ajung acesta.

Fiecare agent este creat iniial ntr-o anumit zon a oraului n funcie de distribuia dat. Acesta primete i un punct de destinaie. Ruta pe care o parcurge agentul ntre cele dou puncte va fi calculat astfel nct aceasta s fie parcurs n timpul cel mai scurt. Viteza de deplasare a agenilor este select aleator la nivelul fiecrui agent. Valoarea vitezei poate lua orice valoare ntre 40 km/h i 80 km/h.

Metoda utilizat n CoReMo pentru a modela micarea agenilor pe strzi este asemntoare cu cel utilizat n RepastCity. Micarea agenilor este modelat ca i n RepastCity utiliznd proieciile GIS i proiecia reelei de drumuri. Reeaua de drumuri a simulatorului este format din segmente. Aceste segmente sunt citite dintr-un fiier .shapefile i fiecrui segment i este atribuit un obiect de timp arc. Arcele sunt orientate (existnd i strzi cu sens unic). Reeaua de drumuri poate fi modelat printr-un graf orientat care este format din totalitatea arcelor. O strad poate fi format din mai multe segmente. Interseciile mai multor strzi reprezint jonciunile.

Fiecrui arc i este asociat un cost care reprezint timpul mediu de parcurgere a acestuia de ctre ageni. Pe baza acestor costuri sunt calculate distanele cele mai scurte ntre dou puncte. Algoritmul de rutare calculeaz, ca i n cazul algoritmului utilizat n RepastCity, list cu coordonatele care formeaz rutele agenilor de la origine pn la destinaie i dup aceea urmeaz deplasarea pe ruta planificat. Calculul celei mai scurte rute se realizeaz tot utiliznd funcia specializat din RepastSymphony care folosete algoritmul Dijkstra. n cazul platformei CoReMo costurile reprezint timpii de parcurgere a segmentelor.

n cazul platformei CoReMo distana cu care se deplaseaz fiecare agent la un interval de timp stabilit este calculat n funcie de viteza acestuia. Agentul nu trebuie s ating fiecare coordonat aflat n ruta predefinit. n cazul n care distana parcurs la un interval de timp stabilit i permite trecerea de o anumit coordonat acesta va ajunge pe urmtorul segment i nu la coordonat. n acest mod el i va pstra viteza stabilit iniial. 3.5.3 CoReMo Citadel

Modulul CoReMo Citadel reprezint o extensie a modului CoReMo Core. Acesta a fost implementat cu scopul de a modela sistemul multi-agent propus n cadrul acestei tezei. n cadrul acestui modul au fost adugate componentele de infrastructur, s-au extins comportamentele agenilor mobili cu scopul de a face posibil implementarea scenariului de livrare a produselor i a fost implementat comportamentul a doi noi ageni: agentul dispecer i agentul detector al incidentelor.

Pentru a crea ntreaga infrastructur necesar modelrii scenariului propus au fost adugate urmtoarele componente: depozitele n cadrul crora sunt depozitate materiale de construcie (depozitele se afl n zone metropolitane la periferia oraului pentru ca acesta s poat fi alimentat de autovehicule de mare tonaj), antierele (formate pentru construcia cldirilor, pentru lucrri de reabilitare, etc.) care sunt distribuite n ntregul ora. Toate aceste componente sunt preluate din fiiere .shp. Pentru depozite sunt definite locaiile acestora, iar n cazul antierelor

18

sunt definite locaiile acestora, intervalele de timp la care trebuie livrate materialele de construcie i depozitul la care se afl acele materiale.

De transportul materialelor se vor ocupa agenii inteligeni mobili care aparin unei firme de distribuie. n cadrul acestui modul se realizeaz modelarea comportamentului agenilor mobili inteligeni (agenii care livreaz materialele n cadrul antierelor). La nivelul acestora a fost integrat un modul de inteligen artificial prin care acetia i reconfigureaz comportamentul n funcie de starea traficului.

La nivelul agentului dispecer sunt realizate planurile iniiale ale agenilor mobili, la nivelul acestuia fiind integrat de asemenea un modul de inteligen artificial. La nivelul comportamentului detector al incidentelor a fost integrat algoritmul care face posibil detectarea n timp real a ambuteiajelor aprute n trafic.

PROCESAREA EVENIMENTELOR N CADRUL SISTEMELOR MULTI-AGENT

Cercetrile privind sistemele multi-agent sunt orientate pe procesarea cunotinelor, problema procesrii unui volum foarte mare de evenimente nefiind abordat ntr-un mod explicit [20]. De aceea apare necesitatea integrrii n cadrul sistemelor multi-agent unei tehnologii prin care s fie realizat procesarea n timp real unui volum mare de evenimentelor.

Tehnologia adoptat n lucrare n acest scop este CEP. n cadrul sistemului multi-agent propus, CEP a fost integrat la nivelul agentului detector al incidentelor. n lucrare a fost propus un algoritm care realizeaz detectarea n timp real a ambuteiajelor aprute n trafic. Pentru realizarea testelor acest algoritm a fost integrat n cadrul modulului CoReMo Citadel.

4.2 Arhitectura sistemelor bazate pe evenimente

4.2.1 Evenimente i notificri Un eveniment este definit n [23] ca fiind o ntmplare de orice natur care are loc n

cadrul unui sistem. Notificarea reprezint mesajul trimis care informeaz destinatarul n legtur cu apariia evenimentului. n contextul sistemelor software evenimentul reprezint cauza iar notificarea reprezint efectul.

Exist situaii (cazul n care evenimentele sunt produse de acelai tip de senzori) n care structura i semantica anumitor evenimente rmne aceeai i se modific doar momentul de apariie al evenimentului i datele coninute de acesta. Pentru acest tip de evenimente n locul construciei fiecrui obiect asociat acestora sunt utilizate clase de evenimente [22]. Acest lucru este echivalent cu definirea unui tip reutilizabil n cadrul limbajului de programare, iar acest tip este numit tipul evenimentului. Fiecare obiect prin care este reprezentat un eveniment reprezint o instan a unui tip de evenimente.

Evenimentele pot fi simple sau compuse (rezultnd din corelarea mai multor evenimente simple sau alte evenimente compuse). Evenimentele simple pot fi generate prin observarea individual a unui senzor, pot fi evenimente temporale etc. Evenimentele compuse rezult din agregarea mai multor evenimente.

4.2.2 Transmiterea notificrilor 4.2.2.3 Modaliti de procesare a evenimentelor Exist trei modaliti principale de a realiza procesarea evenimentelor [34]:

19

procesarea evenimentelor simple: n momentul n care a avut loc un eveniment n cadrul sistemului se genereaz o aciune n conformitate cu acel eveniment;

procesarea fluxurilor de evenimente ESP (Event Stream Processing): notificrile evenimentelor sunt trimise sub forma unor fluxuri consumatorilor. Aceast modalitate permite luarea deciziilor n timp real.

procesarea evenimentelor complexe CEP: evalueaz mai multe evenimente i apoi se genereaz deciziile. Corelarea evenimentelor poate fi cauzal, temporal sau spaial. CEP necesit interpretri complexe ale evenimentelor, definirea modelelor de evenimente i tehnici de corelare.

4.3 Procesarea evenimentelor complexe CEP este utilizat cu succes n aplicaii care necesit transferul i procesarea unui numr

foarte mare de evenimente, care necesit monitorizarea n timp real a proceselor pentru analiza datelor n timp real, generarea rezultatelor n timp real pentru a permite luarea deciziilor ntr-un timp ct mai scurt.

Pentru a realiza procesarea evenimentelor n timp real CEP utilizeaz o abordare inovativ, instrumente de nivel nalt pentru definirea modului de procesare i analiz a evenimentelor. Acesta permite o definire simpl a logicii care este aplicat evenimentelor de intrare.

Conceptul utilizat de CEP pentru analiza i procesarea evenimentelor este asemntor conceptulului fundamental al bazelor de date relaionale [54]. 4.4 Evaluarea comparativ a platformelor CEP

Pe piaa platformelor CEP exist un numr mare de productori i specialiti. Pentru a putea selecta din aceast multitudine de platforme pe cea potrivit n dezvoltarea propriei aplicaii este necesar realizarea unui studiu comparativ. Forrester a realizat un astfel de studiu comparativ al principalelor platforme CEP existente n 2009 pe pia [59].

Acest studiu general a reprezentat doar o orientare pentru realizarea comparaiei platformelor propuse. Pentru a avea o imagine ct mai bun a platformelor s-a considerat o list de 3 platforme care au fost evaluate n detaliu. Platformele considerate au fost StreamInsight, Oracle i EsperTech.

Pentru nceput au fost considerate i TIBCO, Drools StreamInsight, Oracle i EsperTech. Aceste dou platforme nu au fost incluse n studiul comparativ prezentat n continuare din cauza lipsei documentaiei detaliate privind modul de dezvoltare al unei aplicaii, limbajul utilizat pentru procesarea evenimentelor n cazul platformei TIBCO i faptul c limbajul de definire al interogrilor n cazul platformei Drools este bazat pe regulile de producie (dezavantajele acestui limbaj au fost discutate anterior).

Criteriile alese au inut cont de necesitile aplicaiei n care urmeaz s fie utilizat platforma selectat. Acestea sunt:

Platforma de dezvoltare: platforma pe care este dezvoltat i ruleaz platforma; Limbajul de definire al interogrilor: aceste limbaje trebuie s furnizeze mecanisme

precum filtrarea, corelarea, agregarea evenimentelor, utilizarea ferestrelor de timp, definirea modelelor evenimentelor.

Modelul de dezvoltare al aplicaiilor: modul n care este construit o aplicaie. Rata de transfer: timpul n care sunt procesate evenimentele; Scalabilitatea: capacitatea platformelor de a manipula un volum mare de evenimente.

20

Disponibilitatea: abilitatea de a furniza un timp de funcionare continuu i de a preveni pierderea evenimentelor.

Interfee pentru monitorizare i administrare: mecanismele disponibile dezvoltatorului aplicaiei pentru monitorizare i control.

StreamInsight este o platforma CEP aflat la nceput. Rata de transfer obinut n cazul acestei platforme este mult mai mare dect a celorlalte dou. Acest criteriu este unul foarte important deoarece procesarea evenimentelor n cadrul sistemului multi-agent trebuie realizat n timp real. Aceasta nu are implementate mecanisme pentru mbuntirea scalabilitii i disponibilitii sistemului. Din aceste motive n cazul sistemului multi-agent nu va fi utilizat aceast platform.

Oracle CEP pune la dispoziie, ca i Esper, instrumente pentru mbuntirea scalabilitii, disponibilitii i performanelor sistemului. Ambele au rata de transfer la nivelul microsecundelor, ceea ce este un lucru foarte important. Utiliznd una din aceste platforme se poate obine detectarea incidente n timp real. Ambele platforme sunt dezvoltate n Java, ceea ce reprezint un avantaj deoarece simulatorul CoReMo, n cadrul cruia trebuie integrat motorul CEP, este dezvoltat tot n Java.

Limbajul Oracle CQL (Continuous Query Language) utilizat de platforma Oracle, este bazat pe SQL (Structured Query Language) la care s-au adugat construcii pentru suportul fluxurilor de date. Limbajul EPL (Event Processing Language) utilizat de platforma Esper este bazat i acesta pe SQL permind o nvare uoar dar i suport pentru tehnologiile moderne. Acesta este orientat pe obiecte.

Din aceste dou platforme Oracle i Esper ultima este open-source. Pe baza celor prezentate anterior a fost selectat platforma Esper pentru a fi utilizat n

procesarea evenimentelor din cadrul sistemului multi-agent propus.

4.5 Utilizarea CEP n procesarea evenimentelor din cadrul sistemelor multi-agent Utilizarea tehnologiei CEP n procesarea informaiilor transmise n cadrul unui sistem

multi-agent reprezint o abordare nou n tehnologia sistemelor multi-agent. Aceasta deoarece pn n acest moment n literatura de specialitate, conform [20], nu exist abordri clare legate de procesarea evenimentelor detectate n cadrul unui astfel de sistem. Metodele existente sunt orientate pe procesarea cunotinelor. Acestea nu ridic problema procesrii n timp real a unui volum mare de evenimente. n acelai timp n sistemele multi-agent lipsesc conceptele legate de descrierea dependentelor temporale ntre evenimente [20].

4.5.1 Motivaia utilizrii CEP n cadrul sistemelor multi-agent n cadrul unui sistem multi-agent, precum cel propus, datele transmise sunt reprezentate

sub forma notificrilor prin care sunt semnalate apariii ale diferitelor evenimente. n cazul sistemului propus evenimentele sunt reprezentate de schimbarea poziiei agenilor mobili n reeaua de drumuri. Numrul acestor evenimente crete considerabil o dat cu mrirea numrului de ageni mobili care se deplaseaz pe strzi.

Notificrile tuturor evenimentelor sunt trimise la nivelul agentului detector al incidentelor, care trebuie s detecteze n timp real, pe baza acestora, incidentele. Metoda utilizat pentru a realiza procesarea evenimentelor trebuie s aib capacitatea de a detecta n timp real, pe baza evenimentelor simple primite din cadrul sistemului, situaii neprevzute care pot influena comportamentul agenilor mobili (n cazul de fa incidentele). n acelai timp modulul de

21

procesare a evenimentelor trebuie s aib capacitatea de a procesa un numr foarte mare de evenimente n timp real.

4.5.2 Integrarea CEP la nivelul agentului detector al incidentelor n cazul sistemului propus n aceast tez, tehnologia CEP a fost integrat n procesul de

decizie al agenilor. Sistemul inteligent de control al traficului nu i propune doar detectarea global a incidentelor utiliznd mai muli ageni de procesare, ci integrarea la nivelul unui agent global detectarea incidentelor. Informaiile privind detecia unui incident sunt transmise la nivelul fiecrui agent inteligent, la nivelul crora sunt luate calculate noi rute. 4.5.3 Detectarea incidentelor n timp real utiliznd CEP

n literatur au fost propui diferii algoritmi pentru realizarea detectrii incidentelor aprute n trafic. n cadrul acestor algoritmi se face distincia ntre detectarea unui accident sau ambuteiaj.

4.5.3.1 Algoritmul propus

Algoritmul propus pentru detectarea incidentelor din trafic i propune doar semnalarea ambuteiajelor. Detectarea unui accident se face prin ambuteiajului aprut n urma acestuia.

Datele de intrare ale algoritmului sunt informaiile legate de trafic care pot proveni de la agenii mobili aflai n trafic sau de la componentele de infrastructur. Pentru a simplifica scenariul s-a presupus ca informaiile pe baza crora se realizeaz detecia incidentelor provin doar de la agenii mobili. Aceste date sunt primite la nivelul acestui agent sub form de evenimente simple. Evenimentele simple sunt primite cu o frecven de o serie de cadre pe agent. Pe baza evenimentelor simple, motorul CEP genereaz ca date de ieire evenimente complexe rezultate din corelarea acestora (operaii precum gruparea, agregarea, sortarea, filtrarea, fuziunea, divizarea sau duplicarea). Evenimentele complexe generate semnaleaz apariia incidentelor.

Ca n cazul oricrui algoritm de procesare a evenimentelor este necesar definirea modelului evenimentelor i cel al interogrilor. Trebuie s se stabileasc nc din etapa proiectrii care sunt evenimentele care prezint interes n cadrul sistemului i care sunt interogrile utilizate n corelarea evenimentelor simple cu scopul de a detecta ambuteiajele aprute n trafic.

Modelul evenimentelor Pentru definirea modelului evenimentelor utilizat n cadrul algoritmului propus este

necesar definirea tipurilor de evenimente semnalate n cadrul sistemului care prezint interes. Principalele tipuri de evenimente care prezint interes n cadrul aplicaiei propuse sunt urmtoarele:

evenimentele care semnaleaz poziia autovehiculelor; evenimentele care semnaleaz numrul de autovehicule aflate pe fiecare strad; evenimentele care semnaleaz apariia incidentelor pe anumite strzi.

Din aceste trei tipuri de evenimente cele care semnaleaz poziia autovehiculelor sunt considerate evenimentele simple. Aceste evenimente sunt generate la nivelul fiecrui autovehicul n momentul n care acetia se deplaseaz pe strad.

Fiecare instan a acestui tip de evenimente conine n corpul evenimentelor urmtoarele atribute:

22

identificatorul strzii pe care se afl vehiculul; poziia actual a vehiculului; numrul de nmatriculare a vehiculului; viteza cu care ruleaz acesta n acel moment de timp.

Urmtoarele dou tipuri de evenimente generate n cadrul sistemului sunt considerate evenimente complexe deoarece acestea rezult n urma interogrilor din cadrul motorului CEP. Evenimentele care semnaleaz numrul de autovehicule aflate pe fiecare strad sunt generate n urma interogrii realizate asupra evenimentelor simple (de poziionare).

Fiecare instan a acestui tip de evenimente conine n corpul evenimentelor urmtoarele atribute:

identificatorul strzii pe care se afl vehiculul; numrul de vehicule care se afl pe strada respectiv; lungimea strzii i densitatea strzii.

Evenimentele care semnaleaz apariia incidentelor pe anumite strzi sunt generate n urma interogrii realizate asupra evenimentelor complexe prin care se semnaleaz numrul de autovehicule aflate pe fiecare strad. n cazul n care densitatea strzii este mai mare dect o densitate etalon (densitatea maxim pentru care se poate considera circulaia normal pe o anumit strad) este semnalat apariia unui incident. Incidentele se vor salva ntr-un vector care va conine strzile blocate de un incident.

Modelul interogrilor Pentru a realiza detectarea incidentelor s-au utilizat dou interogri:

prima este utilizat pentru detectarea numrului de maini aflate pe fiecare strad; cea de a doua este utilizat pentru a detecta ambuteiajele care au aprut n trafic.

Evenimentele simple care semnaleaz poziia autovehiculelor sunt interogate pentru nceput pentru a realiza calculul numrul de vehicule aflate pe fiecare strad la un moment dat de timp. Interogarea se realizeaz astfel nct s se numere o singur dat un vehicul (chiar dac acesta poate trimite evenimente legate de poziia sa cu o periodicitate mai mare dect cea a calculului incidentelor). Acest lucru se face n funcie de numrul de nmatriculare al vehiculelor (acesta reprezentnd identificatorul vehiculelor).

Evenimentele complexe care semnaleaz numrul de autovehicule aflate pe fiecare strad rezultate dup prima interogare sunt din nou interogate cu scopul de a determina densitatea de vehicule a fiecrei strzi. Formula de calcul a densitii pe o unitate de lungime L pe care se afl un numr de n , la un anumit moment de timp 1t este dat de formula:

L)t(n

t,LK 11 (4.1) Valoarea calculat prin aceast formula 4.1 este comparat cu o densitate etalon.

Densitatea etalon reprezint densitatea maxim admis pentru ca o strad s nu fie considerat congestionat. n cazul densitii etalon se consider faptul c distana regulamentar dintre 2 autovehicule este de 5 metri. Astfel lund n calcul faptul c lungimea autovehiculelor este de 4 metri, distana necesar unui autovehicul este de 9 metri. Astfel n cazul n care 1n , formula densitii etalon devine:

91etK (4.2)

23

n cazul n care densitatea, calculat pentru o strad, este mai mare dect densitatea etalon este semnalat apariia unui incident. Reconfigurarea noilor rute se va face pe baza noilor timpi de parcurgere a strzilor. Acetia sunt modificai imediat dup detectarea unui incident pe o anumit strad.

Costurile strzilor blocate sunt generate ca fiind un timp foarte mare, echivalent cu faptul c strada respectiv este blocat. 4.5.4 Rezultate obinute prin integrarea n platformei CoReMo

Pentru a putea urmri rezultatele obinute de algoritmul de detectare a incidentelor s-a realizat integrarea acestuia n simulatorul CoReMo la nivelul agentului detector al incidentelor. n cazul n care un incident blocheaz traficul pentru o perioad mai mare de timp, acesta este detectat de mai multe ori. Algoritmul de detectare al incidentelor va gsi toate incidentele aprute n trafic pe durata unui interval de timp prestabilit. Aceasta indiferent dac un incidentul a fost detectat i anterior. n acest mod nu este necesar estimarea timpului n care traficul strzii este decongestionat. n urma simulrii s-a observat c acest algoritm detecteaz ambuteiajele majore aprute n trafic. Algoritmul, avnd la baza calculul densitii ntregii strzi, nu ine cont de distribuia autovehiculelor, ci doar de numrul acestora. Acesta realizeaz detectarea n timp real a ambuteiajelor care pot duce la creterea semnificativ a timpului petrecut n trafic de ctre agenii mobili. Agenii pot rmne blocai n trafic doar n cazul n care acetia fac parte din primii ageni sosii n urma producerii unui accident.

Rezultatele obinute au artat faptul c utilizarea CEP pentru a procesa n timp real evenimentele din cadrul unui sistem multi-agent reprezint o metod fezabil. Avantajele utilizrii CEP n detecia ambuteiajelor. Principalele avantaje ale utilizrii CEP n algoritmul de detectare a incidentelor sunt [11]:

realizarea procesrii n timp real a unui volum mare de evenimente: procesarea numrului mare de evenimente transmise de agenii mobili este creat ntr-un timp foarte scurt;

asocierea evenimentelor cu momentul de timp la care s-au produs: fiecare nou eveniment prin care este semnalat poziia unui agent are asociat i momentul de timp la care a fost semnalat;

corelarea evenimentelor simple n timp real: corelarea evenimentelor este realizat n funcie de locaia i momentul de timp la care au fost semnalate;

face posibil detectarea n timp real a unor situaii care pot influena comportamentul agenilor: n cazul de fa aceste situaii sunt reprezentate de ambuteiajele aprute n trafic. Agenii, pe baza acestora, realizeaz calculul noilor rute.

Un alt avantaj considerabil este disponibilitatea modulului CEP. ntregul sistem multi-agent depinde de buna funcionare a acestui modul. Pentru a evita situaiile n care modulul CEP nu funcioneaz, platformele CEP pun la dispoziie diferite metode prin care s reduc timpii de nefuncionare a sistemului la 0 i prin care previne pierderea evenimentelor. Prin aceste metode este rezolvat problema ntreruperii funcionrii modulului de procesare a evenimentelor.

MODELAREA PROCESULUI DE DECIZIE n cazul sistemului multi-agent propus este necesar luarea deciziilor la nivelul agenilor.

Acest lucru este necesar pentru ca agenii s poat realiza coordonarea comportamentelor n timp real. Din acest motiv algoritmii propui att la nivelul agentului dispecer, dar mai ales cel

24

propui la nivelul agenilor mobili inteligeni trebuie s genereze soluiile ntr-un timp ct mai scurt. Pentru ca algoritmii s genereze soluii optime, acetia necesit un interval de timp care n cele mai multe situaii este mai mare dect timpul necesar gsirii unei soluii (sistemul fiind dinamic starea acestuia se poate schimba ntr-un interval foarte scurt de timp, de ordinul secundelor).

5.3 Procesul de decizie al agenilor inteligeni n sistemul propus activitile agenilor sunt reprezentate de livrarea materialelor de

construcie la antierele din cadrul oraului. Fiecare livrare trebuie realizat ntr-un anumit interval de timp, ceea ce duce la necesitatea alocrii strzilor care fac parte din ruta unui autovehicul pe durata anumitor intervale de timp. Resursele sunt reprezentate de strzile oraului. Pe aceste strzi nu poate circula un numr infinit de autovehicule, ci numrul acestora este stabilit n funcie de lungimea strzilor, lungimea mainilor, numrul de benzi a strzilor, etc.

Planificarea i replanificarea rutelor n timp real reprezint probleme complexe care necesit optimizarea timpului petrecut de ageni n trafic. Aceste probleme au ca origine problema TSP (Travelling Salesman Problem), fiind probleme derivate acesteia.

5.3.2 Procesul de decizie al agenilor inteligeni mobili 5.3.2.1 Scenariul

Scenariul se refer la livrarea de ctre un agent a materialelor de construcie la antierele distribuite n cadrul unui ora. Transportul trebuie realizat astfel nct fiecare material s fie livrat n momentul utilizrii acestuia deoarece capacitatea antierelor este limitat. Pentru aceasta la nivelul fiecrui antier este definit un interval de timp n care trebuie livrate materialele. Livrarea trebuie s se realizeze astfel nct intervalele de timp s fie respectate i timpul petrecut de agent n trafic s fie ct mai apropiat de timpul rutei iniiale. 5.3.2.2 Metoda propus

Algoritmul propus primete ca date de intrare reeaua de drumuri, locaia agentului, locaia depozitului destinaie, locaia antierelor i intervalele de timp n care trebuie livrate materialele asociate fiecrui antier.

Pentru reducerea acestui timp a fost necesar obinerea unui graf simplificat, derivat din graful care descrie reeaua de drumuri. Prin construcia grafului simplificat (fig. 5.4) s-a urmrit realizarea reducerii algoritmului de replanificare.

Fig. 5.4. Modul de obinere a grafului simplificat n cazul replanificrii rutei unui agent

25

5.3.2.3 Implementarea utiliznd solverul ASP DLV

Limbajul sistemului DLV [56] permite definirea att a constrngerilor tari, ct i a constrngerilor slabe. n cadrul soluiilor generate, constrngerile tari sunt acele constrngeri care trebuie neaprat respectate n timp ce cele slabe pot fi nclcate. Constrngerile slabe sunt utilizate pentru a realiza optimizarea problemelor.

Constrngerile tari utilizate n cadrul algoritmului propus rezolv urmtoarele probleme: calculul rutei agentului astfel nct s i continue drumul din punctul de unde se realizeaz

replanificarea i s ajung la depozitul destinaie trecnd prin toate antierele unde mai are de livrat materiale;

calculeaz timpul de sosire la fiecare antier (innd cont de timpul petrecut de agent pentru descrcarea materialelor);

respectarea intervalelor de timp definite la nivelul fiecrui antier. Constrngerile slabe sunt utilizate n algoritmul propus pentru a minimiza timpul petrecut n trafic de fiecare agent. Seturile de rspunsuri generate de sistemul DLV conin arcele asociate rutei agentului. Construcia rutei se realizeaz prin ordonarea acestor arce. 5.3.2.4 Implementarea utiliznd solverul CP Choco

Datele de intrare pentru algoritmul de planificare a rutelor agenilor implementat n solverul Choco sunt: antierele cu intervalele de timp asociate i graful simplificat a reelei de drumuri.

Pentru a rezolva problema propus a fost utilizat constrngerea global ),( nsrestrictioxtree [55] definit n cadrul solverului.

Matricea costurilor reprezint o matrice ptratic n care sunt introdui timpii medii de parcurgere ai arcelor. Numrul liniilor i coloanelor este dat de numrul de antiere la care agentul trebuie s livreze materialele la care se adun numrul 2 (locaia agentului i depozitul destinaie). Pentru a obine rezultate ntr-un timp ct mai scurt s-a realizat o ordonare a nodurilor n cadrul matricei costurilor. Aceasta a fost realizat n urmtorul mod. Prima coloan reprezint costurile arcelor care unesc nodul reprezentat de poziia actual a agentului i toate cele x noduri. Urmtoarele coloane reprezint costurile arcelor care unesc nodurile reprezentate de antierele i toate cele x noduri. Ultima coloan reprezint costurile arcelor care unesc nodurile reprezentate de antierele i toate cele x noduri.

antierele au fost ordonate n funcie de intervalele de timp definite pentru fiecare. A fost considerat ordinea cresctoare a mijlocului intervalului de timp.

Suma costurilor arcelor reprezint variabila obiectiv a algoritmului. Scopul este de a minimiza aceast valoare, astfel nct timpul petrecut de agent n trafic s fie ct mai scurt.

Pentru ca agenii s nu treac de mai multe ori pe la acelai antier a fost utilizat constrngerea )x,...,x(ntallDiffere n 1 .

5.3.3 Procesul de decizie al agentului dispecer

5.3.3.1 Scenariul

Scenariul se refer la crearea rutelor iniiale ale agenilor mobili inteligeni. Livrarea materialelor de ctre ageni trebuie s se realizeze astfel nct intervalele de timp s fie respectate i

26

timpul petrecut de ageni n trafic s fie ct mai mic. Acest scenariu reprezint o variant extins a scenariului prezentat la procesul de decizie a agenilor mobili inteligeni. 5.3.3.2 Metoda propus

Reeaua de drumuri, numrul depozitelor, materialelor depozitate n cadrul fiecrui depozit i numrul agenilor care sunt disponibili reprezint datele de intrare pentru algoritm. Algoritmul propus asociaz agenii cu depozitele astfel nct un agent s nu poat fi atribuit mai multor depozite, asigur ca toate materialele de construcie s fie livrate la antierul asociat n intervalul de timp stabilit i minimizeaz timpul petrecut de ageni n trafic.

Reprezentarea reelei de drumuri este fcut ca i n cazul algoritmului de replanificare a rutelor la nivelul unui agent printr-un graf simplificat (fig. 5.8) [15].

Fig. 5.8. Modul de obinere a grafului simplificat n cazul planificrii rutelor iniiale

5.3.3.3 Implementarea utiliznd solverul ASP DLV

Algoritmul pentru planificarea rutelor agenilor reprezint o variant extins a algoritmului utilizat n cazul replanificrii rutei unui singur agent. Din acest motiv au fost pstrate constrngerile tari utilizate pentru crearea rutei unui agent, acestea fiind readaptate la construcia mai multor rute. Constrngerile care au fost adugate au fost cele prin care se realizeaz atribuirea materialelor de construcie agenilor.

Constrngerile slabe, ca i n cazul planificrii rutei unui agent, sunt utilizate pentru a minimiza timpul petrecut n trafic de ageni.

Seturile de rspunsuri generate de sistemul DLV conin arcele asociate fiecrui agent. Predicatul way este caracterizat prin identificatorul agentului, nodul de start a arcului, nodul de final al arcului i costul arcului. Pe baza acestor arce sunt generate rutele fiecrui agent. 5.3.3.4 Implemetarea utiliznd solverul CP Choco

Datele de intrare pentru algoritmul de planificare a rutelor agenilor, implementat n solverul Choco, sunt: numrul agenilor, numrul depozitelor, antierele cu intervalele de timp asociate i graful simplificat al reelei de drumuri.

Matricea costurilor n acest caz este construit n felul urmtor. Primele coloane reprezint costurile arcelor care unesc nodurile reprezentate de ctre depozitele de start i toate cele x noduri. Urmtoarele coloane reprezint costurile arcelor care unesc nodurile reprezentate de antierele i toate cele x noduri. Ultima coloan reprezint costurile arcelor care unesc nodurile reprezentate de antierele i toate cele x noduri.

27

antierele au fost ordonate, ca i in cazul algoritmului de replanificare pentru un singur agent, dup ordinea cresctoare a mijlocului intervalului de timp.

Suma costurilor arcelor reprezint i n acest caz variabila obiectiv a algoritmului. Scopul este de a minimiza aceast valoare, astfel nct timpul petrecut de ageni n trafic s fie ct mai scurt. Pentru ca agenii s nu treac de mai multe ori la acelai antier i n acest caz a fost utilizat constrngerea ),...,( 1 nxxntallDiffere .

5.3.4 Rezultate Primul lucru observat n urma testrii ambilor algoritmi implementai cu DLV ct i cu

Choco a fost faptul c partea de optimizare a algoritmilor conduce la creterea timpului n care sunt generate soluiile.

n cazul implementrii algoritmilor utiliznd sistemului DLV, constrngerile slabe nu au putut fi eliminate deoarece fr utilizarea acestor constrngeri nu se poate obine reducerea timpului petrecut de ageni n trafic. Soluia gsit pentru a mbunti timpul de generare a soluiilor a fost de a aduga n invocaia sistemului cmpul tbountcos (se limiteaz valoarea costului total al rutelor agenilor) i N (se limiteaz valoarea maxim a ntregilor care fac parte din algoritmi).

i n cazul solverului Choco se pune problema ngrdirii costului total al rutelor agenilor. Aceasta deoarece timpul necesar cutrii soluiei optime este mare n comparaie cu timpul necesar generrii soluiilor dorit a fi obinut n cazul acestor algoritmi. Acest lucru este realizat prin ncadrarea valorii costului total al rutelor ntr-un anumit interval.

Testele au fost realizate pe un calculator cu procesor Intel Core I5 cu frecvena de 2,27 GHz (Gigahertz) i RAM (Random Access Memory) de 4GB (MegaByte). 5.3.4.1 Algoritmul de planificare a rutelor agenilor mobili inteligeni

n cazul acestui algoritm valoare maxim a costului rutelor agenilor maxCostAgenti este calculat utiliznd urmtoarea formul: serLocConsmaxmax t*NrIntCostAgenti (5.21) unde,

maxInt reprezint valoare maxim a ntregului acceptat n cadrul sistemului; LocConsNr reprezint numrul antierelor unde mai trebuie livrate materiale;

sert reprezint timpul petrecut de un agent la fiecare antier. n cazul implementrii utiliznd sistemul DLV valoarea maxim a ntregului maxInt se

calculeaz utiliznd urmtoarea formul: AgentiogPrmax NrTInt (5.22) unde,

ogPrT reprezint numrul maxim de ore pe care le lucreaz fiecare agent; AgentiNr reprezint numrul agenilor care livreaz materiale.

Timpii generrii soluiilor rezultai n urma testrii celor dou implementri sunt prezentai n tab. 5.1 [14].

28

Tab. 5.1. Rezultatele algoritmului de planificare a rutelor agenilor mobili intelegeni Depozite Ageni Clieni

Timp DLV

[secunde]

Timp Choco

[secunde] 1 3 10 3.59 0.32 1 3 15 11.33 0.45 1 3 20 13.97 0.54 1 4 10 12.45 0.36 1 4 15 18.87 0.43 1 4 20 23.75 0.56 2 6 20 25.75 1.12 2 8 20 12.31 1.88 3 9 25 13.35 1.98 3 12 25 33.55 2.12 3 12 50 - 8.25

5.3.4.2 Algoritmul de replanificare a rutelor agenilor mobili inteligeni n cazul acestui algoritm valoare maxim a costului rutei unui agent maxCost este calculat

utiliznd urmtoarea formul: ITTCost parcursEstSosiremax (5.23) unde,

EstSosireT reprezint timpul de sosire la depozitul destinaie calculat la replanificare precedent sau la planificarea iniial n cazul n care aceea reprezint prima replanificare;

parcursT reprezint timpul parcurs de agent de la replanificare precedent sau la planificarea iniial n cazul n care aceea reprezint prima replanificare; I reprezint ntrzierea maxim acceptat.

n cazul implementrii utiliznd sistemul DLV valoarea maxim a ntregului acceptat n cadrul sistemului maxInt se calculeaz utiliznd urmtoarea formul: serLocConsmaxmax t*NrCostInt (5.24) unde,

maxCost reprezint valoare maxim a costului rutei unui agent; LocConsNr reprezint numrul antierelor unde mai trebuie livrate materiale;

sert reprezint timpul petrecut de un agent la fiecare antier. Timpii generrii soluiilor rezultai n urma testrii celor dou implementri sunt prezentai

n fig. 5.11 [14].

Fig. 5.11. Rezultatele algoritmului de replanificare a rutelor agenilor mobili intelegeni

29

5.3.4.3 Analiza comparativ a implementrilor algoritmilor Criteriile pe baza crora s-a realizat analiza comparativ a celor dou implementri sunt

urmtoarele [14]: modelarea problemei de programare (ct de intuitiv este modelarea), modelarea constrngerilor (posibilitatea definirii de noi constrngeri), suport pentru controlul cutrii (dac utilizatorul poate defini noi strategii de cutare a soluiilor) i timpul de generare a soluiilor.

Din punctul de vedere al modelrii problemelor de programare sistemul DLV s-a dovedit a fi o form care permite modelarea facil a acestui tip de probleme n special pentru utili