Logički agent u Wumpus svijetu

Naziv projekta: Logički agent u Wumpus svijetu.

Autori: 

Cilj projekta je demonstrirati logičko zaključivanje u propozicijskoj logici uz uporabu rezolucijskog pravila.

Programska implementacija nastala je pod mentorstvom doc. dr .sc. Bojane Dalbelo Bašić,

u okviru kolegija «Inteligentni sustavi», ak. god. 2001/02.

ŠTO JE WUMPUS?

Wumpus je jedna stara računalna igra u kojoj postoji agent čiji je jedini zadatak istražiti zadani prostor (npr. pećinu) u kojem se nalazi kovčeg sa zlatom. Agent treba pronaći zlato, uzeti ga, te se vratiti odakle je krenuo. Ako se agent uspije vratiti sa zlatom, zadatak je uspješno obavljen.

Opis igre preuzet je iz literature [1].

Međutim, agenta u njegovoj namjeri ometaju duboke jame u koje on može upasti, a tu je i Wumpus, strašno čudovište koje pojede svakog tko dođe u njegovo polje. Kako agent ne bi lutao naslijepo, postoje određene percepcije koje agent može osjetiti i na taj način odlučiti kojim će putem krenuti. Tako agent na susjednim poljima od polja Wumpusa (susjedna polja su lijevo, desno, gore i dolje, ne i po dijagonali) osjeća jak zadah Wumpusa, a na susjednim poljima od polja na kojem se nalaze jame agent osjeća propuh. Ukoliko agent dođe u polje u kojem se nalazi skriveno zlato, on će primijetiti sjaj te će pronaći i uzeti zlato i vratiti se s njim kući.

Svijet oko agenta je dvodimenzionalna ploča dimenzija N x N. Agent kreće sa pozicije (1,1), odnosno iz donjeg lijevog polja na ploči. Nakon što pronađe zlato ponovo se treba vratiti na polje (1,1).

Zašto je ova igra nama zanimljiva?

Igra je relativno jednostavan primjer na kojem se mogu primijeniti načela umjetne inteligencije. Na prvi pogled problem bi se mogao učiniti trivijalnim. To je opravdano stajalište u slučaju kada je igrač čovjek, odnosno kada čovjek upravlja kretanjem agenta. No, što ako čovjeka zamijenimo računalom. Hoće li računalo biti jednako uspješno u rješavanju ovog problema kao i čovjek? Hoće li možda biti uspješnije? Odgovor na ova i slična pitanja je zapravo nejednoznačan. Svako računalo radi prema unaprijed predviđenom programu i biti će u tolikoj mjeri uspješno koliko je dobro napisan program, odnosno algoritam po kojem računalo radi. Ono što je ovdje značajno jest činjenica da će pod pretpostavkom dobrog algoritma računalo biti neusporedivo brže od čovjeka (za slučaj ove igre, ne i općenito). Ideja je bila napraviti igru koju će igrati računalo, uz prikaz "unutarnjeg znanja i zaključivanja" računala u svakom koraku.

Postavlja se, dakle, problem na koji način računalu predstaviti "znanje" o Wumpus svijetu i kako računalo "natjerati da misli", odnosno kako mu omogućiti da donosi zaključke koji smjer odabrati za daljnje kretanje na temelju poznatih činjenica koje je do tog trenutka saznalo. Jedno od mogućih rješenja opisano je u nastavku, a ujedno je i iskorišteno u našoj realizaciji.

ZAKLJUČIVANJE TEMELJENO NA REZOLUCIJSKOM NAČELU

Rezolucijsko načelo zaključivanja detaljno je opisano u literaturi[3].

Složenost problema automatskog zaključivanja za slučaj igre "Wumpus" je relativno jednostavna, tako da je za učinkovitu realizaciju moguće iskoristiti najjednostavniju metodu automatskog zaključivanja - propozicijsku logiku. Propozicijska logika daje odgovor na pitanje da li je neka logička formula (cilj) logička posljedica unaprijed zadanih formula (premisa).

Na primjer, pretpostavimo da imamo dvije premise koje su istinite

