Planner programming blows my mind

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

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.

- 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

    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

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

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

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

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

This is Prolog nuggets.

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