6 ms·

I'm a little confused about how planning is different from vector reachability, which, from what I understand, has Ackermann complexity rather than EXPTIME. Ca

by bloaf 3y ago

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-yields-numbers-too-big-for-our-universe-20231204/ https://www.quantamagazine.org/an-easy-sounding-problem-yiel...

nickpsecurity 3y ago
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-Michalewicz/dp/3540224947 https://www.amazon.com/How-Solve-Heuristics-Zbigniew-Michale... https://www.jsoftware.us/vol7/jsw0709-23.pdf https://www.jsoftware.us/vol7/jsw0709-23.pdf
eru 3y ago
> [...] 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.
mfunk_ 3y ago
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.
hwayne 3y ago
General planning is undecidable; you can pretty easily encode a Turing machine as actions and make the goal state `Halt`.

by bloaf 3y ago

nickpsecurity 3y ago

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-Michalewicz/dp/3540224947 https://www.amazon.com/How-Solve-Heuristics-Zbigniew-Michale... https://www.jsoftware.us/vol7/jsw0709-23.pdf https://www.jsoftware.us/vol7/jsw0709-23.pdf

eru 3y ago

> [...] 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.

mfunk_ 3y ago

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.

hwayne 3y ago

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