Sistemele multi-agent si Licitatia

Introducere

Sistemele multi-agent sunt una dintre cele mai promitatoare tehnologii dezvoltate in cadrul Inteligentei Artificiale (AI). Intuitiv definit, un agent nu este altceva decat un program care actioneaza autonom, reactioneaza la mediul in care este aplicat, dar si proactiv, in sensul ca poate initia actiuni proprii pentru a-si atinge scopurile pentru care a fost construit.

Agentii pot fi sau fizici sau virtuali. De exemplu, un robot trimis sa exploreze un teritoriu nefamiliar poate fi un agent (robotii autonomi trimisi pe Marte sau o drona care zboara fara control uman pentru a fotografia un teritoriu inamic).

Exemplele unde asemenea programe sunt importante sunt multe.

Unul dintre ele (probabil printre cele mai cunoscute) este comertul electronic. Sa luam de exemplu un consumator care doreste sa cumpere online unul sau mai multe produse de pe un site de licitatii electronice, cum ar fi Ebay.

Un agent ar trebui sa identifice cele mai bune oportunitati de cumparare a respectivului bun/bunuri, sa le selecteze pe cele care satisfac cel mai bine preferintele utilizatorului si, cel mai important, sa liciteze astfel incat sa obtina cel mai bun pret posibil.

Daca asta pare o utopie, trebuie spus ca o parte din tranzactiile online sunt deja automatizate. De exemplu, exista un sistem care permite cresterea automata a pretului pe Ebay pana la o limita stabilita de cumparator. Acest sistem (chiar daca este denumit de site "agent" este, insa, departe de a fi "inteligent", in sensul dat in AI).

Nu doar bunurile "fizice" sunt vandute online, ci si cele virtuale. De exemplu, spatiul disponibil pe ecranul unui utilizator care navigheaza pe web (asa-numitul "spatiu de atentie") are o valoare de reclama destul de importanta. De fiecare data cand folosim un motor de cautare, de exemplu Google sau Yahoo!, o parte dintre linkurile afisate (asa-numitele "sponsored links") sunt alocate printr-o licitatie.

Astfel de licitatii se desfasoara automat, deoarece sunt mult prea frecvente pentru a permite unui utilizator uman sa le urmareasca. Putini isi dau seama ca un simplu click pentru linkurile la unii termeni de cautare (in special cei medicali sau cu valoare de litigiu in Statele Unite) se poate vinde cu cateva zeci de dolari.

O alta aplicatie, la care a lucrat si autorul acestui articol, este automatizarea negocierilor intre companiile de transport dintr-o retea logistica. Astfel, de multe ori, doua sau mai multe companii de transport pot sa isi (re)imparta ordinele de transport, astfel incat ambele sa profite de pe urma tranzactiei.

Optimizarea unor astfel de negocieri este o problema dificila, datorita complexitatii retelelor de transport ale marilor firme, dar care poate fi eficient solutionata de un sistem multi-agent.

Construirea unor agenti "inteligenti" este o disciplina complexa, care necesita atat tehnici de Inteligenta Artificiala (invatarea-masina), dar si unele tehnici dezvoltate initial in economie (in special teoria jocurilor). Dintre tehnicile de invatare-masina pot fi amintite retelele neuronale, retele Bayes, algoritmii evolutivi si multe altele.

De exemplu, retelele neuronale sunt modelate dupa functionalitatea neuronilor umani. O alta metoda o constituie algoritmii genetici (sau evolutivi). Simplu descris, acestia imita, desigur la un nivel simplificat si matematic, modul in care evolutia biologica "gaseste solutii" la probleme.

Important de subliniat este faptul ca aceste metode sunt departe de a modela complexitatea reala a proceselor biologice sau a creierului uman (o parte a acestuia inca nici nu e inteleasa pe deplin), dar s-au dovedit foarte eficiente ca metode de optimizare matematica.

In final, intrebarea care se pune in acest domeniu este: ce ne rezerva viitorul? Unii autori vorbesc de o viziune in care o serie de agenti inteligenti ne inconjoara si se ocupa de toate problemele curente din viata noastra.

Imaginati-va, de exemplu, ca telefonul mobil va contacta un alt agent din telefonul interlocutorului dvs. si va reprograma o intalnire la o alta data, daca sunteti in intarziere, fara sa fie nevoie de o secretara personala. Sau, la plecarea intr-o calatorie, va face toate rezervarile pentru cel mai convenabil hotel, zbor si bilete la diverse evenimente, gasind si cea mai buna combinatie calitate/pret.

Sau ne putem imagina un agent inglobat in cosul de cumparaturi care, la intrarea intr-un supermarket, ne recomanda produsele preferate, drumul catre raftul unde le gasim, dar gaseste si cea mai convenabila oferta de pret pentru ele. Poate face toate acestea, deoarece invata preferintele noastre pe baza vizitelor precedente, dar si pe baza preferintelor altor consumatori care au aceleasi gusturi.

