Ask HN: What Happened to Classical Planning?

https://news.ycombinator.com/item?id=27415526

by sterlind • 5 years ago

6 3 5 years ago

news.ycombinator.com

Classical planning is the problem of reaching a goal state from an initial state, given actions with preconditions and effects. It dates back to 1971, with STRIPS. Nowadays problems are written in PDDL ( https://planning.wiki/ ), and there's a competition for solvers. Many real-world problems from logistics to robotics can be modeled in PDDL.. it's like SMT but for plans instead of propositions.

But PDDL is low-level and cumbersome, the competition problems are small and stale, the solvers haven't gotten much better in a decade and nobody seems to use it in industry. The whole field is stuck in AI winter. Why?

triska2• 5 years 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/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• 5 years 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.

triska2• 5 years 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.

Ask HN: What Happened to Classical Planning?

Related Stories