Tugas 5 AI No 2 - POP ( Partial Order Planning) & Graph Plan

Graph Plan

Hello …

Yuk kita bahas kelanjutan dari postingan sebelumnya untuk memenuhi Tugas 5 No 2 Pada Mata kuliah AI dengan pembahasan Graph  plan.

Sebelumnya, Kalian sudah tau apa itu Graph Plan ???

Graphplan adalah algoritma untuk perencanaan otomatis yang dikembangkan oleh Avrim Blum dan Merrick Furst pada tahun 1995. Graphplan mengambilInput masalah perencanaan yang dinyatakan dalam strip dan mengerjakan, jika salah satu memungkinkan, urutan operasi untuk mencapai keadaan tujuan.

  

Didalam GraphPlan terdapat constrain yang dinamakan Mutually Exclusive Action atau Mutex. Mutex dapat dikatakan Jika dua tindakan tidak dapat dikerjakan secara paralel kita dapat mengatakan bahwa mereka mutually exclusive atau mutex. Hubungan mutex akan bervariasi dari lapisan ke lapisan, jadi kita akan melihat pertanyaan mengenai kapan dua tindakan yang mutex di tingkat i. Hal ini dapat menjadi kenyataan dalam tiga kondisi yang memungkinkan. 

Selain itu terdapat juga mutex yang lain seperti berikut

Berikut ini Contoh penggunaan Graph Plan Yang akan saya Bahas : Birthday Dinner Example

Berikut adalah initial state, goal state, dan aksi aksi yang dapat kita lakukan

Baiklah kita buat GraphPlan nya. Pertama kita letakkan initial state nya.

Lalu kita masukkan aksi yang dapat kita lakukan dan hubungkan denganinitial state.

Setelah itu kita masukkan hasil dari setiap aksi yang bisa kita lakukan.

Oke kita telah membuat dasar dalam GraphPlan. Selanjutnya kita akan membuat Mutex dari GraphPlan ini. Alasan pertama bahwa tindakan dapat mutex adalah karena efek yang tidak konsisten. Jadi, clean mutex dengan carry karena carry membuat clean menjadi salah. Begitu pula dengan garbage mutex dengan carry dan dolly karena carry dan dolly membuat garbage salah. Quite juga mendapatkan efek yang sama dengan dolly karena dolly membuat quite menjadi salah.

Alasan lain Mutex dapat terjadi karena adanya gangguan : suatu aksi meniadakan prekondisi dari aksi yang lain. Carry Mutex dengan cook karena hasil dari carry meniadakan prekondisi dari cook. Dolly mutex wrap karena hasil dari dolly meniadakan prekondisi dari wrap. Selanjtnya carry dan dolly mutex karena mereka saling meniadakan prekondisi mereka.

Kemudian, setiap preposisi mutex dengan negasi nya. Lalu, alasan lain kita mungkin memiliki mutex adalah karena dukungan tidak konsisten. Jadi, garbage mutex dengan not clean dan note quite karena untuk mendapatkan garbage kita harus membiarkan nya dan ini mutex dengan carry dan dolly. Dinner mutex dengan not celan karena cook dan carry mutex pada level sebelumnya. Present mutex dengan not quite karena warp dan dolly mutex pada level sebelumnya. Begitupula dengan not clean dan not quite karena carry dan dolly mutex pada level sebelumnya. Itulah mutex yang bisa kita dapatkan

Kita mulai untuk mendapatkan goals yang kita butuhkan. Pertama kita akan mendapatkan not garbage, kita menggunakan aksi carry, lalu kita mencoba mendapatkan dinner dengan aksi cook satu satunya aksi untuk mendapatkan dinner. Tetapi cook dan carry adalah mutex jadi kita tidak dapat menggunakan aksi tersebut.

Kita coba menggunakan cara lain. Kita akan mendapatkan not garbage dengan aksi dolly, lalu kita dapat mendapatkan dinner menggunakan cook, tetapi kita tidak dapat mendapatkan present dengan satu satu nya cara mendapatkan present yaitu warp, karena warp dengan dolly merupakan mutex.

