2 KOMPLEKSNI ZADACI I NJIHOVO RJEŠAVANJE

2 KOMPLEKSNI ZADACI I NJIHOVO

RJEŠAVANJE

Pri izgradnji sustava sposobnog za rješavanje nekog određenog zadatka trebamo voditi računa o

tri koraka sustavnog rješenja kojeg čini:

1. Postavljanje zadatka kod kojeg definiramo prostor stanja u kojem se nalaze moguća

rješenja zadatka, od početnog stanja ili situacije u kojoj se trenutno nalazimo, preko svih

međustanja do željenog ili ciljnog stanja ili situacije. Početno stanje može biti samo jedno, a

ciljnih stanja može biti više.

2. Analiziranje zadatka kako bismo otkrili sve njegove osobine, te odabrali odgovarajuće

metode rješavanja.

3. Rješavanje zadatka sastoji se u odabiru najbolje (najprimjerenije) tehnike dolaska od

početnog stanja do ciljnog stanja koje nam predstavlja rješenje.

2.1

Postavljanje zadataka

Prvi korak pri rješavanju bilo kojeg zadatka, a pogotovo kada se radi o kompleksnom,

netrivijalnom zadatku, je postavljanje zadatka, formalni opis onoga gdje se nalazimo, gdje želimo ići, što

nam je cilj i kako možemo do tog cilja doći. Nas prije svega zanima postavljanje zadatka na način da ga

možemo riješiti nekim od postupaka umjetne inteligencije. To je dosta drugačiji pristup rješavanju

zadatka od standardnog algoritamskog pristupa s kojim smo se uobičajeno susretali. Algoritamskim

pristupom do rješenja se dođe uvrštavanjem poznatih vrijednosti u određenu formulu. Pri tome nas prije

svega zanimaju problemski zadaci, pa da bismo uočili razliku između pristupa rješavanju kako se to radi

u okviru umjetne inteligencije, pogledajmo najprije kako se problemski zadatak postavlja kod

algoritamskog rješavanja. Koristili smo ga tijekom cijelog školovanja, od rješavanja računskih pričica, pa

do rješavanja i zadataka iz fizike koji i nisu jednostavni. Tri su osnovna koraka:

• definiranje poznatih vrijednosti

Kompleksni zadaci su zamršeni, zapleteni i komplicirani, a za njihovo rješavanje ne

postoje formule u koje bismo uvrstili poznate vrijednosti i izračunali nepoznate.

Kompleksni zadaci rješavaju se na potpuno drugačije načine koristeći postupke kao što

su pretraživanje, zaključivanje ili strojno učenje. Bez obzira koja se tehnika rješavanja

koristi, prvi je korak postavljanje zadatka, nakon čega slijedi analiziranje zadatka i tek

onda rješavanje koje se sastoji u odabiru najprimjerenije tehnike rješavanja zadataka.

“

„

2 KOMPLEKSNI ZADACI I NJIHOVO RJEŠAVANJE

• definiranje nepoznanica, tražene vrijednosti nepoznate veličine koju želimo izračunati i

• definiranje formule, matematičkog izraza koji ćemo koristiti kod rješavanja.

Postupak rješavanja sastoji se od uvrštavanja poznatih vrijednosti u formulu i dobivanja

nepoznatog rješenja. Pogledajmo jednostavni primjer:

Zadatak 1. – Standardni algoritamski pristup rješavanju&zadataka!

Izračunaj brzinu vozila koje je put od 100 m prevalilo za 10 sekundi ako se gibalo jednoliko?

Postavljanje zadatka

1. Poznate vrijednosti:

Put = 100 m

Vrijeme = 10 sekundi

2. Cilj, nepoznata, tražena vrijednost:

Brzina = ?

3. Potrebno znanje – matematička formula:

Brzina = Put / Vrijeme

Rješavanje zadatka – uvrštavanje poznatog u formulu:

Brzina = 100 m / 10 s = 10 m/s

Ponekad zadatak može biti i znatno složeniji pa da bismo došli do rješenja, treba nam i nekoliko

formula, ponekad prilično zahtjevnih, ali kod algoritamskog pristupa rješenje uvijek dobijemo direktnim

matematičkim proračunom.

Postupci rješavanja zadataka metodama umjetne inteligencije bitno su različiti. Riješiti zadatak

znači pronaći put od početnog stanja do ciljnog stanja unutar prostora svih mogućih međustanja.

Međustanja predstavljaju moguća rješenja zadatka. Način prelaska iz jednog međustanja u drugo

definiraju pravila prelaska. Sastavni dio postupka uključuje u svakom koraku usporedbu trenutnog

stanja s ciljnim rješenjem. Ako je postignuto poklapanje, zadatak smo uspješno riješili. Sada je i lakše

shvatiti zamjerku kineske sobe. U osnovi se postupci umjetne inteligencije sastoje u generiranju rješenja,

usporedbi s ciljnim rješenjem i „zapisivanju jedinice ako se rješenje i ciljno rješenje poklapaju”.

Ovakav postupak rješavanja zadataka zahtijeva i drugačije postavljanje zadatka, pri čemu je

važan formalni zapis, po mogućnosti u takvom obliku iz kojeg se lako može prebaciti u programski kod.

