Pertemuan 2Kecerdasan BuatanMasalah, Ruang Masalah, Pelacakan

Masalah dan penyelesaiannya

Untuk membangun sistem atau memecahkan masalah terdapat 4 hal :Definisikan masalah dengan jelasAnalisis masalahIsolasi/kumpulkan masalah dan representasi pengetahuanPilih teknik pemecah masalah terbaik dan terapkan untuk masalah tertentu

Mendefinisikan Masalah sebagai State Space Search (SSS)Misalnya permainan catur , maka SSS nya adalah :Menspesifikasikan posisi awal dari papan caturPeraturan (rules) yang mendefinisikan langkah-langkah yang legalPosisi papan yang merepresentasikan pemenang dari satu sisi atau sisi lainnya.Tujuan (Goal) dari permainan adalah : memenangkan permainan.

Problem Solving AgentGoal-based agent mempertimbangkan action-action yang akan datang dan hasil yang ingin dicapaiAgent Problem Solving Menemukan sequence action untuk mencapai tujuannyaAlgorithm are uninformed Tidak ada informasi untuk Problem, hanya deskripsi pada masalah tersebut

Simple Problem Solving AgentFunction Simple-Problem-Solving-Agent(percept) return an actionInput : percept //a perceptStatic : seq //an action sequence, initially emptystate //some description of the current world stategoal //a goal, initially nullproblem //a problem formulation

State Update-State(state, percept)If seq is empty then dogoal Formulate-Goal(state)problem Formulate-Problem(state,goal)seq Search(Problem)

Action First(seq)Seq Rest(seq)Return action

Goal & Problem FormulationGoal FormulationKondisi saat iniPerformance measureProblem FormulationProses Menemukan state dan aksi-aksi yang akan dilakukan untuk mencapai tujuannyaSearch input problem, output solusi dalam bentuk sequence action

Well-Define Problem & Solution4 Komponen ProblemInitial StateActions : Successor function : Successor-Fn(x) = Goal TestPath CostOptimal Solution path cost terkecil

Contoh KasusAgent kita sedang berlibur dan sekarang sedang di kota Arad RomaniaBesok dia harus naik pesawat dari BucharestGoal dari agent sekarang adalah pergi ke BucharestAction yang tidak berhubungan dengan goal akan dibuang -> decision agent lebih simple

Contoh KasusAgent Mencapai tujuan (ke Bucharest) dengan naik mobilKemana akan pergi setelah dari Arad ?Ada tiga jalan : ke Sibiu, Timisoara, ZerindAgent kita ini masih belum tahu jalan disana (mana yang tercepat) tapi hanya memiliki peta.Dari informasi peta, dilakukan hipotesa terhadap ketiga jalur tsb untuk sampai ke Bucharest

Agent & EnvironmetEnvironmentStaticTidak perlu memperhatikan perubahan yang terjadi pada environmentObservable Ada peta, initial state diketahui (di Arad) DiscreetEnumeration actionDeterministicTidak bisa menangani terhadap hal-hal yang tidak diperkirakan

Well-Defined Problem agentInitial State di AradActions : Successor function {, , }Goal Test In(Bucharest)Path Cost di slide berikutnya

Path Cost Solusi Agent

Formulate Goal & Problem AgentFormulate GoalTiba di Bucharest besokFormulate ProblemStates : kota-kotaActions : mengemudi antar kotaSolusiSequence kota : Arad, Sibiu, Fagaras, Bucharest

Example ProblemToy ProblemDiharapkan bisa mengilustrasikan berbagai macam metode problem-solving Membandingkan performa algoritmaAkan dibahas untuk kasus : vacum cleaner, 8-puzle, 8-Queen ProblemReald World ProblemAirline Travel ProblemTouring ProblemTraveling Salesman ProblemVLSI LayoutRobot NavigationAutomatic Assembly SequencingInternet Searching

