प्लानर प्रोग्रामिंग इतनी हैरान करने वाली क्यों है

 (hillelwayne.com)
2 पॉइंट द्वारा GN⁺ 2024-02-22 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Picat का planner मॉड्यूल वैल्यू असाइनमेंट खोजने वाली logic programming से एक कदम आगे जाकर, लक्ष्य स्थिति तक पहुँचने वाले state changes की sequence को समस्या के रूप में व्यक्त करता है
  • शुरुआत की स्थिति Start, transition rule action(From, To, Action, Cost), और समाप्ति शर्त final(S) परिभाषित करने पर best_plan(Start, Plan) अंतिम स्थिति तक का minimum-cost plan ढूँढ देता है
  • grid path वाले उदाहरण में movement, boundary limits, obstacles से बचना, और कई goals visit करना सिर्फ action और final बदलकर संभाला जाता है; goal visit order को fixed या flexible भी रखा जा सकता है
  • planning feature constraint solving के साथ मिलकर, partition problem में elements हटाकर equal sum में बाँटी जा सकने वाली सबसे बड़ी sublist खोजने जैसे problems भी express कर सकता है
  • Picat एक research language है, इसलिए documentation और error messages कमज़ोर हैं, लेकिन specific computational problems को तेजी से solve करने के लिए tool-oriented language के रूप में यह general languages से ज्यादा concise solutions दे सकता है

Picat और planner programming का basic idea

  • Picat एक research language है जो logic programming, imperative programming, और constraint solving को जोड़ने की कोशिश करती है
  • सामान्य imperative और functional programming में input से output बनाने वाला algorithm लिखा जाता है, लेकिन logic programming और constraint solving में relation को satisfy करने वाले value assignments खोजे जाते हैं
  • Picat में lowercase से शुरू होने वाले non-function identifiers a, b, c जैसे atom होते हैं, और uppercase से शुरू होने वाले identifiers variables होते हैं
  • अभी define न किए गए variable Y वाला member(Y, Arr) जैसा expression हो, तब भी Picat expression को true बनाने वाली value खोजकर assign कर सकता है
    • अगर Arr = [a, b, c, a] है, तो Y a, b, c में से कोई एक हो सकता है
    • इसके बाद X != Y जैसी condition डालने पर possible values और narrow हो जाती हैं
    • member(a, Z) की तरह list खुद अभी unknown हो, तब भी Z को list के रूप में instantiate किया जा सकता है

Planning value assignment नहीं, state changes खोजती है

  • Planning में equation को satisfy करने वाली variable values खोजने के बजाय, किसी specific final state तक पहुँचने वाली variable changes की sequence खोजी जाती है
  • Picat की planning problem में तीन elements चाहिए
    • start state Start
    • state transition दिखाने वाले action functions
    • state final state है या नहीं, यह तय करने वाला final(S)
  • Picat के सभी action functions का नाम action होना चाहिए, और वे चार parameters लेते हैं
    • current state
    • next state
    • action name
    • cost
  • best_plan(Start, Plan) final state तक जरूरी shortest-step या minimum-cost plan को Plan में assign करता है
    • अगर सभी costs 1 रखे जाएँ, तो plan की cost total movement steps की संख्या बनती है
    • अगर length कुछ भी हो और सिर्फ कोई भी plan चाहिए, तो plan(Start, Plan) इस्तेमाल किया जा सकता है

Grid path finding example

  • example problem में grid पर marker origin (0, 0) से शुरू होकर target coordinates तक पहुँचता है
    • हर step में ऊपर/नीचे/बाएँ/दाएँ एक cell move किया जा सकता है
    • grid boundary के बाहर नहीं जा सकते
    • target coordinates पर पहुँचने पर success होता है
  • start state {Origin, Goal} की तरह current position और goal को साथ रखता है
    • Picat का {a, b} array syntax है और practically tuple की तरह इस्तेमाल होता है
  • final({Pos, Goal}) => Pos = Goal. की तरह pattern matching से final condition express की जा सकती है
    • यही चीज pattern matching के बिना लिखनी हो, तो state को पहले {Pos, Goal} में decompose करना होगा
    • अगर कई final conditions हैं, तो उनमें से कोई एक भी true होने पर plan successful होता है
  • move action चार directions {-1,0}, {1,0}, {0,-1}, {0,1} में से एक चुनता है, और जाँचता है कि new coordinates 0..10 range में हैं या नहीं
    • member({Dx, Dy}, Dir) possible direction values खोजने के लिए इस्तेमाल होता है
    • member(Tx, 0..10) और member(Ty, 0..10) coordinates boundary के अंदर हैं या नहीं, यह check करने के लिए इस्तेमाल होते हैं
    • value assign न करने वाले check-only predicate के रूप में membchk भी है
  • result plan {move,{1,0}}, {move,{2,0}} की तरह move action और new coordinates की list के रूप में print होता है
    • Raku script से path visualize किया जा सकता है
    • {Tx, Ty} != {2, 1} जैसी condition जोड़ने पर specific coordinates से बचने वाला obstacle avoidance भी संभव है

