Planner programlamanın şaşırtıcı olmasının nedeni

 (hillelwayne.com)
2 puan yazan GN⁺ 2024-02-22 | 1 yorum | WhatsApp'ta paylaş
  • Picat'ın planner modülü, değer atamaları bulan mantıksal programlamanın bir adım ötesine geçerek, hedef duruma giden durum değişikliği dizisini problem olarak ifade eder
  • Başlangıç durumu Start, geçiş kuralı action(From, To, Action, Cost) ve bitiş koşulu final(S) tanımlandığında best_plan(Start, Plan), son duruma kadar olan en düşük maliyetli planı bulur
  • Izgara yolu örneğinde hareket, sınır kısıtları, engellerden kaçınma ve birden fazla hedefi ziyaret etme; yalnızca action ve final değiştirilerek ele alınır, hedef ziyaret sırası da sabitlenebilir veya serbest bırakılabilir
  • Planlama özelliği kısıt çözümü ile birleşerek, partition problem'de elemanları çıkarıp eşit toplamlara ayrılabilen en büyük alt listeyi bulma gibi problemleri de ifade edebilir
  • Picat bir araştırma dili olduğu için dokümantasyonu ve hata mesajları yetersizdir; ancak belirli hesaplama problemlerini hızlı çözmeye yönelik araç odaklı bir dil olarak genel amaçlı dillere kıyasla daha özlü çözümler sunabilir

Picat ve planner programlamanın temel fikri

  • Picat, mantıksal programlama, imperatif programlama ve kısıt çözümünü birleştirmeyi amaçlayan bir araştırma dilidir
  • Genel imperatif ve fonksiyonel programlamada girdiden çıktı üreten algoritmalar yazılır; mantıksal programlama ve kısıt çözümü ise ilişkileri sağlayan değer atamalarını bulur
  • Picat'ta küçük harfle başlayan fonksiyon dışı tanımlayıcılar a, b, c gibi atom'lardır; büyük harfle başlayan tanımlayıcılar ise değişkendir
  • Henüz tanımlanmamış Y değişkenini içeren member(Y, Arr) gibi ifadelerde de Picat, ifadeyi doğru yapan değerleri bulup atayabilir
    • Arr = [a, b, c, a] ise Y, a, b, c değerlerinden biri olabilir
    • Ardından X != Y gibi bir koşul eklerseniz olası değerler daha da daralır
    • member(a, Z) gibi listenin kendisi henüz bilinmiyorken bile Z bir liste olarak örneklenebilir

Planlama değer ataması değil, durum değişikliği arar

  • Planlama (planning), denklemleri sağlayan değişken değerlerini bulmak yerine, belirli bir bitiş durumuna ulaşan değişken değişikliği dizisini arar
  • Picat'ta bir planlama problemi için üç öğe gerekir
    • Başlangıç durumu Start
    • Durum geçişini temsil eden action fonksiyonları
    • Bir durumun bitiş durumu olup olmadığını belirleyen final(S)
  • Picat'taki action fonksiyonlarının hepsinin adı action olmalı ve dört parametre almalıdır
    • Mevcut durum
    • Sonraki durum
    • Aksiyon adı
    • Maliyet
  • best_plan(Start, Plan), bitiş durumuna kadar gerekli en kısa adımlı veya en düşük maliyetli planı Plan'a atar
    • Tüm maliyetler 1 yapılırsa planın maliyeti toplam hareket adımı sayısı olur
    • Uzunluğu fark etmeksizin herhangi bir plan yeterliyse plan(Start, Plan) kullanılabilir

Izgarada yol bulma örneği

  • Örnek problem, ızgara üzerindeki bir işaretçinin orijin (0, 0) noktasından başlayıp hedef koordinata ulaşmasıdır
    • Her adımda yukarı, aşağı, sola veya sağa bir kare hareket edebilir
    • Izgara sınırlarının dışına çıkamaz
    • Hedef koordinata varınca başarılı olur
  • Başlangıç durumu, {Origin, Goal} gibi mevcut konumu ve hedefi birlikte içerir
    • Picat'taki {a, b} dizi sözdizimidir ve pratikte tuple gibi kullanılır
  • final({Pos, Goal}) => Pos = Goal. şeklinde pattern matching ile bitiş koşulu ifade edilebilir
    • Aynı şeyi pattern matching olmadan yazmak için önce durumu {Pos, Goal} olarak ayrıştırmak gerekir
    • Birden fazla final koşulu varsa bunlardan herhangi biri doğru olduğunda plan başarılı olur
  • Hareket aksiyonu, dört yönden {-1,0}, {1,0}, {0,-1}, {0,1} birini seçer ve yeni koordinatın 0..10 aralığında olup olmadığını kontrol eder
    • member({Dx, Dy}, Dir) olası yön değerlerini bulmak için kullanılır
    • member(Tx, 0..10) ve member(Ty, 0..10) koordinatların sınır içinde olup olmadığını kontrol etmek için kullanılır
    • Değer atamayan, yalnızca kontrol amaçlı predicate olarak membchk de vardır
  • Sonuç planı {move,{1,0}}, {move,{2,0}} gibi hareket aksiyonu ve yeni koordinat listesinden oluşacak şekilde yazdırılır
    • Raku script'iyle yol görselleştirilebilir
    • {Tx, Ty} != {2, 1} gibi bir koşul eklenirse belirli koordinatlardan kaçınan engel kaçınma da mümkündür

