Chapter 1. A problémareprezentáció

A mesterséges intelligencia problémáinak megoldása a probléma megfogalmazásával kezdődik: a problémát leírjuk, reprezentáljuk. Az egyik legelterjedtebb reprezentációs technika az állapottér-reprezentáció (state space representation).

1.1. Az állapottér-reprezentáció

Legyen adott egy probléma, amit jelöljünk -vel.

  • Megkeressük világának legalább egy, de véges sok — a probléma megoldása során fontosnak vélt — meghatározóját. (pl. objektum, pozíció, méret, hőmérséklet, szín, stb.) Tegyük fel, hogy ilyen jellemzőt találtunk.

  • Minden egyes jellemző világát különböző értékekkel jellemzi. (pl. szín: fekete/fehér; hőmérséklet: , stb)

Ha a megadott jellemzők épp rendre a értékekkel rendelkeznek azt mondjuk, hogy

Equation 1.. 


világa a érték -essel leírt állapotban (state) van. A világunk állapotainak halmaza az állapottér (state space).

Jelölje az -edik jellemző által felvehető értékek halmazát . Ekkor állapotai elemei a

Equation 1.. 


halmaznak.

Azokat a feltételeket, amelyek meghatározzák, hogy ebből a halmazból mely érték -esek állapotok kényszerfeltételeknek nevezzük.

Az állapottér tehát az értékhalmazok Descartes-szorzatának a kényszerfeltételekkel kijelölt részhalmaza:

Equation 1.. 


Az állapottér azon állapotát, amit a probléma világa jellemzőinek kezdőértékei határoznak meg, kezdőállapotnak (initial state) nevezzük és -vel jelöljük.

A kezdőállapotból kiindulva a probléma világának sorban előálló állapotait rendre meg szeretnénk változtatni, míg végül valamely számunkra megfelelő ún. célállapotba (goal state) jutunk.

Jelölje a célállapotok halmazát. Megadása kétféleképpen történhet:

  • felsorolással:

  • célfeltételek megadásával:

Általában , hiszen , különben nincs megoldandó feladat.

Hogy célállapotba juthassunk, meg kell tudnunk változtatni bizonyos állapotokat. Az állapotváltozásokat leíró leképezéseket operátoroknak (operator) nevezzük.

Nem minden operátor alkalmazható feltétlenül minden állapotra, ezért meg szoktuk adni az operátorok értelmezési tartományát az operátoralkalmazási előfeltételek segítségével.

Jelöljön az operátorok véges halmazából egy operátort. Ekkor

Equation 1.. 


Definíció

Legyen egy probléma. Azt mondjuk, hogy a problémát állapottér-reprezentáltuk, ha megadtuk az

Equation 1.. 


négyest, azaz

  • az halmazt, a probléma állapotterét,

  • a kezdőállapotot,

  • a célállapotok halmazát és

  • az operátorok véges halmazát.

Jelölése: .

Legyen egy probléma, egy állapottér-reprezentációja és legyenek .

Definíció

Az állapotból az állapot közvetlenül elérhető, ha van olyan operátor, hogy

Equation 1.. 


Jelölése: , ha fontos, hogy állítja elő -ból -t: .

Definíció

Az állapotból az állapot elérhető, ha vagy , vagy van olyan (véges) állapotsorozat, hogy

Equation 1.. 


Jelölése: .

Ha minden esetén, akkor van olyan operátorsorozat, hogy . Ilyenkor azt mondjuk, hogy az állapotból az állapot az operátorsorozat segítségével elérhető. Jelölve: .

Definíció

Legyen . A probléma megoldható ebben az állapottér-reprezentációban, ha van olyan célállapot, hogy . Ha , akkor az operátorsorozat a probléma egy megoldása.

A feladatunk lehet

  • annak eldöntése, hogy megoldható-e a probléma az adott állapottér-reprezentációban,

  • egy (esetleg az összes) megoldás előállítása,

  • egy (esetleg az összes) célállapot előállítása,

  • valamilyen minősítés alapján jó megoldás előállítása (a megoldások között különbséget tehetünk, pl. a megoldás költsége alapján).

Jelölje az operátor állapotra alkalmazásának a költségét.

Definíció

Legyen és a probléma egy megoldása, azaz

Equation 1.. 


.

Legyen rendre , ahol és . Ekkor a megoldás költsége:

Equation 1.. 


Ha , akkor a megoldás költsége az alkalmazott operátorok száma.

Ha az állapottér-reprezentációt valamilyen programozási nyelv segítségével szeretnénk leírni, akkor meg kell adni

  • az állapotok típusát, továbbá a kényszerfeltételeket leíró, logikai értéket visszaadó függvényt;

  • a kezdőállapotot egy állapot típusú konstanssal;

  • a célállapotok halmazát:

    • állapot típusú konstansok felsorolásával vagy

    • a célfeltételt leíró logikai értéket visszaadó függvénnyel;

  • az operátorokat: függvényekkel vagy eljárásokkal. Egy-egy operátorhoz az alkalmazásának előfeltételét leíró logikai függvény is tartozhat. Alkalmas függvénnyel ki lehet számolni (vagy táblázattal meg lehet adni) az operátorok alkalmazási költségeit is.