title: Beyond A*: Better Planning with Transformers via Search Dynamics
    Bootstrapping
summary: 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.
paper_authors._id: 65d8203cbc9081f6c9027f47
paper_authors.name: Lucas Lehnert
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2024-12-09T14:51:02.951Z
paper_authors._id: 67564ccdb65f9a8b975a8d3e
paper_authors.avatarUrl: https://cdn-avatars.huggingface.co/v1/production/uploads/no-auth/8idn0G4mBqC9FetZHmzjA.png
paper_authors.fullname: Lucas Lehnert
paper_authors.type: user
paper_authors.user: lucaslehnert
paper_authors._id: 65d8203cbc9081f6c9027f48
paper_authors.name: Sainbayar Sukhbaatar
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2024-07-30T16:01:26.096Z
paper_authors._id: 66a8611eb51510d82ed54231
paper_authors.avatarUrl: /avatars/ad559e774fee4914091b82c9831ae2a2.svg
paper_authors.fullname: Sainbayar Sukhbaatar
paper_authors.type: user
paper_authors.user: sainbar
paper_authors._id: 65d8203cbc9081f6c9027f49
paper_authors.name: Paul Mcvay
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2024-02-23T12:37:32.217Z
paper_authors._id: 64d68374bcab729cb4adc1c5
paper_authors.avatarUrl: /avatars/e902747fbed594d0540f6bd282ee0a1c.svg
paper_authors.fullname: Paul Mcvay
paper_authors.type: user
paper_authors.user: pmcvay
paper_authors._id: 65d8203cbc9081f6c9027f4a
paper_authors.name: Michael Rabbat
paper_authors._id: 65d8203cbc9081f6c9027f4b
paper_authors.name: Yuandong Tian
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2024-02-23T12:37:43.806Z
paper_authors._id: 6344cf73ee1504dbcd5bdfe7
paper_authors.avatarUrl: /avatars/6dd2bf1f9c5679e5c8c85d62c9836aac.svg
paper_authors.fullname: Yuandong Tian
paper_authors.type: user
paper_authors.user: tydsh
paper_title: Beyond A*: Better Planning with Transformers via Search Dynamics
    Bootstrapping
paper_summary: 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.
paper_ai_summary: 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.
paper_ai_keywords: Transformers Searchformer encoder-decoder symbolic planning Sokoban $A^*$ search token sequence ablation studies maze navigation