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?

Paper authors choose to compare against A* and Sokoban.

A* can't solve even the first level of original Sokoban 90 levels.

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.

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.

> Why is this on Hacker News?

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

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

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

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.

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.

I agree. OP's comment could be quickly rewritten into something useful and just by changing the tone, for example:

"26.8% fewer search steps than standard A∗ search" For reference of prior art, it's slightly better than A*, which is far from SOTA on Sokoban (https://festival-solver.site/).

Especially considering the amount of trivial mainstream tech articles nowadays. It's cool to see more algorithmic topics.

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

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.

Abstract doesn't answer my question.

What is the scientific contribution of the paper?

They trained transformer on pairs of <sokoban_level, A*_optimal_solution>.

> What is the scientific contribution of the paper?

That's not a question you ask other people, that's a bullet point at the top of the outline you created while reading the paper for yourself. You should see the creation of said outline as a measure of your actual interest in the subject.

Having now read the paper, the research area is interesting because optimizations in optimal path finding have applications in robotics, gaming, and reasoning (what the ultimate intention of this paper is).

The research team identified ways to tokenized path finding algorithms for two tasks maze solving and sokoban (a game where a crate has to be pushed to goal) and then trained a model on the execution traces of these algorithms.

The insight this provided was that the "searchformer" model was about 26% faster than the traditional methods. If that is applied to Route-planning, Robotics, and Game Development, it could have tangible performance benefits.

IMHO, it is not a wild breakthrough but an interesting solution to a real-world problem.