Kecerdasan Artifisial

Pertemuan 06

Constraint Satisfaction Problems (CSP)

Mata Kuliah: Kecerdasan Artifisial (AI401) | 3 SKS

🎯 Capaian Pembelajaran

Setelah pertemuan ini, mahasiswa mampu:

Memformulasikan masalah sebagai CSP
Menerapkan teknik constraint propagation
Mengimplementasikan algoritma AC-3
Menerapkan backtracking search untuk CSP
Menggunakan heuristik MRV, Degree, dan LCV
Mengimplementasikan forward checking

📋 Agenda Hari Ini

Bagian 1

Definisi CSP
Contoh CSP Klasik
Constraint Graph

Bagian 2

Constraint Propagation
Backtracking Search
Heuristik & Forward Checking

🤔 Mengapa CSP?

Problem: Algoritma pencarian sebelumnya (BFS, DFS, A*) memperlakukan state sebagai "black box"

CSP memungkinkan kita:

Mengeksploitasi struktur internal masalah
Mendeteksi failure lebih awal
Menggunakan heuristik domain-independent

📐 Definisi Formal CSP

CSP didefinisikan oleh tiga komponen:

X = {X₁, X₂, ..., Xₙ} : himpunan variabel
D = {D₁, D₂, ..., Dₙ} : himpunan domain
C = {C₁, C₂, ..., Cₘ} : himpunan constraint

Solusi: Assignment lengkap yang memenuhi semua constraint

Komponen CSP

Komponen	Deskripsi	Contoh (Map Coloring)
Variabel (X)	Entitas yang diberi nilai	WA, NT, SA, Q, NSW, V, T
Domain (D)	Nilai yang mungkin	{Merah, Hijau, Biru}
Constraint (C)	Batasan yang dipenuhi	Tetangga ≠ warna sama

Jenis-Jenis Constraint

Jenis	Variabel	Contoh
Unary	1 variabel	X₁ ≠ Merah
Binary	2 variabel	X₁ ≠ X₂
Higher-order	> 2 variabel	X₁ + X₂ + X₃ ≤ 10
Global	Banyak variabel	Alldiff(X₁, X₂, ..., Xₙ)

🗺️ Contoh: Map Coloring

Gambar: Constraint graph untuk pewarnaan peta Australia

Formulasi Map Coloring

Variabel:

WA, NT, SA, Q, NSW, V, T

Domain:

{R, G, B} untuk semua

Constraint:

WA ≠ NT
WA ≠ SA
NT ≠ SA
NT ≠ Q
SA ≠ Q
SA ≠ NSW
SA ≠ V
Q ≠ NSW
NSW ≠ V

👑 Contoh: N-Queens Problem

Gambar: Solusi valid 4-Queens dan constraint-nya

Formulasi N-Queens

Variabel: Q₁, Q₂, ..., Qₙ (satu ratu per kolom)

Domain: {1, 2, ..., N} (baris yang mungkin)

Constraint:

Tidak sebaris: Qᵢ ≠ Qⱼ untuk semua i ≠ j
Tidak sediagonal: |Qᵢ - Qⱼ| ≠ |i - j|

🔢 Contoh: Sudoku

Variabel:

81 sel (X₁₁ ... X₉₉)

Domain:

{1-9} atau singleton

Constraint:

9 Alldiff (baris)
9 Alldiff (kolom)
9 Alldiff (kotak 3×3)

Total: 27 × C(9,2) = 972 binary constraint

🔤 Contoh: Cryptarithmetic

SEND + MORE = MONEY

Variabel: S, E, N, D, M, O, R, Y, C₁, C₂, C₃, C₄

Constraint:

Alldiff(S, E, N, D, M, O, R, Y)
S ≠ 0, M ≠ 0
D + E = Y + 10×C₁
... (column constraints)

🔍 CSP sebagai Search Problem

