Babeş-bolyai university of cluj-napoca

2.2 Sisteme multi-agent

Inteligența artificială distribuită este un domeniu de cercetare din aria inteligenței artificiale, fiind o combinație a mai multor domenii precum: informatica, sociologia sau psihologia; dedicată dezvoltării de soluții distribuite pentru probleme complexe, considerate ca având nevoie de inteligență. Inteligența artificială distribuită în sine este împărțită în două subdomenii în concordanță cu P. Stone în [32]: un domeniu de rezolvare a problemelor distribuite și un domeniu al sistemelor multi-agent. Principalele subiecte considerate în programarea sistemelor distribuite sunt probleme de management al informației cum ar fi descompunerea și sintetizarea. De exemplu, o problemă ar putea fi divizată în mai multe subprobleme total independente, mai apoi rezolvate și în cele din urmă asamblate pentru a oferi o soluție problemei originale.

Sistemele multi-agent(SMA) sunt sisteme alcătuite din mai mulți agenți inteligenți care împărtășesc același mediu, de obicei cu posibilitatea de a comunica, coopera sau negocia cu scopul de a-și atinge obiectivele pentru care au fost dezvoltați. Aceste sisteme sunt utilizate în rezolvarea problemelor complexe unde un singur agent sau limitările acestuia nu sunt suficiente.

Caracteristicile sistemelor multi-agent pot fi definite după cum urmează [33]:

• 
  Fiecare agent are informații sau capacități de rezolvare a problemei incomplete și, prin urmare are un punct de vedere limitat.
  
• 
  Nu există un sistem de control la nivel global, ceea ce înseamnă că fiecare agent este o entitate autonomă, fără control, care acționează pe cont propriu.
  
• 
  Datele nu sunt centralizate, fiecare agent având propriul set de informații despre mediul înconjurător.
  
• 
  Calculul se execută în mod asincron.
  

Caracteristic, în sistemele multi-agent fiecare agent are un obiectiv bine definit, urmărind realizarea propriului scop indiferent de obiectivele celorlalți. Cu toate acestea, există situații în care sistemul are un obiectiv global care este prioritar tuturor agenților. Când dezvoltatorii proiectează sisteme multi-agent se confruntă cu două probleme cheie. Prima problemă cunoscută sub numele de problema agent sau micro-problema, este de a dezvolta agenți autonomi cu scopul de a-și îndeplini obiectivele. A doua problemă cunoscută sub numele de problema socializării sau problema macro, este de a proiecta un sistem în care agenții interacționează într-un mod util și coerent. Unele dintre avantajele SMA sunt descrise în cele ce urmează ([33]):

• 
  eficiență de calcul ridicată prin concurență;
  
• 
  fiabilitate îmbunătățită prin redundanță;
  
• 
  extensibilitatea sistemului cu noi agenți și posibilitatea de a schimba capacitățile agenților;
  
• 
  îmbunătățirea mentenabilității datorită modulelor;
  
• 
  reutilizarea agenților în diferite sisteme.
  

Sistemele multi-agent au o gamă largă de utilizare în domenii precum: transportul, jocuri, logistică, producție, planificare, control, de simulare sau de modelare a structurilor sociale.

2.2.1 Comunicarea în sistemele multi-agent

Pentru o comunicare și o coordonare eficientă agenții trebuie să interschimbe date între aceștia. Limbajele de comunicare ale agenților le permite acestora să formeze o adevărată societate, fără a expune procesele lor interne, abordând astfel probleme care un agent individual nu le-ar putea soluționa. Există două abordări principale atunci când discutăm despre comunicarea agenților, prima abordare este bazată pe limbajele de comunicare dedicate agenților, iar cea de-a doua bazată pe așa numitele sisteme Blackboard. În cele ce urmează vom detalia cele două abordări menționate.

Asemănător oamenilor, care folosesc limbajul natural pentru a se exprima, agenții utilizează un limbaj de comunicare specific (Agent Communication Language - ACL) cu scopul de a interschimba informații, intenții și obiective [34]. Aceste limbaje de comunicare sunt bazate pe mesaje, unde agenții trimit mesaje unul celuilalt pentru o mai bună cunoaștere, coordonare sau în scopul unei negocieri. În sistemele multi-agent comunicarea se poate realiza sincron, după expedierea unui mesaj agentul așteaptă răspunsul, sau asincron. Datorită schimburilor multe de mesaje, în majoritatea cazurilor, agenții dezvoltă o relație client-server. Majoritatea limbajelor de comunicare ale agenților au o structură a mesajului bine definită, ce conține informații precum: expeditorul, receptorul, conținutul, performativa, ontologii etc. Un astfel de exemplu poate fi urmărit în cele ce urmează.

