Materi tentang Constraint Satisfaction Problem (CSP) dalam Kecerdasan Buatan (AI) (+ Video Materi)

Assalamu‘alaikum wr. wb.

Halo gais! Sebelumnya, kita telah membahas tentang Algoritma Uninformed dan Informed Search. Sekarang, kita akan membahas tentang Constraint Satisfaction Problem (CS) dalam Kecerdasan Buatan atau Artificial Intelligence.

Constraint Satisfaction Problem (CSP) dalam Kecerdasan Buatan (AI)

MATERI

Sumber Materi : Baeldung.com, Tutorialandexample.com, Javatpoint.com, dan Allfish24.wordpress.com

Kami telah menemukan berbagai macam metode, termasuk pencarian musuh dan pencarian instan, untuk mengatasi berbagai masalah. Setiap metode untuk masalah memiliki satu tujuan: untuk menemukan solusi yang akan memungkinkan pencapaian tujuan tersebut. Namun tidak ada batasan hanya pada kemampuan bot untuk menyelesaikan masalah serta sampai pada tanggapan masing-masing dalam pencarian permusuhan dan pencarian lokal.

Bagian ini membahas Metodologi Optimisasi Kendala (Constraint Optimization Methodology), bentuk lain atau metode perhatian nyata. Dengan namanya, pemenuhan batasan menyiratkan bahwa masalah seperti itu harus diselesaikan sambil mematuhi serangkaian batasan atau pedoman.

Setiap kali masalah sebenarnya variabel sesuai dengan kondisi prinsip yang ketat, dikatakan telah ditangani dengan menggunakan metode pemecahan multi-objektif. Wow, metode apa yang dihasilkan dalam sebuah penelitian yang ingin dicapai dari kerumitan dan pengorganisasian kedua masalah tersebut.

A. Pengertian Constraint Satisfaction Problem (CSP)

Constraint Satisfaction Problem (CSP) adalah sebuah proses menemukan solusi untuk satu set masalah, dimana suatu state (keadaan) harus memenuhi persyaratan atau kriteria tertentu. CSP merupakan permasalahan yang tujuannya untuk mendapatkan kombinasi variabel tertentu yang memenuhi beberapa aturan.

Terdapat 3 (Tiga) Komponen dalam CSP yaitu :

• Variabel : merupakan penampung yang dapat diisi berbagai nilai
• Domain : merupakan kumpulan nilai legal yang dapat diisikan ke variabel
• Constraint/Batasan : merupakan suatu aturan yang ditentukan untuk mengatur nilai yang boleh diisikan ke variabel

Juga, 3 (Tiga) Faktor yang mempengaruhi kepatuhan pembatasan, terutama terkait :

• Ini mengacu pada sekelompok parameter, atau X.
• D: Variabel terkandung dalam kumpulan beberapa domain. Setiap variabel memiliki ruang lingkup yang berbeda.
• C: Ini adalah serangkaian batasan yang harus dipatuhi oleh kumpulan parameter.

Dalam Kepuasan Kendala (Constraint Satisfaction), domain adalah area di mana parameter ditempatkan setelah pembatasan yang khusus untuk tugas tersebut. Ketiga komponen tersebut membentuk teknik kepuasan kendala secara keseluruhan. Pasangan "scope, rel" membentuk angka seperti persyaratan. Cakupannya adalah tupel variabel yang berkontribusi pada batasan, serta rel memang merupakan hubungan yang berisi daftar solusi yang mungkin untuk parameter yang harus diasumsikan untuk memenuhi batasan dari sesuatu seperti masalah tersebut.

B. Jenis-jenis Constraint Satisfaction Problem (CSP)

1. Jenis Domain dalam CSP

Ada dua jenis domain berikut yang digunakan oleh variabel :

• Domain Diskrit : Ini adalah domain tak terbatas yang dapat memiliki satu status untuk banyak variabel. Misalnya, status awal dapat dialokasikan dalam waktu tak terbatas untuk setiap variabel.
• Domain Hingga : Ini adalah domain terbatas yang dapat memiliki keadaan kontinu yang menggambarkan satu domain untuk satu variabel tertentu. Ini juga disebut domain kontinu.

2. Constraint Types dalam CSP

Jenis Kendala (Constraint) di CSP, pada dasarnya ada jenis kendala berikut :

• Constraint Unary : Ini adalah jenis kendala paling sederhana yang membatasi nilai variabel tunggal.
• Constraint Biner : Ini adalah jenis kendala yang menghubungkan dua variabel. Nilai x₂ akan berisi nilai yang terletak di antara x₁ dan x₃.
• Constraint Global : Ini adalah jenis kendala yang melibatkan sejumlah variabel yang berubah-ubah.

Beberapa jenis algoritma solusi khusus digunakan untuk menyelesaikan jenis kendala berikut :

• Kendala Linier (Linear Constraint) : Jenis kendala ini biasanya digunakan dalam pemrograman linier di mana setiap variabel yang berisi nilai bilangan bulat hanya ada dalam bentuk linier.
• Kendala Non-Linier (Non-Linear Constraint) : Jenis kendala ini digunakan dalam pemrograman non-linier di mana setiap variabel (nilai bilangan bulat) ada dalam bentuk non-linier.