Postavljanje zadataka primjereno postupku umjetne inteligencije sastoji se od četiri koraka:

• Definiranja prostora stanja: Potrebno je definirati prostor stanja u kojemu se zadatak

rješava. Prostor stanja rješavanja zadatka čine sva moguća rješenja zadatka, a svako se

rješenje prikazuje na formalan način. Zbog toga se često naziva i prostor rješenja, prostor

pretraživanja ili problemski prostor.

• Definiranje početnog stanja: Unutar prostora stanja rješavanja zadatka trebamo odrediti

početno stanje, stanje koje smo zatekli, stanje iz kojeg krećemo u rješavanje zadatka.

• Definiranja ciljnih stanja: Potrebno je definirati stanja koja možemo smatrati

prihvatljivim rješenjem i koja nazivamo ciljnim stanjima ili konačnim rješenjima. Može

ih biti i više od jednog. U svakom koraku rješavanja ciljna se stanja uspoređuju s trenutnim

stanjem. Njihovo poklapanje znači da smo došli do rješenja.

• Definiranja skupa pravila: Pravila opisuju moguće akcije ili operacije kojima se iz jednog

stanja može doći do nekog drugog stanja unutar prostora rješenja. Ova pravila u biti

predstavljaju znanje kojim se vodimo pri traženju rješenja zadatka.

Potrebno je naglasiti da se postupcima umjetne inteligencije problemski zadatak rješava

pretraživanjem rješenja u prostoru stanja upotrebom pravila uz pomoć odgovarajuće upravljačke

2 KOMPLEKSNI ZADACI I NJIHOVO RJEŠAVANJE

strategije. Upravljačka strategija određuje u koje ćemo novo stanje otići iz stanja u kojem se trenutno

nalazimo. O efikasnosti upravljačke strategije ovisi i efikasnost dolaska do ciljnog rješenja. Prema tome

osnovni postupak rješavanja zadataka umjetne inteligencije jest postupak pretraživanja (engl. Search)

o kojem detaljno govorimo u poglavlju 3. U nastavku će se na dva primjera ilustrirati način postavljanja

i rješavanja zadatka na način koji se koristi u umjetnoj inteligenciji.

Zadatak 2. - Problem punjenja vrčeva (engl. Water Jug Riddle)

Imamo dva vrča, jedan od 4 litre (vrč A) i jedan od 3 litre (vrč B). Ni jedan od njih nema oznake o

količini vode u vrču i jedina pouzdana informacija o tome može se dobiti samo kada su vrčevi prazni

ili puni. Vrčevi se mogu puniti na slavini i prazniti na način da se voda može prelijevati iz vrča u

vrč ili izlijevati na pod. Zadatak glasi ovako: ako se krene od situacije praznih vrčeva, kako u vrč A

od 4 litre uliti točno 2 litre vode? Budući da na vrčevima ne postoje oznake ne možemo kod

prelijevanja vode iz jednog vrča u drugi puniti samo do određene razine. Zadatak bi u tom slučaju

bio trivijalan i riješili bismo ga u dva koraka (napunili vrč B te ga izlijevali u vrč A dok u njemu ne

bi bilo točno pola tekućine). Vrč možemo puniti ili samo do samog vrha ili svu tekućinu iz jednog

vrča preliti u drugi. Zadatak ilustrira slika 2-1.

Slika 2-1. Zadatak dva vrča

Postavljanje zadatka

Trebamo definirati prostor stanja, početno stanje, ciljna stanja i skup pravila:

prostor stanja rješavanja zadatka možemo definirati uređenim parom (x,y) gdje x može biti 0,

1, 2, 3 ili 4 i predstavlja broj litara vode u vrču A od 4 litre, a y može biti 0, 1, 2 ili 3 i predstavlja

broj litara vode u vrču B od 3 litre

početno stanje – oba vrča su prazna, što u prostoru stanja znači (0, 0)

ciljno stanje – zadatak traži 2 litre vode u vrču od A od 4 litre, dok količina vode u vrču B od 3

litre nije važna. To možemo prikazati kao (2, y) gdje je y bilo koja vrijednost iz skupa {0,1,2,3}

skup pravila – početne pretpostavke - vrčevi se mogu puniti i prazniti. Kako ne možemo vidjeti

koliko je točno vode ostalo ili koliko je vode doliveno u vrč (nemamo oznaka) količinu vode

procjenjujemo samo na temelju pamćenja koliko smo vode izlili. Jedino što možemo vidjeti jest je li

vrč pun i tada znamo da je u vrču A 4 litre, a u vrču B 3 litre ili je li neki od vrčeva prazan kada je

u njemu 0 litara. Ovo znanje o punjenju – pražnjenju vrčeva trebamo iskazati na formalni, po

mogućnosti matematički način kako bismo ga mogli primijeniti prilikom prijelaza iz jednog stanja

napunjenosti vrčeva u drugo. Najpogodniji način formalnog zapisa dozvoljenih načina punjenja –

pražnjenja je u obliku pravila prijelaza koja matematički prikazujemo relacijom implikacije. Na

lijevoj strani implikacije je stanje u kojem se dotično pravilo može primijeniti, a na desnoj je stanje

