Vượt qua A*: Lập kế hoạch tốt hơn với Transformer

Beyond A*: Lập kế hoạch tốt hơn bằng Transformer

• Các mô hình Transformer đã đạt được nhiều tiến bộ lớn trong nhiều lĩnh vực ứng dụng, nhưng vẫn tụt lại sau các phương pháp lập kế hoạch dựa trên ký hiệu truyền thống khi giải quyết các bài toán ra quyết định phức tạp.
• Nhóm nghiên cứu đề xuất cách huấn luyện Transformer để giải các bài toán lập kế hoạch phức tạp, đồng thời phát triển mô hình Searchformer, có thể giải tối ưu các câu đố Sokoban chưa từng thấy trước đó trong 93,7% số trường hợp, đồng thời sử dụng ít hơn tới 26,8% số bước tìm kiếm so với tìm kiếm A* truyền thống.
• Searchformer là một mô hình Transformer encoder-decoder được huấn luyện để dự đoán hành vi tìm kiếm của A*, sau đó được tinh chỉnh thông qua expert iteration để tạo ra kế hoạch tối ưu với ít bước tìm kiếm hơn A*.

Phương pháp huấn luyện và hiệu năng

• Trong phương pháp huấn luyện, hành vi tìm kiếm của A* được biểu diễn thành chuỗi token thể hiện thời điểm các trạng thái được thêm vào và loại bỏ khỏi cây tìm kiếm trong quá trình lập kế hoạch ký hiệu.
• Trong nghiên cứu ablation về điều hướng mê cung, Searchformer vượt trội đáng kể so với mô hình cơ sở dự đoán trực tiếp kế hoạch tối ưu, trong khi kích thước mô hình nhỏ hơn 5-10 lần và tập dữ liệu huấn luyện nhỏ hơn 10 lần.
• Nhóm nghiên cứu cho thấy Searchformer hiệu quả trong việc tăng tỷ lệ giải được bài toán và rút ngắn hành vi tìm kiếm đối với các tác vụ ra quyết định lớn và phức tạp hơn như Sokoban.

Ý kiến của GN⁺

• Nghiên cứu này cho thấy một khả năng ứng dụng mới của các mô hình Transformer trong lĩnh vực trí tuệ nhân tạo. Bằng cách đưa ra một cách tiếp cận hiệu quả hơn so với các phương pháp dựa trên ký hiệu hiện có trong việc giải các bài toán ra quyết định phức tạp, đây là một bước tiến quan trọng giúp mở rộng phạm vi ứng dụng của AI.
• Mô hình Searchformer cho thấy khả năng giải quyết vấn đề nhanh hơn và hiệu quả hơn với ít tài nguyên hơn. Đây có thể là một lợi thế lớn, đặc biệt khi triển khai AI trong các môi trường bị hạn chế về tài nguyên.
• Nghiên cứu này gợi ý rằng sự phát triển của công nghệ AI không nhất thiết chỉ phụ thuộc vào nhiều dữ liệu hơn và các mô hình lớn hơn, mà còn có thể đạt được thông qua các phương pháp luận thông minh hơn và những cải tiến về thuật toán. Đây là một hướng tiếp cận rất thú vị và hữu ích xét trên khía cạnh tính bền vững và hiệu quả của nghiên cứu AI.

[GN⁺]

Ý kiến Hacker News