Komponen	Definisi untuk CSP
Initial State	Assignment kosong { }
Successor	Assign nilai ke variabel
Goal Test	Assignment lengkap + semua constraint terpenuhi
Path Cost	Konstan (tidak relevan)

✨ Sifat Komutatif

Commutative Property: Urutan assignment variabel tidak mempengaruhi hasil akhir

Implikasi:

Pilih satu variabel per level
Branching factor = d (ukuran domain)
Search tree lebih kecil

🌊 Constraint Propagation

Constraint Propagation: Teknik mengurangi domain variabel dengan memanfaatkan constraint

Tujuan:

Deteksi inconsistency lebih awal
Kurangi search space
Hapus nilai yang tidak mungkin

📍 Node Consistency

Node Consistency: Semua nilai dalam domain memenuhi unary constraint

Contoh:

D(X₁) = {1, 2, 3, 4, 5}
Constraint: X₁ > 2 dan X₁ ≤ 4
Hasil: D(X₁) = {3, 4}

↔️ Arc Consistency

Arc Consistency: Untuk setiap nilai di D(Xᵢ), ada nilai di D(Xⱼ) yang memenuhi constraint

Contoh Arc Consistency

D(X₁) = {1, 2, 3}, D(X₂) = {1, 2}, Constraint: X₁ < X₂

Arc (X₁, X₂):

X₁=1: Ada X₂>1? ✓ (X₂=2)
X₁=2: Ada X₂>2? ✗ Hapus!
X₁=3: Ada X₂>3? ✗ Hapus!

D(X₁) = {1}

Arc (X₂, X₁):

X₂=1: Ada X₁<1? ✗ Hapus!
X₂=2: Ada X₁<2? ✓ (X₁=1)

D(X₂) = {2}

🔄 Algoritma AC-3

def AC3(csp):
    queue = all_arcs(csp)
    while queue not empty:
        (Xi, Xj) = queue.pop()
        if REVISE(csp, Xi, Xj):
            if domain[Xi] is empty:
                return False
            for Xk in neighbors[Xi] - {Xj}:
                queue.add((Xk, Xi))
    return True

Kompleksitas: O(ed³) — e = edges, d = domain size

Fungsi REVISE

def REVISE(csp, Xi, Xj):
    revised = False
    for x in domain[Xi]:
        # Cek apakah ada support di Xj
        if no y in domain[Xj] satisfies 
           constraint(Xi, Xj):
            domain[Xi].remove(x)
            revised = True
    return revised

🔙 Backtracking Search

Backtracking: DFS yang memilih satu variabel per langkah dan backtrack saat tidak ada nilai legal

Algoritma Backtracking

def BACKTRACK(assignment, csp):
    if assignment is complete:
        return assignment
    var = SELECT_UNASSIGNED_VARIABLE(csp)
    for value in ORDER_DOMAIN_VALUES(var):
        if value is consistent:
            assignment[var] = value
            result = BACKTRACK(assignment, csp)
            if result != failure:
                return result
            del assignment[var]
    return failure

📊 Heuristik Pemilihan Variabel

MRV

Minimum Remaining Values

Pilih variabel dengan domain terkecil

Degree Heuristic

Tiebreaker untuk MRV

Pilih yang constraint terbanyak

Contoh MRV

Variabel	Domain	\|Domain\|
A	{1, 2, 3, 4}	4
B ✓	{1, 2}	2
C	{1, 2, 3}	3

MRV = "Fail-First" → Temukan failure lebih awal!

🎯 Heuristik Pemilihan Nilai

LCV (Least Constraining Value)

Pilih nilai yang menghilangkan paling sedikit nilai dari domain tetangga

Contoh LCV

A memiliki tetangga B dan C, Constraint: A ≠ B, A ≠ C

D(A) = {R, G, B}, D(B) = {R, G}, D(C) = {G, B}

Nilai A	Hilang dari B	Hilang dari C	Total
R	1	0	1 ✓
G	1	1	2
B	0	1	1 ✓

