Mengapa Pemrograman Planner Itu Mengejutkan

 (hillelwayne.com)
2 poin oleh GN⁺ 2024-02-22 | 1 komentar | Bagikan ke WhatsApp
  • Modul planner di Picat melangkah lebih jauh dari pemrograman logika yang mencari penetapan nilai, dengan mengekspresikan masalah sebagai urutan perubahan status menuju status tujuan
  • Jika kita mendefinisikan status awal Start, aturan transisi action(From, To, Action, Cost), dan kondisi akhir final(S), maka best_plan(Start, Plan) akan menemukan rencana berbiaya minimum hingga status akhir
  • Dalam contoh jalur grid, perpindahan, batas tepi, penghindaran rintangan, dan kunjungan ke beberapa tujuan ditangani hanya dengan mengubah action dan final; urutan kunjungan tujuan juga bisa dibuat tetap atau bebas
  • Fitur planning digabungkan dengan constraint solving, sehingga masalah seperti mencari sublist terbesar yang dapat dibagi menjadi dua bagian dengan jumlah sama dengan menghapus elemen pada partition problem juga dapat diekspresikan
  • Picat adalah bahasa riset sehingga dokumentasi dan pesan error-nya terbatas, tetapi sebagai bahasa berbentuk alat untuk cepat menyelesaikan masalah komputasi tertentu, ia bisa memberikan solusi yang lebih ringkas daripada bahasa umum

Ide dasar Picat dan pemrograman planner

  • Picat adalah bahasa riset yang mencoba menggabungkan pemrograman logika, pemrograman imperatif, dan constraint solving
  • Pemrograman imperatif dan fungsional pada umumnya menulis algoritme yang menghasilkan output dari input, sedangkan pemrograman logika dan constraint solving mencari penetapan nilai yang memenuhi relasi
  • Di Picat, identifier non-fungsi yang diawali huruf kecil adalah atom seperti a, b, c, sedangkan identifier yang diawali huruf besar adalah variabel
  • Bahkan dalam ekspresi seperti member(Y, Arr) yang berisi variabel Y yang belum didefinisikan, Picat dapat mencari dan menetapkan nilai yang membuat ekspresi tersebut benar
    • Jika Arr = [a, b, c, a], maka Y bisa menjadi salah satu dari a, b, atau c
    • Jika kemudian ditambahkan kondisi seperti X != Y, nilai yang mungkin akan semakin dipersempit
    • Bahkan saat list itu sendiri belum diketahui, seperti member(a, Z), Picat dapat menginstansiasi Z sebagai list

Planning mencari perubahan status, bukan penetapan nilai

  • Planning mencari urutan perubahan variabel yang mencapai status akhir tertentu, alih-alih mencari nilai variabel yang memenuhi persamaan
  • Masalah planning di Picat membutuhkan tiga elemen
    • Status awal Start
    • Fungsi-fungsi action yang merepresentasikan transisi status
    • final(S) yang menentukan apakah sebuah status merupakan status akhir
  • Semua fungsi action di Picat harus bernama action dan menerima empat parameter
    • Status saat ini
    • Status berikutnya
    • Nama aksi
    • Biaya
  • best_plan(Start, Plan) menetapkan ke Plan rencana dengan jumlah langkah terpendek atau biaya minimum yang diperlukan untuk mencapai status akhir
    • Jika semua biaya dibuat 1, biaya rencana menjadi total jumlah langkah perpindahan
    • Jika hanya membutuhkan rencana apa pun tanpa peduli panjangnya, kita bisa menggunakan plan(Start, Plan)

Contoh pencarian jalur grid

  • Masalah contoh adalah marker di atas grid yang berangkat dari titik asal (0, 0) dan mencapai koordinat tujuan
    • Pada setiap langkah, marker bisa bergerak satu sel ke atas, bawah, kiri, atau kanan
    • Marker tidak bisa keluar dari batas grid
    • Berhasil ketika tiba di koordinat tujuan
  • Status awal memuat posisi saat ini dan tujuan bersama-sama, seperti {Origin, Goal}
    • {a, b} di Picat adalah sintaks array dan pada praktiknya digunakan seperti tuple
  • Kondisi akhir dapat diekspresikan dengan pattern matching seperti final({Pos, Goal}) => Pos = Goal.
    • Untuk menulis hal yang sama tanpa pattern matching, status harus dipecah dulu menjadi {Pos, Goal}
    • Jika ada beberapa kondisi final, planning berhasil saat salah satunya benar
  • Aksi perpindahan memilih salah satu dari empat arah {-1,0}, {1,0}, {0,-1}, {0,1}, lalu memeriksa apakah koordinat baru berada dalam rentang 0..10
    • member({Dx, Dy}, Dir) digunakan untuk mencari nilai arah yang mungkin
    • member(Tx, 0..10) dan member(Ty, 0..10) digunakan untuk memeriksa apakah koordinat berada di dalam batas
    • Untuk predicate khusus pemeriksaan yang tidak menetapkan nilai, ada juga membchk
  • Rencana hasilnya dicetak sebagai daftar aksi perpindahan dan koordinat baru, seperti {move,{1,0}}, {move,{2,0}}
    • Jalur dapat divisualisasikan dengan skrip Raku
    • Jika menambahkan kondisi seperti {Tx, Ty} != {2, 1}, penghindaran rintangan pada koordinat tertentu juga bisa dilakukan