Catatan : Batasan khusus yang berfungsi di dunia nyata dikenal sebagai batasan Preferensi.

3. Propagasi Kendala (Constraint Propagation)

Di ruang negara lokal, pilihannya hanya satu, yaitu mencari solusi. Namun di CSP, memiliki dua pilihan :

• Kita dapat mencari solusi atau
• Kita dapat melakukan jenis inferensi khusus yang disebut propagasi kendala.

Constraint Propagation adalah jenis inferensi khusus yang membantu mengurangi jumlah nilai yang sah untuk variabel. Gagasan di balik propagasi kendala adalah konsistensi lokal.

Dalam konsistensi lokal, variabel diperlakukan sebagai node, dan setiap kendala biner diperlakukan sebagai busur dalam masalah yang diberikan. Ada konsistensi lokal berikut yang dibahas di bawah ini :

• Node Consistency : Variabel tunggal dikatakan konsisten node jika semua nilai dalam domain variabel memenuhi batasan unary pada variabel.
• Arc Consistency : Suatu variabel adalah busur konsisten jika setiap nilai dalam domainnya memenuhi batasan biner dari variabel.
• Path Consistency : Ketika evaluasi satu set dua variabel sehubungan dengan variabel ketiga dapat diperluas ke variabel lain, memenuhi semua kendala biner. Ini mirip dengan konsistensi busur.
• k-consistency : Jenis konsistensi ini digunakan untuk mendefinisikan gagasan tentang bentuk perbanyakan yang lebih kuat. Di sini, kami memeriksa k-konsistensi variabel.

C. Contoh Masalah pada Constraint Satisfaction Problem (CSP)

Constraint Satisfaction mencakup masalah-masalah yang mengandung beberapa kendala saat menyelesaikan masalah. CSP mencakup masalah-masalah berikut :

1. Pewarnaan Graf (Graph Coloring)

Masalah dimana kendalanya adalah tidak boleh ada sisi yang bertetangga yang memiliki warna yang sama.

Pewarnaan Graf dalam CSP

Namun, jika kendala melibatkan lebih dari dua variabel (dalam hal ini, kami menyebutnya global), kami membuat Grafik Hiper kendala. Mereka berisi dua jenis node: node biasa yang mewakili variabel dan hyper-node yang mewakili kendala. Misalnya, Sudoku memiliki kendala 9-ary. Jadi, sebagian dari hyper-graph-nya akan terlihat seperti ini :

Constraint Hypergraphs

Kendala bisa Unier (Unary), yang berarti membatasi satu variabel. CSP dengan batasan unary dan binary saja disebut CSP binary. Dengan memperkenalkan variabel tambahan, kita dapat mengubah kendala global apa pun pada variabel domain hingga menjadi satu set kendala biner. Jadi, tampaknya kita dapat fokus pada CSP biner dan tidak perlu mengembangkan pemecah yang mempertimbangkan batasan tingkat tinggi.

Namun, masih dapat membayar untuk bekerja dengan kendala global. Alasannya adalah batasan seperti ALL_DIFFERENT lebih mudah diimplementasikan dan dipahami daripada sekumpulan batasan biner. Selain itu, pemecah yang mengeksploitasi spesifik kendala global bisa lebih efisien daripada yang hanya beroperasi pada kendala Biner dan Unier.

2. Bermain Sudoku

Gameplay yang batasannya adalah tidak ada angka dari 0-9 yang dapat diulang di baris atau kolom yang sama.

Permainan Sudoku

3. Masalah n-queen

Dalam masalah n-queen, batasannya adalah tidak boleh ada queen yang ditempatkan secara diagonal, pada baris atau kolom yang sama.

Catatan : Masalah n-queen sudah dibahas di Pemecahan masalah di bagian AI.

4. Teka Teki Silang (TTS)

Dalam soal TTS, kendalanya adalah harus ada susunan kata yang benar, dan harus bermakna.

Crossword Problem

5. Masalah Kotak Latin (Latin Square Problem)

Dalam game ini tugasnya adalah mencari pola yang terjadi beberapa kali dalam game. Mereka mungkin dikocok tetapi akan berisi digit yang sama.

6. Masalah Cryptarithmetic

Masalah ini memiliki satu batasan terpenting yaitu, kami tidak dapat menetapkan digit yang berbeda untuk karakter yang sama. Semua digit harus mengandung alfabet unik.

7. Pemecah Kemunduran (The Backtracking Solver)

Di sini, kami akan menyajikan Algoritma Backtracking untuk kepuasan kendala. Idenya adalah memulai dari solusi kosong dan mengatur variabel satu per satu sampai kita menetapkan nilai untuk semuanya. Saat menetapkan variabel, kami hanya mempertimbangkan nilai yang konsisten dengan variabel yang ditetapkan sebelumnya. Jika kita menyadari bahwa kita tidak dapat menetapkan variabel tanpa melanggar batasan, kita mundur ke salah satu variabel yang telah kita tetapkan sebelumnya. Kemudian, kami menetapkannya ke nilai berikutnya dalam domainnya dan melanjutkan dengan variabel lain yang belum ditetapkan.

