Ágens: Bármely élőlény akivel/amivel a világban összefuthatunk. De ugyanúgy lehet bármely cselekvésre képes entitás, mint például egy robot, vagy egy automata porszívó.

Ágensfüggvény: Az élőlényre/robotra jellemző viselkedési séma, amely tetszőleges szituációban meghatározza, hogy mit tesz.

Ágensprogram: Az élőlény testének azon része, amely kiválasztja a megfelelő cselekvést az ágensfüggvény alapján.

Racionalitás: Racionális például egy vállalat, ha profitot termel. Általában racionális valami, ha olyan cselekvéseket választ ki, amelyek az aktuális szituációban legoptimálisabbnak tűnnek.

Autonómia: Egy élőlény a viselkedési sémájának egy részét a génjeiben hordozza. Ez megfelel a beépített, a priori tudásának. Az, hogy ez mekkora rész, függ az élőlény fajától. Vannak olyan élőlények, amelyek kizárólag az örökölt viselkedést képesek követni, vannak azonban mások, amelyek képesek tanulni. Amikor egy élőlény elkezdi a tapasztalataival bővíteni a viselkedési sémáját, autonómmá válik.

Reflexszerű ágens: Egy olyan élőlény, amely szituációk egy konkrét halmazában tud mit kezdeni magával (ilyen például a ganajtúró bogár) és a szituációt mérlegelő számítás nélkül dönt, megfelel egy reflexszerű ágensnek.

Modellalapú ágens: Egy olyan élőlény, amely már rendelkezik legalább kezdetleges emlékezettel: képes megjegyezni információkat a környezetéről és azokat futási időben képes számításokon keresztül bevonni a döntésébe.

Célorientált ágens: Célorientált ágensnek tekinthető egy vállalat, amelynek célja, hogy minél nagyobb profitot érjen el, és működése közben kizárólag ez az egy elv vezérli.

Hasznosságorientált ágens: Hasznosságorientált ágensnek tekinthető például egy non-profit vállalat, amely egymással ütköző érdekeket igyekszik kielégíteni egyszerre: minél jobb szolgáltatást az adott területen, miközben lehetőleg igyekszik elkerülni, hogy adósságba keveredjen, de nem feltétlenül célja, hogy bevételt termeljen. (A különbség tehát egy célorientált ágens és egy hasznosságorientált ágens között az, hogy amíg a célorientált ágens csak a célt látja maga előtt, addig a hasznosságorientált ágens képes több cél elérésére tett erőfeszítés között mérlegelni.)

Tanuló ágens: Bármely olyan élőlény megfelel egy tanuló ágensnek, amely képes a tapasztalatait beépíteni a viselkedési sémájába, azaz tanul. Előfordulhat persze olyan helyzet, hogy valaki hibásan tanul meg valamit. Ilyenkor kudarccal végződik a tanulás.

Ágens típusok, kicsit más megközelítésben:

- Aladár egy reflexszerű ágens. Ha valamilyen inger éri, azonnal és gondolkodás nélkül cselekszik. Ha megéhezik, megeszik egy szendvicset. Ha fázik, felvesz egy pulóvert. Ha nincs nála szendvics és pulóver, kétségbe esik...

- Béla célorientált ágens. Ha valamilyen inger éri, gyorsan végiggondolja, mi lenne a legésszerűbb reakció. Ha megéhezik, megnézi, mi van a hűtőben. Ha fázik, keres valami meleg ruhát.

- Cecília hasznosságorientált ágens. Ha valamilyen inger éri, végiggondolja, mi lenne a legpraktikusabb reakció. Ha megéhezik, kiválasztja a hűtőben lévő dolgok közül, amelynek a laktatóság/kalória aránya a legjobb. Ha fázik, keres valami olyan ruhát, ami legalább egy kicsit meleg, de jól is áll neki.