Kita tidak bisa mendapatkan goal dengan cara ini. Untuk itu kita menggunakan depth two plan. Yaitu dengan menambahkan dua level lagi pada graph.

Pada aksi ini kita mendapatkan mutex sama seperti level sebelumnya.

Pada level selanjutnya kita juga mendapatkan mutex seperti pada level sebelumnya. Tetapi ada sedikit perbedaan mutex disini dengan di level sebelumnya. Pada level ini dinner tidak mutex dengan carry karena kita bisa mendapatkan dinner dengan membiarkan nya dan tetap bisa melakukan carry. Begitupun dengan present tidak mutex dengan dolly karena kita bisa mendapatkan present dengan membiarkan nya dan dapat tetap melakukan dolly.

 Setelah kita selesai dengan mutex kita coba mencari lagi apa yang kita butuhkan dan akhirnya kita berhasil dengan melakukan cara nya sebagai berikut.

Referensi:

1.                  http://dantikpuspita.com/konsep-dan-pengertian-dasar-graph-graf/

2.                  https://en.wikipedia.org/wiki/Graphplan  

3.                  http://whitenote03.blogspot.co.id/2016/10/penyelesaian-masalah-menggunakan.html

4.                  https://ocw.mit.edu/...and.../Lecture12FinalPart1.pdf

Tugas 5 AI No 1 - POP ( Partial Order Planning) & Graph Plan

POP ( Partial Order Planning) & Graph Plan

Hallo ….

Kembali lagi dengan saya :D Pembahasan kali ini saya akan membahas tentang  penyelesaian suatu contoh pada kasus Planning dengan menggunakan Partial Order Planning dan Graph Plan.

Perlu di ingat postingan ini untuk memenuhi Tugas 5 No 1 dan No 2 pada Mata Kuliah Pengantar Kecerdasan Tiruan (AI) pada universitas Muhammadiyah Prof.DR.Hamka, Fakultas Teknik. Prodi Teknik Informatika yang diampu oleh Mia Kamayani ST, MT.

Sebelumnya apa kalian sudah tau apa itu planning ?

Planning itu adalah suatu metode penyelesaian masalah dengan cara memecah masalah ke dalam sub-sub masalah yang lebih kecil, menyelesaikan sub-sub masalah satu demi satu, kemudian menggabungkan solusi-solusi dari sub-sub masalah tersebut menjadi sebuah solusi lengkap dengan tetap mengingat dan menangani interaksi yang ada antar sub masalah.  Dan Berikut ini adalah contoh dari permasalahan yang akan kita bahas dan berikut solusi jawabannya..

1. Shopping (POP)

Langkah awal:

Tahap selanjutnya menambahkan go(HDW) sebagai (X1) untuk mencapai untuk mencapai at(HDW) dan menambahkan go(SM) sebagai (X₂) untuk mencapai at(SM).

Langkah selanjutnya kita bisa menjalankan langkah actian go(X₁) dan precond Go(HDW), dengan menggunakan effect at(Home). Serta menjalankan langkah action go(X₂) dan precond Go(SM), dengan menggunkan effect at(Home) seperti gambar diatas.

Setelah selesai dengan langkah sebelumnya, kita harus memperhatikan masalah apa saja yang mungkin terjadi yang bisa kita lihat pada gambar diatas. Pada gambar diatas, masalah terjadi dapat kita lihat pada bulatan yang ditunjuk oleh tanda panah, kita dapat memperhatikan bahwa Go(SM) tidak bisa tersambung ke at(Home) sebagai akibat sudah dimiliki oleh at(X₁), dan juga berlaku sebaliknya untuk Go(HDW).

Solusi yang dapat kita ambil, mungkin kita bisa memerlukan Go(SM) terjadi setelah Go(HDW). Kita bisa memutuskan untuk memenuhi at(X₂) dengan hasil at(HDW) Go(HDW) dan at(HDW) Go(HDW), tetapi jika kita menuju at(HDW) Go(HDW) kita tidak bisa menuju at(HDW) Sells(HDW,D).

