Beyond A*: Better Planning with Transformers
arxiv.org
arxiv.org
It's in Game AI Pro 2 [0] if anyone is curious.
[0] https://www.amazon.ca/Game-AI-Pro-Collected-Professionals/dp...
Authors still gotta eat.
So this can be interpreted as a generic statement to say there might be progress during learning iterations (compared to its own arbitrary first iteration baseline). I think it's important to not getting carried away and assume the recent immense progress in generative AI is just easily repeated for any other AI task. There's also quantum computing having been advertised for over a decade now for a break through in planning and optimization efficiency.
> We also demonstrate how Searchformer scales to larger and more complex decision making tasks like Sokoban with improved percentage of solved tasks and shortened search dynamics.
Worth mentioning that Sokoban is nowhere near a complex decision making task let alone state of the art in an academic or commercial planning/optimization context.
> A∗'s search dynamics are expressed as a token sequence outlining when task states are added and removed [...] during symbolic planning.
Go ahead and compare against eg. Quantum Prolog's readily available container planning problem and solutions [1] then to generate exactly that in the browser - a plan with symbolic actions to perform - or alternatively, a classic Graphplan or CLIPS planning competition problem.
Perhaps we can reach full inception. Let's use our current best-of-breed predictive models to learn heuristics for neural architecture search (NAS) and search for new neural blocks (better than transformer and mamba).
Many in the community have tried to create various solvers and things get very hard once the grid gets to be over 5x5. However, some interesting levels with very high maximum step counts have been discovered by the thinky communnity (via simulated annealing)
So, slightly better than A* which is far from SOTA on Sokoban (https://festival-solver.site/).
What is impressive in this paper? Why is this on Hacker News?
Comments like these are antithetical to a strong technical sharing community.
"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/).
Anything that is on HN is on HN because the community likes it
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?
A* can't solve even the first level of original Sokoban 90 levels.
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.
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 is the scientific contribution of the paper?
They trained transformer on pairs of <sokoban_level, A*_optimal_solution>.
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.
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.
https://player.oration.app/09fefe41-f2a7-4257-a25e-30e479b30...
In most modern discrete optimization libraries, e.g. CPLEX it's the heuristics and tuning that explain the performance.
I'm less understanding of using a end to end learning approach to replace a well understood optimal search routine, but that might be pearl clutching.
It just seems to me the authors missed that opportunity.
In a few years we'll all be writing about how much more efficient actual code is compared to AI perhaps ;)
Meanwhile, you and I will be talking about how our low-level, handwritten Ruby on Rails code is so much faster and more efficient, and closer to the metal so you can understand what's _really_ going on.
That is going to be really amazing.
(S)ETH is a bit of a bummer if you only consider the dominate term in big-O, for the general case.
On a different note, they choose such a bad heuristic for the A* for Sokoban. The heuristic they choose is "A∗ first matches every box to the closest dock and then computes the sum of all Manhattan distances between each box and dock pair". I played Sokoban for 20 minutes while reading the paper and I feel like this is a very poor exploration heuristic (you often need to move boxes away from goal state to make progress).
"Planformer" seems unused and would reduce confusion
(also since "Search" implies RAG etc which is not what this model is about)
On second thought, in the spirit of A* perhaps they can rename it to O' short for Optimus Prime but this probably will break most of the databases in the world [1],[2].
[1] Exploits of a Mom:
[2] Prime (symbol):
> Megatron is a large, powerful transformer [...]
I wish someone could come up with an algorithm that would outperform a trained model. This way we would actually understand how it works.
I suspect that the actual execution time would be far faster with the A* implementation than any of the transformers.
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.
I once tried my hands on the PCB routing and here's a simple problem of simultaneous multipath search that is unsolvable:
A.....b
B.....a
The search algorithm sometimes required to prove absence of the solution. A* can do that, transformers? I do not think so.
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.
Your answer does not show anything related to the ability of transformers to prove absence of solution, to be precise.
Transformers can only do what is called weak negation.
if (not (goal X)), then (assert not x)
One example I have seen is: "you can cross if you have no information on a train coming”
VS:
"you can cross if you have evidence that no train is coming"
See the difference?
As to what 'transformers' can encode is ambiguous and depends on many factors but here is some light reading.
https://direct.mit.edu/tacl/article/doi/10.1162/tacl_a_00493...
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).
So you're saying I shouldn't read this paper?
A* is not particularly good. If all the algorithm can do is mirror it by training on its output what's the point?
I publish in this area and this is a common thing for reviewers to bring up when authors don't report wall clock time. And then for papers to be rejected. What's the value in making an algorithm that's drastically slower? Not much.
Perhaps as an important stepping stone? Deferred optimization and all that.
Some people call the flag planting. You publish something that doesn't work with keywords you suspect will be important in the future. Then hope others will cite you.