Does anyone here have experience solving planning problems like these in Prolog?
For the delivery company example mentioned on the site, I’d imagine a database, perhaps just ‘library(persistency)’, storing the fleet of cars the company has, the delivery orders, the drivers employed, etc. The constraints would be expressed as prolog relations.
I may be implementing a system like this soon, and would like to hear war stories of doing it with a library like OptaPlanner or Prolog.
Declarative programming is very interesting. Some people are mentioning Prolog being slow. Well, I took an undergrad class on Prolog, and my perception is that Prolog can be very performant doing complete searches, but:
1) You need to know how to encode the constraints so they can be evaluated efficiently, not just write them.
2) A common way to achieve 1) is to encode a problem as a SAT problem and use a modern SAT solver. They are pretty sick. You can write great SAT solvers in Prolog, but there are already many good ones in many languages, so it's quite poinless unless you do it for fun or learning.
3) Compared to most statistical methods / heuristics, searches in Prolog will be slow. And in most cases statistical methods will do fine anyway, because there will be at least decent solutions to be easily found.
My conclusion is that we often confuse the problems of "proving that a plan is optimal" with "finding a good plan", which are indeed related, but use very different techniques to reach solutions.
I think the statistical methods would be better compared to a sat solver like Z3. Prolog gives you more flexibility, but it isn't going to be able to use the advanced search techniques that Z3 can take advantage of. Optimizers like Optaplanner are in sort of the same family as Z3, but they often trade being better at optimization for the ability to quickly find solutions, particularly if the number of solutions is small.
In my experience, seeing OptaPlanner pitted against the other best-of-the-best enterpise-grade solvers, OptaPlanner wins when scaling out - very clearly. Not when scaling down. This is the nature of the Local Search algorithms.
I think it very much depends on how hard your problem is. Small problems / search spaces will be fine in Prolog, but most realistic sized problems will quickly exhaust brute force search, and you will need to consider Local Search (like OptaPlanner), or Mixed Integer Programming, specialised Constraint Programming etc. There is a whole field of study on this - https://en.wikipedia.org/wiki/Discrete_optimization
Depending on which types of constraints you need to express your problem space, you could use plain Prolog or (more likely) make use of excellent constraint libraries like CLP(FD) for SWI-Prolog [1]. It's important to note that these are built into and tightly integrated with most Prolog. So people who point out that Prolog's backtracking search is too limited and/or slow are not taking the full picture into account.
I also recommend checking out Picat, a Prolog-derived language with excellent support for constraints programming and many built-in global constraints (a very important tool for larger-scale constraint programming) [2]. As of the recently released version 3 (featured on HN [3]), Picat also supports traditional Prolog syntax. IMO Picat is still rough around the edges when it comes to error messages, modularization etc, but if nothing else it's excellent for learning and for prototyping constraint models.
I’m not sure what the state of the art is, but certainly Prolog has been used for these kinds of things. Specialised dialects like ECLiPSe [1] have lots of options for solving constraint optimisation problems.
I think the biggest challenge in optimization problems is converting the constraints from object/concept space to integer/constraint space and back. Once you're done with that, it doesn't really matter which tools you use as long as they provide the mathematical operations necessary.
> In a more general sense, ASP includes all applications of answer sets to knowledge representation and the use of Prolog-style query evaluation for solving problems arising in these applications.
Prolog is a very different kind of system. It basically does backtracking natively, and everything else you have to build as libraries just like in any other language.
For the delivery company example mentioned on the site, I’d imagine a database, perhaps just ‘library(persistency)’, storing the fleet of cars the company has, the delivery orders, the drivers employed, etc. The constraints would be expressed as prolog relations.
I may be implementing a system like this soon, and would like to hear war stories of doing it with a library like OptaPlanner or Prolog.