3 ms·

Many features available in dedicated planning systems are now subsumed by modern Prolog systems and their constraint solvers. For example, SICStus Prolog now pr

by triska 5y ago

Many features available in dedicated planning systems are now subsumed by modern Prolog systems and their constraint solvers. For example, SICStus Prolog now provides sophisticated constraints for resource planning such as cumulative/[1,2] and related global constraints: https://sicstus.sics.se/sicstus/docs/4.3.2/html/sicstus/Scheduling-Constraints.html https://sicstus.sics.se/sicstus/docs/4.3.2/html/sicstus/Sche... The efficiency and expressiveness of global constraints in SICStus Prolog and also other Prolog systems have improved tremendously over the past few decades, and my impression is that these Prolog systems suffice to solve many planning, resource allocation and scheduling tasks that arise in practice, with the added advantage of tight integration in a full-fledged high-level programming language. The documentation of SICStus Prolog used to include a statement that a third of all airline tickets worldwide are processed with this system.

sterlind 5y ago
how do you actually do planning with Prolog, though? I've tried to model my domain in ASP (Potassco), and I had to use iterative deepening. as I increased the number of objects in my problem, planning slowed exponentially, despite the problem being highly symmetric. my impression is that SAT-based solvers wouldn't be able to keep up as well as search algorithms, but I've been running out of luck with those too.
- triska 5y ago
  The idea is to post the relevant constraints, i.e., the relations that ought to hold, by using the predicates that the Prolog system provides for constraint solving. After the constraints are posted, one of the search strategies can be tried. Examples of common search strategies provided by constraint solvers over finite domains are "ff" (first-fail) and "leftmost". If the problem is highly symmetric, then it may be useful to post so-called symmetry breaking constraints, i.e., constraints that remove areas of the search space that are not interesting because they correspond to other parts of the search space that are already tried. Adding symmetry breaking constraints can also speed up SAT-based solvers significantly, especially complete solvers like SATO. These constraints may have adverse effects on local-search based SAT solvers because such solvers tend to work better if more solutions are present.

by triska 5y ago

sterlind 5y ago

how do you actually do planning with Prolog, though? I've tried to model my domain in ASP (Potassco), and I had to use iterative deepening. as I increased the number of objects in my problem, planning slowed exponentially, despite the problem being highly symmetric. my impression is that SAT-based solvers wouldn't be able to keep up as well as search algorithms, but I've been running out of luck with those too.

triska 5y ago
The idea is to post the relevant constraints, i.e., the relations that ought to hold, by using the predicates that the Prolog system provides for constraint solving. After the constraints are posted, one of the search strategies can be tried. Examples of common search strategies provided by constraint solvers over finite domains are "ff" (first-fail) and "leftmost". If the problem is highly symmetric, then it may be useful to post so-called symmetry breaking constraints, i.e., constraints that remove areas of the search space that are not interesting because they correspond to other parts of the search space that are already tried. Adding symmetry breaking constraints can also speed up SAT-based solvers significantly, especially complete solvers like SATO. These constraints may have adverse effects on local-search based SAT solvers because such solvers tend to work better if more solutions are present.