1)    Lijevo od agenta je jama.

2)    Ako je lijevo od agenta jama, tada agent ne smije ići lijevo.

Ako tvrdnju

    "Lijevo od agenta je jama" označimo logičkom varijablom A,

a tvrdnju

    "Agent smije ići lijevo" označimo logičkom varijablom B,

naš početni skup premisa prelazi u notaciju koju koristi propozicijska logika:

1)    A

2)    A ®  ~B

Jasno je da iz te dvije premise proizlazi tvrdnja

3)    "Agent ne smije ići lijevo".

odnosno tvrdnja 3) je logička posljedica premisa 1) i 2).

Označimo novoizvedenu tvrdnju "Agent ne smije ići lijevo" logičkom varijablom C.

Koristeći terminologiju propozicijske logike, kažemo da je C logička posljedica premisa  A  i  A® ~B.

Da je tome tako lako je pokazati primjenjujući pravilo modus ponens koje kaže:

    ako je istinita tvrdnja F i istinita tvrdnja F®G, tada je istinita i tvrdnja G.

Primijenimo li ovo pravilo na naš slučaj ono glasi:

    ako je istinita tvrdnja A i istinita tvrdnja A® ~B, tada je istinita i tvrdnja ~B.

~B je, dakle, logička posljedica zadanih premisa, a ako se pažljivije pogleda tvrdnja C je zapravo ekvivalentna tvrdnji ~B, te je i C njihova logička posljedica.

Ovdje je važno primijetiti da propozicijska logika može dati odgovor samo na pitanje da li je neki cilj logička posljedica pretpostavljenih premisa. Tako, na primjer, možemo dobiti odgovor na pitanje "Da li agent smije ići lijevo?", ali ne možemo postaviti pitanje "Kojim smjerom agent može krenuti?". U drugom slučaju propozicijska logika bi u nekim slučajevima mogla potražiti odgovor na pitanje, ali to ne vrijedi općenito.

Gore opisano razmatranje je pogodno za implementaciju na računalu.

Na temelju početnog znanja (zadah oko Wumpusa, propuh oko jame), te stećenih percepcija, agent odnosno računalo, može izvesti novo znanje o smjeru kojim bi htio krenuti. Za svaki smjer računalo ispituje da li je siguran ili opasan. Ukoliko se pokaže da je pretpostavka (siguran smjer ili opasan smjer) logička posljedica stečenog znanja, računalo će moći zaključiti kojim smjerom treba napredovati.

Algoritam zaključivanja koji koristi računalo

Računalo, odnosno program koristi jednu od varijanti automatskog zaključivanja uporabom propozicijske logike, nazvanu rezolucija opovrgavanjem.

Za primjenu rezolucije opovrgavanjem ili obične rezolucije sve logičke formule (premise i cilj) potrebno je zapisati u klauzalnoj formi. Klauzalna forma je oblik u kojem su logičke formule zapisane u obliku konjunkcije klauzula, dok klauzula predstavlja disjunkciju literala (atoma).

Takve su logičke formule oblika

4) (A1 v A2 v ... v An) Λ (B1 v B2 v ...v Bn) Λ ... Λ (X1 v X2 v ... v Xn)

Klauzalni oblik formula ne predstavlja ograničenje jer se operatorima negacije, konjunkcije i disjunkcije može predstaviti svaka logička formula, a DeMorganovi zakoni i distributivnost Booleove algebre s obzirom na konjunkciju i implikaciju omogućuju svođenje na klauzalni oblik.

Na taj način se formule, ali i cijela baza znanja mogu zapisati kao skup klauzula među kojima se implicitno podrazumijeva konjunkcija, a svaka se klauzula može smatrati jednom istinitom premisom.

Međutim, je li baza znanja u obliku skupa klauzula ekvivalentna početnim premisama prije transformacije?

Odgovor na ovo pitanje je potvrdan, a temelji se na sljedećem obrazloženju.

