Vì sao lập trình planner lại đáng kinh ngạc

 (hillelwayne.com)
2 điểm bởi GN⁺ 2024-02-22 | 1 bình luận | Chia sẻ qua WhatsApp
  • Mô-đun planner của Picat tiến thêm một bước so với lập trình logic vốn tìm phép gán giá trị, bằng cách biểu diễn bài toán dưới dạng chuỗi thay đổi trạng thái dẫn tới trạng thái mục tiêu
  • Nếu định nghĩa trạng thái bắt đầu Start, quy tắc chuyển tiếp action(From, To, Action, Cost) và điều kiện kết thúc final(S), thì best_plan(Start, Plan) sẽ tìm ra kế hoạch chi phí tối thiểu để đi tới trạng thái cuối cùng
  • Trong ví dụ tìm đường trên lưới, việc di chuyển, giới hạn biên, tránh chướng ngại vật và ghé nhiều mục tiêu đều có thể xử lý chỉ bằng cách thay đổi action và final, đồng thời thứ tự ghé mục tiêu cũng có thể cố định hoặc để tự do
  • Khả năng lập kế hoạch còn có thể kết hợp với giải ràng buộc, nên cũng có thể biểu diễn những bài toán như partition problem, nơi ta tìm danh sách con lớn nhất có thể chia thành hai phần có tổng bằng nhau bằng cách loại bỏ một số phần tử
  • Picat là một ngôn ngữ nghiên cứu nên còn thiếu tài liệu và thông báo lỗi, nhưng với vai trò ngôn ngữ công cụ để giải nhanh các bài toán tính toán nhất định, nó có thể cho lời giải ngắn gọn hơn ngôn ngữ thông thường

Ý tưởng cơ bản về Picat và lập trình planner

  • Picat là một ngôn ngữ nghiên cứu nhằm kết hợp lập trình logic, lập trình mệnh lệnh và giải ràng buộc
  • Lập trình mệnh lệnh hoặc hàm thông thường viết thuật toán tạo đầu ra từ đầu vào, còn lập trình logic và giải ràng buộc thì tìm phép gán giá trị thỏa mãn một quan hệ
  • Trong Picat, các định danh không phải hàm bắt đầu bằng chữ thường như a, b, c là atom, còn các định danh bắt đầu bằng chữ hoa là biến
  • Ngay cả trong biểu thức như member(Y, Arr) có chứa biến chưa được định nghĩa Y, Picat vẫn có thể tìm và gán giá trị sao cho biểu thức đúng
    • Nếu Arr = [a, b, c, a] thì Y có thể là một trong a, b, c
    • Nếu thêm điều kiện như X != Y thì tập giá trị khả dĩ sẽ bị thu hẹp hơn nữa
    • Ngay cả khi chưa biết chính danh sách, như member(a, Z), nó vẫn có thể khởi tạo Z thành một danh sách

Lập kế hoạch không tìm phép gán giá trị mà tìm thay đổi trạng thái

  • Thay vì tìm giá trị biến thỏa mãn phương trình, lập kế hoạch (planning) sẽ tìm chuỗi thay đổi biến để đi tới một trạng thái kết thúc nhất định
  • Một bài toán planning trong Picat cần ba thành phần
    • Trạng thái bắt đầu Start
    • Các hàm action biểu diễn chuyển tiếp trạng thái
    • final(S) để xác định một trạng thái có phải trạng thái kết thúc hay không
  • Các hàm action trong Picat đều phải có tên là action và nhận bốn tham số
    • Trạng thái hiện tại
    • Trạng thái tiếp theo
    • Tên action
    • Chi phí
  • best_plan(Start, Plan) sẽ gán vào Plan một kế hoạch có số bước ngắn nhất hoặc chi phí nhỏ nhất để tới trạng thái kết thúc
    • Nếu mọi chi phí đều là 1 thì chi phí kế hoạch sẽ chính là tổng số bước di chuyển
    • Nếu chỉ cần một kế hoạch bất kỳ, không quan trọng độ dài, có thể dùng plan(Start, Plan)