A lényeges különbség a kettő között, hogy amíg a teljesítménymérték az ágens viselkedésének egészét vizsgálja, beleértve a korábban megtett lépéseket is, addig a hasznosságfüggvény csak egy adott állapotban segít kiválasztani a következő optimális cselekvést.

a) Lehetséges több mint egy ágensprogram, amely egy adott ágensfüggvényt valósít meg? Adjon meg egy példát, vagy mutassa meg, miért nem lehetséges!

A kérdés tulajdonképpen beugratós. Két ágensprogram különböző, ha különbözőképpen működik (más algoritmust valósít meg), de ekvivalens, ha ugyanarra a bemenetre ugyanazt az eredményt adja (ugyanarra az érzékeléssorozatra ugyanazzal a cselekvéssel reagál). Így azt mondhatjuk, hogy lehetséges több különböző ágensprogram, amely ugyanazt az ágensfüggvényt valósítja meg, de ekkor ezek az ágensprogramok ekvivalensek!

Jegyezzük meg, hogy az ekvivalencia ezen definíciója semmit nem mond az ágensprogram hatékonyságáról! Könnyen előfordulhat, hogy két ágensprogram ekvivalens, de az egyik lényegesen hatékonyabb, mint a másik. A jó ágensprogram szerkesztésekor a feladat tulajdonképpen az, hogy megtaláljuk az adott ágensfüggvényt megvalósító ekvivalens ágensprogramok közül a legoptimálisabbat!

b) Vannak olyan ágensfüggvények, amelyeket nem lehet programmal megvalósítani?

Az ágensfüggvény egy absztrakt matematikai függvény. Függvények programmal való megvalósíthatóságáról szól a kiszámíthatóság-elmélet. Eszerint léteznek olyan problémák, amelyekre nem létezik algoritmus, amely megoldaná őket. A válasz tehát igen, léteznek ilyen ágensfüggvények. Nem kell azonban megijedni, bármely elméletileg kiszámítható függvényhez létezik olyan program, amely kiszámítja azt, ez tehát nem jelent komoly gyakorlati akadályt.

Angol nyelven értő olvasó többet megtudhat a kiszámíthatóság-elméletről itt: http://en.wikipedia.org/wiki/Computability_theory_(computer_science)

Matematikával megérteni a világot, Beszélgetés Lovász Lászlóval (Természet Világa, 140. évf., 6. sz., 2009. június): http://www.termeszetvilaga.hu/szamok/tv2009/tv0906/lovasz.html

c) Rögzítve egy géparchitektúrát, igaz-e, hogy minden egyes ágensprogram pontosan egy ágensfüggvényt valósít meg?

Igen. Emlékeztetünk, hogy az ágensfüggvény nem feltétlenül függvény, azaz lehetséges, hogy érzékelések egy sorozatához több cselekvést is rendel, ekkor az ágens nem-determinisztikus. Erre olyankor van szükség, amikor az ágensnek valamilyen véletlenszerű cselekvést kell megvalósítania. Így tehát a véletlenszerűen viselkedő ágensprogram is pontosan egy ágensfüggvényt valósít meg. Ha pedig az ágensprogram determinisztikus, akkor a válasz triviális.

a) Mutassa meg, hogy a 2.3. ábrán látható egyszerű porszívó ágensfüggvény igenis racionális a 70. oldalon felsorolt feltételezésekkel!

Az adott feltételek mellett az ágens teljesítménymértéke az 1000 egységből álló élettartam végére legfeljebb 2000 lehetne: ennyit kapna akkor, ha minden mező minden pillanatban tiszta. Könnyen belátható, hogy az ágens a legrosszabb esetben is (amikor mindkét mező koszos kezdetben) legalább 1996 pontot kap:

Mivel egy ágensnek egységnyi időre van szüksége a porszíváshoz és a lépéshez is, ezért ahhoz, hogy minden mezőt megtisztítson, legalább három időegységre van szüksége. (Általánosságban, ha minden mező piszkos, és n mező van, akkor 2n-1 időegységre: n-re a porszíváshoz, n-1-re a mozgáshoz.) Tehát a maximális két pontot időegységenként legkorábban a negyedik időpillanattól kezdve kaphatja. Az első időpillanatban semmilyen viselkedéssel sem kaphatna pontot, hisz mindkét mező piszkos. Így tehát nincs olyan ágens, amely az adott feltételek mellett 1996-nál több pontot érhetne el. Tehát ez az ágens racionális.

b) Írjon le egy racionális ágensfüggvényt arra a módosított teljesítménymértékre, amely levon egy pontot minden elmozdulásért! Szüksége van-e a függvénynek megfelelő ágensprogramnak belső állapotra?

Látható, hogy a fenti ágenssel az a probléma, hogy ha már végzett, akkor sem hagyja abba a porszívást. Szerkeszthetünk olyan ágenst, amely észreveszi, ha már végzett, és onnan kezdve nem tesz semmit. Egy ilyen ágens egy ponttal kapna kevesebbet, mint az iménti (hiszen összesen egy mezőt mozog), viszont szüksége lenne egy belső állapotra, amely nyilvántartja, hogy mely mezőkben takarított már ki.

Tovább mehetünk azonban még egy lépéssel! Vegyük észre, hogy a kosz eredeti elrendezésétől függetlenül a (Szív; Átmegy-a-szomszéd-mezőbe; Szív) cselekvéssor mindenképp megtisztítja az összes mezőt! (Feltettük, hogy az ágens ismeri a helyzetét, tehát értelmes az 'Átmegy-a-szomszéd-mezőbe' cselekvés.) Az olvasó most azt mondhatja: 'Hohó! Mi van akkor, ha mindkét szoba üres? Akkor feleslegesen mozog az ágens!' Ez igaz. Ettől azonban racionális marad, hisz a pillanatnyi állapotában még nem tudhatja, hogy a másik mezőben van-e kosz, így racionális viselkedés feltételeznie, hogy van! Ha ugyanis azt feltételezné, hogy nincs, holott van, és nem megy át megnézni, elesik 998 ponttól!

c) Mutasson lehetséges ágensterveket olyan esetekre, amikor tiszta négyzetek piszkossá válhatnak, és a környezet geográfiája ismeretlen! Értelmes dolog-e, hogy ezekben az esetekben az ágens saját tapasztalataiból tanuljon? Ha igen, akkor mit kellene megtanulnia?

Olyan porszívóvilágra, ahol tiszta négyzetek piszkossá válhatnak, jó megoldás lehet az eredeti megközelítés: az ágens ide-oda cikázik, és port szív, ha kell. Ez racionális viselkedés addig, amíg nincs semmiféle ismeretünk arról, hogy milyen gyakran válnak tiszta mezők piszkossá. Ha azonban tudjuk, hogy minden időpillanatban egy mező p valószínűséggel válik piszkossá, kiszámíthatjuk annak várható értékét, hogy mennyi idő elteltével válik jó eséllyel (a 'jó esélyt' általában 95%-nak szokás választani a statisztikában) újra piszkossá, és ekkor megvizsgálni. Így minimalizálhatjuk a büntetést, amit a miatt kapunk, hogy a mező piszkos vagy feleslegesen mozogtunk. Amennyiben az ágens eleinte nem tud semmit a 'bepiszkolódás' valószínűségéről, úgy érdemes megtanulnia azt úgy, hogy eleinte gyakran felkeres minden mezőt, majd ha már elég tapasztalatot szerzett, csak akkor mozog, ha úgy ítéli, már jó eséllyel szükséges takarítania.