Birden fazla hedef ve maliyet minimizasyonu

  • Birden fazla hedefi ziyaret etmek için Goal, tek bir koordinat yerine [{2, 2}, {3, 4}] gibi bir hedef kuyruğuna dönüştürülür
  • Hedefe varıldığında hedef listesinden ilgili öğeyi kaldıran yeni bir action eklenir
    • [Head|Tail], listeyi ilk eleman ve geri kalanı olarak ayırır
    • Goal = [Pos|Rest], yalnızca mevcut konum Pos hedef listesinin ilk öğesiyle aynı olduğunda doğru olur
    • Yeni durum {Pos, Rest} yapılırsa ulaşılan hedef kaldırılmış olur
  • Tüm hedeflerin ziyaret edilip edilmediği final({Pos, Goal}) => Goal = []. ile belirlenir
    • Bitiş koşulu artık mevcut konumun belirli bir hedefle aynı olup olmadığı değil, hedef listesinin boş olup olmadığıdır
  • Hedefleri belirlenmiş sırayla ziyaret etmek her zaman genel en kısa yolu üretmez
  • Hedef sırasını yok sayıp tüm yolu minimize etmek için mark aksiyonu değiştirilir
    • Goal = [Pos|Rest] yerine, mevcut konumun hedef listesinin herhangi bir yerinde bulunup bulunmadığı member(Pos, Goal) ile kontrol edilir
    • To = {Pos, delete(Goal, Pos)} ile ziyaret edilen hedef listeden kaldırılır
    • Bu yöntemde Picat bir sonraki gidilecek hedefi seçerek toplam yol uzunluğunu minimize edebilir

Planlama ve kısıt çözümünün birleşimi

  • Picat'ın planlama özelliği diğer Picat özellikleriyle bütünleşir; planlama ile kısıt çözümü birlikte kullanılabilir
  • Örnekte ele alınan partition problem, bir sayı listesini toplamları eşit iki gruba ayıran NP-complete bir problemdir
  • Bu program, sayı listesinden elemanlar çıkararak eşit toplamlara ayrılabilen en büyük alt listeyi bulur
    • Girdi sayı listesinden eleman çıkarmak bir plan aksiyonu olarak tanımlanır
    • final(Numbers), ilgili sayı listesi için geçerli bir partition çözümü olup olmadığını kontrol eder
    • cp modülünün kısıtlarıyla her elemanın sol veya sağ gruba girip girmediği 0..1 değişkeniyle ifade edilir
    • Toplamın bir taraftaki grubun toplamının iki katı olması için kısıt konur
  • Örnek çıktıda [5,17] çıkarıldıktan sonra kalan liste iki gruba ayrılarak her birinde 1108 toplamı elde edilebilir
    • 32+99+977=1108
    • 122+77+86+59+47+154+141+172+49+62+109+30=1108
  • Bu yöntem, geçerli kısıtları doğrudan çözmekle kalmaz; geçerli bir kısıt durumuna ulaşmak için gereken değişiklikleri de plan olarak ifade eder

Picat kullanırken sınırlamalar ve uygun kullanım alanları

  • Picat bir araştırma dili olduğu için prodüksiyon kullanımı önerilmez
  • Konfor sağlayan özellikleri çok değildir; iyi dokümantasyon veya açık hata mesajları da yetersizdir
    • Çözülebilir bir plan olmadığında hata *** error(failed,main/0) şeklinde yazdırılır
  • Windows'ta çalışabilmesi, birçok araştırma diline kıyasla daha iyi bir özellik olarak değerlendirilir
  • Picat, bakımı yapılacak veya paylaşılacak kod yazmaya yönelik bir dilden ziyade, belirli türde hesaplama problemlerini çözmek için kullanılan bir toolkit diline daha yakındır
  • Genel programlama dilleri ve kısıt çözücülerle ele alınması zor olan bazı problemler Picat ile oldukça zarif biçimde çözülebilir