koje će se dobiti nakon primjene tog pravila. Ukupno je 8 dozvoljenih pravila prijelaza:

1. Napuniti 4-litarski vrč. (x, y | x < 4)

(4, y)

2. Napuniti 3-litarski vrč. (x, y | y < 3)

(x, 3)

3. Isprazniti 4-litarski vrč na zemlju. (x, y | x > 0)

(0, y)

2 KOMPLEKSNI ZADACI I NJIHOVO RJEŠAVANJE

4. Isprazniti 3-litarski vrč na zemlju. (x, y | y > 0)

(x, 0)

5. Isprazniti svu vodu iz 4-litarskog vrča u 3-litarski. (x, y | x + y

≤

3 & x > 0)

(0, x+y)

6. Isprazniti svu vodu iz 3-litarskog vrča u 4-litarski (x, y | x + y

≤

4 & y > 0)

(x+y, 0)

7. Izliti vodu iz 4-litarskog vrča u 3-litarski dok nije pun.

(x, y | x + y

≥

3 & x > 0)

(x-(3-y), 3)

8. Izliti vodu iz 3-litarskog vrča u 4-litarski dok nije pun.

(x, y | x + y

≥

4 & y > 0)

(4, y-(3-x))

Rješavanje zadatka

Da bi se riješio zadani zadatak osim pravila prijelaza koja predstavljaju znanje o prijelazu iz jednog

stanja u drugo, treba nam i upravljačka strategija koja nas vodi kroz pravila. U ovom slučaju

možemo koristiti jednostavnu upravljačku strategiju koja kaže:

Usporedi lijevu stranu implikacije s trenutnim stanjem te ako je zadovoljena primjeni to pravilo.

Ciklički prolazi kroz sva pravila od prvog do osmog.

Kasnije ćemo vidjeti da odabir ovakve strategije odgovara postupku koji se zove pretraživanje po

dubini. Naglasimo da o efikasnosti strategije upravljanja ovisi i efikasnost postupka rješavanja

postavljenog zadatka.

Strategija treba biti efikasna, a efikasna je prije svega ako uzrokuje kretanje ali pri tome kretanje

ne smije biti kretanje u krug. Neuspješna strategija bila bi ona koja bi se prolazom kroz nekoliko

stanja ponovo vratila u početno stanje, a da ni jedno od prijeđenih stanja nije bilo ciljno stanje.

Takva strategija nikada ne bi došla do rješenja. Drugi zahtjev je da strategija bude sustavna.

Uzmimo za primjer nešto drugačiju strategiju. Na svakom koraku slučajno biramo pravilo koje

ćemo testirati. Ova strategija uzrokuje kretanje i možda će dovesti do rješenja, ali to nije sigurno i

vjerojatno ćemo napraviti puno nepotrebnih koraka prije nego dođemo do cilja. Strategija u ovom

slučaju nije sustavna. Sustavna strategija je izgradnja cijelog prostora mogućih rješenja koji

možemo prikazati grafom tipa stablo. Na vrhu, u početnom ili korijenskom čvoru je početno stanje,

a ciljno stanje će ako do njega dođemo biti negdje na dnu poslije prolaska kroz određeni broj razina

stabla. Slika 2-2 prikazuje nekoliko razina prostora rješenja zadataka dva vrča.

Slika 2-2. Nekoliko razina prostora rješenja zadatka dva vrča

Početno stanje je (0, 0). To se stanje poklapa s lijevom stranom 1. i 2. pravila, pa su dva moguća

sljedeća stanja (4, 0) i (0, 3). Primijenimo li pravilo 1. dobijemo stanje (4, 0), dok pravilo 2. daje

stanje (0, 3). Svako od ovih stanja uspoređujemo s ciljnim stanjem (2, y). Ako se stanja ne

podudaraju nastavljamo dalje graditi prostor rješenja zadatka. Proces se nastavlja sve dok se neko

od stanja ne poklopi s ciljnim stanjem. Pri tome se mogu koristiti različite strategije razvoja

prostora rješenja o kojima ćemo kasnije više govoriti. Ovdje ćemo naglasiti jedino to da je posebno

važno izbjeći petlje, na način da se nastoji spriječiti da se pojedina stanja ponovo pojave. Na primjer

stanje (0,0) je početno stanje, ali ono se i dva puta javlja u drugom redu razvoja. Isto tako stanje

(4,3) se u istom redu dva puta ponavlja. Efikasna strategija formiranja prostora rješenja je ona koja

će ove čvorove isključiti iz daljnjeg razvoja. Zadaci ovakvoga tipa nemaju samo jedno rješenje.

2 KOMPLEKSNI ZADACI I NJIHOVO RJEŠAVANJE

Jednakovrijednih rješenja može biti i više. Na primjer ako rješenje zadatka dvaju vrčeva

vrednujemo po broju prijeđenih koraka od početka do cilja, dva moguća jednakovrijedna rješenja

Broj iznad strelice označava koje smo pravilo primijenili. U oba se slučaja do rješenja dolazi nakon

šest koraka pa su, što se tiče"brzine dolaska od početnog do ciljnog čvora, identični. Međutim postoji