Svaka se formula može svesti na oblik 4), odnosno na klauzalni oblik. Jedino što je upitno je može li se konjunkcija među klauzulama implicitno podrazumijevati, tj. smije li se svaka klauzula smatrati neovisnom premisom. Ako je formula u obliku 4) istinita, tada je istinita i svaka pojedinačna klauzula. Prema tome, klauzule proizašle iz iste formule mogu se smatrati neovisnim premisama. Slično je i sa cjelokupnom bazom znanja. Baza znanja se sastoji od većeg broja formula koje su sve istinite, a unutar pojedine formule sve su klauzule također istinite.

Rezolucijsko načelo

Rezolucijsko načelo u skupu klauzula traži dvije klauzule u kojima se pojavljuju komplementarni literali. Nova klauzula se gradi tako da se odbacuju komplementarni literali, a preostali literali iz obje klauzule ulaze u novu klauzulu. Ovo je opravdano sljedećim: ako se u dvije različite klauzule (sve su klauzule u bazi znanja istinite) pojavljuje isti literal, ali u jednoj potvrdan, a u drugoj negiran, jasno je da istinitost tih dviju klauzula ne proizlazi iz tog literala nego iz preostalih koji nemaju komplementarnog para (dovoljno je da je jedan literal u klauzuli istinit da klauzula bude istinita zbog disjunkcije). Vrijednost istinitosti literala ne može biti istovremeno istina i laž.

Zbog toga komplementarni literali predstavljaju višak informacije i mogu se odbaciti.

Naš početni skup premisa

1)    A

2)    A ®  ~B

eliminacijom implikacije u premisi 2) prelazi u skup

1)    A

2)    ~A v ~B

što ujedno zadovoljava klauzalni oblik.

Traženjem komplementarnih literala u klauzulama 1) i 2) pronalazimo literale A i ~A. Odbacivanjem komplementarnih literala, i gradnjom nove klauzule od preostalih dobiva se nova klauzula koja je njihova logička posljedica.

3)    ~B

Isti smo rezultat dobili i primjenjujući pravilo modus ponens.

Kako je formula 3) istinita, ona se može dodati u bazu znanja i u daljnjim koracima ravnopravno koristiti.

Ovaj bi se postupak sada ponavljao sve dok se ne bi izvela klauzula koja je naš cilj.

Mala modifikacija ovog postupka je rezolucijsko načelo opovrgavanjem.

Ovdje je ideja da se u skup premisa doda formula koja je negacija ciljne formule koja se želi izvesti i nakon toga se primijeni gornji postupak rezolucijskog zaključivanja.

Međutim, postupak se malo razlikuje. Kod običnog rezolucijskog načela cilj nam je bio izvesti ciljnu klauzulu. Ukoliko bismo u tome uspjeli, tada bismo znali da je naš pretpostavljeni cilj istinit. Ovdje negaciju cilja dodajemo u skup premisa i nastojimo izvesti praznu klauzulu NIL. Praznu klauzulu je moguće izvesti iz dviju klauzula koje sadrže samo međusobno komplementarne literale, i nijedan drugi literal koji bi preostao nakon odbacivanja komplementarnih.

Uz pretpostavku da je ciljna formula istinita, tada je njezina negacija koja se dodaje u bazu znanja lažna. U tom slučaju baza sadrži lažne klauzule i skup klauzula baze je nekonzistentan, odnosno kontradiktoran.

Ako iz takvog nekonzistentnog skupa izvedemo praznu NIL klauzulu, to znači da svaka interpretacija koja zadovoljava skup klauzula baze, zadovoljava i NIL klauzulu. Budući da NIL klauzulu ne zadovoljava nijedna interpretacija, onda nijedna interpretacija ne zadovoljava ni skup klauzula baze, što znači da je baza nekonzistentna. Jedini uzrok nekonzistentnosti baze može biti novododana formula negacije cilja. To znači da je negacija cilja lažna, a tada je pretpostavljena ciljna formula istinita.

NIL klauzulu ne može zadovoljavati nijedna interpretacija budući da je izvedena iz dviju suprotnih tvrdnji od kojih samo jedna može biti istinita.