Toy ProblemVacuum CleanerStates : Berada di salah satu dari dua lokasi yang ada, yg masing2 mungkin bersih atau kotor. Jadi jml kemungkinan state = 2 * 22Initial State ?Successor Function ? .Goal Test ?Path Cost ?

Toy ProblemVacuum CleanerStates : Berada di salah satu dari dua lokasi yang ada, yg masing2 mungkin bersih atau kotor. Jadi jml kemungkinan state = 2 * 22Initial State : Sembarang stateSuccessor Function : (kekiri,kekanan,bersihkan)Goal Test : Semua lokasi bersihPath Cost : Setiap aksi = 1 point

Toy ProblemThe 8-PuzzlesState : ?Initial State : ?Successor Function : ? .Goal Test : ?Path Cost : ?

Toy ProblemThe 8-PuzzlesState : lokasi dari 8 kotak angka dan 1 kotak kosongInitial State : Sembarang stateSuccessor Function : (kotak kosong bergerak kekiri, kekanan, keatas atau kebawah)Goal Test : Tersusun kotak angka yang diinginkanPath Cost : Setiap bergerak bernilai 1

Toy Problem8-Queen ProblemState : ? .Initial State : ? .Successor Function : ? .Goal Test : ? .

Toy Problem8-Queen ProblemState : susunan 0..8 ratu pada papan caturInitial State : Tidak ada ratu pada papan caturSuccessor Function : Masukkan ratu ke papan caturGoal Test : Tidak ada ratu yang saling serang

A Water Jug ProblemAnda diberi dua buah jug, yang satu ukuran 4 galon dan yang lain 3 galon. Kedua jug tidak memiliki skala ukuran. Terdapat pompa yang dapat digunakan untuk mengisi jug dengan air. Bagaimana anda mendapatkan tepat 2 galon air di dalam jug 4 ukuran galon?

Pendefinisian masalahRuang masalah untuk masalah di atas dapat digambarkan sebagai himpunan pasangan bilangan bulat (x,y) yang terurut, sedemikian hingga x = 0, 1, 2, 3, atau 4 dan y = 0, 1, 2, atau 3; x menyatakan jumlah air dalam jug ukuran 4 galon, dan y menyatakan jumlah air dalam jug ukuran 3 galon. Keadaan mula-mula adalah (0,0). State tujuan adalah (2,n) untuk setiap nilai n.

Operator-opeartor (aturan produksi) yang digunakan untuk memecahkan masalah terlihat pada tabel

1.(x,y)If x < 4(4,y)Isi penuh jug 4 galon

2.(x,y) If y < 3(x,3)Isi penuh jug 3 galon

3.(x,y)If x > 0(x-d,y)Buang sebagian air dari jug 4 galon

4.(x,y)If y > 0(x,y-d)Buang sebagian air dari galon ukuran 3 galon

5.(x,y)If x > 0(0,y)Kosongkan jug 4 galon

6.(x,y)If y > 0(x,0)Kosongkan jug 3 galon

7.(x,y) If x+y 4 and y > 0(4,y-(4-x))Tuangkan air dari jug 3 galon ke jug 4 galon sampai jug 4 galon penuh8. (x,y) If x+y 3 and x > 0(x-(3-y),3)Tuangkan air dari jug 4 galon ke jug 3 galon sampai jug 3 galon penuh

9.(x,y) If x+y 4 and y > 0(x+y,0)Tuangkan seluruh air dari jug 3 galon ke jug 4 galon

10.(x,y)If x+y 3 and x > 0(0,x+y)Tuangkan seluruh air dari jug 4 galon ke jug 3 galon11.(0,2)(2,0)Tuangkan 2 galon air dari jug 3 galon ke jug 4 galon12.(2,y)(0,y)Buang 2 galon dalam jug 4 galon sampai habis.

Solusi untuk Water Jug Problem

Jumlah galondalam jug 4 galon Jumlah galon dalam jug 3galon Aturan yangdilakukan 0 0 0 3 2 3 0 9 3 3 2 4 2 7 0 2 5 atau 12 2 0 9 atau 11

