> A breaded chicken Picat with lemon jasmine rice
This is Prolog nuggets.
Planner programming blows my mind
41–50 of 75 posts
Re: Planner programming blows my mind
#42This 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
}
[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]
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
Re: Planner programming blows my mind
#43Is 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…
sorry what is Z3?
Re: Planner programming blows my mind
#44Earlier 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…
Yup. & when you get a model that works matched up with an industrial scale decision problem that's valuable to solve, arguably it's only of academic interest if you can solve it "optimally". The problem is only a simplified model of reality anyway -- it's often better to get a quick close-enough approximate solution to a problem that's a good approximation of the situation than an exact optimal solution to a simpler…
I disagree with the first statement for some industries. My industry has several companies that have amongst the hardest MILP problems in the world that have millions of variables and constraints and need to be globally optimal for the sake of fairness and to save many millions of dollars per year. Electricity markets are extremely complicated and although it would be amazing to simplify things, the decisions and prices need to be correct. Also, performance is critical as these auctions are running 24/7. They're also always being changed as well, so black-box globally optimal solutions are a need to have.
Re: Planner programming blows my mind
#45Earlier quoted context omitted.
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 optimali…
Hmmm...for this problem, have you tried Hexaly? Just curious.
Re: Planner programming blows my mind
#46Earlier 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…
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.)
MIP, LP, Nonlinear for GUROBI. GUROBI and CPLEX can do planning of course if you formulate your problem in a certain way, but some solvers like Hexaly show large performance gains for things like vehicle routing vs GUROBI as they take a very different approach (don't use LP or MIP).
Re: Planner programming blows my mind
#47Earlier quoted context omitted.
Are the commercial offerings you mentioned better than TimeFold? [0] (formerly known as OptaPlanner before the main developers forked it) TimeFold's heuristics-based approach makes fast solutions to even highly-complex scenarios within the reach of anyone who can write Java or Python expressions that evaluate to true when constraints are satisfied. [0] https://timefold.ai/
I just hate it when you go to the pricing page and theres NO PRICING. None.
A lot of these companies started out with listed pricing and then grew and got crazy expensive. One of the nice things about the Mosek solver is that the price is listed and it is reasonable. I just dislike their API and documentation as it's written for mathematicians and not business SMEs.
Re: Planner programming blows my mind
#48Earlier 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…
If any of these had reasonable pricing I’d be happy to pay, but if the first price you see is ‘contact us’ you can be certain it’s too much for hobby use…
For GUROBI at least, you can access a free version directly through Anaconda or Pip I think that is limited to a few months and can only solve smaller problems. It does give you a sense of its capabilities. It is also free for academics. It is extremely expensive for production use though.
Re: Planner programming blows my mind
#49Earlier quoted context omitted.
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 optimali…
Hmmm...for this problem, have you tried Hexaly? Just curious.
No I haven't, but in our case CP-SAT works very well and license-wise it's free.
Re: Planner programming blows my mind
#50Earlier quoted context omitted.
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…
sorry what is Z3?
https://github.com/Z3Prover/z3
Here is an actual description: https://z3prover.github.io/papers/programmingz3.html#sec-int...