Npr. samo iz premisa oblika  A i ~A moguće je izvesti NIL klauzulu, a te su dvije premise u kontradikciji i nema interpretacije za koju bi obje bile istinite.

Pokažimo na već korištenom primjeru primjenu rezolucije opovrgavanjem.

Početni skup premisa u klauzalnoj formi je:

1)    A

2)    ~A v ~B

Želimo provjeriti istinitost tvrdnje ~B , odnosno "Agent ne smije ići lijevo".

U skup premisa se dodaje negacija cilja,  B.

1)    A

2)    ~A v ~B

3)    B

Primjenom rezolucije na 1) i 2) dobiva se nova klauzula

4)    ~B

te konačno još jednom primjenom rezolucije na 3) i 4) izvodimo NIL klauzulu.

Zaključak je da je tvrdnja ~B istinita.

Postupak rezolucije opovrgavanjem se zaustavlja kada izvedemo NIL klauzulu (ciljna fomula je dokazana), ili kada više nismo u mogućnosti izvesti novu klauzulu (ciljna formula nije dokazana).

Rezolucijsko zaključivanje uporabom opovrgavanja cilja iskorišteno je kao osnovna metoda zaključivanja računala u implementaciji igre "Wumpus".

PROGRAMSKA IMPLEMENTACIJA

Ideja je bila da se napravi programska implementacija igre "Wumpus" koju će igrati računalo, a da se pri tom prikazuju svi potrebni podaci i podatkovne strukture koje su nužne da bi računalo povuklo potez. Tako se u svakom trenutku može vidjeti cjelokupna baza znanja u klauzalnoj formi, te postupak kojim računalo izvodi novo znanje uporabom rezolucije opovrgavanjem ili primjenom pravila modus ponens.

Kao što je već rečeno, osnovni algoritam zaključivanja temeljen je na rezoluciji opovrgavanjem. Prije svake nove odluke o sljedećem potezu računalo ispituje sva četiri moguća smjera napredovanja. Moguća su tri ishoda takvog ispitivanja:

    1)    dokazano je da je polje sigurno

    2)    dokazano je da je polje opasno

    3)    stanje polja nije poznato jer još nema dovoljno podataka da bi se utvrdilo, polje je nesigurno

Moguće je da u jednom trenutku postoji više sigurnih smjerova kojima bi se moglo krenuti. U takvim slučajevima računalo odabire jedan od njih, ali vodi listu ostalih sigurnih, a neposjećenih polja. Ako nema susjednih sigurnih polja (uvijek postoji barem jedno susjedno sigurno polje, ono na kojem je agent bio korak prije, ali ono se ne razmatra jer je već posjećeno kako bi se izbjegla vrtnja u krug), pregledava se lista sigurnih polja koja još nisu posjećena te se po sigurnim poljima vraća do nekog od prethodno otkrivenih sigurnih polja. Slično je i sa nesigurnim poljima. Ako oko agenta ne postoji nijedno sigurno polje, pregledom liste neposjećenih nesigurnih računalo utvrđuje da li takva postoje te odabire jedno od njih. Tu računalo riskira potez jer igra na nesigurno. Ukoliko i taj korak izostane računalo zaključuje da su preostala neposjećena polja sva opasna. U tom slučaju igra nije rješiva. Računalo odabire bilo koje opasno polje i odvodi agenta u smrt.

Strategija računala je, dakle, da igra s minimalnim rizikom, slično kao što bi u takvoj situaciji radio i čovjek.

Algoritam omogućava računalu da je taj minimalni rizik doista minimalan, tj. računalo će igrati naslijepo samo u situacijama kada doista nema više sigurnim polja, a agenta će svjesno odvesti u sigurnu smrt samo ako igra doista nije rješiva.

OPIS RADNOG OKRUŽENJA

Radna ploha podijeljena je u nekoliko dijelova.

Prikazana su dva svijeta po kojima se agent kreće. Na jednom je prikazano stvarno stanje svijeta sa rasporedom jama, Wumpusa i zlata, onako kako su ti objekti dinamički pseudoslučajnim odabirom generirani. Na drugom je prikazan svijet u obliku kako ga poznaje agent. Tu se vidi trenutni položaj agenta, te sve što je agent (računalo) do tog trenutka saznao i na temelju tog saznanja zaključio.

