6 ms·

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

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 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 ago
It 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 ago
So 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 ago
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 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
  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 problem that's a poorer approximation. If you're lucky enough to get a problem that's basically stable over time, where the problem structure doesn't change, then maybe you can get improved solutions rapidly at industrial scale replacing use of a black-box MIP solver like Gurobi/CPLEX with a decomposition that exploits the problem structure, where sub-problems can be solved by some specialized graph algorithm or heuristic or brute force (if they all have bounded size), and the general purpose MIP/LP solver can be left with the job of figuring out how to deal with the shared resources and constraints that bind the subproblems together. The downside to a highly specialised custom solver is that it usually isn't flexible to changing requirements (unless you get very lucky) -- a slight change in business rule can break the problem structure that underpins the entire solution approach.
  - 7thaccount 3y ago
    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.
pea 3y ago
Why don't high quality open-source solvers exist? The SOTA in other numerical computing is often open-source. I've always wondered why optimization was different.
muldvarp 3y ago
I've used MIP, SAT and plenty of other solver technologies and they aren't perfect but I got them to work most of the time. I've never once in my life been able to get a CP solver to solve anything that's even close to a real world problem.

polivier 3y ago

It 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 ago

So 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 ago

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 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
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 problem that's a poorer approximation. If you're lucky enough to get a problem that's basically stable over time, where the problem structure doesn't change, then maybe you can get improved solutions rapidly at industrial scale replacing use of a black-box MIP solver like Gurobi/CPLEX with a decomposition that exploits the problem structure, where sub-problems can be solved by some specialized graph algorithm or heuristic or brute force (if they all have bounded size), and the general purpose MIP/LP solver can be left with the job of figuring out how to deal with the shared resources and constraints that bind the subproblems together. The downside to a highly specialised custom solver is that it usually isn't flexible to changing requirements (unless you get very lucky) -- a slight change in business rule can break the problem structure that underpins the entire solution approach.
- 7thaccount 3y ago
  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.

pea 3y ago

Why don't high quality open-source solvers exist? The SOTA in other numerical computing is often open-source. I've always wondered why optimization was different.

muldvarp 3y ago

I've used MIP, SAT and plenty of other solver technologies and they aren't perfect but I got them to work most of the time. I've never once in my life been able to get a CP solver to solve anything that's even close to a real world problem.