Merita mentionat ca aceste tehnologii nu pun doar probleme pur tehnice, ci si sociale. De exemplu, am fi dispusi sa delegam decizii financiare (chiar unele privitoare la tranzactii reduse ca valoare) unui program software? Sau, mai relevant, in ce masura suntem dispusi sa lasam astfel de programe sa stocheze si sa comunice cu alte programe preferintele noastre.

Licitatia Olandeza

In licitatia olandeza vanzatorul oferteaza mai multe produse identice, iar cumparatorii liciteaza fiecare cu oferte de cumparare in care se specifica numarul de articole care se doresc cumparate si pretul oferit pentru un articol. Licitatia se incheie atunci cand expira perioada specificata de vanzator. Pentru stabilirea castigatorilor se ierarhizeaza cumparatorii dupa pretul oferit si dupa momentul in care a fost facuta oferta, in cazul in care mai multe oferte au acelasi pret. Castigatorii licitatiei sunt desemnati primii din ierarhie, parcurgandu-se ierarhia pana cand se cumpara toate produsele oferite spre vanzare. Acestia platesc un pret egal cu cel al ofertei castigatoare cu pretul cel mai mic. Daca doua oferte au acelasi pret, prioritate are cea facuta mai devreme.

De exemplu, sa presupunem ca se vand 10 calculatoare si avem urmatoarele oferte de cumparare:

A cumpara 3 cu 500 RON.

B cumpara 2 cu 400 RON.

C cumpara 2 cu 1000 RON.

D cumpara 10 cu 100 RON.

E cumpara 4 cu 300 RON.

F cumpara 7 produse cu 200 RON.

Castigatori sunt:

C - 2 produse (a oferit 1000 RON).

A - 3 produse (a oferit 500 RON).

B - 2 produse (a oferit 400 RON).

E - restul de 3 produse (a oferit 300 RON).

E-Commerce

Licitatia olandeza este folosita in comertul on-line. Internetul este o piata mare de desfacere a produselor si in strainatate. Printre cele mai cunoscute site-uri de licitatii se numara www.ebay.com (sept 1995), www.amazon.com, www.bidville.com. Primul site pentru comert electronic a aparut in mai 1995, Onsale. Imediat dupa aceea, a aparut Ebay. In figura de mai jos am facut o cautare pe site-ul www.ebay.com dupa un anumit tip de produse, si anume "Cameras & Photo". Imi apare fiecare produs disponibil, iar in dreptul fiecarui produs este scris numarul de licitatori, pretul si timpul ramas pana la incheierea licitatiei.

Licitatia olandeza presupune din start vinzarea mai multor produse. Se fixeaza un pret minim, sub care obiectele nu se pot instraina. Cumparatorii pun cite un pret pentru un anumit numar de obiecte. In final, sistemul acorda obiectele in functie de pretul oferit.

Agenti in E-Commerce

Din perspective utilizatorului unei astfel de solutii de comert online, adica licitatia olandeza, un agent este un program care ajuta oamenii si actioneaza in numele lor. Agentii pot avea urmatoarele caracteristici :

- lucreaza continuu pentru a atinge un obiectiv, care este dat de proprietarul lor. Durata lor de viata este data de proprietarii lor. Agentii pot ramane in viata dupa ce si-au atins obiectivul, pana ceand sunt opriti in mod explicit de catre proprietari.

- sunt capabili sa interanctioneze cu mediul in care isi desfasoara activitatea. Ei simt schimbarile mediului si actioneaza in functie de aceste modificari.

- pot comunica de asemenea cu agenti pereche prin protocoale de coordonare/comunicare si isi pot impartasi cunostintele astfel incat obiectivele sa fie atinse cat mai repede.

- pot avea control asupra propriilor actiuni si necesita minimul de efort uman. Ei sunt capabili sa lucreze independent, fara interventia umana directa.

- pot adapta comportamentul in conformitate cu experientele lor pentru a se potrivi cu preferintele si interesele diferitilor utilizatori.

- pot calatori de la o gazda la alta. Capacitatea de a calatori le da posibilitatea de a se muta la un sistem care contine un obiect cu care agentii respectivi doresc sa interactioneze.

Modelul Markov Chain pentru licitatia olandeza

Ofertantul vine din coada de

asteptare,reviziteaza licitatia

Cumparatorul este interesat,dar nu este

dispus sa plateasca atat

Un nou ofertant 

soseste la licitatie

Vanzatorul inregistreaza

castigatorul final al licitatiei

Etapele acestui model

S0 - un nou ofertant intra pe site-ul pe care se face licitatia. El ramane in S0 doar daca nu trimite o oferta sau decide sa mai astepte.

- se trece din S0 in S1 daca ofertantul decide sa reviziteze mai tarziu licitatia. Coada de asteptare contine toti cumparatorii precedenti care asteapta.In acest moment, licitatorul modifica pretul de la suma $P la $P-$C .

- un cumparator existent in coada de asteptare decide sa reviziteze licitatia, pentru a verifica noul pret pus de licitator. Decizia este aceeasi ca in cazul sosirii unui nou ofertant pe site. Se trece din starea S1 in starea S0 ori de cate ori un ofertant vrea sa iasa din coada de asteptare.