Beberapa tujuan dan minimisasi biaya

  • Untuk mengunjungi beberapa tujuan, Goal diubah dari satu koordinat menjadi antrean tujuan seperti [{2, 2}, {3, 4}]
  • Tambahkan action baru yang menghapus item tersebut dari daftar tujuan saat sudah tiba di tujuan
    • [Head|Tail] membagi list menjadi elemen pertama dan sisanya
    • Goal = [Pos|Rest] hanya benar ketika posisi saat ini Pos sama dengan item pertama dalam daftar tujuan
    • Jika status baru dibuat sebagai {Pos, Rest}, tujuan yang sudah dicapai akan dihapus
  • Apakah semua tujuan telah dikunjungi ditentukan dengan final({Pos, Goal}) => Goal = [].
    • Kondisi akhir bukan apakah posisi saat ini sama dengan tujuan tertentu, melainkan apakah daftar tujuan sudah kosong
  • Mengunjungi tujuan dalam urutan yang telah ditentukan tidak selalu menghasilkan jalur total terpendek
  • Untuk mengabaikan urutan tujuan dan meminimalkan keseluruhan jalur, ubah aksi mark
    • Alih-alih Goal = [Pos|Rest], gunakan member(Pos, Goal) untuk memeriksa apakah posisi saat ini ada di mana pun dalam daftar tujuan
    • Dengan To = {Pos, delete(Goal, Pos)}, tujuan yang sudah dikunjungi dihapus dari daftar
    • Dengan cara ini, Picat dapat memilih tujuan berikutnya dan meminimalkan panjang jalur keseluruhan

Menggabungkan planning dan constraint solving

  • Fitur planning Picat terintegrasi dengan fitur Picat lainnya, dan planning dapat digunakan bersama constraint solving
  • Partition problem yang dibahas sebagai contoh adalah masalah NP-complete untuk membagi list angka menjadi dua grup dengan jumlah yang sama
  • Program ini menghapus elemen dari list angka untuk mencari sublist terbesar yang dapat dibagi menjadi dua dengan jumlah yang sama
    • Menghapus elemen dari daftar angka dijadikan aksi planning
    • final(Numbers) memeriksa apakah daftar angka tersebut memiliki solusi partition yang valid
    • Dengan constraint dari modul cp, tiap elemen direpresentasikan sebagai variabel 0..1 yang menentukan apakah ia masuk ke grup kiri atau kanan
    • Constraint dibuat agar total jumlah menjadi dua kali jumlah salah satu grup
  • Dalam output contoh, setelah menghapus [5,17], list yang tersisa dapat dibagi menjadi dua grup yang masing-masing menghasilkan jumlah 1108
    • 32+99+977=1108
    • 122+77+86+59+47+154+141+172+49+62+109+30=1108
  • Pendekatan ini tidak berhenti pada menyelesaikan constraint yang valid secara langsung, tetapi juga mengekspresikan perubahan untuk mencapai status constraint yang valid sebagai planning

Keterbatasan Picat dan kegunaan yang cocok

  • Picat adalah bahasa riset sehingga tidak direkomendasikan untuk penggunaan produksi
  • Fitur kenyamanannya tidak banyak, dan dokumentasi yang baik maupun pesan error yang jelas juga kurang
    • Ketika tidak ada rencana yang dapat diselesaikan, error dicetak seperti *** error(failed,main/0)
  • Fakta bahwa ia dapat dijalankan di Windows dinilai lebih baik daripada banyak bahasa riset lainnya
  • Picat lebih dekat ke bahasa toolkit untuk menyelesaikan jenis masalah komputasi tertentu, bukan bahasa untuk menulis kode yang akan dipelihara atau dibagikan
  • Beberapa masalah yang sulit ditangani dengan bahasa pemrograman umum dan constraint solver dapat diselesaikan dengan cukup elegan menggunakan Picat