Diğer planlama dilleri ve ilgili kavramlar

  • Planlama aslında robotik ve AI alanlarında öncülük edilen bir konudur; günümüzde ise video oyunu AI'ında Goal Oriented Action Planning (GOAP) adıyla sık kullanılır
  • PDDL, bağımsız planlayıcıların girdi olarak aldığı bir planlama betimleme dilidir
    • SAT'te DIMACS'ın betimleme biçimi olarak kullanılmasına benzer bir rol oynar

İlgili okumalar

1 yorum

 
GN⁺ 2024-02-22
Hacker News yorumları

  • Picat’in planlama modunu gerçek işte kullandım
    Birden çok ekipman grubunun bakımını koordine eden bir sistemin prototipini yaptım; “nasıl yapılacağını” değil, “ne istediğini”, “hangi eylemlerin mümkün olduğunu” ve “hangi kısıtların korunması gerektiğini” girdi olarak veriyordunuz
    Küçük örneklerde en iyi planları iyi üretiyordu ama gerçek ölçeğe çıkınca beklendiği gibi dağıldı; planlama problemleri sonuçta EXPTIME olduğu için sınırları büyüktü
    Picat’te sezgiseller tanımlamak için bir kaçış yolu var; ben de durum yüklemlerinin random forest ve naive Bayes sınıflandırıcılarıyla umut vadeden yolları tahmin ettirdim, ama simetri kırma kısıtları ve hiyerarşik planlama ekleyince bile çok fazla el emeği gerektirdi
    Klasik GOFAI problem alanlarında hâlâ bir yapay zeka kışı var gibi
    Planlama problemi “potansiyel olarak üstel uzunlukta plan üreten polinom zamanlı bir üreteç” döndürecek şekilde yeniden formüle edilirse belki olmayabilir

    • Ticari çözücüler açık kaynaklı olanlardan performans açısından çok daha iyi; cüzdanı da çok daha hızlı boşaltıyorlar
      Aklıma CPLEX, Xpress, GUROBI, Hexaly geliyor; Hexaly özellikle çizelgeleme veya araç rotalama problemlerinde iyi
      Genelde sektörde yaygın kullanılan diller için API’lerle erişiliyor; bunun, genel amaçlı işlerde zayıf kalan özel çözücü dillerinden çok daha mantıklı olduğunu düşünüyorum
      Python’dan GUROBI çağırmak çok kolay ve Python’ın genel özelliklerini de aynen kullanabiliyorsunuz
      Mosek, GUROBI’den çok daha ucuz ama ikisinin API’si de oldukça düşük seviyeli ve performansı da GUROBI kadar iyi değil
    • Bu durumda CP-SAT(https://developers.google.com/optimization/cp) gibi bir şeyin iyi ölçeklenmiş olması muhtemel
      Bu çözücü akıl almaz sayıda değişken ve kısıtı kolayca işliyor; yerleşik sezgiselleri de harika
    • Eski planlayıcılar arama uzayını daraltmak için hangi kuralın uygulanacağını belirleyen meta kurallar veya sezgiseller içerirdi
      Bazı sistemler problemi farklı temsillere ayırıp bunlara özelleşmiş otomatik çözücüler bağlardı
      Aklıma Jahob Analysis System ve Cyc geliyor
      Pratik kullanım açısından klasik yapay zekadaki en temiz tasarım Procedural Reasoning System’dı; zayıf yanları modern yöntemlerle tamamlanmış, yeniden yapılmış bir sürümünü görmek isterdim
      https://en.wikipedia.org/wiki/Procedural_reasoning_system
    • Neden yüksek kaliteli açık kaynak çözücüler yok merak ediyorum
      Diğer sayısal hesaplama alanlarında en güncel teknolojinin çoğu zaman açık kaynak olduğunu görüyoruz; optimizasyon alanı neden farklı, hep merak etmişimdir
    • Sonuçlar ya da performans açısından bakınca, Prolog’u belli belirsiz hatırlayarak kabaca yazılmış bir derinlik öncelikli aramadan gerçekten çok farklı değil gibi geliyor

  • Kısıt programlama topluluğunda aktif bir HN kullanıcısı olan hakank, yani Hakan Kjellerstrand, Picat materyalleri ve örneklerini topladığı bir siteye sahip: http://www.hakank.org/picat/

  • Her zamanki gibi Prolog önermek isterim
    Zarif, anlaşılması kolay ve daha olgun; sonlu alan kısıt çözümü istiyorsanız temel kurulumuyla bile yeterli
    Bunun dışında MiniZinc, farklı amaçlara özelleşmiş birçok çözücüye erişmek için harika bir arayüz; uzman değilseniz istediğiniz sonuca daha yakın olmanız muhtemel
    Prolog’un pek çok avantajı var ama iyi performans almak için gereken “mekanik sezgi” hızla epey ciddi bir seviyeye çıkabiliyor
    Picat ile bir şey yazdıysanız, aynı şeyi başka dillerde nasıl yazacağınızı da düşünmek iyi olur
    Bu tür oyuncak problemler diğer dillerde de kolaydır; çoğu fonksiyonel dilde Dijkstra ya da A* birkaç satırdır ve çoğu zaman mesele, arama algoritmasının durum uzayını tanımlamaktan ibarettir

  • İnceleyenlerden biri olarak Predrag’ı görmek sevindiriciydi ama aynı zamanda hiç şaşırtıcı değildi
    Firebase technical screen böyle bir araç olsaydı çok daha kolay olurdu gibi geliyor; sonuçta o da bir başka optimizasyon problemiydi
    Picat ile yeniden çözmeyi de istiyorum
    Programlama dilleri tarafında da ilginç işler yapıyor: https://github.com/obi1kenobi/trustfall

  • İlk düşündüğüm şey “kendi kendine çözmen gereken bir tip sistemi gibi” oldu
    TypeScript’te naifçe ifade etmeye çalıştım ama a, b, c hepsi aynı olabildiği için hiçbir şey çözülmedi
    Doğru ifade etmeye çalışınca bir ölçüde kullanılabilir görünen bir biçime kadar geldim ama hâlâ assertion kullanıyor ve Y’nin tipini de düzgün ifade edemiyor
    Bu süreç, planlayıcı tarzı programların sadelik ve kısalık açısından ne kadar güçlü olduğunu aksine gösteriyor
    TypeScript bu tür kısıtları ifade edecek kadar güçlü değil gibi
    Denediğim TS Playground bağlantısı: http://tinyurl.com/3p2pzdtn

  • GOAP’ın yeniden anıldığını görmek güzel
    F.E.A.R.’daki düşmanların bu kadar eğlenceli olmasının gizli sosu buydu; Jeff Orkin’in nasıl çalıştığına dair makalesi de okunması kolay ve keyifli

  • Prolog ve biraz CLPFD’yi gerçek işte kullanıyorum; gerçekten çok iyi
    Her yerde olmasını isterdim; daha doğrusu saflığı vurgulayan mantıksal bir çekirdek bırakıp imperatif davranışları kenarlara itmek isterdim
    Sektörün bu kadar kötü araçlara sıkışmış gibi görünmesi üzücü

  • Prolog’a benziyor ve ilginç görünüyor

  • Bu programlama biçiminin kendisi tamamen yeni değil
    Üniversitede Prolog öğrenmiştim ve epey benzer görünüyor ama Prolog’da planlayıcı özelliği yoktu
    Yine de planlayıcı, problem çözmenin çok zarif ve basit bir yolu
    Yazının sonundaki video oyunu kısmını görünce merak ettim
    Planlayıcı özelliği birkaç satır açık kodla problemi çok kolay çözdürüyor ama imperatif yazılmış algoritmalarla karşılaştırınca performansı nasıl olur?
    Picat benzer dillerle karşılaştırıldığında oldukça verimli gibi [1], ama “standart” dillerle karşılaştırma bulamadım
    [1]: https://arxiv.org/abs/1405.2538

  • Bilgisayara yalnızca ulaşılması gereken durumu söyleme hayali bende de var
    Planlama topluluğunu veya çözücüleri pek bilmiyorum; ortools ile naifçe biraz uğraşmışlığım var, ama A* ile bir durumdan hedef duruma giden kod üretmeyi denemiştim
    Durumlar arasında hareket etmek için assembly komutları üretiyor, fonksiyon çağrılarının gizli durum geçişlerini bile bulup hedefe ulaşıyordu
    Aramayı hızlandırmak için Python multiprocessing ile paralel çalıştırdım; her iş parçacığında komşu üretimi farklı olduğundan dinamik komşu üretimi kullandım
    İlk denemede A*’ı paralelleştirmek zor olduğu için sharding gerekiyordu
    Deneyimin hayali, bilgisayara “şu anda elimde olanı” ve “istediğimi” söyleyince doğru geçiş yolunu kendi kendine bulması
    Kişisel olarak programlamayı Factorio’ya ya da bir fabrika gibi lojistiğe yakın görüyorum
    Bu yüzden buna “sliding puzzle” diyorum; doğru resmi görmek için nesneleri oradan oraya taşımanız gereken bir bulmaca olduğu için
    GitHub deposu ve notlar: https://github.com/samsquire/sliding-puzzle-codegen-memory
    Replit: https://replit.com/@Chronological/SlidingPuzzle3