Probabilistic Focal Search: Algoritma Baru Bikin Pencarian 90% Lebih Cepat?

Kamu pasti pernah dengar soal bounded-suboptimal search, kan? Jadi gini: kita mau cari solusi yang 'cukup bagus' — dalam faktor w dari yang optimal — tapi pengen prosesnya cepet, nggak mau habisin resource buat nyari yang sempurna. Focal Search (FS) jadi salah satu pendekatan populer buat ini. Dia pakai heuristic guidance di dalam FOCAL, yaitu sekumpulan node di frontier yang eligible di bawah threshold w * f_min. Tapi ada masalah klasik: kebijakan deterministik FS sering bikin f_min nggak bergerak untuk banyak ekspansi. Akibatnya FOCAL nggak membesar, node-node yang mungkin bisa bawa ke solusi feasible justru gak kebaca.

Nah, di sinilah Probabilistic Focal Search (PFS) masuk cerita. Peneliti di arXiv (paper 2609.10584v1) ngusulin ide simpel tapi powerful: ikutin pilihan guided FS dengan probabilitas p, tapi dengan probabilitas 1-p, ekspansi node minimum-f dari OPEN. Cabang kedua inilah yang dorong lower bound (f_min) maju. Kalau f_min naik, threshold w * f_min ikut naik, FOCAL jadi lebih lebar, dan node-node yang sebelumnya gak eligible bisa masuk. Intinya: balancin antara guidance dan lower-bound advancement. Mekanisme ini bisa ngurangin waktu sampe ketemu solusi bounded pas progress diblokir oleh delayed FOCAL admission.

Probabilistic Focal Search: Solusi Acak yang Nyata

Gimana caranya PFS kerja? Algoritma ini nggak cuma pilih satu jalur doang. Dia lempar dadu (secara metafora) tiap langkah: dengan probabilitas p, dia ikut policy guided FS standar — yang biasanya milih node paling menjanjikan berdasarkan heuristic. Tapi dengan probabilitas 1-p, dia ambil node dengan f paling kecil di OPEN. Pilihan kedua ini yang bikin f_min bergerak. Kalau f_min naik, batas FOCAL (w * f_min) ikut naik, jadi lebih banyak node yang masuk FOCAL. Node-node yang sebelumnya 'terjebak' di luar FOCAL sekarang punya kesempatan diekspansi. Ini mirip kayak exploration-exploitation trade-off di reinforcement learning, tapi diterapin di search tree.

Keuntungannya jelas: pas deterministic search macet karena f_min nggak naik-naik (plateau), PFS bisa 'nembak' node minimum-f buat dorong lower bound. FOCAL jadi lebih inklusif, search space yang tadi tertutup jadi terbuka. Peneliti bilang mekanisme ini paling ngefek pas progress limited by delayed FOCAL admission. Kalau search sudah efisien sendiri (f_min naik cepet), tambahan probabilistik ini gak terlalu ngefek — bahkan bisa nambah overhead kecil. Jadi PFS itu kayak 'turbo' yang hanya nyala pas mesin macet.

Hasil Benchmark: Bisa Turun 90% Node Expansion

Peneliti benchmark PFS vs FS di tiga domain klasik: N-Puzzle, Pancake Sorting, dan Traveling Salesperson Problem (TSP). Mereka test multiple nilai w (bound factor) dan p (probabilitas). Hasilnya mengejutkan: di setting di mana f_min plateau lama — delay FOCAL admission jadi bottleneck — PFS bisa ngurangin node expansions sekitar 90% atau lebih. Di N-Puzzle dan TSP, gain-nya gede banget. Tapi di Pancake Sorting, di mana deterministic search sudah efisien banget naikin f_min, benefit PFS lebih kecil. Ini konfirmasiin hipotesis: PFS paling cuan pas FOCAL admission adalah bottleneck utama.

Buat anytime algorithm family, mereka bikin Anytime Probabilistic Focal Search (APFS) dan test di Generalized Covering TSP (GCTSP). APFS ngalahin semua algoritma anytime yang ditest di evaluasi GCTSP. Artinya, bukan cuma one-shot search yang untung, tapi versi anytime-nya juga superior. Buat kamu yang kerja di routing, logistics, atau optimization problems yang butuh solusi berkualitas dengan deadline ketat, ini insight yang worth to explore.

Transfer ke Dynamic Potential Search Jadi PDPS

Sebagai eksperimen transfer sekunder, peneliti terapin scheduler probabilistik yang sama ke Dynamic Potential Search (DPS). Lahirnya Probabilistic Dynamic Potential Search (PDPS). Hasilnya: mekanisme ini juga transfer ke potential guidance, tapi efek common-success-nya masih domain-dependent dan bound-dependent. Artinya, nggak selalu manjur di semua domain — perlu tuning p dan w yang cermat. Tapi fakta bahwa ide probabilistik 'lower-bound advancement' bisa dipindahin ke framework guidance lain (bukan cuma FOCAL) itu sendiri sudah kontribusi teoritis yang solid. Buka pintu buat Probabilistic A*, Probabilistic WA*, dll.

Kapan PFS Paling Berguna?

Dari data benchmark, pola jelas: PFS shine pas deterministic search mengalami f_min plateau yang panjang. Di N-Puzzle dan TSP, di mana heuristic sering ngeblok progress lower bound, PFS bikin breakthrough. Di Pancake Sorting, di mana heuristic lebih informatif dan f_min naik steady, FS standar sudah cukup bagus — PFS cuma nambah overhead probabilistik tanpa gain signifikan. Jadi kalau kamu develop solver untuk domain dengan heuristic 'lemah' atau deceptive (banyak local minima, plateau), PFS worth a shot. Tapi kalau heuristic sudah strong dan search sudah smooth, stick dengan FS standar aja.

Practical takeaway buat kamu: kalau lagi bangun bounded-suboptimal planner untuk robotik, game AI, atau logistics, coba implement PFS dengan p sekitar 0.7-0.9 (tergantung domain). Test di benchmark kecil dulu, bandingin node expansion vs FS. Kalau liat f_min sering stuck, PFS bakal cuan banget. Jangan lupa tune w juga — bound factor yang terlalu ketat (w mendekati 1) bikin FOCAL sempit, PFS butuh ruang gerak. Paper ini fresh dari arXiv, jadi belum tentu ada library siap pakai, tapi implementasinya straightforward: cuma tambah random branch di loop ekspansi utama.