Planner programming blows my mind

I've actually used Picat's planning mode at work!

I prototyped a system to orchestrate maintenance on fleets of devices. The idea was that, rather than telling the system how to do it (e.g. workflows to roll out an update), you'd tell the system what you wanted (e.g. up to date machines), what actions were available (e.g. pull a machine from rotation, apply an update), and what constraints to obey (e.g. X of Y machines must be online, don't work in more than two regions simultaneously.)

I modeled a few scenarios like that in Picat and had it generate optimal plans. It worked swimmingly for pet problems, but predictably fell over scaling to cattle sizes. Planning is EXPTIME after all (e.g. Towers of Hanoi).*

Picat does have an escape hatch - you can define heuristics - so I built a random forest of state predicates and trained a naive Bayes classifier to predict fruitful paths. But even with that, and symmetry breaking constraints, and even some hierarchical planning, I couldn't make it work without too much handholding.

It's still AI winter for the classic GOFAI problem domains, apparently. :/

* maybe not, actually, if you reformulate the planning problem as returning a polynomial-time generator of a potentially exponentially long plan

Is this related to Answer Set Programming? Seems like there’s an overlap.

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

Looks Prolog-ish. Interesting, thanks for sharing.

Really hating the trend of putting half of the document behind series of “click here to unhide the content” dropdowns.

But hey it runs on Windows, which is better than 99% of research languages.

So rude. Why would I want to run WINE just for that?

I'd -- as usual -- suggest Prolog. Its elegant, easier to understand and more mature. It comes with "batteries included" if you want constraint solving over finite domains.

Besides that MiniZinc is a phenomenal interface to a whole range of solvers specialised to various purposes which are more likely to get you where you want to go if you're not an expert. In the Prolog case -- for all its benefits -- the amount of "mechanical sympathy" required to make it perform well can become substantial very quickly.

Finally, once you've written something in Picat, have a think about how you'd write it in some other language. I think you'll find .. for these toy problems, its easy in other languages too. After all, its a handful of lines to write Dijkstra or A* in most functional programming languages, and defining a state space for a search algorithm is essentially all you're ever doing.

Minor sidenote: For Prolog-esk syntaxes, rather than writing "comma first" to solve the problem of moving lines around, I've found that ending predicates with a simple `true.` solves it more elegantly.

This is interesting. The dream of telling the computer where to end up is something I have to.

It might be interesting to someone but I used A* to do code generation to go from one state to target state. I'm not experienced with the planning community or solvers except for playing around naively with ortools.

I generate assembly instructions to move between states.

  start_state = {
    "memory": [0, 0, 0, 0],
    "rax": 0,
    "rbx": 1,
    "rcx": 2,
    "rdx": 3,
    "rsp": -1,
    "rdi": -1,
    "rbp": -1
  }

  end_state = {
    "memory": [3, 1, 2, -1],
    "rax": 3,
    "rbx": 2,
    "rcx": 1,
    "rdx": 0,
    "rsp": 6,
    "rdi": -1,
    "rbp": -1
  }

  [start, mov %rax, (%rdx), mov %rbx, (%rbx), mov %rcx, (%rcx), mov %rdx, (%rsp), mov %rax, %rsp, mov %rdx, %rax, mov %rsp, %rdx, mov %rcx, %rsp, mov %rbx, %rcx, mov %rsp, %rbx, call minus1(rdi=-1) -> rsp=4, call fourtofive(rsp=4) -> rsp=5, call fivetosix(rsp=5) -> rsp=6]

I also run it in parallel to speed up search using python multiprocessing and do dynamic neighbour generation because neighbour generation is different between threads and I couldn't parallelise A* with my original attempts without sharding this.

The dream of my experimentation is that you tell the computer what you have and what you want it works out the correct traversals for you.

For my personal intuition programming is logistics like factorio or a factory. This is why it's called "sliding puzzle", it's a puzzle where you have to move things around to see the correct picture.