Praćenje procesa zaključivanja i izvođenja novog znanja moguće je pregledom triju tekstualnih polja.

Jedno polje služi za prikaz početne baze znanja. Početna baza znanja sadrži znanje koje je agentu poznato i prije nego što započne igru.

Na primjer:

p1) ako na polju (1,1) nema propuha, tada nema jame na polju (1,2) ni na polju (2,1)

U tom polju se tijekom igre bilježe i sve percepcije koje agent osjeća.

Na primjer:

p2) nema propuha na polju (1,1)

U drugom tektualnom polju prikazano je izvedeno znanje koje je agent, odnosno računalo, izveo na temelju početne baze znanja i prikupljenih percepcija.

Na temelju premisa p1) i p2) novoizvedeno znanje upisano u ovom polju će biti

i1) nema jame na polju (1,2)

i2) nema jame na polju (2,1)

Treće, preostalo tekstualno polje služi za prikaz postupka izvođenja novog znanja. Tu se prikazuje koja se ciljna formula ispituje, postupak rezolucije opovrgavanjem, te rezultat ispitivanja.

U svakom koraku rezolucije opovrgavanjem prikazano je iz kojih dviju klauzula je izvedena nova klauzula. Pritom su klauzule u početnoj bazi znanja označene indeksom p, dok su izvedene klauzule označene indeksom i, i pripadajućim brojem.

OPIS GRAFIČKIH SIMBOLA

Neposjećena polja:

    neposjećeno polje, ništa se još o njemu ne zna

    neposjećeno polje, postoji opasnost da je tamo jama

    neposjećeno polje, ali se zna da je tamo sigurno jama

    neposjećeno polje, postoji opasnost da je tamo Wumpus

    neposjećeno polje, ali se zna da je tamo sigurno Wumpus

    neposjećeno polje, postoji opasnost od jame ili Wumpusa

    neposjećeno polje, ali se zna da je tamo sigurno i jama i Wumpus

    neposjećeno polje, ali se zna da je sigurno, nema ni jame ni Wumpusa

Posjećena polja:

    prazno polje, ništa se na njemu ne osjeća

    polje na kojem se trenutno nalazi agent, u fazi istraživanja, kreće se po sigurnom putu

    polje na kojem se trenutno nalazi agent, u fazi istraživanja, ali na putu prema nesigurnom polju

    agent je upravo pronašao zlato

    agent se vraća noseći zlato

    na tom se polju osjeća zadah, na nekom od susjednih je Wumpus

    na tom se polju osjeća propuh, na nekom od susjednih je jama

    na tom se polju osjeća i zadah i propuh, na nekom od susjednih je Wumpus i jama

Kraj igre:

    agent je stradao, zadatak nije obavljen

Igra je napisana u programskom jeziku Java, korištenjem alata Borland Java Builder 4.0 kao Java Applet, te je prilagođena za izvršavanje na web-u korištenjem nekog od web-preglednika.

Da bi se Java Applet mogao izvršavati preko web-preglednika potrebno je imati instaliranu podršku za JVM (Java Virtual Machine), što ima većina preglednika, te još dodatni Java plug-in (JRE 1.3.1 - Java Runtime Environment 1.3.1) koji bi se, ukoliko nije instaliran na lokalno računalo, trebao automatski skinuti sa stranica Sun Microsystems Inc. prilikom pokretanja.

Literatura:  

[1] Russell, S. J.; Norvig, P. (1995).  Artificial Intelligence, A Modern Approach, Prentice Hall, New Jersey

[2] Dalbelo Bašić, B. (2001). Bilješke za predavanja, http://www.zemris.fer.hr/education/is/

[3] Robinson, J.A. (1965). A machine-oriented logic based on the resolution principle, Journal of the ACM, 12(1), 23-4.

Wumpus - programska izvedba

Dejan Škvorc

Zagreb, siječanj 2002.