Rendszertervezés laboratórium 2 (vimiad02)

MIT3 - Versengő ágensek intelligens elosztott rendszerekben - Elektronikus jegyzőkönyv - BME-MIT

Bevezetés

Célkitűzések

Jelen labormérés célja, hogy a hallgatók játékos formában és minimális programozási teher mellett ismerkedjenek meg az árveréssel, mint az informatikai kooperatív protokollok egyik fontos formájával. A méréshez egy teljes grafikus keretrendszert biztosítunk. A célunk ezzel az, hogy a hallgatók a kreativításukat a nyertes (vagy csak egyszerűen érdekes) licit stratégiák kitalálásában, összemérettetésében és az utólagos értékelésében éljék ki.

A MIT3 és MIT4 labormérések lebonyolítása a hagyományostól eltérő módon történik úgy, hogy a hivatalosan az órarendben ütemezett laboralkalmak során mindössze konzultációs lehetőséget nyújtunk, mely konzultáción a részvétel nem kötelező. A labor teljesítéséhez a feladatok megfelelő szinten történő kidolgozása és jelen elektronikus jegyzőkönyv határidőre történő beadása a követelmény a https://hf.mit.bme.hu portálon keresztül. A mérés során a hallgatók önállóan dolgoznak, a feladat teljesítése és értékelése is egyénileg (nem mérőpárokban) történik. A mérés tervezett időigénye: 1 óra felkészülés, 1 óra ismerkedés a keretrendszerrel valamint 3 óra ágens fejlesztés, kísérletezés és dokumentálás.

Ágensek és aukciók

Az árverés általánosságban az olyan áruknak való vételi-eladási procedúrája, amikhez nemigen rendelhető hozzá egy konkrét árcímke. Ilyen lehet pl. egy kép, egy ékszer, egy könyvritkaság, de lehet egy értékes ércmennyiség, kommunikációs frekvenciasáv egy része, vagy egy telephely. Gépi ágenseknél az árverés egy fontos protokoll, mert a versengő ágensek körében egyfajta kooperatív megoldást kényszerít ki az olyan "áruk" megosztásában, mint a végzendő feladat, átadható erőforrás, leköthető (segítségre fordítható) időtartam, kölcsönösen elfogadott elosztott problémamegoldás, stb. Az árverésen az árajánlatok (licitek), a stratégiák és a kimenetel meghatározza, hogy ki kapja az árukat és mennyit fizet. A legegyszerűbb (és a közéletben megszokott) árveréseknél azt tételezzük fel, hogy:

  1. egyetlen áru van,
  2. mindegyik ajánlattevőnek van egy hasznosságértéke az árura, és
  3. ezek az értékek csak az ajánlattevő számára ismertek.

Az ajánlattevők megteszik az ajánlataikat, és a legmagasabb ajánlat nyeri el az árut, de a konkrét árveréstípus lebonyolítási szabályai határozzák meg, hogyan tehetők meg az ajánlatok, és mi a győztes által fizetendő ár (ami nem szükségszerűen a licitje). Az árverések legismertebb típusa az angol árverés (English auction), amelyben az árverező mindaddig növeli az áruk árát, amíg csak egyetlen ajánlattevő marad, ellenőrizve közben, hogy vajon az ajánlattevők érdekeltek-e még. Az árverás alapvető tulajdonsága, hogy a legnagyobb hasznosságértékkel bíró ajánlattevő nyeri el az árukat (bmax + d) áron, ahol bmax a legmagasabb ajánlat az összes többi résztvevő között, és d a nyertes résztvevő benevezett utolsó licitnövekménye.

A mérésben egy angol árverés keretein belül próbálhatják ki, hogy mennyire ügyesek árverési licitstratégiák megalkotásában!

Az AuctionFramework keretrendszer

Bevezetés