Solusi yang dapat kita ambil dengan menempatkan Go(SM) antara GO(HDW) dan at(HDW) yang ditunjukan oleh tanda panah pada gambar diatas. Tetapi jika seperti itu kita harus menuju dua kali ke Go(HDW) karena sehabis ke Go(HDW) kita menuju Go(SM) dan balik lagi ke Go(HDW) untuk Buy(Drill).

Solusi yang dapat diambil dengan meletakan Go(SM) terjadi setelah Buy(Drill). Dengan menandakan nya dengan garis putus putus berwarna merah untuk memastikan bahwa hal ini terjadi.

Setelah kita berada di GO(SM) kita bisa Buy(Milk) dan Buy(Bananas) dan terakhir menuju at(Home).

Sekian penjelasan permasalahan yang dapat saya jelaskan. Sebenarnya banyak pilihan yang dapat dilakukan untuk membuat POP ini diantara nya kita melakukan Go(SM) dahulu untuk melakukan Buy(B) dan Buy(M). Lalu setelah itu melakukan aksi Go(HDW) pada aksi Go(SM). Ya semacam itulah, ini hanya salah satu contoh yang dapat saya jelakan/bagikan kepada anda.

Referensi:

1.                  http://dantikpuspita.com/konsep-dan-pengertian-dasar-graph-graf/

2.                  https://en.wikipedia.org/wiki/Graphplan  

3.                  http://whitenote03.blogspot.co.id/2016/10/penyelesaian-masalah-menggunakan.html

4.                  https://ocw.mit.edu/...and.../Lecture12FinalPart1.pdf

CONSTRAINT SATISFACTION PROBLEM (CSP) Tugas 4 AI

HALLO …

Assalamualaikum …

Kembali lagi dengan blog saya ini :d. kali ini saya akan memposting Tugas 4 AI dengan Bahasan yaitu CSP (CONSTRAINT SATISFACTION PROBLEM). Yuk langsung saja di cek guys postingannya, Kita berbagi-bagi ilmu :d . Perlu di ingat postingan ini untuk memenuhi Tugas 4 pada Mata Kuliah Pengantar Kecerdasan Tiruan (AI) pada universitas Muhammadiyah Prof.DR.Hamka.

CONSTRAINT SATISFACTION PROBLEM..

 

apa sih CSP itu? Constraint Satisfaction Problem merupakan sebuah pendekatan untuk menyelesaikan suatu masalah dengan tujuan menemukan keadaan atau objek yang memenuhi sejumlah persyaratan atau kriteria.

Constraint Satisfaction Problem juga adalah suatu permasalahan seseorang harus mencari nilai untuk set variabel (finite) yang memenuhi set constraint (finite). Komponen-komponen yang terdapat pada Constraint Satisfaction Problem adalah Variabel yang merupakan penampung dapat diisi berbagai nilai, Constraint yang merupakan suatu aturan yang ditentukan untuk mengatur nilai boleh diisikan ke variabel, atau kombinasi variable, Domain yang merupakan kumpulan nilai legal dapat diisi ke variable, Solusi yang merupakan assignment nilai-nilai dari domain ke setiap variabel tidak ada constraint yang dilanggar. Serta Assignment & Solusi.

Komponen-komponen yang ada di CSP: 

1.      Set Variabel
Merupakan sesuatu yang memiliki nilai bervariasi, kemudian dapat juga didefiniskan sebagai hal yang berbeda beda dalam bahasa pemprograman yang diwakili oleh simbol untuk variasi nilai tertentu.

2.      Set Domain
Merupakan kumpulan nilai legal yang dapat diisi ke variabel. 

3.      Set Constraint/Batasan
Menspesifikan kombinasi nilai yang diperbolehkan.

4.      Assignment >>> pemberian nilai pada suatu variabel.

5.      Solusi >>> pemberian nilai-nilai pada setiap variabel yang memenuhi semua constraint yang  telah ditetapkan untuk persoalan, sehingga nilainilai variabel tersebut merupakan solusi untuk persoalan.