Ha a környezet geográfiája ismeretlen, akkor nyílván érdemes annak feltérképezése és megtanulása, így elkerülve azt, hogy az ágens olyan mezőket feleslegesen látogasson meg, amelyeken már kitakarított. Kombinálható az előző problémával (azaz hogy tiszta mezők bepiszkolódhatnak), ekkor érdemes előbb feltérképezni (és közben megtisztítani) a környezetet, majd ezután foglalkozni az esetleges újra bekoszolódó mezőkkel!

a) Robot focijátékos;

Első megközelítésben tervezzünk olyan robotot, amely teljesen úgy viselkedik és ugyanazokkal a megszorításokkal rendelkezik, mint egy normál futballjátékos: lábakon jár és szalad, élő szóban kommunikál, csak egy irányba lát egyszerre, nem rendelkezik speciális érzékelőkkel, stb.

Teljesítménymérték: Lőtt gólok száma, gólhelyzetek száma illetve azok minősége (mekkora esélyük volt, hogy sikeresek legyenek), adott gól-passzok száma, adott passzok száma, megszerzett labdák száma, kicselezett ellenfelek száma, kivédett gólhelyzetek száma, szabálytalanságok száma, fáradtság (üzemanyag, ha úgy jobban tetszik).

Környezet: Focipálya, kapuk, bíró, partjelzők, csapattársak, ellenfelek, labda.

Beavatkozók: Láb, száj (kommunikáció a csapattársakkal!).

Érzékelők: Szem, fül.

Most tekintsünk el a korábbi megszorításoktól, és tervezzünk olyan robotot, amely más hasonló robotokkal alkot egy csapatot. Ekkor nem szükséges például, hogy a kommunikációhoz az élő szóra hagyatkozzunk, megoldhatjuk rádióval is, sokkal gyorsabban! Igyekezzünk továbbra is emberszerű architektúrát kiépíteni, hogy a futball szabályai (pl. a labdát csak rúgni szabad, megfogni nem) alkalmazhatók maradjanak.

Teljesítménymérték: Lőtt gólok száma, gólhelyzetek száma illetve azok minősége (mekkora esélyük volt, hogy sikeresek legyenek), adott gól-passzok száma, adott passzok száma, megszerzett labdák száma, kicselezett ellenfelek száma, kivédett gólhelyzetek száma, szabálytalanságok száma, fáradtság (üzemanyag, ha úgy jobban tetszik).

Környezet: Focipálya, kapuk, bíró, partjelzők, csapattársak, ellenfelek, labda.

Beavatkozók: Láb, rádió-adó.

Érzékelők: Infravörös érzékelők a környezet érzékéléséhez, GPS helymeghatározó, jelölve a csapattársak helyzetét, rádió-vevő.

b) Internetes könyvvásárló ágens;

Ez alatt egy olyan alkalmazást értünk, amelynek megadhatunk könyvek paramétereit, majd ez alapján megkeresi őket internetes web áruházakban, antikváriumokban, és megrendeli őket nekünk.

Teljesítménymérték: Teljesített megrendelések száma, összköltség.

Környezet: Web-oldalak, internet.

Beavatkozók: Műveletek internetes tranzakciók indításához, kijelző, esetleg felolvasó a felhasználóval való kommunikációhoz.

Érzékelők: Műveletek internetes rendelés felvételéhez, billentyűzet, esetleg mikrofon a felhasználóval való kommunikációhoz.

c) Autonóm Mars terepjáró;

Egy Autonóm Mars terepjáró a Marson keres talajmintákat, miközben igyekszik minél jobb állapotban maradni, és elkerülni a barátságtalan marslakókat.

Teljesítménymérték: Üzemanyagszint, épség (igyekezzen elkerülni a rongálódást!), begyűjtött minták száma és minősége.

Környezet: Dombok, szakadékok, kőzetek, marslakók, egyéb terepjárók.

Beavatkozók: Kerekek, karok.

Érzékelők: Kamerák, infravörös érzékelők, talajminta-elemzők.

d) Matematikusok tételbizonyító segítője.

