Company LOGO
SZOFTVERES SZEMLÉLTETÉS A MESTERSÉGES INTELLIGENCIA OKTATÁSÁBAN _
Jeszenszky Péter Debreceni Egyetem, Informatikai Kar
[email protected]
mmo2009.kfrtkf.hu
Company LOGO
Mesterséges intelligencia oktatás a DE Informatikai Karán
• • •
mmo2009.kfrtkf.hu
Évtizedes hagyományok Az oktatási kínálatban számos a témához kötődő, magas színvonalon oktatott kurzus szerepel folyamatosan A téma hangsúlyosan jelenik meg a képzésben
•
A képzés gerincét jelentő GI, MI és PTI BSc szakokon kötelezőként teljesítendő egy bevezető MI kurzus, amely jelenleg A mesterséges intelligencia alapjai címen fut
Company LOGO
A bevezető MI kurzus
• •
• • mmo2009.kfrtkf.hu
A tárgyalt főbb témakörök: problémák állapottér-reprezentálása, megoldást kereső rendszerek, kétszemélyes stratégiai játékok és lépésajánló algoritmusok Fontossága: eszközt ad problémák számítógép által kezelhető megfogalmazásához (állapottérreprezentáció), másrészt pedig univerzális, bizonyítottan helyesen működő algoritmusokat azok megoldásához Célok: a hallgatók önállóan legyenek képesek valós problémák formalizálására, ennek alapján el tudjanak készíteni egy a problémát megoldó számítógépes programot Az oktatás előadások és gyakorlatok formájában történik
Company LOGO
A MI gyakorlati oktatása
• • • • • mmo2009.kfrtkf.hu
A félév első felében a gyakorlatokon problémák formalizálása, az állapottér-reprezentációk és megoldáskereső algoritmusok implementálása műhelymunka keretében A félév végén hasonló felfogásban kerülnek tárgyalásra a kétszemélyes stratégiai játékok és lépésajánló algoritmusok Szilárd matematikai logikai és programozási alapok szükségesek (megfelelő tantárgyi előfeltételek) Az utóbbi években a gyakorlatok programozási nyelve elsősorban a Java Nagyon hasznos a szemléltetés (alapfogalmak és az algoritmusok működése kapcsán)
Company LOGO
Szoftverek a gyakorlatok oktatásához
•
Az előadó által kifejlesztett nyílt forrású (GNU GPL licenc alatt terjeszett) osztálykönyvtár, amely az alábbiakat tartalmazza:
• • • •
mmo2009.kfrtkf.hu
•
OO keretrendszer számítógépes problémamegoldáshoz A tárgyalt megoldáskereső algoritmusok valamint számos különböző probléma állapottérreprezentációjának implementációja a keretrendszerben OO keretrendszer kétszemélyes stratégiai játékokhoz Néhány kétszemélyes stratégiai játék (például Othello és malom játék) valamint lépésajánló algoritmus (minimax módszer, negamax módszer, alfa-béta vágás) implementációja a keretrendszerben Eszközök alapfogalmak és a megoldáskereső algoritmusok működésének szemléltetéséhez
Company LOGO
A programcsomag szemléltető eszközei
•
Az eszköztár:
• • •
•
mmo2009.kfrtkf.hu
Programok állapottérgráfok és játékfák grafikus ábrázolásához Explicit gráfok Programok megoldáskereső algoritmusok működésének grafikus ábrázolásához
Az előadó nem ismer más ilyen képességekkel rendelkező eszközt
Company LOGO
Állapottérgráfok és játékfák rajzolása
•
•
Ha az állapottér-reprezentációs Java osztály megfelelően implementálja a programcsomag interfészeit, akkor tetszőleges probléma és kétszemélyes stratégiai játék esetén képes a program ábrázolni a teljes állapottérgráfot vagy játékfát Nagy gráfok esetén megadható mélységi korlát illetve előállítható makroszkópikus nézet
•
mmo2009.kfrtkf.hu
Utóbbi a gráf szerkezetét szemlélteti olyan módon, hogy minden csúcs csupán egy címke nélküli pontként jelenik meg rajta
Company LOGO
Állapottérgráf megjelenítése (1): a 8-as játék 3 mélységig felépített gráfja
mmo2009.kfrtkf.hu
Company LOGO
Állapottérgráf megjelenítése (2): a misszionáriusok és kannibálok probléma gráfja makroszkópikus nézetben (16 csúcs és 17 irányítatlan él)
mmo2009.kfrtkf.hu
Company LOGO
Állapottérgráf megjelenítése (3): a 8-as játék 6 mélységig felépített gráfja makroszkópikus nézetben (103 csúcs és 104 irányítatlan él)
mmo2009.kfrtkf.hu
Company LOGO
Explicit gráfok
• •
• • mmo2009.kfrtkf.hu
A csomag részeként implementált problémák az állapottérgráf tipikusan nagy mérete miatt nem alkalmasak a megoldáskereső eljárások működésének szemléltetéséhez Egy explicit gráf egy XML-ben leírt, tipikusan kisméretű állapottérgráf (azonban méretére nincs felső korlát), amelynek célja kifejezetten szemléltetés
•
A formátum egy XML séma formájában adott
A csomag valamennyi megoldáskereső eljárása képes explicit gráfokat is kezelni Egy gráfot leíró XML dokumentumban meg lehet adni: a gráf csúcsait (opcionális heurisztikus értékekkel), a gráf éleit (opcionális élköltségekkel), néhány kiegészítő információt (például az élköltségek mértékegységét)
Company LOGO
Egy explicit gráf XML-ben
<node id="Budapest"/> <node id="Cegléd"/> <node id="Eger"/> <node id="Füzesabony"/> <node id="Hatvan"/> <node id="Karcag"/> <node id="Miskolc"/> <node id="Nyíregyháza"/> <node id="Tiszafüred"/> <node id="Szolnok"/> <node id="Újszász"/> <edge <edge <edge <edge ...
mmo2009.kfrtkf.hu
source="Budapest" target="Cegléd" cost="73"/> source="Budapest" target="Hatvan" cost="67"/> source="Budapest" target="Újszász" cost="84"/> source="Cegléd" target="Szolnok" cost="27"/>
Company LOGO
Az explicit gráf a programmal ábrázolva
mmo2009.kfrtkf.hu
Company LOGO
Megoldáskereső algoritmusok működésének ábrázolása
• • •
mmo2009.kfrtkf.hu
Adottak a tárgyalt megoldáskereső algoritmusok olyan megvalósításai, amelyek a működésüket szemléltető képsorozatokat állítanak elő A képsorozatok elemei a megoldáskereső adatbázisának tartalmát ábrázolják lépésrőllépésre Ábra szemlélteti a programok által előállított megoldást is
Company LOGO
A probléma az optimális keresővel előállított megoldása a programmal ábrázolva
mmo2009.kfrtkf.hu
Company LOGO
Az optimális kereső működését szemléltető képsorozat (1)
(a)
(b)
mmo2009.kfrtkf.hu
(c)
Company LOGO
Az optimális kereső működését szemléltető képsorozat (2)
(d)
mmo2009.kfrtkf.hu
(e)
Company LOGO
Az optimális kereső működését szemléltető képsorozat (3)
(f) mmo2009.kfrtkf.hu
Company LOGO
Az optimális kereső működését szemléltető képsorozat (4)
(g) mmo2009.kfrtkf.hu
Company LOGO
Az optimális kereső működését szemléltető képsorozat (5)
(h) mmo2009.kfrtkf.hu
Company LOGO
Az optimális kereső működését szemléltető képsorozat (6)
mmo2009.kfrtkf.hu
Company LOGO
Az optimális kereső működését szemléltető képsorozat (7)
mmo2009.kfrtkf.hu
Company LOGO
Az optimális kereső működését szemléltető képsorozat (8)
mmo2009.kfrtkf.hu
Company LOGO
A programok futtatása (1)
• • •
A szemléltető programokat az ai.framework.visualization csomag tartalmazza Futtatás parancssorból megfelelő paraméterezéssel lehetséges Fontosabb parancssori argumentumok:
• • •
mmo2009.kfrtkf.hu
Az explicit gráf elérési útvonalának megadása --xml <elérési-útvonal> formában Az állapottér-reprezentációs Java osztály teljes minősített nevének megadása --classname
formában A program által generált képeket tartalmazó könyvtár megadása --outputdir <elérésiútvonal> formában (alapértelmezés az aktuális könyvtár)
Company LOGO
A programok futtatása (2)
•
Például a korábbi képsorozatot a java ai.framework.visualization.OptimalSearch --xml graph.xml parancs végrehajtásával állíthatjuk elő
• • •
mmo2009.kfrtkf.hu
Az explicit gráfot a graph.xml állomány tartalmazza Az aktuális könyvtárban jönnek létre a 0.png, 1.png, 2.png, … képállományok, amelyek az algoritmus egyes lépéseiben mutatják az adatbázis tartalmát Ugyancsak az aktuális könyvtárban jön létre a probléma állapottérgráfjába berajzolt megoldást tartalmazó solution.png képállomány
Company LOGO
Megvalósítás
• • •
A programcsomag teljes egészében Java-ban készült A gráfok rajzolása a nyílt forrású Graphviz szoftverrel történik
•
A Graphviz nem Java nyelven készült, sajnos Java interfész sem létezik hozzá
• •
mmo2009.kfrtkf.hu
http://www.graphviz.org/
Az ai.util.graphviz csomagban egy Java API a Graphviz által kezelt DOT formátumú gráfok generálásához A DOT állományokból képeket előállító bináris futtatható konverziós programok meghívása a java.lang.Runtime osztály segítségével
Company LOGO
Továbbfejlesztési lehetőségek
• • •
mmo2009.kfrtkf.hu
Grafikus felhasználói felület explicit gráfok felhasználóbarát készítéséhez, amely nem igényli az XML formátum használatának ismeretét sem Grafikus felhasználói felület a szemléltető programok felhasználóbarát futtatásához A szemléltető programokban különálló képállományok helyett animáció előállítása
Company LOGO
További információk
•
mmo2009.kfrtkf.hu
A szoftver szabadon elérhető az alábbi címen: http://www.inf.unideb.hu/~jeszy/mestint/
