4 ms·

Wouldn't that be an overkill to train a model specifically for that? I wish someone could come up with an algorithm that would outperform a trained model. This

Wouldn't that be an overkill to train a model specifically for that? I wish someone could come up with an algorithm that would outperform a trained model. This way we would actually understand how it works.

jvanderbot 3y ago
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.
- SnowflakeOnIce 3y ago
  Note that the paper doesn't measure execution time of the A* or Transformer-based solutions; it compares length of A* algorithm traces with length of traces generated by a model trained on A* execution traces. I suspect that the actual execution time would be far faster with the A* implementation than any of the transformers.
- bamboozled 3y ago
  Was the pun intended ?
wongarsu 3y ago
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.
Moldoteck 3y ago
do you want the solution faster or more precise? Depending on the answer you would pick either A* or this model
- SnowflakeOnIce 3y ago
  They don't report execution time in the paper. It's likely that the A* implementation would run faster in terms of CPU or wall clock.
  - Moldoteck 3y ago
    Transformer model that optimally solves previously unseen Sokoban puzzles 93.7% of the time, while using up to 26.8% fewer search steps than standard A∗ search. Doesn't fewer search steps imply faster?
    - senand 3y ago
      No, each step could take significantly more time (and resources).
feverzsj 3y ago
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.

jvanderbot 3y ago

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.

SnowflakeOnIce 3y ago
Note that the paper doesn't measure execution time of the A* or Transformer-based solutions; it compares length of A* algorithm traces with length of traces generated by a model trained on A* execution traces. I suspect that the actual execution time would be far faster with the A* implementation than any of the transformers.
bamboozled 3y ago
Was the pun intended ?

wongarsu 3y ago

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.

Moldoteck 3y ago

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

SnowflakeOnIce 3y ago
They don't report execution time in the paper. It's likely that the A* implementation would run faster in terms of CPU or wall clock.
- Moldoteck 3y ago
  Transformer model that optimally solves previously unseen Sokoban puzzles 93.7% of the time, while using up to 26.8% fewer search steps than standard A∗ search. Doesn't fewer search steps imply faster?
  - senand 3y ago
    No, each step could take significantly more time (and resources).

feverzsj 3y ago

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.