Hacker News Reader

Comment by bloaf | Hacker News Reader

I'm a little confused about how planning is different from vector reachability, which, from what I understand, has Ackermann complexity rather than EXPTIME. Can anyone help me out with the constraints on "planning" that allow it to be solved in a sane amount of time?

https://www.quantamagazine.org/an-easy-sounding-problem-yiel...

View on HN

> [...] from what I understand, has Ackermann complexity rather than EXPTIME.

Really bad worst case times aren't necessarily bad in practice, if most instances you actually encounter can be solved quickly (especially if you are happy to be satisfied with worse than proven-optimal solutions.)

Compare how Hindley-Milner type inference, which forms the basis of Rust's or Haskell's type systems, is double-exponential in the worst case (or something like that), but typically fast in practice.

We normally pick up stuff like that in papers, blog posts, etc. The only heuristics book I remember was How to Solve It. I also found a survey paper on heuristics. Here they are in case they help:

https://www.amazon.com/How-Solve-Heuristics-Zbigniew-Michale...

https://www.jsoftware.us/vol7/jsw0709-23.pdf

I think in classic planning like STRIPS, the size of the state space is bounded exponentially in the size of the input (conditions can be either true or false). This is not the case of vector reachability.

I'm not familiar with picat, but the arithmetic operations used in the blog post suggest to me that the size of the state space is not necessarily bounded by the input. I believe the mention of EXPTIME in the post was removed.

General planning is undecidable; you can pretty easily encode a Turing machine as actions and make the goal state `Halt`.

Reply on news.ycombinator.com