razlika u postupku kojim dolazimo do ovog slijeda koraka. Jedno od ovih rješenja može se pronaći

brže uz manji razvoj prostora rješenja, pa nam je takvo rješenje pogodnije zato što do njega dolazimo

s manje truda.

Kod ovakvog tipa zadatka važno je uočiti da smo prostor rješenja zadatka razvijali tijekom

rješavanja zadatka. Spuštali smo razinu po razinu i postupno razvijali prostor rješenja, a u svakom smo

koraku koristili bazu znanja i u njoj tražili odgovarajuće pravilo primjenjivo baš za to stanje. Rješavanja

zadatka postupkom umjetne inteligencije u ovom se primjeru svodi na sustavno razvijanje prostora

rješenja zadatka odgovarajućom strategijom kako bismo pronašli stanje koje odgovara ciljnom stanju.

Zadatak dva vrča je primjer zadatka kod kojeg je relativno jednostavno definirati cilj, pravila i

prostor stanja, ali to nije uvijek tako. Postoje zadaci u kojima je teško definirati i prostor rješenja, a

ponekad i ciljno stanje i pravila prijelaza. Uzmimo za primjer zadatak razumijevanja rečenice govornog

jezika. Ovdje se ni jedna od značajki zadatka ne može jednostavno postaviti.

Sustav kod kojeg je znanje u obliku skupa pravila, strategija upravljanja i baza podataka u koju

se spremaju svi podaci bitni za rješavanje zadatka naziva se produkcijski sustav. Velik broj stručnih

sustava koji su u upotrebi upravo je oblika produkcijskog sustava, pa ćemo se toj problematici

produkcijskog sustava još puno puta vraćati.

Pogledajmo i drugačiji tip problema koji možemo riješiti metodom umjetne inteligencije.

Zadatak 3. - Problem trgovačkog putnika (engl. Travelling Salesman Problem)

Trgovački putnik treba na Braču obići četiri mjesta: Supetar, Pučišća, Sumartin i Nerežišća te se

vratiti u početni grad. Svaki od gradova smije posjetiti samo jedanput. Postoje ceste koje spajaju

bilo koja dva grada, a dužine u km dane su u tablici 2-1.

Tablica 2-1. Udaljenost između naselja na otoku Braču u km

Zadatak je pronaći kružnu, najkraću rutu tako da se obiđu svi gradovi i vrati natrag u početni

grad, a da ukupni prevaljeni put bude najkraći. Položaj gradova na karti otoka Brača prikazuje

slika 2-3.

U poglavlju 4.4.1 Produkcijski sustavi nalazi se Prolog kod za rješavanje ovog problema.

1. 7. 4. 3. 1. 7.