Egy tételbizonyító segédeszköz matematikusoknak segít tételek bizonyításában azzal, hogy például megkeresi az összefüggést két tétel vagy definíció között.

Teljesítménymérték: Bizonyításhoz használt segédtételek mennyisége, bonyolultsága.

Környezet: Tételek, lemmák és definíciók adatbázisa, tételbizonyító matematikusok.

Beavatkozók: Kijelző, esetleg felolvasó a felhasználóval való kommunikációhoz.

Érzékelők: Billentyűzet, esetleg mikrofon a felhasználóval való kommunikációhoz.

Amennyiben a tételbizonyító segédeszköz közvetlenül egy adatbázishoz csatlakozik (például hogy azt automatikusan bővítse), úgy a beavatkozók és érzékelők adatbázis-műveletek lesznek. (Írás illetve olvasás.)

a) Robot focijátékos;

A környezet részlegesen megfigyelhető (kivéve, ha valamilyen módon megoldjuk, hogy az egyes robotjátékosok a pálya teljes egészét belássák egyszerre), sztochasztikus (az elrúgott labdát arrébb fújhatja a szél, a többi játékos mozgása nem mindig kiszámítható, az ellenfél kicselezhet, stb.), sorozatszerű (legalábbis két rúgott gól között), dinamikus (hisz több játékos van a pályán), folytonos (túlzó egyszerűsítés lenne bármely kísérlet diszkrétté tenni), többágenses (megint csak gondoljunk a többi játékosra), ezen belül pedig részben kooperatív (a csapattársakkal), részben kompetitív (az ellenféllel).

Hasznosságorientált ágenst érdemes választani, hisz ez egy csapatjáték: gólt lőni nyílván sok pontot eredményez a teljesítményértékben, de a cél mégis az, hogy a csapat együttesen sok gólt lőjön, és sok helyzetben jobb passzolni, mint kapura lőni!

b) Internetes könyvvásárló ágens;

A környezet részlegesen megfigyelhető (nem rendelkezhetünk az internet teljes adatbázisával egyszerre), determinisztikus (bár az esetleges hálózati problémák miatt tekinthető sztochasztikusnak...), epizódszerű (a legtöbb esetben a megrendelések függetlenek, de kivételt jelenthetnek esetleges törzsvásárlói kedvezmények!), diszkrét (az internet végességéből adódóan), egyágenses (bár felkészülhetünk arra az esetre, ha több hasonló ágens próbálja megszerezni ugyanazt az egy ritka kötetet, ekkor többágenses, kompetitív).

Sok konkuráló szempont felmerülhet internetes vásárlás esetén: a szállító megbízhatósága, a könyv ára, a szállítási idő/távolság, stb. Ezeket egyszerre szeretnénk optimalizálni, így itt is érdemes hasznosságorientált ágenst tervezni.

c) Autonóm Mars terepjáró;

A környezet részlegesen megfigyelhető (a Mars elég nagy...), sztochasztikus (időjárás a Marson is van), sorozatszerű (korábbi cselekvések kihatással lehetnek későbbiekre), dinamikus (a Földhöz képest statikusnak tűnhet, de valójában nem az), folytonos, egyágenses vagy többágenses (lehet több, akár együttműködő, akár konkuráló terepjáró).

Mivel szeretnénk, ha a terepjáró autonóm lenne, elvárjuk tőle, hogy összetett szituációkban is jól teljesítsen. Ehhez érdemes hasznosságorientált ágenst választani.

d) Matematikusok tételbizonyító segítője.

A környezet teljesen megfigyelhető (a tételek halmaza bővülhet, de az ágens erről fog tudni), determinisztikus (csak bizonyított tételeket veszünk fel a tételek halmazába), epizódszerű (ha az ágens képes ’bizonyítási trükköket’ tanulni, akkor lehet sorozatszerű), statikus (ha egy tételt egyszer már bebizonyítottunk, az igaz is marad), diszkrét (a tételek és definíciók száma véges), egyágenses.