(tell

Sender: Agent1

Receiver: Agent2

Language: ASCII

Ontology: negociere

Content: valoare_nouă = 1000

)

2.2.1.1 Performative

O performativă este de obicei atașată conținutului unui mesaj și determină ce tip de interacțiune va fi utilizat. Semnificația acestora poate fi faptul că, conținutul este o afirmație, o interogare, o comandă sau un alt act de comunicare [40]. Performativele descriu de asemenea modul în care expeditorul dorește ca răspunsurile să fie livrate. În exemplul anterior perofmativa ”tell” este utilizată pentru a informa receptorul că mesajul expediat este unul informativ și că nu se solicită un răspuns.

2.2.1.2 Ontologii

”A specification of a representational vocabulary for a shared domain of discourse — definitions of classes, relations, functions, and other objects — is called an ontology”

[Gruber, 1993]

Folosind alte cuvinte pentru a descrie o ontologie putem spune că aceasta este o specificare conceptuală, o descriere a conceptelor și relațiilor existente într-o societate a agenților. În exemplul oferit mai sus, conținutul mesajului este plasat în contextul unei licitații, concept care este definit atât pentru expeditor cât și pentru receptor.

În ansamblul limbajelor de comunicare ale agenților, regăsim două care au influențat într-o mare măsură acest domeniu: Knowledge Query and Manipulation Language (KQML) [14] și Foundation for Intelligent Physical Agents – Agent Communication Language (FIPA-ACL) [34].

2.2.1.3 Knowledge Query and Manipulation Language (KQML)

Knowledge Query and Manipulation Language (KQML) este un limbaj de comunicare al agenților, conceput la începutul anilor ’90 de către Knowledge Sharing Efort (KSE) [14], un consorțiu condus în cea mai mare parte de către cercetători în domeniul inteligenței artificiale. După cum sugerează și numele acestuia, KMQL nu a fost inițial conceput ca un limbaj de comunicare al agenților, ci mai degrabă ca o colecție de tipuri de mesaje speech-act-like, exprimate ca șiruri de caractere ASCII, cu o sintaxă asemănătoare LISP, fiind transportate cu ajutorul protocoalelor TCP/IP, care vizează cunoașterea și schimbul de informații între sistemele software privite ca baze de cunoștințe virtuale. În zilele noastre, KMQL este privit ca un limbaj de comunicare de nivel înalt orientat spre mesaje si protocoale între agenții software. Arhitectura limbajului este un stratificată, diferențiind trei straturi semnificative: stratul de conținut (content layer), stratul mesajelor (message layer) și stratul de comunicare (communication layer). Stratul de conținut înglobează conținutul mesajului, care poate fi utiliza orice reprezentare (de exemplu: codul ASCII sau cod binar). Stratul de comunicare codifică un set de parametrii, cum ar fi identitatea expeditorului și cea a receptorului. Stratul mesajelor este nucleul limbajului KMQL, definind printre altele: protocolul de transport (TCP/IP, UDP, SMTP, IIOP etc.), limbajul conținutului, ontologia folosită și performativa atașată de expeditor conținutului.

Aceste trei straturi indică faptul că limbajul KMQL este capabil de a analiza, ruta și expedia mesaje, indiferent de conținutul acestora. Anumite caracteristici KQML includ independența față de mecanismul de transport, față de limbajul conținutului, precum și independența ontologiei utilizate în conținut.

2.2.1.4 Foundation for Intelligent Physical Agents (FIPA)

Foundation for Intelligent Physical Agents (FIPA) [34] este o organizație internațională dedicată promovării industriei agenților inteligenți prin dezvoltarea specificațiilor care suportă interoperabilitatea între agenți si aplicații bazate pe agenți. Specificațiile se refera la gestiunea agenților, limbajele de comunicare între agenți, formatul mesajelor de comunicare etc. Gestiunea agenților se refera la cadrul normativ în care agenții FIPA există și operează, stabilind modelul logic de referință pentru crearea, înregistrarea, localizarea, comunicarea, migrarea și retragerea agenților. Modelul include entitățile logice prezentate in Figura 2.1, fiecare desemnând un serviciu.

Figura 2.1 FIPA – Modelul entităților (vezi Figura 1 din [34])