Pilih A = R atau A = B (LCV = 1)

⏩ Forward Checking

Forward Checking: Hapus nilai inkonsisten dari domain variabel tetangga segera setelah setiap assignment

Deteksi failure lebih awal
Jika domain tetangga kosong → backtrack!

Ilustrasi Forward Checking

Gambar: Domain dikurangi setelah setiap assignment

Contoh Forward Checking

Map coloring: WA, NT, SA dengan D = {R, G, B}

Step 1: Assign WA = R

D(NT) = {G, B} (hapus R)
D(SA) = {G, B} (hapus R)

Step 2: Assign NT = G

D(SA) = {B} (hapus G)

Step 3: Assign SA = B ✓

Solusi: {WA: R, NT: G, SA: B}

🌲 Tree-Structured CSP

Tree-structured CSP: Constraint graph membentuk tree (tanpa cycle)

Keuntungan:

Dapat diselesaikan dalam O(nd²)
Tanpa backtracking!

Algoritma: Arc consistency dari leaf ke root, lalu assign dari root ke leaf

✂️ Cutset Conditioning

Cutset: Variabel yang jika dihapus menghasilkan tree structure

Jika cutset berukuran c:

Kompleksitas: O(d^c × (n-c)d²)

🎖️ Aplikasi Pertahanan

Resource Allocation

Alokasi tim/unit ke sektor operasi dengan berbagai constraint

Frequency Assignment

Alokasi frekuensi komunikasi tanpa interference

Scheduling

Penjadwalan patroli, operasi, dan shift personel

📋 Studi Kasus: Alokasi Tim

4 tim (Alpha, Bravo, Charlie, Delta) ke 4 sektor (S1-S4)

Constraint:

Alpha tidak boleh ke S1
Bravo-Charlie harus adjacent
Delta tidak boleh ke S4

Solusi: Alpha:S4, Bravo:S2, Charlie:S1, Delta:S3

🧠 Quiz Time!

Pertanyaan 1:

Apa yang dimaksud dengan Arc Consistency?

A. Semua nilai memenuhi unary constraint

B. Graph tidak memiliki cycle

C. Setiap nilai memiliki support di tetangga ✓

D. Semua constraint terpenuhi

🧠 Quiz Time!

Pertanyaan 2:

MRV heuristic memilih variabel dengan:

A. Domain terbesar

B. Domain terkecil ✓

C. Constraint paling sedikit

D. Constraint paling banyak

MRV = "Fail-First" → Temukan failure lebih awal!

🧠 Quiz Time!

Pertanyaan 3:

Kompleksitas waktu algoritma AC-3 adalah:

A. O(n²)

B. O(nd²)

C. O(ed³) ✓

D. O(2ⁿ)

📝 Ringkasan

Konsep	Deskripsi
CSP	Variabel + Domain + Constraint
Node Consistency	Unary constraint satisfaction
Arc Consistency	Binary constraint support
AC-3	O(ed³) arc consistency
MRV + Degree	Variable ordering heuristics
LCV	Value ordering heuristic
Forward Checking	Early failure detection

📅 Pertemuan Berikutnya

Pertemuan 07: Review dan Latihan Komprehensif

Persiapan Ujian Tengah Semester (UTS)

Review Pertemuan 1-6
Latihan soal komprehensif
Tips mengerjakan UTS

📚 Referensi

Russell, S. & Norvig, P. (2020). Artificial Intelligence: A Modern Approach (4th Ed.). Pearson. Chapter 6
Poole, D.L. & Mackworth, A.K. (2023). Artificial Intelligence: Foundations of Computational Agents (3rd Ed.). Cambridge University Press. Chapter 4
CS188 Berkeley AI Materials: https://inst.eecs.berkeley.edu/~cs188/

Terima Kasih

🤖 Kecerdasan Artifisial

Pertemuan 06: Constraint Satisfaction Problems (CSP)

Ada pertanyaan?