7 ms·
Planner programming blows my mind
- rad_gruchalski 3y agoLooks Prolog-ish. Interesting, thanks for sharing.
- hwayne 3y agoAFAICT Picat is a direct descendant of B-Prolog and shares a lot of idioms (like tabling) with it. https://en.wikipedia.org/wiki/B-Prolog https://en.wikipedia.org/wiki/B-Prolog
- OhMeadhbh 3y agoTHX for the reference. I used Prolog a fair amount in the 90s, but didn't know about B-Prolog. Now I do. And I came here to make @rad_gruchalski's comment. So... thx for making that comment so I don't have to.
- hakank 3y agoYes, the underlying engine of Picat is - a slightly altered- B-Prolog, which is available as the "bp" module, from which one can use many of traditional Prolog constructs, for example `bp.length/2` instead of Picat's `length/1` function. This can help when porting Prolog programs to Picat. In fact, quite a few Prolog programs can be run directly in Picat, perhaps with just some few adjustment. For some example of the available predicates in the bp module, see my http://hakank.org/picat/v3_utils.pi http://hakank.org/picat/v3_utils.pi . Also, see http://hakank.org/picat/#v3 http://hakank.org/picat/#v3 for some examples of ported Prolog programs.
- sterlind 3y agoI've actually used Picat's planning mode at work! I prototyped a system to orchestrate maintenance on fleets of devices. The idea was that, rather than telling the system how to do it (e.g. workflows to roll out an update), you'd tell the system what you wanted (e.g. up to date machines), what actions were available (e.g. pull a machine from rotation, apply an update), and what constraints to obey (e.g. X of Y machines must be online, don't work in more than two regions simultaneously.) I modeled a few scenarios like that in Picat and had it generate optimal plans. It worked swimmingly for pet problems, but predictably fell over scaling to cattle sizes. Planning is EXPTIME after all (e.g. Towers of Hanoi).* Picat does have an escape hatch - you can define heuristics - so I built a random forest of state predicates and trained a naive Bayes classifier to predict fruitful paths. But even with that, and symmetry breaking constraints, and even some hierarchical planning, I couldn't make it work without too much handholding. It's still AI winter for the classic GOFAI problem domains, apparently. :/ * maybe not, actually, if you reformulate the planning problem as returning a polynomial-time generator of a potentially exponentially long plan
- polivier 3y agoIt is possible that something like CP-SAT (https://developers.google.com/optimization/cp https://developers.google.com/optimization/cp) would have scaled well in your case. This solver easily handles an absurd amount of variables and constraints, and has excellent heuristics built-in.
- nickpsecurity 3y ago"Planning is EXPTIME after all (e.g. Towers of Hanoi).*" The old planners would include meta-rules, or heuristics, that decided which rules to apply. That would cut the search space. Some split the problem into different representations with specialized, automated solvers. Jahob Analysis System and Cyc come to mind. Far as for real-world use, the neatest design I remember from classic A.I. was the Procedural Reasoning System. I've always wanted to see a version of it rebuilt with modern methods supplementing its weaknesses. Just for kicks and to see what it could do. https://en.wikipedia.org/wiki/Procedural_reasoning_system https://en.wikipedia.org/wiki/Procedural_reasoning_system
- OJFord 3y agoSo it's not actually different (in result/performance) from the depth-first search you'd get naïvely mashing some keys dimly recalling prolog?
- 7thaccount 3y agoThere are plenty of commercial solvers out there that beat the pants off the open source options in terms of performance and in terms of depleting one's wallet :) CPLEX, Xpress, GUROBI, and Hexaly all come to mind. Hexaly is really good for scheduling problems and things like vehicle routing. You typically access these via an API they offer you for the popular industry languages. This approach seems to make a lot more sense to me than having a dedicated solver language that isn't as good for all the general purpose stuff. Calling GUROBI from Python is a breeze as is all the standard stuff in Python. Mosek is a lot cheaper than GUROBI, but both of it's APIs are extremely low level and the performance isn't as good as GUROBI either.
- shoo 3y ago
- polivier 3y agoFor those interested, HN user hakank (Hakan Kjellerstrand), who is a very active member of the constraint programming community (among others), has a ton of Picat resources and examples on his website: http://www.hakank.org/picat/ http://www.hakank.org/picat/
- deleted 3y ago[deleted]
- pcthrowaway 3y agoMy first thought was, this looks like a type system, except you need to solve it yourself. In Typesecript, naively: const main = <a extends any, b extends any, c extends any>([a_, b_, c_]: [a, b, c, a]) => { type SomeTuple = [a, b, c, a]; const X: a = a_; const Y: Exclude<SomeTuple, a> // = <put solved value here, get a type error if the value does not satisfy the constraints> console.log(X, Y); } Except nothing solves this because a, b, and c can all be the same. After trying to express this correctly, I ended up with something that appears useable (but that still uses assertions and doesn't really express the type of Y correctly). type Narrowable = string | number | bigint | boolean; /* Express the type of a value in a tuple that is not the type of the second parameter For example: - ValOfTupleExceptFor<[1,1,6,2,3], 1> -> 6 - ValOfTupleExceptFor<[1,1,6,2,3], 6> -> 1 */ type ValOfTupleExceptFor< Tup extends readonly Narrowable[], Val extends Tup[number] > = Tup extends [infer First, ...(infer Rest extends Narrowable[])] ? First extends Val ? Rest extends [] ? never : ValOfTupleExceptFor<Rest, Val> : First : never; const NO_SOLUTION: unique symbol = Symbol('NO_SOLUTION') const getValOfTupleExcluding = (tup: readonly Narrowable[], val: (typeof tup)[number]): ValOfTupleExceptFor<typeof tup, typeof val> => { const [first, ...rest] = tup; if (!first) { return NO_SOLUTION as never; } if (first === val) { return getValOfTupleExcluding(rest, val); } return first as ValOfTupleExceptFor<typeof tup, typeof val>; } const main = <a extends Narrowable, b extends Narrowable, c extends Narrowable>([a_, b_, c_]: [a, b, c, a]) => { const someTuple = [a_, b_, c_, a_] as const; const X: a = a_; // This still resolves to type 'never' const Y: ValOfTupleExceptFor<typeof someTuple, a> = getValOfTupleExcluding(someTuple, a_); console.log(X, Y); } Which really highlights how powerful the 'planner' style program is in terms of simplicity and conciseness. I guess Typescript isn't even powerful enough to express this kind of constraint. edit: TS playground link with some experiments if anyone's interested: http://tinyurl.com/3p2pzdtn http://tinyurl.com/3p2pzdtn
- bloaf 3y agoI'm a little confused about how planning is different from vector reachability, which, from what I understand, has Ackermann complexity rather than EXPTIME. Can anyone help me out with the constraints on "planning" that allow it to be solved in a sane amount of time? https://www.quantamagazine.org/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204/ https://www.quantamagazine.org/an-easy-sounding-problem-yiel...
- nickpsecurity 3y agoWe normally pick up stuff like that in papers, blog posts, etc. The only heuristics book I remember was How to Solve It. I also found a survey paper on heuristics. Here they are in case they help: https://www.amazon.com/How-Solve-Heuristics-Zbigniew-Michalewicz/dp/3540224947 https://www.amazon.com/How-Solve-Heuristics-Zbigniew-Michale... https://www.jsoftware.us/vol7/jsw0709-23.pdf https://www.jsoftware.us/vol7/jsw0709-23.pdf
- eru 3y ago> [...] from what I understand, has Ackermann complexity rather than EXPTIME. Really bad worst case times aren't necessarily bad in practice, if most instances you actually encounter can be solved quickly (especially if you are happy to be satisfied with worse than proven-optimal solutions.) Compare how Hindley-Milner type inference, which forms the basis of Rust's or Haskell's type systems, is double-exponential in the worst case (or something like that), but typically fast in practice.
- mfunk_ 3y agoI think in classic planning like STRIPS, the size of the state space is bounded exponentially in the size of the input (conditions can be either true or false). This is not the case of vector reachability. I'm not familiar with picat, but the arithmetic operations used in the blog post suggest to me that the size of the state space is not necessarily bounded by the input. I believe the mention of EXPTIME in the post was removed.
- hwayne 3y agoGeneral planning is undecidable; you can pretty easily encode a Turing machine as actions and make the goal state `Halt`.
- fumeux_fume 3y agoIs this related to Answer Set Programming? Seems like there’s an overlap.
- sterlind 3y agothey're syntactically related in that both come from the Prolog world, and you can indeed use ASP to do planning (there's examples of Towers of Hanoi and Blockworld in the ASP guidebook), and you can incorporate heuristics into ASP. ...but actually they're really different! ASP isn't Turing-complete - it's a lot more like an SMT solver. crucially, there's a grounding stage, where the set of every expressible term in the model (its Herbrand universe) is explicitly written down. so if you have e.g. `f(a;b). g(X,Y) :- f(X),f(Y).` then it will write out every expansion of g during pre-processing. this makes ASP very powerful, and very fast even at complex problems, but it dooms the solver if the universe is large. in contrast, Picat is basically a souped up Prolog. it's a full programming language, and it doesn't require grounding so infinite state spaces are okay. it leverages its tabling mechanism to memo-ize predicates evaluation, and it automatically manages the time/space tradeoff with search, which is nifty. but at the end of the day it's brute force, not deep witchcraft like Z3.
- fumeux_fume 3y agoI see, thanks for your explanation!
- sgt101 3y agosorry what is Z3?
- phi-go 3y agohttps://github.com/Z3Prover/z3 https://github.com/Z3Prover/z3 Here is an actual description: https://z3prover.github.io/papers/programmingz3.html#sec-intro https://z3prover.github.io/papers/programmingz3.html#sec-int...
- crabmusket 3y agoNice to see GOAP being referenced again. It was the secret sauce that made F.E.A.R.'s enemies so fun. And Jeff Orkin's paper on how it works is very readable and entertaining.
- asciimike 3y agoPleasantly surprised to see Predrag show up as a reviewer, but at the same time not at all surprised: - The [Firebase technical screen](https://startupandrew.com/posts/how-firebase-interviewed-software-engineers/ https://startupandrew.com/posts/how-firebase-interviewed-sof...) would have been much easier with something like this, as it was Just Another Optimization Problem™. Part of me wants to try it again with Picat! - He's doing other very interesting things with programming languages, e.g.: https://github.com/obi1kenobi/trustfall https://github.com/obi1kenobi/trustfall
- Guthur 3y agoI've actually been using Prolog professionally including some CLPFD, and I love it. I want it everywhere. Or more precisely i want a logical core with emphasis on purity and push imperative action to the edges. It so sad that as an industry we seemed locked into really bad tools.
- cwillu 3y agoReally hating the trend of putting half of the document behind series of “click here to unhide the content” dropdowns.
- usgroup 3y agoI'd -- as usual -- suggest Prolog. Its elegant, easier to understand and more mature. It comes with "batteries included" if you want constraint solving over finite domains. Besides that MiniZinc is a phenomenal interface to a whole range of solvers specialised to various purposes which are more likely to get you where you want to go if you're not an expert. In the Prolog case -- for all its benefits -- the amount of "mechanical sympathy" required to make it perform well can become substantial very quickly. Finally, once you've written something in Picat, have a think about how you'd write it in some other language. I think you'll find .. for these toy problems, its easy in other languages too. After all, its a handful of lines to write Dijkstra or A* in most functional programming languages, and defining a state space for a search algorithm is essentially all you're ever doing.
- moffkalast 3y ago> A breaded chicken Picat with lemon jasmine rice This is Prolog nuggets.
- johnthescott 3y agoyep. gasps of genetic algos from the '90s still alive?
- samsquire 3y agoThis is interesting. The dream of telling the computer where to end up is something I have to. It might be interesting to someone but I used A* to do code generation to go from one state to target state. I'm not experienced with the planning community or solvers except for playing around naively with ortools. I generate assembly instructions to move between states. start_state = { "memory": [0, 0, 0, 0], "rax": 0, "rbx": 1, "rcx": 2, "rdx": 3, "rsp": -1, "rdi": -1, "rbp": -1 } end_state = { "memory": [3, 1, 2, -1], "rax": 3, "rbx": 2, "rcx": 1, "rdx": 0, "rsp": 6, "rdi": -1, "rbp": -1 } Generates [start, mov %rax, (%rdx), mov %rbx, (%rbx), mov %rcx, (%rcx), mov %rdx, (%rsp), mov %rax, %rsp, mov %rdx, %rax, mov %rsp, %rdx, mov %rcx, %rsp, mov %rbx, %rcx, mov %rsp, %rbx, call minus1(rdi=-1) -> rsp=4, call fourtofive(rsp=4) -> rsp=5, call fivetosix(rsp=5) -> rsp=6] It finds all the hidden state transitions of function calls to get to the goal. I also run it in parallel to speed up search using python multiprocessing and do dynamic neighbour generation because neighbour generation is different between threads and I couldn't parallelise A* with my original attempts without sharding this. The dream of my experimentation is that you tell the computer what you have and what you want it works out the correct traversals for you. For my personal intuition programming is logistics like factorio or a factory. This is why it's called "sliding puzzle", it's a puzzle where you have to move things around to see the correct picture. Github repo with some notes: https://github.com/samsquire/sliding-puzzle-codegen-memory https://github.com/samsquire/sliding-puzzle-codegen-memory Replit: https://replit.com/@Chronological/SlidingPuzzle3 https://replit.com/@Chronological/SlidingPuzzle3
- klyrs 3y ago> But hey it runs on Windows, which is better than 99% of research languages. So rude. Why would I want to run WINE just for that?
- hwayne 3y agoRuns on Windows too. 99% of the research projects I run into are Mac/Linux only.
- clemiclemen 3y agoThis approach to programming is not all new to me (I studied Prolog at university which looks very similar but does not have the planner feature) but the planner is a very elegant and simple way of solving problems. The comments about video game at the end of the article makes me wonder: the planner feature allows solving problems very easily by writing few lines of clear code. However, how does the performance compares against an algorithm written in imperative programming? Picat seems to be fairly efficient compared to similar languages [1] but I don't find a comparison against "standard" languages. [1]: https://arxiv.org/abs/1405.2538 https://arxiv.org/abs/1405.2538
- deleted 3y ago[deleted]
- simplify 3y agoMinor sidenote: For Prolog-esk syntaxes, rather than writing "comma first" to solve the problem of moving lines around, I've found that ending predicates with a simple `true.` solves it more elegantly.