Beyond A*: Better Planning with Transformers

also because googling for "Searchformer" brings up a different paper and model: https://www.sciencedirect.com/science/article/abs/pii/S01722...

"Planformer" seems unused and would reduce confusion

(also since "Search" implies RAG etc which is not what this model is about)

Megatron would be better IMO.

Wouldn't that be a trademark violation?

Sacagawea is my proposed name.

I think Searchformer is kind of catchy. :shrug:

It is in the abstract, very first line. "While Transformers have enabled tremendous progress in various application settings, such architectures still lag behind traditional symbolic planners for solving complex decision making tasks. In this work, we demonstrate how to train Transformers to solve complex planning tasks ..."

This paper is interesting (to me) as an example of how to use transformers for decision making. I don't particularly care if it is up to A* standards at the moment.

What? Someone somewhere tried to do something and wasn't the most optimal possible solution? We should just ban their account honestly.

Comments like these are antithetical to a strong technical sharing community.

So A* is the most optimal search algorithm under the specific constraints it specifies. You can't do better.

However, sometimes the specific domain you are searching has other constraints that can be exploited to do better than A*. An example of this being Jump Point Search that exploits certain properties of grid searches if you can only move in certain ways.

If you were able to write a general searching algorithm that can effectively exploit the whatever the specific properties of the underlying domain "automatically" without you having to actually work out what they are, that would be useful right?

Because they used a transformer to reach a nice solution, better than a typical A* search, which is a "naive" or go to solution. And they didn't think about designing an algorithm. I find it quite impressive that a simple encoder-decoder transformer can achieve so much.

Some people find things interesting regardless of if they break records.

Has anyone compared planning algorithms by complexity against optimality (error)?

Why is this on Hacker News?

Anything that is on HN is on HN because the community likes it

In certain computer science problems, a suboptimal action at time t may give rise to an optimal outcome at time >t.

Why wouldn't this be the case for research generally? Has our community really devolved to the point where things should only be noteworthy insofar as they optimize for SOTA for a given problem?

What a sad thought.

It's on hn because it sounds similar to the so called Q* algorithm, the supposed secret openai algo that has seen a huge amount of speculation.

Because it's further evidence for the "unreasonable effectiveness of transformers", i.e. that transformers are a fully-general approach for all kinds of learning tasks, not just next-token prediction. Obviously there is a strong and a weak version of that hypothesis and the strong version is probably not true, but to the extent that we appear to be honing in Nature's "one true way" to learn how to accomplish a task, that seems like important news.

For your convenience, here is the list of NP-complete problems where "AI" works better than the state of the art in the worst case:.

From my understanding this is very much still active research, without any clear wins deployed in production settings.

do you want the solution faster or more precise? Depending on the answer you would pick either A* or this model

Well in this case, A* outperforms in terms of funding a solution when it exists. It's just the transformer produces a solution faster, but misses some.

Shortest path search is a very well understood problem, and for "simple" cases A* is the gold standard.

You could probably tweak the heuristic used by A* to the problem to get similarly good results (at much lower compute cost than running what amounts to an LLM with huge context length). But this is a toy problem. The interesting thing about the paper is that you might be able to get good-performing search algorithms for any problem with a cookie-cutter process, instead of spending many man-hours tweaking a hand-written search algorithm. It might also be possible to easily adapt it to much more complex search problems, like cooperatively evading other agents navigating in the same space.

Path planning is highly dynamic and requires real time adjustment. In mature software, the heuristics are already highly optimized for local road/traffic data and users. So, I don't think AI can actually outperform them yet.

...and finally enter a world where literally no one understands anymore how the technology works, not even the people developing them. Singularity, here we come...

"Every time I fire a linguist, the performance of the speech recognizer goes up." --Frederick Jelinek

I love these books (and nice to see Steve Rabin still doing them), but $120 for an ebook? That's unexpected.

To be fair, they said at the end that their path-finder is not yet competitive with the SOTA. The paper tests how well a transformer does at predicting an execution trace (like in a JIT compiler) and whether this can help improve heuristics in things like path-finding. I'm weary because transformers are slow.

also https://github.com/anvaka/ngraph.path

I agree, learning admissible heuristics will retain worst case performance, which has always been the measuring stick for these algorithms. It's not at all uncommon to find faster solutions for the average or even p99 cases that cannot provide guarantees on the worst case.

I think it is just the bubble/hype effect around transformers and AI. I might try to use transformers to solve tic-tac-toe and apply for some VC moneys.

In a few years we'll all be writing about how much more efficient actual code is compared to AI perhaps ;)

Yeah, at first I read that as it using 26.8% of the original steps, but reducing the number of steps by 26.8% is not that impressive. I wonder whether it actually reduces total search time as there is added overhead of running the neural network.

There’s a lot more pieces, agency being a big one but online learning is required too and many other layers beyond that.

That's probably the foreseeable future, ingesting ever larger amounts of data hoping it prevents hallucinations.

Approximating exhaustive search is not logic or causality.

In this case, A* is in a finite, bounded 3030 grid. As A is just a type of branch and bound algorithm, which the degenerate form is exhaustive search. Which should be able to 'prove' the absence of a path by simply failing to find one before exhausting all paths.

PCB routing is not as simple as this problem for real world problems.

Digging into why TSP with a positive integer Euclidean metric is NP-C but with a real valued Euclidean metric is NP-hard may be one way to think about it.

But if you choose the right metric and huristic, in what approximates a finite space, A* can run an exhaustive search in practical time.

It is probably a good idea to separate search space exhaustion from no-instance proving which in the case of decision problems can cause confusion.

If you think of NP as relating to yes-instances, co-NP is the no-instances.

It would be interesting to see the comparison between Prolog and a similar purposes LLM

Thanks for sharing, I've been looking for an app like this for ages.

What makes you say Cornell? Isn't this from Meta?

Thank you! Great games! Super nice execution! I love it!

I have a hunch they made their decision to train off that particular type of A* traces to avoid an exponential number of embeddings.

Informative comments like this is the reason I go to the comment section before reading the article.

The part of MCTS that matters for solving it is the Bellman equation, which is a component of the Bellman-Ford shortest-path algorithm, so all of those methods are part of a continuum.

Which one works best is pretty sensitive to the exploratory decisionmaking algorithm: do I search this cell first, or that one? That heuristic is the differentiator, whether it is put on top of a Dijkstra-style algorithm (A*) or a Bellman-Ford-style algorithm (MCTS).

It's also not clear to me how one would determine that an ML model-generated plan is indeed optimal, or how far from optimal it is. A*-based approaches give you these things.

What do you mean by that?