Inference dalam CSP

Back to IF3170 Inteligensi Artifisial

Topic

Questions/Cues

• Apa itu inference dalam CSP?

• Apa itu constraint propagation?

• Apa itu local consistency?

• Apa itu Node Consistency?

• Apa itu Arc Consistency (AC)?

• Apa itu Path Consistency (PC)?

• Apa itu K-Consistency?

Reference Points

• IF3170_Materi04_AI-CSP.pdf (Slide 7-12)

Tujuan Inference: Constraint Propagation

Dalam konteks CSP, inference adalah proses menggunakan constraints (batasan) untuk mengurangi jumlah nilai legal (pilihan yang valid) untuk setiap variabel. Proses ini disebut Constraint Propagation.

Ide utamanya adalah untuk mendeteksi ketidakkonsistenan sedini mungkin, sehingga ruang pencarian menjadi lebih kecil. Kunci dari constraint propagation adalah menerapkan berbagai jenis konsistensi lokal (local consistency).

1. Node Consistency

Ini adalah bentuk konsistensi yang paling sederhana. Sebuah variabel dikatakan node-consistent jika setiap nilai dalam domainnya memenuhi unary constraint (batasan pada satu variabel) dari variabel tersebut.

• Contoh: Jika kita memiliki constraint SA ≠ hijau dan domain awal untuk SA adalah {merah, hijau, biru}, maka untuk mencapai node consistency, kita harus menghapus hijau dari domain SA.

• Hasil: Domain baru untuk SA menjadi {merah, biru}.

• Sebuah jaringan CSP disebut node-consistent jika semua variabel di dalamnya sudah node-consistent.

2. Arc Consistency (AC)

Ini adalah jenis konsistensi yang paling umum digunakan. Sebuah variabel $X_i$​ disebut arc-consistent terhadap variabel lain $X_j$ jika untuk setiap nilai dalam domain $D_i$​, ada setidaknya satu nilai dalam domain $D_j$​ yang memenuhi binary constraint antara $X_i$​ dan $X_j$​.

• Logikanya: Jika ada nilai v di domain $X_i$​ yang tidak memiliki “pasangan” yang valid di domain $X_j$​, maka nilai v tersebut tidak mungkin menjadi bagian dari solusi, sehingga bisa dihapus.

• Contoh: Misal domain WA dan NT adalah {merah, biru} dan constraint-nya adalah WA $\ne$ NT. Arc (WA, NT) sudah konsisten karena jika WA=merah, NT bisa biru, dan jika WA=biru, NT bisa merah.

• Contoh lain (penghapusan): Misal domain X = {1, 2, 3} dan Y = {1, 2} dengan constraint $X<Y$.

  • Untuk X=1, Y bisa 2 (valid).

  • Untuk X=2, tidak ada nilai Y yang lebih besar (tidak valid).

  • Untuk X=3, tidak ada nilai Y yang lebih besar (tidak valid).

  • Maka, nilai 2 dan 3 dihapus dari domain X. Domain baru X menjadi {1}.

3. Path Consistency (PC)

Path Consistency memperkuat konsistensi dengan melihat variabel secara bertiga. Sepasang variabel $\{X_i,X_j\}$ dikatakan path-consistent terhadap variabel perantara $X_m$​​ jika setiap assignment yang konsisten untuk $\{X_i,X_j\}$ dapat diperluas dengan sebuah nilai untuk $X_m$​ sehingga constraint pada $\{X_i,X_m\}$ dan $\{X_m,X_j\}$ juga terpenuhi.

• Contoh: Dalam pewarnaan peta Australia dengan 2 warna (merah, biru). Pasangan {WA, SA} memiliki assignment konsisten {WA=merah, SA=biru}. Tapi, jika kita lihat variabel perantara NT, tidak ada warna yang bisa diberikan ke NT yang memenuhi constraint NT $\ne$ WA dan NT $\ne$ SA secara bersamaan. Maka, assignment {WA=merah, SA=biru} tidak konsisten dan dapat dieliminasi.

4. K-Consistency

Ini adalah generalisasi dari konsep konsistensi.

• 1-Consistency: Sama dengan Node Consistency.

• 2-Consistency: Sama dengan Arc Consistency.

• 3-Consistency: Sama dengan Path Consistency.

Secara umum, sebuah CSP dikatakan k-consistent jika untuk setiap set dari k−1 variabel yang memiliki assignment konsisten, selalu ada nilai yang valid untuk variabel ke-k manapun.

Summary

Inference dalam CSP, atau Constraint Propagation, adalah teknik untuk menyederhanakan masalah dengan menegakkan konsistensi lokal untuk mengurangi domain variabel. Mulai dari yang paling sederhana (Node Consistency untuk unary constraint), yang paling umum (Arc Consistency untuk binary constraint), hingga yang lebih kuat (Path Consistency), tujuan utamanya adalah untuk menghapus nilai-nilai yang tidak mungkin menjadi bagian dari solusi akhir, sehingga mempercepat proses pencarian.

Additional Information

Trade-off antara Inference dan Pencarian

Menjalankan algoritma konsistensi (seperti AC-3 untuk Arc Consistency) membutuhkan waktu komputasi. Ada sebuah trade-off:

• Terlalu sedikit inference: Algoritma pencarian (seperti backtracking) harus menjelajahi ruang pencarian yang sangat besar dan akan sering menemui jalan buntu.

• Terlalu banyak inference: Waktu yang dihabiskan untuk melakukan propagation sebelum pencarian bisa jadi lebih lama daripada waktu yang dihemat selama pencarian.

Arc Consistency seringkali menjadi titik tengah yang baik, karena cukup kuat untuk mengurangi domain secara signifikan namun tidak terlalu mahal secara komputasi.

Strong vs Weak K-Consistency

Ada juga konsep Strong k-consistency, yang berarti sebuah CSP bersifat j-consistent untuk semua j≤k. Jika kita bisa membuat sebuah CSP menjadi strong n-consistent (di mana n adalah jumlah variabel), maka solusi dapat ditemukan tanpa perlu melakukan backtracking sama sekali. Namun, mencapai ini biasanya memiliki kompleksitas waktu dan ruang yang terlalu tinggi.