कई goals और cost minimization

  • कई goals visit करने के लिए Goal को single coordinate की जगह [{2, 2}, {3, 4}] जैसी goal queue में बदलते हैं
  • goal पर पहुँचने पर goal list से उस item को हटाने वाला नया action add करते हैं
    • [Head|Tail] list को first element और बाकी हिस्से में बाँटता है
    • Goal = [Pos|Rest] तभी true होता है जब current position Pos goal list के first item के बराबर हो
    • new state को {Pos, Rest} रखने पर पहुँचा हुआ goal हट जाता है
  • सभी goals visit हुए या नहीं, यह final({Pos, Goal}) => Goal = []. से तय होता है
    • current position किसी specific goal जैसी है या नहीं, इसकी बजाय final condition यह बनती है कि goal list empty है या नहीं
  • goals को fixed order में visit करने का तरीका हमेशा overall shortest path नहीं बनाता
  • goal order ignore करके overall path minimize करना हो, तो mark action बदलते हैं
    • Goal = [Pos|Rest] की जगह member(Pos, Goal) से check करते हैं कि current position goal list में कहीं भी शामिल है या नहीं
    • To = {Pos, delete(Goal, Pos)} से visited goal को list से हटाते हैं
    • इस तरीके में Picat next goal चुनकर overall path length minimize कर सकता है

Planning और constraint solving का combination

  • Picat की planning capability अन्य Picat features के साथ integrated है, और planning तथा constraint solving को साथ इस्तेमाल किया जा सकता है
  • example में लिया गया partition problem numbers की list को equal sum वाले दो groups में बाँटने का NP-complete problem है
  • यह program numbers की list से elements हटाकर, equal sum में बाँटी जा सकने वाली सबसे बड़ी sublist खोजता है
    • input number list से elements हटाने को planning action बनाया गया है
    • final(Numbers) check करता है कि उस number list के लिए valid partition solution है या नहीं
    • cp module की constraints से हर element left या right group में जाता है या नहीं, इसे 0..1 variable से express किया जाता है
    • constraint रखा जाता है कि total sum एक side के group sum का double हो
  • example output में [5,17] हटाने के बाद बची list को दो groups में बाँटकर हर एक का sum 1108 बनाया जा सकता है
    • 32+99+977=1108
    • 122+77+86+59+47+154+141+172+49+62+109+30=1108
  • यह तरीका सिर्फ valid constraints को directly solve करने तक सीमित नहीं रहता, बल्कि valid constraint state तक पहुँचने के लिए changes को भी plan के रूप में express करता है

Picat इस्तेमाल करते समय limitations और suitable use cases

  • Picat research language है, इसलिए production use के लिए recommended नहीं है
  • इसमें convenience features ज्यादा नहीं हैं, और अच्छी documentation या clear error messages भी कम हैं
    • जब कोई solvable plan न हो, तो error *** error(failed,main/0) की तरह print होता है
  • Windows पर run कर पाना कई research languages की तुलना में बेहतर माना गया है
  • Picat maintain या share किए जाने वाले code लिखने की language से ज्यादा, specific kinds के computational problems solve करने की toolkit language के करीब है
  • general programming languages और constraint solvers से जिन कुछ problems को handle करना कठिन था, उन्हें Picat से काफी elegant तरीके से solve किया जा सकता है

दूसरी planning languages और related concepts

  • Planning की शुरुआत मूल रूप से robotics और AI में हुई थी, लेकिन आजकल video game AI में इसे अक्सर Goal Oriented Action Planning(GOAP) नाम से इस्तेमाल किया जाता है
    • आम तौर पर इसे दूसरी language के ऊपर library के रूप में बनाया जाता है, या custom search strategy से implement किया जाता है
    • GOAP के बारे में explanation इस resource में देखा जा सकता है
  • PDDL एक planning description language है जिसे standalone planners input के रूप में लेते हैं
    • यह SAT में DIMACS के description format के रूप में इस्तेमाल होने जैसी भूमिका निभाता है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-02-22