Contoh permasalahan CSP yang akan saya bahas ini adalah Timetabling yang mengenai PENJADWALAN MATAKULIAH DENGAN MENGGUNAKAN ALGORITMA GENETIKA DAN METODE CONSTRAINT SATISFACTION

Mengingat masalah penjadwalan perkuliahan di Perguruan Tinggi merupakan masalah NPhard secara komputasi. Pada penelitian ini metode Algoritma Genetika dipadukan dengan metode Constraint Satisfaction Problem, dengan kromosom yang dihasilkan metode Algoritma Genetika diproses dengan metode Constraint Satisfaction Problem. Dengan cara ini dapat batasan-batasan pada penjadwalan yang harus dipenuhi dapat dijamin tidak terlanggar. Hal ini akan membuat proses heuristic pada Algoritma Genetika menjadi terarah dan membuat keseluruhan proses menjadi lebih efisien.

Permasalahan penjadwalan pengajaran klasik didefinisikan sebagai berikut

[1]: Terdapat sejumlah mkelas c1, ..., cm, n guru t1, ..., tn, dan p periode 1, ..., p. Terdapat pula matriks integer non negative Rm_n, yang disebut matriks requirements, dengan rij adalah jumlah pelajaran yang diberikan oleh guru tj pada kelas ci. Permasalahan penjadwalan adalah mengalokasikan kelas pada periode sedemikian sehingga tidak ada pengajar dan kelas yang dijadwalkan terjadi pada satu pelajaran pada saat yang sama.

Definisi klasik ini belum dapat memenuhi kebutuhan penjadwalan perkuliahan di Perguruan Tinggi seperti:

·         Seorang dosen terkadang hanya dapat mengajar pada jam-jam dan hari-hari tertentu.

·         Setiap mata kuliah yang diajarkan memiliki alokasi semester sehingga perlu pengaturan agar penjadwalan matakuliah pada semester yang sama tidak bersamaan dan mahasiswa pada semester tersebut dapat mengikuti semua matakuliah yang dialokasikan kepadanya.

·         Dalam satu hari seorang dosen seharusnya maksimal mengajar dua kelas. Masalah penjadwalan perkuliahan di Perguruan Tinggi merupakan masalah NP-hard secara komputasi, sehingga sejumlah penelitian  menerapkan metode heuristic untuk melakukan otomasi terhadap masalah penjadwalan. Masalah penjadwalan perkuliahan berbeda dari satu universitas ke universitas, bahkan dari satu jurusan ke jurusan lain pada universitas yang sama.

Faktor-faktor yang berpengaruh dalam pembentukan jadwal meliputi:

1. Dosen

Seorang dosen tidak dapat mengajar beberapa mata kuliah pada jam yang sama. Selain itu, seorang dosen terkadang hanya dapat mengajar pada jam-jam dan hari-hari tertentu saja, sehingga perlu untuk memesan jadwal khusus yang tidak dapat diganggu mata kuliah yang lain.

2. Ruang

Mengingat jumlah ruang yang dimiliki terbatas, maka perlu diperhatikan ruang yang tersedia agar tidak menggangu jalannya perkuliahan. Jadwal harus hanya mengakomodasi ruang yang ada.

3. Waktu

Waktu merupakan batasan berapa menit yang diperlukan untuk satu jam kuliah. Selain itu, ada hari-hari yang jam kuliah dibatasi sampai dengan jam tertentu (misalnya jam kuliah hari Jumat dibatasi mulai jam 07.30 sampai jam 11.00 dan dimulai kembali jam 13.00). Dengan batasan-batasan waktu ini, jadwal hanya akan berada pada waktu yang ditentukan.

4. Matakuliah

Mengingat setiap matakuliah memiliki semester mata kuliah itu diajarkan, maka perlu adanya aturan yang membatasi penjadwalan matakuliah, agar mata-kuliah itu sesuai dengan aturan-aturan penjadwalan. Aturan-aturan yang harus diperhatikan dalam membuat jadwal meliputi:

_ Tidak boleh ada satu ruang yang diisi dua kali dalam satu waktu yang sama.

_ Tidak boleh ada Nomor Induk Pegawai (NIP) dosen yang sama pada hari dan jam yang sama.

_ Kemunculan matakuliah pada semester yang sama dibatasi maksimal dua kali pada satu hari.

_ Pada masing-masing semester, mahasiswa harus dapat mengambil matakuliah sesuai dengan kurikulum yang ditentukan jurusan sehingga jika mahasiswa mengambil matakuliah sesuai kurikulum tidak ada matakuliah yang tidak bisa diambil karena jadwal yang bersamaan dengan jadwal matakuliah lain pada semester yang sama.

_ Matakuliah dengan kode matakuliah yang sama (kelas paralel) harus ada pada hari yang sama, kecuali jika dosennya sama.

_ Jarak matakuliah antarsemester dengan semester berikutnya pada jam yang sama harus lebih besar dari jarak yang ditetapkan pengguna. Ini berguna untuk memberikan keleluasaan mahasiswa mengambil matakuliah yang tidak berada pada semester mahasiswa tersebut, misalnya kasus mahasiswa mengulang suatu matakuliah atau mahasiswa yang memiliki Indeks Prestasi tinggi mengambil suatu matakuliah lain di semester lebih tinggi.

_ Dalam satu hari, dosen mengajar maksimal dua kelas.

Metode Algoritma Genetika :

Gambar 1 : Flowchart Proses Algoritma Genetika

Hal-hal yang dilakukan pada proses inisialisasi Algoritma Genetika adalah:

1. Menginisialisasi tabel hasil dengan menghapus data yang lama dan mengisikan data default.

2. Mendata setting paramater Algoritma Genetika dari database.

3. Mendata matakuliah yang ditawarkan dan matakuliah dari database sebagai data kromosom.

4. Membentuk kromosom sebagai populasi awal.

5. Memproses preprocessing untuk memperkirakan apakah jadwal dapat dibuat. Proses ini melakukan penghitungan jumlah data yang dibutuhkan untuk membuat jadwal dan membandingkannya dengan jumlah domain yang tersedia. Jika domain tersebut mencukupi, proses pembuatan jadwal dapat dilanjutkan; sedangkan jika domain tidak mencukupi, jadwal dianggap tidak dapat dibuat dan proses dibatalkan.

Model Algoritma Genetika yang akan digunakan untuk melakukan optimasi adalah sebagai berikut:

1. Seleksi.

Pada seleksi, dilakukan penilaian atas nilai fitness. Akibatnya, fitness yang memiliki kualitas kromosom paling baik memiliki kemungkinan terpilih ke dalam generasi selanjutnya lebih besar. Seleksi yang dipakai di sini adalah seleksi yang menggunakan metode roulette wheel. Pada seleksi ini perlu diperhatikan jumlah maksimal populasi sebagai input, agar populasi tidak menjadi terlalu besar dan memakan banyak waktu, dan populasi juga tidak menjadi terlalu kecil dan mengakibatkan kromosom terlalu mirip sehingga operasi kromosom tidak akan banyak berpengaruh.

2. Crossover.

Crossover yang digunakan adalah penyilangan dua titik dengan permutasi. Pemilihan kromosom yang akan di-crossover-kan ditentukan oleh probabilitas yang ditentukan dalam setting parameter Algoritma Genetika. Banyak gen yang ditukar juga mengikuti setting parameter Algoritma Genetika. Dalam melakukan penyilangan, setiap dua kromosom akan menghasilkan dua offspring baru hasil penyilangan.

3. Mutasi.

Mutasi dilakukan setelah operasi kromosom ini dilakukan dengan menukar gen secara random. Dalam proses ini perlu diperhatikan tingkat mutasi dan tingkat probabilitas terjadi mutasi. Jika sering terjadi mutasi, antar generasi selanjutnya akan kehilangan kemiripan dan pencarian akan menjadi acak. Tetapi, jika mutasi terlalu sedikit, kromosom akan menjadi terlalu mirip dan kromosom baru akan muncul terlalu lama pada populasi.