• Có một nghiên cứu thú vị về việc sử dụng transformer cho lập kế hoạch chuyển động của robot. Việc một cánh tay robot di chuyển từ điểm này sang điểm khác mà không va vào vật thể là một bài toán rất khó, vì bài toán này có tính liên tục và ở không gian chiều cao. Các phương pháp lập kế hoạch trước đây đòi hỏi tính toán lớn và cũng không thật sự tốt. Đây là một trong những lý do khiến chuyển động của robot trông "thiếu tự nhiên" và robot không thực hiện tốt nhiều tác vụ mà chúng ta mong muốn. Cách tiếp cận này có vẻ cạnh tranh được với các phương pháp lập kế hoạch khác và đưa ra phương án lập kế hoạch đường đi tối ưu nhanh hơn.
• Tò mò không biết họ có thử thuật toán J* đã chỉnh sửa, một phiên bản tối ưu hóa của thuật toán A* cho đồ thị game/tìm đường, trước khi bắt đầu hướng nghiên cứu này hay không. Với những ai quan tâm, có thông tin về "Game AI Pro 2".
• Lập kế hoạch vốn đã được xử lý tốt bằng các kỹ thuật hiện có như tìm kiếm trên đồ thị, SAT-solver, OR, Prolog, v.v. Vấn đề thường nằm ở tối ưu hóa giữa nhiều phương án khả thi, và tôi nghi ngờ liệu transformer có phù hợp để làm việc đó hay không. Vai trò của công nghệ LLM có vẻ gần hơn với việc chuyển mô tả ngôn ngữ tự nhiên thành chương trình có thể thực thi; mà Prolog rốt cuộc cũng được thiết kế cho NLP cổ điển, nên hai thứ này khá gần nhau.
• Dịch máy từng bao gồm việc giải mã ngữ pháp phức tạp và tìm kiếm, nhưng giờ transformer được dùng cho MT, với cách giải mã đơn giản hơn nhiều và gần như không cần tìm kiếm. Có lẽ chúng ta có thể đạt tới một "khởi đầu hoàn chỉnh", nơi dùng mô hình dự đoán tốt nhất hiện nay để học heuristic cho neural architecture search (NAS), rồi tìm kiếm các khối mạng nơ-ron mới tốt hơn transformer và Mamba.
• Cụm từ "ít hơn 26,8% bước tìm kiếm so với tìm kiếm A* tiêu chuẩn" cho thấy hiệu năng chỉ nhỉnh hơn A* một chút, nhưng trong Sokoban thì vẫn chưa đạt mức hiện đại nhất (SOTA). Điều gì thực sự ấn tượng trong bài báo này, và tại sao nó lại được đưa lên Hacker News, là điều tôi thắc mắc.
• Nếu transformer có thể lập kế hoạch, thì AGI (trí tuệ nhân tạo tổng quát) có thể chỉ cần được đào tạo tốt hơn.
• Có cung cấp một bản theo định dạng audiobook tóm tắt bài báo này cho những người học tốt qua thính giác.
• Bài báo này làm tôi nhớ đến bài về Neural Network Diffusion từng ở trang chủ HN hôm qua. Ở bài trước, họ huấn luyện một mô hình để bỏ qua các bước SGD; còn trong bài này, họ bỏ qua các bước tìm kiếm A*. Mặt khác, việc chọn heuristic của A* cho Sokoban lại không tốt. Khi đọc bài báo, tôi chơi Sokoban khoảng 20 phút và cảm thấy heuristic tìm kiếm quá yếu, vì để tiến triển thì bạn thường phải đẩy các hộp ra xa trạng thái mục tiêu.
• Tôi tự hỏi có ai đang duy trì một danh sách các thuật toán cổ điển hoặc các bài toán NP-đầy đủ mà hiện nay deep learning đã xử lý tốt hơn hay không.
• Tôi rất lạc quan về việc dùng heuristic được học trong các thuật toán rời rạc như A* hoặc Focal search. Trong hầu hết các thư viện tối ưu hóa rời rạc hiện đại, điều giải thích hiệu năng — như ở CPLEX — chính là heuristic và tuning. Tôi kém hiểu hơn về việc dùng cách tiếp cận học end-to-end để thay thế các quy trình tìm kiếm tối ưu đã được hiểu rất rõ, nhưng có thể đó chỉ là lo lắng thái quá. Tôi nghĩ các tác giả đã bỏ lỡ cơ hội đó.