Ví dụ tìm đường trên lưới

  • Bài toán ví dụ là một marker trên lưới xuất phát từ gốc tọa độ (0, 0) và đi tới tọa độ mục tiêu
    • Mỗi bước có thể di chuyển một ô theo bốn hướng lên, xuống, trái, phải
    • Không được đi ra ngoài biên lưới
    • Khi tới tọa độ mục tiêu thì thành công
  • Trạng thái bắt đầu chứa cả vị trí hiện tại và mục tiêu, ví dụ {Origin, Goal}
    • Trong Picat, {a, b} là cú pháp mảng nhưng thực tế thường được dùng như tuple
  • Có thể biểu diễn điều kiện kết thúc bằng pattern matching như final({Pos, Goal}) => Pos = Goal.
    • Nếu viết cùng nội dung mà không dùng pattern matching thì phải tách trạng thái thành {Pos, Goal} trước
    • Nếu có nhiều điều kiện final thì kế hoạch sẽ thành công khi chỉ cần một điều kiện đúng
  • Action di chuyển chọn một trong bốn hướng {-1,0}, {1,0}, {0,-1}, {0,1} rồi kiểm tra xem tọa độ mới có nằm trong phạm vi 0..10 hay không
    • member({Dx, Dy}, Dir) được dùng để tìm các giá trị hướng hợp lệ
    • member(Tx, 0..10) và member(Ty, 0..10) được dùng để kiểm tra tọa độ có nằm trong biên không
    • Với predicate chỉ dùng để kiểm tra mà không gán giá trị, có thể dùng membchk
  • Kế hoạch kết quả được in ra dưới dạng danh sách các action di chuyển và tọa độ mới như {move,{1,0}}, {move,{2,0}}
    • Có thể dùng script Raku để trực quan hóa đường đi
    • Nếu thêm điều kiện như {Tx, Ty} != {2, 1} thì cũng có thể tránh chướng ngại vật bằng cách né một tọa độ cụ thể

Nhiều mục tiêu và tối thiểu hóa chi phí

  • Để ghé nhiều mục tiêu, Goal không còn là một tọa độ đơn mà trở thành hàng đợi mục tiêu như [{2, 2}, {3, 4}]
  • Thêm một action mới để khi tới mục tiêu thì loại mục tiêu đó khỏi danh sách mục tiêu
    • [Head|Tail] tách danh sách thành phần tử đầu và phần còn lại
    • Goal = [Pos|Rest] chỉ đúng khi vị trí hiện tại Pos trùng với phần tử đầu trong danh sách mục tiêu
    • Nếu đặt trạng thái mới là {Pos, Rest} thì mục tiêu đã đạt sẽ bị loại bỏ
  • Việc đã ghé hết mọi mục tiêu hay chưa được xác định bằng final({Pos, Goal}) => Goal = [].
    • Điều kiện kết thúc không còn là vị trí hiện tại có bằng một mục tiêu cụ thể hay không, mà là danh sách mục tiêu đã rỗng chưa
  • Việc thăm mục tiêu theo thứ tự cố định không phải lúc nào cũng cho ra đường đi ngắn nhất tổng thể
  • Nếu bỏ qua thứ tự mục tiêu và muốn tối thiểu hóa toàn bộ lộ trình thì có thể thay đổi action mark
    • Thay vì Goal = [Pos|Rest], dùng member(Pos, Goal) để kiểm tra xem vị trí hiện tại có nằm ở bất kỳ đâu trong danh sách mục tiêu hay không
    • To = {Pos, delete(Goal, Pos)} sẽ loại bỏ mục tiêu đã ghé khỏi danh sách
    • Với cách này, Picat có thể tự chọn mục tiêu tiếp theo để tối thiểu hóa độ dài toàn bộ đường đi