Várhatóan elegendő lesz célorientált ágenst tervezni, mivel a bizonyítás nehézsége lényegében a lépések számától függ, elég ezt minimalizálni.

a) Lehet-e tökéletesen racionális egy egyszerű reflexszerű ágens ebben a környezetben? Magyarázza meg, miért!

Igen, lehet. Az, hogy egy ágens racionális, mindössze annyit jelent, hogy a jelenlegi tudása alapján maximalizálni igyekszik a teljesítménymértékét. Mivel kezdetben mindössze a kezdőnégyzetről tudja eldönteni az ágens, hogy piszkos-e, a többiről fel kell tételeznie, hogy az. (Már a 2.04. feladatban indokoltuk, miért kell a legrosszabbra felkészülni.) Így tehát a feladat visszavezethető az utazó ügynök problémájára: minden mezőt szeretnénk meglátogatni legalább egyszer, a lehető legkevesebb mozgással. A kapott megoldást felhasználhatjuk egy reflexszerű ágens tervezéséhez:

Az így kapott ágens racionális lesz, hisz a jelenlegi tudása alapján maximalizálja a teljesítménymértékét.

Fontos azonban megjegyezni, hogy az utazó ügynök probléma NP-teljes, ami azt jelenti, hogy nincs rá polinomiális idejű megoldás, tehát a feladat nehéz.

b) Mi a helyzet az állapottal rendelkező reflexszerű ágensekkel? Tervezzen egy ilyen ágenst!

A 70. oldal specifikációja szerint a környezet topológiája (a mezők elrendezése) a priori ismert, tehát nincs szükség annak feltérképezésére, és mivel már megtisztított mezők nem válhatnak újra piszkossá, azt sem kell nyilvántartani, hogy hol van még kosz. Így egy belső állapot bevezetésével nem nyerünk semmit.

c) Hogyan változna meg az (a) és (b) pontokra adott válasza, ha az ágens észlelései a környezet összes négyzetére megmondják neki, hogy azok tiszták, vagy piszkosak?

Nagyon sokat változtat, ha az ágens észleli a környezet összes négyzetét, ilyenkor ugyanis már nem igaz az, hogy egy előre betáplált út biztosan racionális lesz! Az első esetben feltételeztük minden mezőről, hogy piszkos, és úgy terveztünk utat még az ágens tervezési fázisában. Mivel a tervezési fázisban továbbra sem ismert a kosz elrendeződése, ugyanúgy kell az ágenst tervezni, feltételezve, hogy minden mező koszos. Azonban amikor az ágens működni kezd, és az első időpillanatban egyszerre érzékel minden mezőt, kiderülhet, hogy vannak felesleges szakaszok a korábban optimálisnak hitt útvonalban. Ezek megváltoztatására azonban egy egyszerű reflexszerű ágensnek nincs lehetősége!

Más a helyzet viszont egy belső állapottal rendelkező reflexszerű ágenssel! Egy ilyen ágens esetében ugyanis megtehető, hogy az útvonalat nem a tervezési fázisban, hanem az első időpillanatban teszi meg, amikor már ismeri a kosz elrendeződését. A megtervezett útvonalat a belső állapotban nyilvántartva már képes lesz az ágens elkerülni a felesleges kerülőket.

a) Lehet-e tökéletesen racionális egy egyszerű reflexszerű ágens ebben a környezetben? Magyarázza meg, miért!

Nem. A probléma itt az, hogy nem ismert a környezet topológiája, és emiatt nem mondható meg, hogy merre érdemes elindulni benne. Az előző esetben csak azért tudtuk biztosítani az racionalitást, mert a környezet ismert volt, és így előre megadhattunk egy optimális útvonalat.