Hacker News की राय

  • Picat का planning mode असली काम में इस्तेमाल किया है
    कई equipment groups के maintenance को coordinate करने वाला एक system prototype बनाया था, और तरीका यह था कि “कैसे करना है” नहीं, बल्कि “क्या चाहिए”, “कौन-से actions संभव हैं”, “कौन-सी constraints माननी हैं” input किए जाते थे
    छोटे examples में यह optimal plan अच्छी तरह बनाता था, लेकिन जैसे ही असली scale तक बढ़ा, उम्मीद के मुताबिक टूट गया, और planning problem आखिरकार EXPTIME है, इसलिए सीमाएं बड़ी थीं
    Picat में heuristics define करने का एक escape hatch है, इसलिए state predicates के random forest और naive Bayes classifier से promising paths predict करवाए, लेकिन symmetry-breaking constraints और hierarchical planning जोड़ने के बाद भी बहुत ज्यादा manual work लगा
    classic GOFAI problem domains में लगता है अभी भी AI winter बची हुई है
    अगर planning problem को इस तरह reformulate किया जाए कि वह “potentially exponentially long plan generate करने वाला polynomial-time generator” लौटाए, तो शायद बात अलग हो

    • commercial solvers open source की तुलना में performance में भी बहुत बेहतर हैं और wallet भी बहुत तेजी से खाली करवाते हैं
      CPLEX, Xpress, GUROBI, Hexaly याद आते हैं, और Hexaly scheduling या vehicle routing problems में खास तौर पर अच्छा है
      आम तौर पर industry में ज्यादा इस्तेमाल होने वाली languages के API से access किया जाता है, और मुझे लगता है कि general-purpose tasks में कमजोर dedicated solver languages की तुलना में यह तरीका कहीं ज्यादा practical है
      Python से GUROBI call करना बहुत आसान है, और Python की normal features भी वैसे ही इस्तेमाल कर सकते हैं
      Mosek, GUROBI से बहुत सस्ता है, लेकिन दोनों के API बहुत low-level हैं और performance भी GUROBI जैसी नहीं है
    • इस case में CP-SAT(https://developers.google.com/optimization/cp) जैसी चीज शायद अच्छे से scale हुई होती
      यह solver absurdly बड़ी संख्या में variables और constraints आसानी से handle करता है, और built-in heuristics भी शानदार हैं
    • पुराने planners search space कम करने के लिए कौन-सा rule apply करना है, यह तय करने वाली meta rules या heuristics शामिल करते थे
      कुछ systems problem को अलग-अलग representations में बांटकर specialised automatic solvers लगाते थे
      Jahob Analysis System और Cyc याद आते हैं
      practical use के लिहाज से classic AI में सबसे साफ design Procedural Reasoning System था, और इसकी कमजोरियों को modern methods से पूरा करके बना कोई नया version देखना चाहूंगा
      https://en.wikipedia.org/wiki/Procedural_reasoning_system
    • सोचता हूं कि high-quality open source solvers क्यों नहीं हैं
      बाकी numerical computing fields में अक्सर state-of-the-art open source होता है, लेकिन optimization field अलग क्यों है, यह हमेशा सवाल रहा
    • results या performance के हिसाब से देखें, तो यह Prolog की धुंधली याद के साथ जल्दी में लिखे गए depth-first search से असल में बहुत अलग नहीं लगता

  • constraint programming community में active HN user hakank, यानी Hakan Kjellerstrand, ने Picat material और examples की बहुत सारी चीजें इकट्ठा करके एक site बनाई है: http://www.hakank.org/picat/

  • हमेशा की तरह Prolog recommend करना चाहूंगा
    elegant है, समझने में आसान है और ज्यादा mature है, और अगर finite-domain constraint solving चाहिए तो basic setup ही काफी है
    इसके अलावा MiniZinc अलग-अलग purposes के लिए specialised कई solvers तक पहुंचने का शानदार interface है, इसलिए अगर आप expert नहीं हैं तो आपके desired result के करीब पहुंचने की संभावना ज्यादा है
    Prolog के बहुत फायदे हैं, लेकिन अच्छी performance निकालनी हो तो जरूरी “mechanical sympathy” जल्दी ही काफी ज्यादा हो सकती है
    अगर आपने Picat में कुछ लिखा है, तो यह भी सोचें कि वही चीज दूसरी languages में कैसे लिखेंगे
    ऐसे toy problems दूसरी languages में भी आसान हैं, और ज्यादातर functional languages में Dijkstra या A* कुछ lines में हो जाता है; आखिर में अक्सर बस search algorithm का state space define करना ही काम होता है

  • reviewer के रूप में Predrag को देखकर अच्छा लगा, लेकिन बिल्कुल surprise भी नहीं हुआ
    Firebase technical screen ऐसे tool के साथ बहुत आसान रहा होता, और आखिरकार यह भी एक और optimization problem था
    इसे Picat में फिर से solve करके देखने का मन भी होता है
    वह programming languages की तरफ भी दिलचस्प काम कर रहे हैं: https://github.com/obi1kenobi/trustfall

  • पहला खयाल आया कि “यह तो ऐसा type system है जिसे खुद solve करना पड़ता है”
    TypeScript में naive तरीके से express करने की कोशिश की, लेकिन a, b, c सभी समान हो सकते थे, इसलिए कुछ solve नहीं हुआ
    ठीक से express करने की कोशिश करते-करते एक हद तक usable लगने वाले form तक पहुंचा, लेकिन अभी भी assertions इस्तेमाल करने पड़ते हैं और Y का type भी ठीक से express नहीं हो पाता
    यह process उल्टा दिखाता है कि planner-style programs simplicity और conciseness में कितने powerful हैं
    लगता है TypeScript इस तरह की constraints express करने लायक powerful नहीं है
    experiment वाला TS Playground link: http://tinyurl.com/3p2pzdtn

  • GOAP का फिर से mention होता देखना अच्छा लगा
    F.E.A.R. के enemies इतने मजेदार थे, इसका secret sauce वही था, और Jeff Orkin का working-style paper भी पढ़ने में आसान और मजेदार है

  • Prolog और थोड़ा CLPFD असली काम में इस्तेमाल कर रहा हूं और यह सच में अच्छा है
    काश यह हर जगह होता, और ज्यादा सही कहूं तो purity पर जोर देने वाला logic core हो और imperative behavior को edges पर धकेल दिया जाए
    दुख होता है कि industry ऐसे खराब tools में फंसी हुई लगती है

  • Prolog जैसा दिखता है और दिलचस्प है

  • यह programming style अपने आप में पूरी तरह नई नहीं है
    university में Prolog पढ़ा था और यह काफी similar लगता है, लेकिन Prolog में planner functionality नहीं थी
    हालांकि planner problem solve करने का बहुत elegant और simple तरीका है
    article के end में videogame वाला हिस्सा देखकर curiosity हुई
    planner functionality कुछ lines के साफ code से problem को बेहद आसानी से solve करा देती है, लेकिन imperative तरीके से लिखे algorithm से compare करें तो performance कैसी होगी?
    Picat similar languages की तुलना में काफी efficient लगता है [1], लेकिन “standard” languages से comparison नहीं मिला
    [1]: https://arxiv.org/abs/1405.2538

  • computer को सिर्फ वह state बताने का सपना मेरा भी है, जहां पहुंचना है
    planning community या solvers के बारे में ज्यादा नहीं जानता और ortools को naive तरीके से थोड़ा आजमाया है, लेकिन मैंने A* से एक state से target state तक जाने वाला code generation किया है
    states के बीच move करने के लिए assembly instructions generate किए, और function calls के hidden state transitions तक खोजकर target तक पहुंचा
    search तेज करने के लिए Python multiprocessing से parallel execution भी किया, और हर thread में neighbour generation अलग था, इसलिए dynamic neighbour generation इस्तेमाल किया
    original attempt में A* को parallelize करना मुश्किल था, इसलिए sharding की जरूरत पड़ी
    मेरे experiment का सपना है कि computer को “अभी मेरे पास क्या है” और “मुझे क्या चाहिए” बताएं, तो वह सही movement path खुद ढूंढ निकाले
    personally, programming मुझे Factorio या factory जैसी logistics लगती है
    इसलिए मैं इसे “sliding puzzle” कहता हूं, क्योंकि यह ऐसी puzzle है जिसमें सही picture देखने के लिए चीजों को इधर-उधर move करना पड़ता है
    GitHub repository और notes: https://github.com/samsquire/sliding-puzzle-codegen-memory
    Replit: https://replit.com/@Chronological/SlidingPuzzle3