Github repo with some notes: https://github.com/samsquire/sliding-puzzle-codegen-memory

Replit: https://replit.com/@Chronological/SlidingPuzzle3

For those interested, HN user hakank (Hakan Kjellerstrand), who is a very active member of the constraint programming community (among others), has a ton of Picat resources and examples on his website: http://www.hakank.org/picat/

My first thought was, this looks like a type system, except you need to solve it yourself. In Typesecript, naively:

    const main = <a extends any, b extends any, c extends any>([a_, b_, c_]: [a, b, c, a]) => {
      type SomeTuple = [a, b, c, a];
      const X: a = a_;
      const Y: Exclude<SomeTuple, a> // = <put solved value here, get a type error if the value does not satisfy the constraints>
      console.log(X, Y);
    }

    type Narrowable = string | number | bigint | boolean;
    /*
      Express the type of a value in a tuple that is not the type of the second parameter
      For example:
      - ValOfTupleExceptFor<[1,1,6,2,3], 1> -> 6
      - ValOfTupleExceptFor<[1,1,6,2,3], 6> -> 1
    */
    type ValOfTupleExceptFor<
      Tup extends readonly Narrowable[],
      Val extends Tup[number]
    > = Tup extends [infer First, ...(infer Rest extends Narrowable[])]
      ? First extends Val
        ? Rest extends []
          ? never
          : ValOfTupleExceptFor<Rest, Val>
        : First
      : never;
    
    const NO_SOLUTION: unique symbol = Symbol('NO_SOLUTION')
    const getValOfTupleExcluding = (tup: readonly Narrowable[], val: (typeof tup)[number]): ValOfTupleExceptFor<typeof tup, typeof val> => {
      const [first, ...rest] = tup;
      if (!first) {
        return NO_SOLUTION as never;
      }
      if (first === val) {
        return getValOfTupleExcluding(rest, val);
      }
      return first as ValOfTupleExceptFor<typeof tup, typeof val>;
    }
    
    const main = <a extends Narrowable, b extends Narrowable, c extends Narrowable>([a_, b_, c_]: [a, b, c, a]) => {
      const someTuple = [a_, b_, c_, a_] as const;
      const X: a = a_;
      // This still resolves to type 'never'
      const Y: ValOfTupleExceptFor<typeof someTuple, a> = getValOfTupleExcluding(someTuple, a_);
      console.log(X, Y);
    }

edit: TS playground link with some experiments if anyone's interested: http://tinyurl.com/3p2pzdtn

A breaded chicken Picat with lemon jasmine rice

This is Prolog nuggets.

Nice to see GOAP being referenced again. It was the secret sauce that made F.E.A.R.'s enemies so fun. And Jeff Orkin's paper on how it works is very readable and entertaining.

This approach to programming is not all new to me (I studied Prolog at university which looks very similar but does not have the planner feature) but the planner is a very elegant and simple way of solving problems.

The comments about video game at the end of the article makes me wonder: the planner feature allows solving problems very easily by writing few lines of clear code. However, how does the performance compares against an algorithm written in imperative programming?

Picat seems to be fairly efficient compared to similar languages [1] but I don't find a comparison against "standard" languages.

[1]: https://arxiv.org/abs/1405.2538

Pleasantly surprised to see Predrag show up as a reviewer, but at the same time not at all surprised:

- The [Firebase technical screen](https://startupandrew.com/posts/how-firebase-interviewed-sof...) would have been much easier with something like this, as it was Just Another Optimization Problem™. Part of me wants to try it again with Picat!

- He's doing other very interesting things with programming languages, e.g.: https://github.com/obi1kenobi/trustfall

I've actually been using Prolog professionally including some CLPFD, and I love it. I want it everywhere. Or more precisely i want a logical core with emphasis on purity and push imperative action to the edges.

It so sad that as an industry we seemed locked into really bad tools.