d) Egy állapottal rendelkező reflexszerű ágens jobban teljesíthet egy egyszerűnél? Tervezzen egy ilyen ágenst, és mérje meg a teljesítményét különböző környezetekben! Tud ilyen típusú racionális ágenst tervezni?

Igen. A környezet térképét építhetjük fel a belső állapotban, ami segíthet elkerülni a céltalan bolyongást. Továbbra sem lesz azonban az ágens racionális, mert először fel kellene derítenie a környezetet, mielőtt egy optimális útvonalat meg tudna határozni.

Mivel az ágens a 2.10. feladat szerint nem ismeri a környezetét, ezért kénytelen azt először feltérképezni. Mivel nem 'látja' a szomszéd mezőket, minden esetben meg kell próbálnia körülnézni minden irányban. Ha továbbra is fennáll, hogy a mozgás egy pont levonással jár és az ütközésérzékelő menet közben áll le, de korábban már megtisztított mezők már nem koszolódnak be, úgy legjobb helyben maradni, ellenkező esetben ugyanis az ágens vak bolyongása nagyon költséges lehet.

a) Murphy törvénye: az idő 25%-ában a Felszívás művelet nem tudja feltakarítani a padlót, ha az piszkos, illetve kiönti rá a koszt, ha az tiszta. Hogyan érinti az ágens programját az, ha a piszokérzékelő az idő 10%-ában rossz választ ad?

Ilyenkor elő fognak fordulni olyan esetek, amikor a porszívó a hibás érzékelés miatt koszt csinál, ahelyett, hogy takarítana. Nem jelent megoldást erre a problémára az sem, ha takarítás után ellenőrizzük az eredményt, hiszen ekkor is lehet téves az érzékelés. Jó módszer lehet, ha az ágens az esetek 90%-ában feltételezi, hogy sikeres volt az érzékelés, és 10% eséllyel újra érzékel.

b) Kisgyerekek: minden időlépésben minden mezőnek 10% esélye van bepiszkolódni. Tud javasolni egy racionális ágenstervet erre az esetre?

Ha az érzékelés továbbra is csak az adott szobában tudja megvizsgálni a koszt, és a mozgás pontlevonással jár, úgy az ágens bajban van. Kénytelen lesz ugyanis folyamatosan, vagy legalábbis bizonyos időközönként bejárni a szobákat, hogy ellenőrizze, bepiszkolódtak-e. Érdemes lehet olyan belső állapotos ágenssel kísérletezni, amely nyilvántartja a már meglátogatott szobákat, és minden időegységben 10% eséllyel bepiszkolja őket (mezőnként külön-külön 10% eséllyel), ezzel mímelve a porszívóvilág működését. Ha valahol piszkos mezőt sejt, felkeresi, és ellenőrzi.

Ennél jobb módszer lehet, ha addig várunk az egyes már meglátogatott mezők újbóli ellenőrzésével, amíg nagyon valószínűvé nem válik, hogy azok piszkossá váltak. Minden időegységben egymástól függetlenül 10% eséllyel lesz piszkos egy tiszta mező. Kicsit átfogalmazva, 90% az esélye, hogy tiszta marad. Két időegység alatt annak az esélye, hogy egy adott mező tiszta marad, már csak 81% (0.9*0.9), azaz annak az esélye, hogy egyik időegység alatt sem koszolódott be a mező). Formálisan annak esélye, hogy n időegység után is tiszta maradjon a padló, (0.9)ⁿ, azaz ha azt akarjuk megtudni, hogy mikor lesz ez a valószínűség kisebb egy bizonyos rögzített m-nél, akkor az n = log_(0.9)m egyenletet kell megoldanunk. Tehát ha például m-et 0.05-nek (5%) választjuk, akkor n értéke 28.433 körül lesz, így ha ennél több időegység telt el a legutóbbi ellenőrzés óta, akkor kevesebb, mint 5% az esélye, hogy az adott mező még mindig tiszta.

Készítette: Ács Gergely András, BME