Kết hợp planning và giải ràng buộc

  • Khả năng planning của Picat được tích hợp với các tính năng Picat khác, nên có thể dùng planning cùng với giải ràng buộc
  • Bài toán partition problem trong ví dụ là bài toán NP-complete: chia một danh sách số thành hai nhóm có tổng bằng nhau
  • Chương trình này loại bỏ một số phần tử khỏi danh sách số đầu vào để tìm danh sách con lớn nhất vẫn có thể chia thành hai phần có tổng bằng nhau
    • Việc loại bỏ phần tử khỏi danh sách đầu vào được xem là action của planning
    • final(Numbers) kiểm tra xem danh sách số hiện tại có nghiệm partition hợp lệ hay không
    • Các ràng buộc trong mô-đun cp biểu diễn việc mỗi phần tử thuộc nhóm bên trái hay bên phải bằng biến 0..1
    • Ràng buộc được đặt sao cho tổng toàn bộ phải bằng hai lần tổng của một phía
  • Trong kết quả ví dụ, sau khi loại bỏ [5,17], danh sách còn lại có thể được chia thành hai nhóm đều có tổng 1108
    • 32+99+977=1108
    • 122+77+86+59+47+154+141+172+49+62+109+30=1108
  • Cách làm này không chỉ dừng ở việc giải trực tiếp một bộ ràng buộc hợp lệ, mà còn biểu diễn bằng planning những thay đổi cần thiết để đi tới trạng thái ràng buộc hợp lệ

Giới hạn và trường hợp phù hợp khi dùng Picat

  • Picat là ngôn ngữ nghiên cứu nên không được khuyến nghị cho môi trường production
  • Nó không có nhiều tính năng tiện dụng, đồng thời cũng thiếu tài liệu tốt và thông báo lỗi rõ ràng
    • Khi không có kế hoạch khả thi, lỗi có thể được in ra như *** error(failed,main/0)
  • Việc có thể chạy trên Windows được xem là một điểm tốt hơn nhiều ngôn ngữ nghiên cứu khác
  • Picat gần với một ngôn ngữ kiểu toolkit để giải những loại bài toán tính toán cụ thể hơn là một ngôn ngữ để viết mã cần bảo trì hay chia sẻ
  • Một số bài toán vốn khó xử lý bằng ngôn ngữ lập trình thông thường kết hợp với bộ giải ràng buộc lại có thể được giải khá thanh lịch bằng Picat