Bahasa planning lain dan konsep terkait

  • Planning awalnya dirintis dalam robotika dan AI, tetapi kini sering digunakan dalam AI video game dengan nama Goal Oriented Action Planning(GOAP)
  • PDDL adalah bahasa deskripsi planning yang diterima sebagai input oleh planner independen
    • Perannya mirip dengan DIMACS yang digunakan sebagai format deskripsi dalam SAT

Bacaan terkait

1 komentar

 
GN⁺ 2024-02-22
Komentar Hacker News

  • Pernah memakai mode perencanaan Picat dalam pekerjaan nyata
    Saya membuat prototipe sistem untuk mengoordinasikan pemeliharaan beberapa kelompok peralatan, dengan cara memasukkan “apa yang diinginkan”, “tindakan apa yang mungkin”, dan “batasan apa yang harus dipatuhi”, bukan “bagaimana melakukannya”
    Pada contoh kecil, sistem ini mampu membuat rencana optimal dengan baik, tetapi saat skalanya membesar ke ukuran nyata, seperti yang diduga semuanya runtuh; masalah perencanaan pada akhirnya EXPTIME, jadi batasnya besar
    Picat punya jalan keluar untuk mendefinisikan heuristik, jadi saya membuat random forest dan pengklasifikasi naive Bayes atas predikat status untuk memprediksi jalur yang menjanjikan, tetapi bahkan setelah menambahkan batasan pemecahan simetri dan perencanaan hierarkis, tetap terlalu banyak pekerjaan manual
    Tampaknya di ranah masalah GOFAI klasik masih ada musim dingin AI
    Mungkin tidak demikian jika masalah perencanaan dirumuskan ulang agar mengembalikan “generator waktu polinomial yang menghasilkan rencana yang berpotensi panjangnya eksponensial”

    • Solver komersial jauh lebih baik dari open source dalam hal performa, dan jauh lebih cepat mengosongkan dompet
      Yang terlintas CPLEX, Xpress, GUROBI, Hexaly; Hexaly sangat bagus khususnya untuk penjadwalan atau masalah rute kendaraan
      Biasanya di industri aksesnya lewat API untuk bahasa yang banyak dipakai, dan menurut saya pendekatan ini jauh lebih masuk akal dibanding bahasa solver khusus yang lemah untuk pekerjaan umum
      Memanggil GUROBI dari Python sangat mudah, dan fitur umum Python tetap bisa dipakai apa adanya
      Mosek jauh lebih murah daripada GUROBI, tetapi API keduanya sangat low-level dan performanya juga tidak sebaik GUROBI
    • Untuk kasus ini, sesuatu seperti CP-SAT(https://developers.google.com/optimization/cp) kemungkinan bisa diskalakan dengan baik
      Solver ini mudah menangani jumlah variabel dan batasan yang tidak masuk akal banyaknya, dan heuristik bawaannya juga sangat bagus
    • Planner lama mengurangi ruang pencarian dengan menyertakan meta-rule atau heuristik untuk menentukan aturan mana yang diterapkan
      Sebagian sistem membagi masalah ke representasi yang berbeda-beda dan memasangkan solver otomatis yang terspesialisasi
      Yang terlintas adalah Jahob Analysis System dan Cyc
      Dari sisi penggunaan nyata, rancangan paling rapi di AI klasik adalah Procedural Reasoning System, dan saya ingin melihat versi yang dibuat ulang dengan menambal kelemahannya memakai metode modern
      https://en.wikipedia.org/wiki/Procedural_reasoning_system
    • Saya penasaran mengapa tidak ada solver open source berkualitas tinggi
      Di bidang komputasi numerik lain, teknologi mutakhir sering kali open source; saya selalu bertanya-tanya mengapa bidang optimisasi berbeda
    • Dari sisi hasil atau performa, rasanya ini tidak terlalu berbeda dari depth-first search yang ditulis seadanya sambil samar-samar mengingat Prolog

  • Ada situs milik HN user yang aktif di komunitas constraint programming, hakank, alias Hakan Kjellerstrand, yang mengumpulkan banyak materi dan contoh Picat: http://www.hakank.org/picat/

  • Seperti biasa, saya ingin merekomendasikan Prolog
    Elegan, mudah dipahami, lebih matang, dan jika ingin penyelesaian constraint finite domain, konfigurasi dasarnya saja sudah cukup
    Selain itu, MiniZinc adalah antarmuka yang sangat bagus untuk mengakses berbagai solver yang terspesialisasi untuk beragam tujuan, jadi jika Anda bukan pakar, kemungkinan hasil yang diinginkan akan lebih mudah dicapai
    Prolog punya banyak kelebihan, tetapi “rasa mekanis” yang dibutuhkan untuk mendapat performa bagus bisa cepat menjadi cukup besar
    Jika Anda menulis sesuatu dengan Picat, ada baiknya juga memikirkan bagaimana hal yang sama akan ditulis dalam bahasa lain
    Masalah mainan seperti ini juga mudah di bahasa lain; di sebagian besar bahasa fungsional, Dijkstra atau A* hanya beberapa baris, dan pada akhirnya sering kali yang perlu dilakukan hanyalah mendefinisikan ruang status untuk algoritma pencarian

  • Senang melihat Predrag sebagai reviewer, tetapi sama sekali tidak mengejutkan
    Firebase technical screen sepertinya akan jauh lebih mudah jika ada alat seperti ini, dan pada akhirnya itu juga masalah optimisasi lain
    Saya juga jadi ingin mencobanya lagi dengan Picat
    Ia juga melakukan pekerjaan menarik di bidang bahasa pemrograman: https://github.com/obi1kenobi/trustfall

  • Pikiran pertama saya: “ini seperti sistem tipe yang harus dipecahkan sendiri”
    Saya mencoba mengekspresikannya secara naif dengan TypeScript, tetapi karena a, b, c semuanya bisa sama, tidak ada yang terselesaikan
    Saat mencoba mengekspresikannya dengan benar, saya sampai pada bentuk yang tampaknya cukup bisa dipakai, tetapi masih harus memakai assertion dan tipe Y juga tidak bisa diekspresikan dengan benar
    Proses ini justru menunjukkan betapa kuatnya program bergaya planner dalam hal kesederhanaan dan keringkasan
    TypeScript tampaknya tidak cukup kuat untuk mengekspresikan constraint semacam ini
    Tautan TS Playground eksperimen: http://tinyurl.com/3p2pzdtn

  • Senang melihat GOAP disebut lagi
    Itulah bumbu rahasia yang membuat musuh di F.E.A.R. begitu menarik, dan makalah Jeff Orkin tentang cara kerjanya juga mudah dibaca dan menyenangkan

  • Saya memakai Prolog dan sebagian CLPFD dalam pekerjaan nyata, dan itu sangat bagus
    Saya berharap ini ada di mana-mana; lebih tepatnya, saya ingin menaruh inti logika yang menekankan kemurnian, lalu mendorong perilaku imperatif ke pinggir
    Sedih rasanya melihat industri seperti terjebak dalam alat-alat yang begitu buruk

  • Terlihat mirip Prolog dan menarik

  • Cara pemrograman seperti ini sendiri tidak sepenuhnya baru
    Saya belajar Prolog di universitas dan ini terlihat cukup mirip, tetapi Prolog tidak punya fitur planner
    Namun planner adalah cara yang sangat elegan dan sederhana untuk memecahkan masalah
    Bagian tentang video game di akhir tulisan membuat saya penasaran
    Fitur planner memungkinkan masalah diselesaikan dengan sangat mudah dalam beberapa baris kode yang jelas, tetapi bagaimana performanya dibanding algoritma yang ditulis secara imperatif?
    Picat tampaknya cukup efisien dibanding bahasa-bahasa serupa [1], tetapi saya tidak menemukan perbandingan dengan bahasa “standar”
    [1]: https://arxiv.org/abs/1405.2538

  • Saya juga punya mimpi untuk hanya memberi tahu komputer status yang harus dicapai
    Saya tidak terlalu mengenal komunitas perencanaan atau solver, hanya pernah mengutak-atik ortools secara naif, tetapi saya pernah mencoba menghasilkan kode untuk berpindah dari satu status ke status tujuan dengan A*
    Sistem itu menghasilkan instruksi assembly untuk berpindah antarstatus, dan bahkan menemukan transisi status tersembunyi dari pemanggilan fungsi untuk mencapai tujuan
    Untuk mempercepat pencarian, saya juga menjalankannya paralel dengan Python multiprocessing, dan karena setiap thread menghasilkan tetangga yang berbeda, saya memakai pembuatan tetangga dinamis
    Pada percobaan awal, A* sulit diparalelkan sehingga perlu sharding
    Mimpi eksperimen saya adalah memberi tahu komputer “apa yang saya miliki sekarang” dan “apa yang saya inginkan”, lalu komputer menemukan sendiri jalur perpindahan yang benar
    Secara pribadi, saya melihat pemrograman lebih seperti logistik, seperti Factorio atau pabrik
    Karena itu saya menyebutnya “sliding puzzle”, sebab ini adalah teka-teki di mana kita harus memindah-mindahkan barang untuk melihat gambar yang benar
    Repositori GitHub dan catatan: https://github.com/samsquire/sliding-puzzle-codegen-memory
    Replit: https://replit.com/@Chronological/SlidingPuzzle3