Az AuctionFramework keretrendszer egy Java alkalmazás, melyet teljes forráskóddal innen tölthető le. Az alkalmazás AuctionFramework főosztályának main() metódusával futtatható és önálló grafikus felülettel rendelkezik. A szimulátorban implementált aukció a hagyományos angol aukció.

A keretrendszerrel együtt három mintaágenst teszünk közzé, melyek stratégiája az alábbi:

A grafikus szimulátor

A keretrendszer grafikus felületének főablakát az alábbi ábra szemlélteti.

A felhasználói felületen a következő beállítások végezhetők el:

A szimuláció a következő eszközökkel vezérelhető:

A fenti képen látható beállításokat nem módosítva a Load gombra kattintva a szimulátor a „Minden tétel.txt” fájlból betölti a licit tárgyait, létrehoz 1-1 példányt az 1-es és 3-as ágensből, valamint 2 példányt a 2-es ágensből. Minden ágens az összesített licitérték 10%-ával gazdálkodhat, ami jelen esetben 77 000 egység keretet jelent.

A szimuláció betöltése után az Items offered mezőben kék színnel láthatók a licitre váró elemek. Az egyes kék egységek fölé helyezve a kurzort az elemek leírása és kikiáltási ára látható. A bal szélen a Participant agents panelben minden résztvevő ágenshez egy-egy panel tartozik. Itt látható az ágens vagyona, illetve az, hogy egyelőre egyetlen tételt se vásároltak meg.

A szimulációt a Step gombbal léptetve a keretrendszer megvételre kínálja az első tételt az 1500 egységes kikiáltási áron. A résztvevő ágensek zöld színükkel jelzik, hogy a kikiáltási áron licitálni kívánnak a termékre.

A Step gomb ismételt lenyomásával a keretrendszer 1600-ra emeli a licitálási árat.

Látható, hogy az első két ágens nem kíván licitálni, míg a második kettő továbbra is versenyben marad. (Ez összhangban van az ágensek fentiekben ismertetett stratégiájával, hiszen Agent1_1 csak kikiáltási áron hajlandó válaszolni, Agent2_1 és Agent2_2 véletlenszerűen dönt, Agent3_1 pedig addig tartja a licitet, amíg a pénzéből futja rá.)

A Step gomb néhány további megnyomása hatására (amikor véletlenül Agent2_1 és Agent2_2 sem tartja a licitet) Agent3_1 megnyeri az aukciót és a termék bekerül a grafikus felületen is az általa megvásárolt termékek közé. A grafikus felület a tárgyakra a zöld-piros színtartománnyal jelzi, hogy az ágens a kikiáltási árhoz képest mennyire drágán vásárolta meg az adott elemet.

Az aukciót a Run gomb lenyomásával tovább futtatva az látható, hogy eleinte minden terméket Agent3_1 üt le, igaz, hogy erőszakos és kitartó stratégiája miatt sokszor elég drágán vásárol (időnként a kikiáltási árhoz képest ötszörös áron is).

Az ablak alján látható Efficiency grafikon azt mutatja, hogy az ágens a pénzét milyen hatékonysággal költötte el. A kikiáltási áron megvásárolt tárgyak 100%-os hatékonyságnak számítanak, a drágábban megszerzett tárgyak arányosan rontják a hatékonyságot. A fenti ábrán látszik, hogy az Agent3_1 70-80%-os hatékonysággal dolgozik. A grafikont Fortune nézetre kapcsolva az ágensek eddig megszerzett vagyona látható.

Az aukció jelen fázisában egyedül az Agent3_1 rendelkezik vagyonnal, azonban pénzügyi kerete máris 12 200 egységre apadt. A szimulációt tovább futtatva látható, hogy az Agent3_1 már a 40. elem előtt elkölti teljes vagyonát.

Ezt követően Agent1_1 veszi át a vezetést, viszont az ő pénzügyi kerete is hamar kimerül. Ami az ágensek hatékonyságát illeti, az első három ágens minden kikiáltási árhoz közel vásárolt meg (Agent1_1 konkrétan kikiáltási áron, a másik két ágens minimálisan e felett), így a hatékonysága ennek a három ágensnek közel azonos.