4. Penentuan Fitness.

Penentuan fitness pada dasarnya adalah pemberian nilai kuantitatif yang mewakili kualitas dari kromosom. Hal pertama yang dilakukan proses ini adalah proses Pembuatan Jadwal sesuai kromosom yang dipilih dengan memprosesnya dengan Constraint Satisfaction Problem, dan hasilnya akan diberi nilai fitness.Fungsi fitness yang dibuat merupakan rata-rata waktu tunggu antarkuliah mahasiswa dalam satu minggu sehingga semakin kecil waktu tunggu maka akan semakin baik (waktu tunggu antar kuliah mahasiswa menjadi minimal).

Metode CSP

Gambar 2 : Flowchart Pembuatan Jadwal dengan menggunakan CSP

Data pesan jadwal yang sudah dibuat. Setelah data pesan jadwal valid maka dilakukan pembuatan jadwal menggunakan CSP. Gambar 2 menunjukkan flowchart pembuatan jadwal dengan menggunakan CSP yang dilakukan. Proses yang terjadi dalam pembuatan jadwal pada Gambar 2 dapat diuraikan sebagai berikut:

1.      Menginisialisasi, yaitu persiapan data yang dibutuhkan oleh Constraint Satisfaction.

2.      Memilih variabel yang ingin diisikan, jika melakukan pemilihan dengan menggunakan MRV maka diambil variabel yang memiliki domain paling sedikit, jika tidak menggunakan MRV akan diambil secara berurutan sesuai urutan pada variabel.

3.      Memilih nilai yang masih valid dari domain untuk variabel yang dipilih.

4.      Meng-assignment variabel dan domain ke dalam solusi, kemudian mengurangi domain valid dari setiap variabel berdasarkan constraint yang dimiliki variable yang di-assign.

5.      Jika solusi sudah terbentuk, dilanjutkan ke langkah

6.      Jika solusi belum ditemukan kembali ke langkah 2.

7.      Jika setiap variabel sudah terisi, solusi sudah terbentuk, kemudian CSP akan memberikan hasilnya kembali ke Algoritma Genetika untuk dievaluasi.

Model Constraint Satisfaction yang digunakan untuk menyelesaikan masalah penjadwalan adalah sebagai berikut:

1. Penelusuran dengan Backtracking (BT).

Algoritma backtracking menggunakan Constructive methods, yang berarti mengembangkan solusi partial sedikit demi sedikit dengan tetap menjaga consistency, sehingga mencapai consistent complete assignment.

2. Forward Checking (FC).

Forward checking berkerja dengan membuat suatu tabel yang menyatakan nilai domain yang masih tersedia untuk setiap variabel. Kemudian pada tabel ini dihilangkan domain yang sudah tidak boleh diambil lagi.

3. Minimum Remaining Value (MRV).

Minimum remaining value dapat bekerja bersamaan dengan FC dengan memilihkan variabel yang diisikan. Variabel yang dipilih adalah variabel yang memiliki domain paling sedikit. Pertimbangan yang digunakan adalah variabel yang jumlah domain-nya paling sedikit mempunyai kesempatan gagal lebih besar. Hal ini dapat memotong percabangan tree yang tidak perlu dan mempercepat waktu pembuatan jadwal.

Referensi :

1.      Werra, D.D.: An Introduction to Timetabling. European Journal of Operational Research 19(2) (1985) 151–162

2.      Arntzen, H., Løkketangen, A.: A Local Search Heuristic for a University Timetabling Problem. Technical report, Dalle Molle Institute for Artificial Intelligence (2007) Diakses 31 August 2007, http://www.idsia.ch/Files/ttcomp2002/arntzen.pdf.

3.      Chiarandini, M., Birattari, M., Socha, K., Rossi- Doria, O.: An Effective Hybrid Algorithm for University Course Timetabling. Journal of Scheduling 9(5) (2006) 403–432

4.      http://web.csulb.edu/~obenli/DSS/node7.html