- daca noul ofertant este de acord cu suma $P, atunci licitatorul il inregistreaza ca final castigator si se trece din starea S0 in starea S2.

Licitatia olandeza este numita dupa cel mai cunoscut exemplu pe care il pot da, Licitatia olandeza a florilor.

Flora Holland este o organizatie alcatuita din urmatoarele licitatii de flori(in ordinea cifrelor de afaceri) : Aalsmeer, Naaldwijk, Rijnsburg, Bleiswijk, Venlo si Eelde, prima fiind cea mai mare.

In timp ce licitatiile Bleiswijk, Venlo si Eelde servesc pietei locale, celelalte trei sunt desemnate ca locatii de export. Cel mai mare concurent al organizatiei Flora a fost VBA in Aalsmeer, dar cei doi concurenti au socat industria prin anuntul pe care l-au facut cu intentia lor de a se unii. Cele doua organizatii si-au alaturat fortele din 1 ianuarie 2008.

Remote buying (KOA)

Ca si la licitatiile cu imagini, unde produsele nu sunt prezente fizic la licitatia ceas, cu « Remote buying »( cumpararea la distanta), cumparatorii nu sunt nevoiti sa stea intre standuri. Numarul de companii care aleg ca metoda de comert « cumpararea la

distanta » creste din ce in ce mai mult. Deseori, ei stabilesc o camera speciala in companie care sa se ocupe de acest obiectiv. Ca si cultivator, poti urmari online pe Internet cum decurge pocesul de cumparare. In figura urmatoarea putem observa detalii despre modul in care se face licitatia si cumpararea la distanta, datele care se introduc si ceasul care masoara timpul parcurs in licitatie.

Cum functioneaza KOA?

Pe ecranul tau, un ceas este tot timpul afisat ca ceas principal. Acesta poate fi folosit pentru cumpararea la distanta Celelalte ceasuri apar pe fundal, deci poti sa comuti de pe un ceas pe urmatorul rapid. Pe langa ceasul principal, mai poti avea deschise inca cinci ceasuri  pe ecran pentru a urmarii aceste licitatii de-odata. Aceste ceasuri splimentare afiseaza numele cultivatorului, produsul, si structura pretului.

Cumparatorii la distanta pot sa downloadeze informatia din ziua de aprovizionare, fiecare zi de licitatie incepand de la ora 4 dimineata. Practic, aceasta inseamna ca de la ora 5 dimineata deja ai toate informatiile de care ai nevoie pentru aproximativ 99.9% din totalul de flori taiate, serele si gradinile botanice aprovizionate pe ziua respectiva.

Pentru a mentine ceasul atractiv pentru cumparatori, restructurarea si imbunatatirea permanenta a procesului de licitatie sunt necesare. La Aalsmeer, toate ceasurile traditionale au fost deja inlocuite cu proiectii mari ale ceasurilor pe ecran. Ceasurile proiectate pe ecran au diferite setari, care permit sa fie afisate mai multe informatii. In acest fel, cultivatorii pot difuza propriile fotografii si logo-uri exact la momentul in care produsele lor sunt licitate. Aceasta ajuta clientii sa ia o decizie de cumparare buna si sigura.

Comparatii ale aplicatiilor licitatiei olandeze

Concluzii:

Licitatia olandeza este o metoda foarte buna de a obtine profit, tocmai de aceea este folosita in multe aplicatii. Site-urile despre care am vorbit sunt folosite de foarte multi oameni, si cu siguranta numarul acestora se va mari. In acest moment increderea oamenilor in aceste site-uri este limitata, deoarece multi dintre noi ne temem sa incercam ceva nou. Tehnologia avanseaza, asa cum si gandirea noastra se va schimba cu timpul, si ne va fi mult mai usor sa gasim produsele de care avem nevoie si sa le cumparam la distanta.

Putem alege dintr-o gama variata de produse, putem chiar sa negociem pretul acelui produs, deci cu siguranta aceasta metoda de a cumpara ne va fi la indemana tuturor.

Probabil ca, in viitorul nu foarte indepartat, agentii inteligenti vor juca un rol major in desfasurarea acestor tehnici de negociere si probabil se va incerca crearea unor agenti mult mai destepti care se se ridice la un nivel cat mai real si care sa schimbe modul in care oamenii cumpara si vand bunuri si servicii.

Bibliografie :

R. Murch and T. Johnson, Intelligent Software Agents, chapter 14, pages

131{137, Prentice Hall, 1999.

2. N. Jennings, K. Sycara, and M. Wooldridge, A roadmap of agent research

and development, in Journal of Autonomous Agent and Multi-Agent Systems,

pages 7{38, 1998.

3. https://www.ebay.com, eBay.

T. Kimoto and K. Asakawa, Stock market prediction system with modular

neural networks, in Proceedings of the IJCNN, pages 1{6, San Diego, 1990.

5. https://www.floraholland.com/en/Pages/default.aspx

6.https://www.cse.cuhk.edu.hk/~lyu/student/mphil/anson/anson_thesis.pdf