Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Planner programming blows my mind

hillelwayne.com

Post reply on HN
Print view View original

21–30 of 75 posts

Re: Planner programming blows my mind

#21

Post by eru »

bloaf wrote: post #12

I'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-yiel...

> [...] 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.

Re: Planner programming blows my mind

#23

Post by sterlind »

7thaccount wrote: post #10
sterlind wrote: post #3

I'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 machin…

There 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 mor…

Gurobi is a MIP solver right, not a planner? I use Gurobi at work for a certain kind of bi-level programming and it's amazing, like literally ~500x faster than CBC. Picat's planner is more like a Prolog flavor of PDDL (e.g. fast-downward and its ilk.)

Re: Planner programming blows my mind

#24

Post by sterlind »

whatever1 wrote: post #16
polivier wrote: post #14

Earlier quoted context omitted.

> There 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 :) While this is generally true, there are some exceptions. I recently compared the performance of CP-SAT vs CPLEX for a problem (linear constraints and objective). For large instances where proving optimality in a reasonable time was out of the question, CP…

If feasibility is your goal then cp/sat solvers/heuristics should be your tool of choice. I you have optimality requirements (aka from the feasible solutions find the absolutely best) then optimization is the way to go

can't you just use the strong duality theorem to reframe an integral optimization problem as a system of integer inequalities? I thought you usually don't do that because the satisfaction problem is harder in practice.

Re: Planner programming blows my mind

#25

Post by sterlind »

fumeux_fume wrote: post #19

Is this related to Answer Set Programming? Seems like there’s an overlap.

they'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.

Re: Planner programming blows my mind

#26

Post by asciimike »

Pleasantly 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-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

Re: Planner programming blows my mind

#27

Post by fumeux_fume »

sterlind wrote: post #25
fumeux_fume wrote: post #19

Is this related to Answer Set Programming? Seems like there’s an overlap.

they'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…

I see, thanks for your explanation!

Re: Planner programming blows my mind

#28

Post by polivier »

whatever1 wrote: post #16
polivier wrote: post #14

Earlier quoted context omitted.

> There 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 :) While this is generally true, there are some exceptions. I recently compared the performance of CP-SAT vs CPLEX for a problem (linear constraints and objective). For large instances where proving optimality in a reasonable time was out of the question, CP…

If feasibility is your goal then cp/sat solvers/heuristics should be your tool of choice. I you have optimality requirements (aka from the feasible solutions find the absolutely best) then optimization is the way to go

I think that you've misunderstood what I said. For large instances of this specific problem (and when the time limit is too short to allow either CP-SAT or CPLEX to prove optimality) the best integer feasible solution found by CP-SAT is generally of better quality (w.r.t. the objective value) than the best integer feasible solution found by CPLEX. Furthermore, in some cases, CP-SAT can offer a certificate of optimality faster than CPLEX.

Re: Planner programming blows my mind

#29

Post by mlsu »

eigenvalue wrote: post #20
7thaccount wrote: post #10

Earlier quoted context omitted.

There 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 mor…

What about this one: https://www.cvxpy.org/ If you can convert your problem into a convex one (which I believe is often possible if you’re clever about how you express it), that would seem to be a pretty good option, no?

CVXpy is a frontend that transforms problems into a form that different solvers can understand.

It does make it very easy to format problems in Python but you still need a solver like Gurobi on the backend. You can use a variety of solvers on the same problem though, which is nice:

https://www.cvxpy.org/tutorial/advanced/index.html#choosing-...

My understanding is that Gurobi the best -- but also the most expensive.

Re: Planner programming blows my mind

#30

Post by Guthur »

I'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.

Post reply on HN