(0,0) ( 4,0) (1,3) (1,0) (0,1) (4,1) (2,3)®®®®®®

)0,2()2,0()2,4()3,3()0,3()3,0()0,0(

.6.3.82.6.2

®®®®®®

2 KOMPLEKSNI ZADACI I NJIHOVO RJEŠAVANJE

Slika 2-3. Karta otoka Brača s položajem naselja

Postavljanje zadatka

Ovo je jedan od klasičnih zadataka nazvan problem trgovačkog putnika za koji postoje i različita

rješenja temeljena na teoriji grafova. U duhu umjetne inteligencije zadatak postavljamo na način

da definiramo:

prostor stanja rješavanja zadatka su gradovi koje se treba obići i koje ćemo simbolički označiti

slovima S – Supetar, B – Nerežišća, D – Pučišća, G – Sumartin (ove simboličke oznake koristimo sa

pojednostavljene cestovne mreže otoka Brača prikazane na slici 3-8, na kojoj u sljedećem poglavlju

detaljno objašnjavamo postupke pretraživanja). Gradovi dolaze u čvorove stabla problema, a veze

između čvorova predstavljaju udaljenosti od gradova u km.

početno stanje - trgovac kreće iz grada S – Supetra

ciljno stanje - trgovac se treba vratiti u grad S i proći sve ostale gradove samo jedan put

skup pravila - ovdje nema nekih posebnih pravila. Jedino pravilo po kojem gradimo prostor

rješenja zadatka je da sljedeći grad na nižoj razini ne smije biti niti jedan grad koji je u toj liniji

trgovac već prošao s obzirom na to da smo u postavljanju zadataka definirali da trgovac ne smije

kroz isti grad proći dva puta.

Rješavanje zadatka

Najjednostavniji sustavni pristup rješavanju ovog zadatka je postavljanje prostora stanja

rješavanja zadatka u obliku stabla koje sadrži sve moguće gradove i to u slijedu kako ih trgovac

treba posjetiti. Uz to za svaku rutu zbrajamo prijeđene udaljenosti, te nađemo najkraću. Izgled

stabla rješenja prikazuje slika 2-4.

Zadatak ima dva rješenja: put Supetar (S) – Nerežišća (B) – Sumartin (G) – Pučišća (D) – Supetar

(S) i put Supetar (S) – Pučišća (D) – Sumartin (G) – Nerežišća (B) – Supetar (S) s obzirom da je

dužina u oba slučaja 100 km. Ova sustavna metoda izgradnje cijelog prostora rješenja je uspješna

samo dok je broj gradova mali. Ako postoji N gradova, potrebno je istražiti (N-1)! različitih putova.

To je za 4 grada 1

3 = 6 putova, dok se za 11 gradova broj kombinacija penje na 3.628.800, a za

50-ak gradova broj kombinacija je blizu 10

. Možda ovaj broj na prvi pogled i ne izgleda velik, ali

ako spomenemo da je prema mišljenju kozmologa svemir star oko 10

sekunda onda 10

poprima

sasvim drugačiju dimenziju. Ovakav nagli rast kombinacija naziva se kombinacijska eksplozija.

Ona predstavlja ograničenje sustavnom rješavanju zadatka. Još veći problem kombinacijske

eksplozije je igra šaha.

2 KOMPLEKSNI ZADACI I NJIHOVO RJEŠAVANJE

Slika 2-4. Prostor rješenja za zadatak trgovačkog putnika koji treba proći kroz pet gradova

U prvom koraku imamo oko 15-ak mogućih poteza, u drugom približno 15

, u trećem 15

čime broj

vrtoglavo raste. Za rješavanje ovakvog tipa zadatka potrebno je definirati potpuno drugačiju

strategiju upravljanja koja će dovesti do cilja bez potrebe da se prođu sve moguće kombinacije.

Predložena će"strategija do cilja dovesti jako brzo, a jedini je problem što nije sigurno da će dati

najbolje rješenje, odnosno najkraći put. Dat će rješenje koje se koji put poklopi s najboljim, a koji

put ne, ali će i tada biti relativno blizu najboljeg rješenja. Postupak se naziva heurističko

pretraživanje (engl. Heuristic Search)."

Sama riječ heuristika grčkog je porijekla i dolazi od riječi „heurisko” (εύρίσκω) što znači otkrio

sam. To je također i korijen poznate riječi „Eureka!”, Arhimedovog uzvika „Pronašao sam!” kada je

otkrio metodu određivanja čistoće zlata. Heurističko pretraživanje je postupak kojim se povećava

efikasnost postupka traženja, obično uz žrtvovanje potpunosti. Postoji niz općenitih heuristika koje

su korisne za rješavanje velikog broja zadataka, dok s druge strane postoje i specijalizirane

heuristike razvijene za potrebe rješavanja zadataka određene, uske domene.

Primjer univerzalne heuristike koristan pri rješavanju kombinacijskih problema, kao što je naš

zadatak trgovačkog putnika, je algoritam najbližeg susjeda (engl. Nearest Neighbour

Algorithm). U našem slučaju on se sastoji samo od dva koraka:

Otiđi u najbliži grad.

Ponovi prvo pravilo dok se ne obiđeš sve gradove.

Prema slici 2-4 to bi značilo iz Supetra (S) otići u Nerežišća (B) s obzirom na to da su najbliža, zatim

u Pučišća (D) i onda u Sumartin (G) koji je još ostao, pa natrag u Supetar (S). U ovom primjeru

vidimo da algoritam najbližeg susjeda ne daje ujedno i jedno od najboljih rješenja (ukupno najkraći

pređeni put). U nekoj drugoj situaciji ukupno prijeđeni put može biti i najkraći, ali heurističko

pravilo to ne garantira.

Bez heuristike su zadaci u kojima se javlja kombinacijska eksplozija puno teže rješivi, ali postoje

i drugi razlozi koji govore u prilog heuristike. Iako heuristika ne garantira najbolje rješenje, mi ga u biti

i rijetko kada baš i trebamo. U svom svakodnevnom životu najčešće se rukovodimo prvim

zadovoljavajućim rješenjem. Dobar je primjer parkiranje automobila. Većina će ljudi prekinuti

traženje parking mjesta koje će biti bliže njihovoj konačnoj destinaciji već kada nađu prvo slobodno mjesto

koje je po njihovom sudu dovoljno blizu i zadovoljavajuće. Napomenimo da se o heuristici i heurističkom

pristupu rješavanju zadataka pisalo još 1940-ih godina. Matematičar George P

lya je 1945. godine

objavio knjigu „Kako riješiti” (engl. How to solve it)

u kojoj daje niz heurističkih naputaka kako riješiti

https://math.hawaii.edu/home/pdf/putnam/PolyaHowToSolveIt.pdf

2 KOMPLEKSNI ZADACI I NJIHOVO RJEŠAVANJE

matematičke probleme, ali se njegove heuristike mogu upotrijebiti i kod šire klase problema. Ova je knjiga

ostavila veliki trag na istraživače umjetne inteligencije. U sljedećem poglavlju navode se neki od

Pólyaovih principa analize zadatka. Spomenimo samo da se prema Pólyau svako rješavanje zadatka treba

provoditi u četiri koraka:

• shvatiti (razumjeti) zadatak

• napraviti plan rješavanja

• provesti plan rješavanja i na kraju

• provjeriti rezultat.

Shvatiti zadatak znači prije svega razumjeti što se traži, što je zadano i koja su ograničenja, ali

ako se radi o kompleksnom zadatku, trebamo isto otkriti osnovne značajke ili karakteristike zadatka.

2.2

Osnovne značajke zadataka

Već smo naglasili da je osnovni postupak rješavanja zadataka unutar umjetne inteligencije

postupak pretraživanja. Pretraživanje je skup univerzalnih metoda primjenjiv pri rješavanju široke

klase problema, a uključuje primjerice već spomenuto heurističko pretraživanje, slijepo i usmjereno

pretraživanje o kojima ćemo u 3. poglavlju detaljnije govoriti. Međutim, svaka od tehnika pretraživanja

uključuje i niz specifičnih tehnika primjenjivih za određeni tip zadataka. Kako bi se mogla izabrati

odgovarajuća metoda ili kombinacija nekoliko različitih metoda, potrebno je analizirati zadatak uzimajući

u obzir njegove osnovne značajke. Najvažnije od njih su:

1. Dekompozicija – može li se zadatak razbiti u više nezavisnih podzadataka lakših za

rješavanje?

2. Zanemarivanje – mogu li se zanemariti neki od koraka rješavanja zadataka?

3. Predvidivost – je li prostor rješenja zadatka predvidiv?

4. Očitost rješenja – je li dobro rješenje očito u usporedbi s ostalim mogućim rješenjima?

5. Dosljednost znanja – je li baza znanja koja je potrebna za rješavanje zadatka dosljedna

(konzistentna), bez kontradikcija?

6. Uloga znanja – koja je uloga znanja u rješavanju zadatka? Je li znanje neophodno

potrebno za rješavanje zadatka ili je potrebno samo za olakšavanje rješavanja zadatka?

7. Interaktivnost – zahtijeva li zadatak interakciju čovjeka i računala tijekom rješavanja?

Pogledajmo ukratko svaku od ovih značajki.

2.2.1 Dekompozicija

Ako je moguće zadatak razbiti u niz jednostavnijih zadataka, tada se i jednostavnije metode mogu

primijeniti za njegovo rješavanje. Ovo je standardni postupak koji se primjenjuje kod rješavanja

matematičkih zadataka. Tipičan primjer je rješavanje integrala koji obično rastavljamo na osnovne

integrale koji su tabličnog oblika. Kod rješavanja integrala to možemo raditi zato što vrijedi zakon

superpozicije, ali su kompleksni zadaci često takvi da suma parcijalnih rješenja ne odgovara ukupnom

rješenju pa je dekompoziciju često nemoguće napraviti.

2.2.2 Zanemarivanje

Važna karakteristika zadatka je može li se pojedini korak u rješavanju zanemariti ili se treba

ponoviti. Zadaci kod kojih se pojedini korak može zanemariti mogu se uspješno rješavati upravljačkom

strukturom koja se nikada ne vraća unatrag, pa je stoga jednostavna i brza. Zadaci koji zahtijevaju

ponavljanje svih koraka imat će složeniju strukturu upravljanja, koja će dopuštati vraćanje unatrag ako

se napravi pogrešan potez, dok se kod neponovljivih problema pogrešan potez ne smije napraviti, zato što

2 KOMPLEKSNI ZADACI I NJIHOVO RJEŠAVANJE

nema popravljanja. Na primjer, ako u zadatku dva vrča naiđemo na neko stanje koje smo već imali,

možemo ga zanemariti i time skratiti proces traženja rješenja.

2.2.3 Predvidljivost

Uz značajku zanemarivanja važna je i značajka predvidljivosti prostora rješenja zadatka.

Pitanje je jesu li buduća rješenja predvidiva s određenim stupnjem sigurnosti ili su nepredvidiva.

Planiranjem postupka rješavanja prva klasa problema može se relativno uspješno riješiti, dok se kod

druge klase u najboljem slučaju može garantirati s većom ili manjom sigurnošću da će se zadatak moći

riješiti. Najteži zadaci su neponovljivi i nepredvidivi.

Tipičan primjer takvih zadataka su različite igre u kojima sudjeluju najmanje dva igrača pa

sljedeće stanje ovisi o reakciji protivničkih igrača. U ovu grupu mogu spadati pravni savjetodavni

(ekspertni) sustavi koji bi npr. trebali predložiti postupak obrane, ili pak zadaci upravljanja samohodnim

robotom u nepoznatom ambijentu.

2.2.4 Očitost rješenja

Sljedeće je pitanje je li rješenje apsolutno dobro ili relativno dobro. U odnosu na nj

razlikujemo tzv. zadatke bilo kojeg puta (engl. Any-Path Problem) i zadatke najboljeg puta (engl. Best-

Path-Problems). Prvi su lakši za rješavanje zato što je svako rješenje, bez obzira na put do njega, dobro

rješenje i ne treba se uspoređivati s rješenjem koje je dobiveno na neki drugi način. Zadatak bilo kojeg

puta je primjer dva vrča u slučaju da dolazimo do rješenja s istim brojem koraka. Oba rješenja koja smo

naveli su jednako vrijedna i potpuno nam je svejedno do kojeg smo prvo došli. Zadatak trgovačkog putnika

je zadatak tipa najboljeg puta. Ne možemo garantirati da smo došli do najboljeg rješenja dok ne prođemo

sve kombinacije. To što zadatak ima dva najkraća puta za postupak rješenja nije bitno. Da smo stvarno

prešli najkraći put, znamo tek nakon što testiramo sva moguća rješenja.

2.2.5 Dosljednost znanja

Dosljednost (konzistentnost) baze znanja također je važna značajka koja utječe na postupak

rješavanja. Na primjer, ako baza znanja sadrži logičke tvrdnje da je A točno i da A nije točno, tijekom

rješavanja zadatka i izgradnje prostora rješenja u nekom trenutku nećemo znati kako postupiti. Znanje

potrebno za prijelaz iz jednog stanja u drugo nije dosljedno.

Posebno je kritična situacija u vezi dosljednosti znanja ako znanje prikazujemo klasičnom, na

primjer predikatnom logikom. Predikatni račun nije prilagođen nedosljednoj bazi znanja. Kritična je i

situacija u kojoj imamo sustav koji uči kod kojega postoji mogućnost dodavanja novoga znanja u bazu

znanja. Novo, dodano znanje ne smije biti u kontradikciji s nekim već postojećim znanjem. Ako je u

kontradikciji, onda jednu od kontradiktornih tvrdnji trebamo izbrisati. U okviru istraživanja vezanih s

provjerom dosljednosti baze znanja razvijen je posebni sustav održavanja istinitosti (engl. Truth

Maintenance System) čiji je zadatak provjeravati dosljednost baze znanja nakon dodavanja novog znanja.

2.2.6 Uloga znanja

Ponekad je baza znanja nužna za rješavanje zadatka. Bez nje se ne može razvijati prostor

rješenja niti se može iz jednog stanja prelaziti u drugo. Tipičan je primjer zadatak dva vrča. Ako ne znamo

što s vrčevima možemo napraviti, ne možemo niti riješiti zadatak. Pretpostavimo li da zadatak zadamo

nekome tko nikada u životu nije vidio vrč ili posudu i ne zna da se vrč može puniti, on ne može niti riješiti

zadatak. Pravila o punjenju i pražnjenju vrčeva bitan su dio postupka rješavanja.

S druge strane postoje zadaci kod kojih znanje služi samo za ubrzavanje postupka rješavanja,

npr. ako bismo imali računalo neograničene brzine i kapaciteta, tada bi se zadatak trgovačkog putnika

mogao riješiti bez posebnog znanja jednostavnim generiranjem svih mogućih putova. U ovom tipu

zadatka znanje, na primjer u obliku heurističkog pravila, služi samo za ubrzavanje postupka rješavanja.

Slična je situacija i kod igre šaha. Računalo neograničene brzine i kapaciteta bit će uspješno u igri šaha

2 KOMPLEKSNI ZADACI I NJIHOVO RJEŠAVANJE

samo na temelju osnovnog znanja o dozvoljenim potezima, međutim isto to računalo nikada ne bi moglo

predvidjeti rezultate na izborima ako ima samo znanje o tome da se može glasati ili za stranku A ili za

stranku B. Tu osnovno znanje nije dovoljno. Da bi rezultati predviđanja ishoda izbora bili suvisli, treba

velika količina specijalističkog znanja.

2.2.7 Interaktivnost – uloga čovjeka

Posljednja karakteristika vezana je s načinom rješavanja i odnosi se na pitanje je li se zadatak

rješava potpuno samostalno, bez ikakve asistencije čovjeka, ili je zadatak takav da ga se rješava

nesamostalno, pa je u određenom koraku rješavanja zadatka bitan čovjek kao dodatni izvor informacija

bez kojih se ne može doći do dobrog rješenja. Naravno da je prvi tip zadataka puno teži za rješavanje.

Tipičan primjer samostalnog rješavanja zadatka je kretanje samohodnog robota po nepoznatom terenu

bez asistencije čovjeka, a tipičan primjer nesamostalnog rada su razni savjetodavni dijagnostički sustavi

ili detekcijski sustavi. Na Fakultetu elektrotehnike, strojarstva i brodogradnje Sveučilišta u Splitu

razvijen je sustav za rano otkrivanje šumskog požara analizom slike u vidljivom dijelu spektra OIV Fire

Detect AI

temeljen na različitim postupcima umjetne inteligencije.

Da je sustav potpuno samostalan, on bi nakon detekcije automatski podigao požarnu uzbunu i

pokrenuo postupak gašenja. Međutim, kako ovakvi sustavi uvijek imaju određeni broj lažnih alarma,

odmah je na početku osmišljen kao nesamostalni, poluautomatski sustav. Ako ovaj sustav detektira

mogući šumski požar, prezentira ga čovjeku operateru koji donese konačnu odluku o tome radi li se o

požaru ili ne. Da bi ostvario svoj cilj, a to je rana detekcija šumskog požara, nužno mu je dodatno znanje

čovjeka koji kaže: „Da, to je stvarno požar" i klikne na naredbu POTVRDI ALARM ili kaže: „Ne, to nije

požar" i klikne na naredbu PONIŠTI ALARM (slika 2-5).

Slika 2-5. Operatorski ekran inteligentnog sustava za rano otkrivanje šumskog požara. Za ispravno

funkcioniranje sustava nužna je interaktivnost s operatorom koji donosi konačnu odluku o tome je li na

slici požar ili nije klikom na odgovarajuću naredbu.

2.3

Rješavanje zadatka metodama umjetne inteligencije

Već smo naglasili da su osnovne metode umjetne inteligencije za rješavanja zadataka tzv. slabe

metode koje se ne zasnivaju na formuli ili strogom matematičkom algoritmu. Osnovni postupak

rješavanja naziva se pretraživanje, a pretražuje se prostor stanja u kojem se nalaze moguća rješenja

zadatka kojem se traži put od početnog stanja do ciljnog (ili ciljnih) stanja. U prethodnim smo poglavljima

upoznali dva tipična tipa zadataka umjetne inteligencije čijem se rješavanju može pristupiti postupcima

Za detalje pogledajte https://oiv.hr/en/services-and-platforms/oiv-fire-detect-ai

2 KOMPLEKSNI ZADACI I NJIHOVO RJEŠAVANJE

umjetne inteligencije. U problemu dva vrča prostor rješenja zadataka gradili smo postupno iz koraka u

korak, a u svakom koraku iz baze znanja (osam pravila punjenja/pražnjenja) tražili smo pravila koja

možemo primijeniti u tom trenutku. Kako ćemo razvijati prostor rješenja ili, kako je uobičajeno u

terminologiji umjetne inteligencije reći, kako ćemo razvijati čvor (engl. Expanding the Node) stabla

rješenja zadatka, ovisi o strategiji pretraživanja što je tema sljedećeg poglavlja. I u drugom zadatku

koji je predstavljao problem trgovačkog putnika gradili smo prostor rješenja zadatka samo što ga je sada

činio slijed posjećivanja gradova s liste. Nisu postojala pravila prelaska iz jednoga stanja u drugo zato što

se iz bilo kojeg grada moglo voziti u bilo koji drugi grad. Strategija pretraživanja u ovom je slučaju

definirala u koji ćemo sljedeći grad od svih preostalih neposjećenih gradova otići. Problemu trgovačkog

putnika sličan je problem najkraćeg puta (engl. Shortest Path Problem) kada se traži najkraći put

između dva grada i problem kineskog poštara (engl. Chinese Postman Problem) kada se traži zatvoreni

put kojim ćemo proći sve ceste koje spajaju gradove s tim da kroz svaki grad prođemo barem jedanput.

Svi su ovi zadaci pogodni za rješavanje primjenom odgovarajuće strategije pretraživanja, a različitim

strategijama pretraživanja detaljno se bavi sljedeće poglavlje.

................................................

Dodatak: U poglavlju o interaktivnosti i ulozi čovjeka u donošenju konačne odluke spomenuli smo

inteligentni sustav za rano otkrivanje šumskog požara analizom slike u vidljivom dijelu spektra OIV

Fire Detect AI, koji je razvijen na Fakultetu elektrotehnike, strojarstva i brodogradnje Sveučilišta u

Splitu. Kako se sustav temelji na brojnim inteligentnim tehnologijama, ovdje ćemo malo više o njemu

kazati. Kako se radi o sustavu, to znači da ima više sastavnih dijelova koje možemo izdvojiti iz okružja

u kojem djeluje i da ima svoju svrhu. Svaki inteligentni sustav mora imati tri osnovne komponente. Prvi

dio su osjetila (senzore) kojima dobiva sliku o okružju u kojem djeluje. Drugi dio je centralni dio u

kojem se ulazne senzorske informacije obrađuju, analiziraju, te se na temelju njih i pohranjenog znanja

donose odluke o djelovanju. Ova se informacija prenosi trećem dijelu kojeg čine izvršne strave

(aktuatori) pomoću kojih inteligentni sustav povratno djeluje na svoje okružje. Inteligentni sustav može

biti virtualni i realni. Virtualni inteligentni sustav djeluje u virtualnom okružju (na primjer Internet),

pa su mu i osjetila i izvršne sprave virtualni, a ulazne i izlazne informacije su datoteke. Realni

inteligentni sustav djeluje u stvarnom, realnom okružju u kojem i mi djelujemo, pa su mu osjetila i izvršne

naprave tehnički uređaji. Osnovna svrha OIV Fire Detect AI je upozoravanje na pojavu požara otvorenog

prostora u nastajanju i predviđanje njegovog mogućeg širenja, pa su mu osjetila visokorezolucijske,

panoramske kamere i meteorološke stanice, a izvršne sprave naprave za podizanje alarma (vizualnog i

akustičkog). U centralnom dijelu sustava analiziraju se ulazne slike koristeći različite napredne postupke

digitalne obrade i analize slike, te se na temelju njih u dijelu za zaključivanje, na temelju različitih

mehanizama zaključivanja, donosi odluka da li su na slici značajke požara otvorenog prostora (pojava

dima i/ili vatra) ili nisu. Ukoliko je zaključak pozitivan podiže se alarm i upozorava osoblje o mogućnosti

pojave požara. Kako sustav radi u kooperaciji s čovjekom operaterom, na njemu je, nakon provjere,

donijeti konačnu odluku da li se stvarno radi o požaru ili ne. Ako se požar potvrdi operater može

pokrenuti i simulator mogućeg kretanja požara slijedećih nekoliko sati, naravno ukoliko ne dođe do

intervencije gašenja požara. Sustav za sada pokriva područje Dalmacije sa stotinjak kamera.