Beyond A*: Better Planning with Transformers via Search Dynamics
  Bootstrapping
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 and present Searchformer, a
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. Searchformer is an encoder-decoder Transformer model trained to predict
the search dynamics of A^*. This model is then fine-tuned via expert
iterations to perform fewer search steps than A^* search while still
generating an optimal plan. In our training method, A^*'s search dynamics are
expressed as a token sequence outlining when task states are added and removed
into the search tree during symbolic planning. In our ablation studies on maze
navigation, we find that Searchformer significantly outperforms baselines that
predict the optimal plan directly with a 5-10times smaller model size and a
10times smaller training dataset. 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.
65d8203cbc9081f6c9027f47
Lucas Lehnert
claimed_verified
2024-12-09T14:51:02.951Z
67564ccdb65f9a8b975a8d3e
https://cdn-avatars.huggingface.co/v1/production/uploads/no-auth/8idn0G4mBqC9FetZHmzjA.png
Lucas Lehnert
user
lucaslehnert
65d8203cbc9081f6c9027f48
Sainbayar Sukhbaatar
claimed_verified
2024-07-30T16:01:26.096Z
66a8611eb51510d82ed54231
/avatars/ad559e774fee4914091b82c9831ae2a2.svg
Sainbayar Sukhbaatar
user
sainbar
65d8203cbc9081f6c9027f49
Paul Mcvay
admin_assigned
2024-02-23T12:37:32.217Z
64d68374bcab729cb4adc1c5
/avatars/e902747fbed594d0540f6bd282ee0a1c.svg
Paul Mcvay
user
pmcvay
65d8203cbc9081f6c9027f4a
Michael Rabbat
65d8203cbc9081f6c9027f4b
Yuandong Tian
admin_assigned
2024-02-23T12:37:43.806Z
6344cf73ee1504dbcd5bdfe7
/avatars/6dd2bf1f9c5679e5c8c85d62c9836aac.svg
Yuandong Tian
user
tydsh
Beyond A*: Better Planning with Transformers via Search Dynamics
  Bootstrapping
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 and present Searchformer, a
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. Searchformer is an encoder-decoder Transformer model trained to predict
the search dynamics of A^*. This model is then fine-tuned via expert
iterations to perform fewer search steps than A^* search while still
generating an optimal plan. In our training method, A^*'s search dynamics are
expressed as a token sequence outlining when task states are added and removed
into the search tree during symbolic planning. In our ablation studies on maze
navigation, we find that Searchformer significantly outperforms baselines that
predict the optimal plan directly with a 5-10times smaller model size and a
10times smaller training dataset. 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.
Searchformer, a Transformer model, outperforms traditional $A^*$ search by optimizing Sokoban puzzle solutions with fewer steps and demonstrates superior performance on maze navigation and more complex tasks.
Transformers Searchformer encoder-decoder symbolic planning Sokoban $A^*$ search token sequence ablation studies maze navigation