A szimulációt végigfuttatva az alábbi helyzet áll elő.

Látható, hogy a túl erőszakos stratégiát választó Agent3_1-től eltekintve az ágensek 98-100%-os hatékonysággal működtek. Az is látható, hogy az ágenseknek nem volt elég pénzügyi keretük az összes terméket megvásárolni (bal oldalon maradtak szürke tárgyak, amikre senki nem tudott vagy akart licitálni), ami nem meglepő, hiszen a 4 ágens össztőkéje csak a meghirdetett tárgyak összértékének felét tette ki.

Ha most a szimulációt újrafuttatjuk az ágensek összvagyonát jelentősen növelve (minden ágensnek a teljes licitérték felét pénzügyi keretként odaadva), akkor alapvetően megváltoznak az erőviszonyok.

Ebben az esetben Agent3_1 hatékonysága továbbra is jelentősen rosszabb a többiekénél (85% a többiek 95% feletti értékéhez képest), azonban az aukció végén vagyona bőven meghaladja versenytársai vagyonát.  A fenti példából jól látható tehát, hogy különböző peremfeltételek mellett ugyanaz a stratégia is nagyon eltérő mértékben lehet eredményes, illetve rávilágít arra is, hogy egy a körülményeket és a többiek viselkedését figyelmen kívül hagyó fixen bedrótozott (akár erőszakosan licitáló, akár erősen spóroló) stratégia univerzálisan nem lehet sikeres.

Ágensek fejlesztése

A keretrendszer egy hagyományos alkalmazás formájában került megvalósításra. Az alkalmazáson belül két package található: az auctionagents tartalmazza az aukcióban résztvevő ágens osztályokat, míg a keretrendszer minden egyéb forrásfájlja az auctionframework package-ben kapott helyet.

Az ágensek forráskódja

Az auctionagents package tartalmazza a fenti példában szereplő Agent1, Agent2 és Agent3 ágensek forráskódját, melyek mind az AbstractAgent osztályból származnak. Az osztálynak két fontos függvénye van:

Az ágensek intelligenciájának fejlesztése alapvetően tehát e két függvény megfelelő implementálását jelenti.

Az ágens érzékelése

Az ágens döntése meghozatalakor a következő ismeretekre támaszkodhat:

Az ágens beavatkozási lehetősége

Az ágens az ask() függvény által visszaadott igaz logikai értékkel tartja az adott licitet, míg hamis visszaadott értékkel kiszáll az adott licitből. Az implementált aukció működésével kapcsolatban az két fontos körülményre szeretnénk felhívni a figyelmet.

Amennyiben az ágens egy licit lépcsőben úgy dönt, hogy kiszáll, ha van az adott tárgyra magasabb lépcső, akkor ott még bármikor újra visszaszállhat. Az tehát, hogy például az 1000 értékű licitlépcsőben az ágens nem tartotta a tétet nem jelenti azt, hogy az 1100-as, 1200-as stb. lépcsőknél (feltéve, hogy még lesznek ilyenek) ne léphetne be ismét aktív licitálóként.

Ha egy bizonyos licitlépcsőn több ágens is tartotta a tétet, majd a következő lépcsőn már senki nem tartja a megemelt tétet, akkor az előző lépcsőn jelentkező közül valaki véletlenszerűen kiválasztva viszi el a tárgyat.

Mérési feladatok

Feladatok

A mérés során a feladat a fentiekben ismertetett AuctionFramework keretrendszerben három saját stratégiával működő ágens implementálása majd az ágensek teljesítményének értékelése a szimulátor használatával. A feladatok során a fő hangsúly nem bonyolult programkód írására helyezendő, a cél sokkal inkább kreatív ágens stratégiák kitalálása és egyszerű implementálása, valamint kísérletezés az ágensekkel a peremfeltételek változtatása mellett!