Meskipun urutan di mana kami menetapkan variabel nilainya tidak memengaruhi kebenaran solusi, itu memengaruhi kemanjuran algoritme. Hal yang sama berlaku untuk urutan di mana kami mencoba nilai dalam domain variabel. Selain itu, ternyata setiap kali kita menetapkan variabel, kita dapat menyimpulkan nilai mana dari variabel lain yang tidak konsisten dengan penugasan saat ini dan membuangnya tanpa melintasi seluruh sub-tree.

a. Pseudocode

Dengan mengingat hal itu, kita menyajikan Pseudocode :

Cara kita menerapkan pemilihan variabel, urutan nilai, dan inferensi sangat penting untuk kinerja. Dalam pencarian tradisional, kami menyempurnakan algoritme dengan merumuskan heuristik khusus masalah yang memandu pencarian secara efisien. Namun, ternyata ada teknik bebas domain yang dapat kita gunakan untuk mempercepat pemecah penelusuran mundur untuk CSP.

b. Inferensi (Kesimpulan)

Mari kita bicara tentang inferensi terlebih dahulu. Itu adalah langkah yang kami lakukan tepat setelah menyetel variabel X ke nilai v di domainnya. Kami mengulangi semua variabel yang terhubung ke X dalam grafik pembatas (hiper) dan menghapus nilai yang tidak sesuai dengan penetapan X = v dari domainnya. Dengan begitu, kami memangkas pohon pencarian saat kami membuang tugas yang mustahil sebelumnya. Teknik ini dikenal sebagai forwarding checking. Namun, kita bisa berbuat lebih banyak.

Setiap kali kita memangkas nilai v dari D_i, kita dapat memeriksa apa yang terjadi pada tetangga X_i di grafik. Lebih khusus lagi, untuk setiap X_j yang terhubung ke X_i melalui kendala , kami memeriksa apakah ada nilai w \in D_j sehingga X_j = w memenuhi C_k hanya jika X_i = v. Nilai apa pun w dapat dibuang karena tugas apa pun yang mengandung X_j = w juga tidak mungkin. Namun, ini mengasumsikan bahwa semua kendala adalah biner.

c. Seleksi Variabel

Strategi langsung untuk pemilihan variabel adalah dengan mempertimbangkan variabel dalam urutan statis yang kami perbaiki sebelum menyelesaikan CSP yang ada. Atau, kita dapat memilih variabel berikutnya secara acak. Namun, itu bukan strategi yang efisien. Jika ada variabel dengan hanya satu nilai di domainnya, masuk akal untuk mengaturnya sebelum yang lain. Alasannya adalah mengoptimalkan kinerja kasus terburuk.

Dalam skenario terburuk, kami tidak dapat menyelesaikan penugasan sebagian saat ini, sehingga penelusuran mundur akan mengembalikan kegagalan setelah melintasi seluruh subpohon di bawah penugasan tersebut. Namun, variabel dengan hanya satu nilai hukum adalah yang paling mungkin berkonflik dengan variabel lain pada tingkat sub-pohon yang lebih dangkal dan mengungkapkan ketidakkonsistenannya. Secara umum, ini adalah alasan untuk heuristik Minimum-Remaining-Values (MRV). MRV memilih variabel dengan nilai hukum paling sedikit yang tersisa di domainnya.

d. Value Ordering

Heuristik pengurutan nilai mengikuti logika yang berlawanan. Saat menyetel X ke sebuah nilai, kita harus memilih salah satu yang mengesampingkan nilai paling sedikit dari domain tetangga X. Intuisi di balik pilihan ini adalah bahwa kita hanya membutuhkan satu solusi, dan lebih mungkin subpohon yang lebih besar memuatnya daripada subpohon yang lebih kecil. Kami menyebut strategi ini heuristik Least-Constraining-Value (LCV).

Di satu sisi, LCV menyeimbangkan kecenderungan MRV untuk memangkas pohon pencarian sebanyak mungkin. Pemecah CSP yang menggabungkan kedua heuristik biasanya sangat efisien dalam praktiknya. Namun, kami harus mencatat bahwa MRV tidak mengharuskan CSP menjadi biner, sedangkan LCV membutuhkannya. Itu bukan masalah karena kami dapat mengonversi CSP apa pun ke bentuk biner. Namun, jika kita menggunakan aturan inferensi yang dibuat khusus yang beroperasi pada batasan tingkat tinggi seperti ALL_DIFFERENT, kita harus memastikan untuk mempertahankan kedua representasi CSP selama eksekusi pemecah pelacakan mundur.

VIDEO

Untuk memahami lebih lanjut terkait dengan Constraint Satisfaction Problem (CSP) dalam AI, lihatlah Video-video YouTube di bawah ini.

Itulah Materi tentang Constraint Satisfaction Problem dalam Kecerdasan Buatan (AI). Mohon maaf apabila ada kesalahan apapun. 

Terima Kasih 😄😘👌👍 :)

Wassalamu‘alaikum wr. wb.