Các ngôn ngữ planning khác và khái niệm liên quan

  • Planning ban đầu được khai phá trong robotics và AI, nhưng ngày nay thường xuất hiện trong AI game dưới tên Goal Oriented Action Planning (GOAP)
  • PDDL là một ngôn ngữ mô tả planning để các planner độc lập nhận làm đầu vào
    • Nó có vai trò tương tự như DIMACS trong SAT, tức là một định dạng mô tả

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-02-22
Ý kiến trên Hacker News

  • Đã thử dùng chế độ lập kế hoạch của Picat trong công việc thực tế
    Tôi đã làm bản mẫu cho một hệ thống điều phối bảo trì các cụm thiết bị, và cách làm là nhập vào không phải “làm như thế nào” mà là “muốn điều gì”, “có những hành động nào khả thi”, và “những ràng buộc nào phải tuân thủ”
    Với ví dụ nhỏ thì nó tạo kế hoạch tối ưu khá tốt, nhưng khi mở rộng lên quy mô thực tế thì đúng như dự đoán là sụp đổ, và vì bài toán lập kế hoạch rốt cuộc là EXPTIME nên giới hạn rất lớn
    Picat có một lối thoát là cho phép định nghĩa heuristic, nên tôi đã dùng random forest và bộ phân loại naive Bayes trên các predicate trạng thái để dự đoán những nhánh có triển vọng, nhưng ngay cả khi thêm ràng buộc phá đối xứng và lập kế hoạch phân cấp thì vẫn tốn quá nhiều công sức
    Có vẻ như trong miền bài toán GOFAI cổ điển, mùa đông AI vẫn còn tồn tại
    Có lẽ sẽ không như vậy nếu tái định nghĩa bài toán lập kế hoạch thành việc trả về “một bộ sinh chạy trong thời gian đa thức tạo ra kế hoạch có độ dài tiềm năng theo cấp số mũ”

    • Các solver thương mại hiệu năng tốt hơn rất nhiều so với mã nguồn mở, và cũng làm ví của bạn trống đi nhanh hơn rất nhiều
      CPLEX, Xpress, GUROBI, Hexaly là những cái tên hiện ra đầu tiên, và Hexaly đặc biệt tốt cho bài toán lập lịch hoặc định tuyến phương tiện
      Thông thường người ta truy cập chúng qua API của các ngôn ngữ phổ biến trong ngành, và theo tôi cách này hợp lý hơn nhiều so với các ngôn ngữ chuyên dụng cho solver vốn yếu ở những tác vụ tổng quát
      Gọi GUROBI từ Python rất dễ, và vẫn có thể dùng đầy đủ các tính năng thông thường của Python
      Mosek rẻ hơn GUROBI rất nhiều, nhưng API của cả hai đều rất low-level và hiệu năng cũng không bằng GUROBI
    • Trong trường hợp này, có khả năng thứ như CP-SAT(https://developers.google.com/optimization/cp) đã mở rộng khá tốt
      Solver này xử lý cực kỳ dễ dàng một lượng biến và ràng buộc phi lý lớn, và các heuristic tích hợp cũng rất xuất sắc
    • Các planner ngày xưa đã giảm không gian tìm kiếm bằng cách đưa vào meta-rule hoặc heuristic để quyết định áp dụng quy tắc nào
      Một số hệ thống chia bài toán thành nhiều biểu diễn khác nhau rồi gắn các solver tự động chuyên biệt vào
      Tôi nhớ tới Jahob Analysis System và Cyc
      Xét về khía cạnh sử dụng thực tế, thiết kế gọn gàng nhất của AI cổ điển có lẽ là Procedural Reasoning System, và tôi muốn được thấy một phiên bản làm lại, bổ sung các điểm yếu của nó bằng phương pháp hiện đại
      https://en.wikipedia.org/wiki/Procedural_reasoning_system
    • Tôi tự hỏi vì sao lại không có solver mã nguồn mở chất lượng cao
      Ở nhiều lĩnh vực tính toán số khác, công nghệ tiên tiến thường là mã nguồn mở, nên tôi luôn thắc mắc vì sao riêng tối ưu hóa lại khác
    • Xét về kết quả hay hiệu năng thì có khi nó cũng chẳng khác mấy so với một bản tìm kiếm theo chiều sâu viết đại khái, mơ hồ gợi nhớ tới Prolog

  • Có một trang do người dùng HN rất tích cực trong cộng đồng constraint programming là hakank, tức Hakan Kjellerstrand, tổng hợp rất nhiều tài liệu và ví dụ về Picat: http://www.hakank.org/picat/

  • Như thường lệ, tôi muốn đề xuất Prolog
    Nó thanh lịch, dễ hiểu và trưởng thành hơn; nếu bạn muốn giải ràng buộc trên miền hữu hạn thì chỉ với cấu hình mặc định cũng đã đủ dùng
    Ngoài ra, MiniZinc là một giao diện tuyệt vời để truy cập nhiều solver chuyên cho các mục đích khác nhau, nên nếu không phải chuyên gia thì khả năng bạn tiến gần kết quả mong muốn với nó sẽ cao hơn
    Prolog có nhiều ưu điểm, nhưng để đạt hiệu năng tốt thì “cảm giác cơ khí” cần thiết có thể nhanh chóng trở nên khá đáng kể
    Nếu bạn đã viết gì đó bằng Picat, có lẽ cũng nên nghĩ xem sẽ viết cùng thứ đó bằng ngôn ngữ khác như thế nào
    Những bài toán đồ chơi kiểu này cũng dễ trong các ngôn ngữ khác, và trong hầu hết các ngôn ngữ hàm, Dijkstra hay A* chỉ cần vài dòng, vì rốt cuộc thường chỉ là định nghĩa không gian trạng thái cho thuật toán tìm kiếm

  • Tôi vui khi thấy Predrag là reviewer, nhưng đồng thời cũng hoàn toàn không ngạc nhiên
    Firebase technical screen hẳn đã dễ hơn nhiều nếu có công cụ như thế này, và suy cho cùng đó lại là một bài toán tối ưu hóa nữa
    Tôi cũng muốn thử giải lại nó bằng Picat
    Anh ấy cũng đang làm những việc thú vị trong mảng ngôn ngữ lập trình: https://github.com/obi1kenobi/trustfall

  • Ấn tượng đầu tiên của tôi là “trông giống một hệ thống kiểu phải tự giải bằng tay”
    Tôi đã thử biểu diễn ngây thơ bằng TypeScript, nhưng vì a, b, c đều có thể giống nhau nên chẳng giải quyết được gì
    Khi cố biểu diễn cho đúng, tôi đã đi tới một hình thức trông có vẻ dùng được phần nào, nhưng vẫn phải dùng assertion và cũng không thể biểu diễn đúng kiểu của Y
    Chính quá trình này lại cho thấy chương trình kiểu planner mạnh đến mức nào về sự đơn giản và cô đọng
    Có vẻ TypeScript không đủ mạnh để biểu diễn loại ràng buộc này
    Link TS Playground đã thử nghiệm: http://tinyurl.com/3p2pzdtn

  • Thật vui khi thấy GOAP lại được nhắc tới
    Đó là bí quyết tạo nên sự thú vị của kẻ địch trong F.E.A.R., và bài viết của Jeff Orkin về cách nó hoạt động cũng rất dễ đọc và thú vị

  • Tôi đang dùng Prolog và một chút CLPFD trong công việc thực tế, và nó thực sự rất tốt
    Tôi ước gì nó có mặt ở khắp nơi; chính xác hơn là tôi muốn giữ một lõi logic nhấn mạnh tính thuần khiết, rồi đẩy hành vi mệnh lệnh ra phần rìa
    Thật đáng tiếc khi ngành này dường như bị mắc kẹt với những công cụ tệ như vậy

  • Trông khá giống Prolog và rất thú vị

  • Bản thân kiểu lập trình này không hoàn toàn mới
    Tôi đã học Prolog ở đại học và nó trông khá giống, nhưng Prolog không có tính năng planner
    Tuy vậy, planner là một cách rất thanh lịch và đơn giản để giải quyết vấn đề
    Phần nói về trò chơi điện tử ở cuối bài làm tôi thấy tò mò
    Tính năng planner giúp giải bài toán rất dễ chỉ với vài dòng mã rõ ràng, nhưng nếu so với một thuật toán viết theo kiểu mệnh lệnh thì hiệu năng sẽ thế nào?
    Picat có vẻ khá hiệu quả nếu so với các ngôn ngữ tương tự [1], nhưng tôi không tìm thấy so sánh với các ngôn ngữ “tiêu chuẩn”
    [1]: https://arxiv.org/abs/1405.2538

  • Tôi cũng có giấc mơ chỉ cần nói cho máy tính biết trạng thái cần đạt tới
    Tôi không rành cộng đồng planner hay solver, mới chỉ nghịch ortools một cách ngây thơ, nhưng đã từng thử sinh mã đi từ một trạng thái tới trạng thái đích bằng A*
    Tôi tạo ra các lệnh assembly để di chuyển giữa các trạng thái, rồi còn tìm cả các chuyển trạng thái ẩn của lời gọi hàm để tới được mục tiêu
    Để tăng tốc tìm kiếm, tôi cũng chạy song song bằng Python multiprocessing, và vì mỗi thread tạo lân cận khác nhau nên tôi dùng cơ chế sinh lân cận động
    Ở lần thử ban đầu, A* khó song song hóa nên cần phải sharding
    Giấc mơ trong thử nghiệm của tôi là chỉ cần cho máy tính biết “những gì đang có” và “những gì muốn có”, rồi nó tự tìm ra con đường di chuyển đúng
    Cá nhân tôi thấy lập trình gần với logistics như trong Factorio hay nhà máy hơn
    Vì vậy tôi gọi nó là “sliding puzzle”, bởi đó là kiểu câu đố phải di chuyển đồ vật qua lại để nhìn ra đúng bức tranh
    Kho GitHub và ghi chú: https://github.com/samsquire/sliding-puzzle-codegen-memory
    Replit: https://replit.com/@Chronological/SlidingPuzzle3