Előkészületek

A feladatok megoldása során használja a „Minden tétel.txt” aukciós katalógus fájlt, és az ágensek vagyon szorzója mindig 0.4 legyen!

1.  Feladat

Módosítsa az Agent1 forráskódját úgy, hogy egy Ön által kitalált stratégia alapján működjön! Futtassa le a szimulációt úgy, hogy csak 3 db Agent1 típusú ágens vesz részt! 

1. kérdés

Ismertesse röviden szövegesen az első megvalósított stratégia működését!

2. kérdés

Másolja be az ágens ask() függvényének kommentekkel ellátott forráskódját!

3. kérdés

Készítsen egy képernyőképet az ágensek viselkedéséről a szimuláció végén a grafikon Fortune nézetében!

Ehhez a válaszhoz kép csatolása szükséges.

4. kérdés

Értékelje az eredményeket! A körülmények megváltozása (például az ágensek számának növekedése, a rendelkezésre álló keretösszeg megváltozása, a licitre kínált tárgyak számának változása, stb.) hogyan befolyásolná az ágensek eredményességét?

2. Feladat

Az Agent2 ágens forráskódjának módosításával hozzon létre egy olyan (az első ágenstől eltérő stratégiájú) ágenst, mely eredményesen képes felvenni a versenyt az első ágenssel. Futtassa a szimulációt 2db Agent1 és 2db Agent2 részvételével!

5. kérdés

Ismertesse röviden szövegesen a második megvalósított stratégia működését! Milyen előnyöket nyújt ez a stratégia az elsőhöz képest?

6. kérdés

Másolja be az ágens ask() függvényének kommentekkel ellátott forráskódját!

7. kérdés

Készítsen egy képernyőképet az ágensek viselkedéséről a szimuláció végén a grafikon Fortune nézetében!

Ehhez a válaszhoz kép csatolása szükséges.

8. kérdés

Értékelje az eredményeket! A körülmények megváltozása hogyan befolyásolná az ágensek eredményességét?

3. Feladat

Az Agent3 ágens forráskódjának módosításával hozzon létre egy harmadik stratégiával dolgozó ágenst úgy, hogy az mindkét korábbi ágens típus bizonyos gyengeségeit képes legyen kihasználni! Futtassa a szimulációt mindhárom ágenstípusból 1-1 résztvevővel!

9. kérdés

Ismertesse röviden szövegesen a harmadik megvalósított stratégia működését! Milyen előnye van ennek a stratégiának a másik kettőhöz képest?

10. kérdés

Másolja be az ágens ask() függvényének kommentekkel ellátott forráskódját!

11. kérdés

Készítsen egy képernyőképet az ágensek viselkedéséről a szimuláció végén a grafikon Fortune nézetében!

Ehhez a válaszhoz kép csatolása szükséges.

12. kérdés

Értékelje az eredményeket! A körülmények megváltozása hogyan befolyásolná az ágensek eredményességét?

Értékelés

A laborfeladatokat a benyújtott elektronikus jegyzőkönyv alapján értékeljük. Minden részfeladat megoldása egy jegyet jelent, illetve további egy jegyet adunk a kitalált stratégiák kreativitása és az elvégzett elemzések és megfontolások alapossága alapján.

Ajánlott irodalom és további felkészülési anyagok

Ajánlott irodalom a mérésben alkalmazott angol aukcióhoz.

Ajánlott (de a méréshez nem szükséges) irodalom azoknak, akik az aukciókról többet szeretnének tudni.

Abszolute ajánlottnak nem nevezhető irodalom olyan komolyabb informatikai érdeklödőknek, akik esetleg kiváncsiak arra, hogy az aukciós protokollok milyen alkalmazásokra tehetnek szert az infomatikában a megszokott internetes „kütyü” árveréseken túlmenően.