Limbajul FIPA ACL are foarte asemănător cu limbajul prezentat anterior, KQML, dar sunt anumite diferențieri pe care am dori să le menționăm. Performativele limbajului FIPA ACL diferă de ce utilizate de KQML, de exemplu performativa ”tell” utilizată în limbajul KMQL este echivalentă cu performativa ”inform” utilizată de limbajul FIPA ACL. O altă diferență majoră a performativelor utilizate de cele două limbaje este faptul că performativele limbajului KQML precum: ”insert”, ”uninsert”, ”delete-one”, ”delete-all” sau ”undelete” permit manipularea directă a cunoștințelor virtuale ale altui agent, în timp ce manipularea acestor cunoștințe nu este permisă în limbajul FIPA ACL. Asemenea limbajului KQML, FIPA ACL nu face un angajament asupra unui anumit limbaj de reprezentare al conținutului, deși limbajul FIPA ACL aduce propriul său limbaj de reprezentare numit SL, limbaj bazat pe logica modală.

2.2.1.5 Sisteme Blackboard

Sistemele Blackboard sunt, în contrast cu alte limbaje de comunicare bazate pe mesaje, o abordare de comunicare centralizată. O metaforă caracteristică și utilizată des pentru a descrie aceste sisteme este prezentată în cele ce urmează:

“Imagine a group of human specialists seated next to a large blackboard. The specialists are working cooperatively to solve a problem, using the blackboard as the workplace for developing the solution. Problem solving begins when the problem and initial data are written onto the blackboard. The specialists watch the blackboard, looking for an opportunity to apply their expertise to the developing solution. When a specialist finds sufficient information to make a contribution, she records the contribution on the blackboard, hopefully enabling other specialists to apply their expertise. This process of adding contributions to the blackboard continues until the problem has been solved.”

Această metaforă prezintă anumite caracteristici ale sistemelor blackboard (35):

• 
  Expertiză independentă. În domeniul informaticii un specialist este un modul software, mai mult, în general, o sursă de cunoștințe, o unitate specializată în rezolvarea unui anumit aspect al problemei. Această abordare permite altora de a adăuga, elimina sau înlocui respectivele surse. Posibilitate de a modifica modulul software creează flexibilitate în proiectarea și mentenabilitatea unor astfel de aplicații.
  
• 
  Diversitatea tehnicilor de rezolvare a problemelor. Fiecare expert aparținând grupului poate avea o perspectivă diferită asupra modului de rezolvare al problemei.
  
• 
  Reprezentare flexibilă a informației. Informația regăsită pe tablă poate avea diferite reprezentări (de exemplu: numere, fraze, formule, desene etc.). Nu există nici o restricție în ceea ce privește structura informațiilor ce pot fi adăugate în acest sistem. Flexibilitatea în sistemele blackboard nu este definită doar de varietatea posibilităților reprezentării datelor, dar, de asemenea de datele care sunt scrise pe tablă (de exemplu: soluții parțiale sau complete, alternative, date de test etc.).
  
• 
  Limbaj comun de interacțiune. Reprezentarea flexibilă a datelor în sistemele blackboard necesită o înțelegere comună a informațiilor. Acest lucru înseamnă că orice sursă de cunoștințe ar trebui să poată accesa și procesa datele publicate în acest sistem. În practică aceste sisteme conțin o reprezentare comună utilizată de către toți experții, asemenea unei legende.
  
• 
  Actualizare în timp real. După cum am menționat anterior, în aceste sisteme, experții pot adăuga, șterge sau modifica anumite informații. De obicei acești experți nu scanează întreaga tablă pentru a detecta modificările asupra informațiilor, ci mai degrabă, aceștia așteaptă ca sistemul să îi notifice asupra acestor schimbări. Acest sistem de actualizare în timp real este foarte util atunci când pe tablă există un volum mare de date.
  
• 
  Nevoia controlului. Un sistem blackboard este format din trei componente majore: modulele de specialitate, tabla în sine și un modul de control care acționează ca un moderator între module, cu scopul de a organiza și programa acțiunile acestora. Când o informație este adăugată aceasta poate oferi informații precum gradul de calitate al contribuției, costul sau rezultatul așteptat.
  
• 
  Obținerea soluției incremental. Ca și expert, acesta pot contribui la rezolvarea problemelor, rafinarea soluțiilor existente, infirma soluții existente sau propune noi direcții în rezolvarea problemelor.
  

Figura 2.2 Organizarea sistemului blackboard (vezi Figura 23 la [37])