Real World ProblemAirline Travel ProblemTouring ProblemTraveling Salesman ProblemVLSI LayoutRobot NavigationAutomatic Assembly SequencingInternet Searching

Karakteristik Masalah Dalam AI : Apakah masalahnya dapat didekomposisi menjadi himpunan sub masalah yang (hampir) independen lebih kecil atau lebih mudah ?Dapatkah langkah penyelesaian diabaikan paling tidak dibatalkan ketika dapat dibuktikan hal tersebut kurang tepat ?Apakah universe masalah dapat diprediksi ?Apakah solusi terbaik dari masalah tertentu jelas, tanpa membandingkan dengan kemungkinan seluruh solusi yang lain?Apakah solusi yang diinginkan sebuah keadaaan atau sebuah jalur dari keadaan ?Apa peran dari pengetahuan ?

Sistem Produksi

Sistem produksi terdiri dari:Himpunan aturan, masing-masing terdiri dari sisi kiri (pola) yang menentukan kemampuan aplikasi dari aturan tersebut dan sisi kanan yang menggambarkan operasi yang dilakukan jika aturan dilaksanakan.Satu atau lebih pengetahuan atau basis data yang berisi informasi apapun untuk tugas tertentu. Beberapa bagian basis data bisa permanen, dan bagian yang lain bisa hanya merupakan solusi untuk masalah saat ini. Informasi dalam basis data ini disusun secara tepat.Strategi kontrol yang menspesifikasikan urutan dimana aturan akan dibandingkan dengan basis data dan menspesifikasikan cara pemecahan masalah yang timbul ketika beberapa aturan sesuai sekaligus pada waktu yang sama.A rule applier (pengaplikasi aturan).

Strategi Kontrol

Syarat-syarat strategi kontrol:cause motion. Perhatikan kembali water jug problem. Jika kita mengimplementasikan strategi kontrol sederhana dengan selalu memilih aturan pertama pada daftar 12 aturan yang telah dibuat, maka kita tidak akan pernah memecahkan masalah. Strategi kontrol yang tidak menyebabkan motion tidak akan pernah mencapai solusi.Systematic. Strategi kontrol sederhana yang lain untuk water jug problem: pada setiap siklus, pilih secara random aturan-aturan yang dapat diaplikasikan. Strategi ini lebih baik dari yang pertama, karena menyebabkan motion. Pada akhirnya strategi tersebut akan mencapai solusi. Tetapi mungkin kita akan mengunjungi beberapa state yang sama selama proses tersebut dan mungkin menggunakan lebih banyak langkah dari jumlah langkah yang diperlukan. Hal ini disebabkan strategi kontrol tersebut tidak sistematik.

Beberapa strategi kontrol yang sistematik telah diusulkan, yang biasa disebut sebagai metoda-metoda dalam teknik searching

Lebih lanjut akan dibahas enam metoda pencarian: Breadth First Search, Uniform Cost Search, Depth First Search, Depth-Limited Search, Iterative-Deepening Depth-First Search, dan Bi-directional search.

Strategi Pencarian

Terdapat empat kriteria dalam strategi pencarian, yaitu:Completeness: Apakah strategi tersebut menjamin penemuan solusi jika solusinya memang ada?Time complexity: Berapa lama waktu yang diperlukan?Space complexity: Berapa banyak memori yang diperlukan?Optimality: Apakah strategi tersebut menemukan solusi yang paling baik jika terdapat beberapa solusi berbeda pada permasalahan yang ada?

Thanks u

TugasSelesaikan masalah dengan AI: takaran minyak tanah hanya untuk 5 liter dan 7 liter. Definisikan masalah dan selesaikan untuk mendapatkan minyak tanah sebanyak 4 liter.Tugas dalam file .doc dan .pdf , laporanKelompok maks 5 orangDikumpulkan maks rabu depan (file) email ke popi_aprilia@yahoo.comLaporan dikumpulkan sabtu depan tanggal 9 oktober 2010

*********************