Lập trình lập kế hoạch, thật đáng ngạc nhiên

 (hillelwayne.com)
2 điểm bởi GN⁺ 2024-02-22 | 1 bình luận | Chia sẻ qua WhatsApp

Tính năng kỳ diệu của ngôn ngữ lập trình Picat

  • 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.
  • Module planner của Picat là một trong những mô hình lập trình thú vị nhất.

Giải thích ngắn gọn về lập trình logic

  • Trong lập trình mệnh lệnh và lập trình hàm, bạn viết một thuật toán nhận đầu vào rồi tạo ra đầu ra.
  • Trong lập trình logic và giải quyết ràng buộc, bạn đưa ra một hệ phương trình rồi tìm các phép gán thỏa các quan hệ đó.

Đặt vấn đề

  • Giải một bài toán đặt một marker lên lưới và di chuyển từ điểm xuất phát (gốc tọa độ) tới một tọa độ mục tiêu.
  • Ở mỗi bước, có thể di chuyển đúng 1 ô theo bốn hướng và không được ra khỏi biên lưới.
  • Chương trình thành công khi marker ở tại tọa độ mục tiêu.

Triển khai đầu tiên

  • Cần cung cấp trạng thái ban đầu Start, một dãy hàm action mô tả chuyển trạng thái, và hàm final(S) xác định trạng thái kết thúc.
  • Gọi best_plan(Start, Plan) để gán cho Plan dãy bước ngắn nhất cần thiết để đạt trạng thái cuối cùng.

Thêm nhiều mục tiêu

  • Bộ hoạch định phải đạt tất cả mục tiêu theo thứ tự.
  • Thêm một hàm action mới: khi đạt được một mục tiêu, xóa mục tiêu đó khỏi hàng đợi.

Tối thiểu hóa chi phí

  • Việc ghé thăm mục tiêu theo thứ tự không phải lúc nào cũng có nghĩa là đường đi tổng cộng ngắn nhất.
  • Nếu bạn muốn tìm đường đi ngắn nhất mà không phụ thuộc thứ tự mục tiêu, hãy sửa action để bộ lập kế hoạch có thể chọn mục tiêu tiếp theo và tối thiểu hóa tổng độ dài đường.

Các biến thể khác

  • Picat hỗ trợ rất nhiều biến thể của lập kế hoạch.
  • best_plan(S, Limit, Plan) giới hạn chi phí tối đa bằng Limit.
  • sequence(P, Action) giới hạn hành động khả thi theo kế hoạch con hiện tại.

Có nên dùng Picat không

  • Picat là một ngôn ngữ nghiên cứu và thiếu nhiều tiện ích như tài liệu tốt hay thông báo lỗi rõ ràng.
  • Picat hữu ích hơn như một ngôn ngữ "công cụ" để giải các bài toán tính toán chuyên biệt.

Phụ lục: Các ngôn ngữ lập kế hoạch khác

  • "Hoạch định" ban đầu được phát triển cho robot và AI, nhưng thường được sử dụng trong AI của trò chơi điện tử dưới dạng "Goal-Oriented Action Planning" (GOAP).
  • PDDL là ngôn ngữ mô tả kế hoạch mà một planner độc lập dùng làm đầu vào.

Ý kiến của GN⁺

  • Đổi mới mô hình lập trình: Module planner của Picat mở ra một chiều mới cho lập trình, đặc biệt mạnh khi giải các bài toán phức tạp như tìm đường.
  • Giá trị giáo dục: Picat có vai trò giáo dục quan trọng trong việc học ngôn ngữ lập trình, giúp tiếp cận các khái niệm về lập trình logic và giải ràng buộc.
  • Giải quyết bài toán cụ thể: Picat có giá trị như một ngôn ngữ công cụ để xử lý các bài toán tính toán chuyên biệt, mang đến cách tiếp cận mới cho những vấn đề khó giải bằng ngôn ngữ lập trình tổng quát.

Bài viết liên quan

1 bình luận

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

  • Kinh nghiệm thực tế sử dụng chế độ lập kế hoạch của Picat tại công việc

    • Phát triển nguyên mẫu hệ thống cho bảo trì thiết bị
    • Yêu cầu hệ thống làm bất cứ thứ gì cần đạt được, thay vì chỉ định cách thực hiện
    • Tạo kế hoạch tối ưu bằng Picat, nhưng gặp vấn đề khi mở rộng quy mô lớn
    • Kế hoạch có độ phức tạp EXPTIME nên theo dự kiến khả năng mở rộng bị giới hạn
    • Đã dùng heuristic, bộ phân loại Naive Bayes, ràng buộc đối xứng… nhưng vẫn cần nhiều công việc quản lý
    • Với các miền bài toán GOFAI cổ điển thì vẫn ở trạng thái AI Winter

  • Thông tin về tài nguyên và ví dụ của Picat

    • Trên website của Hakan Kjellerstrand, thành viên năng nổ của cộng đồng lập trình ràng buộc, có cung cấp tài nguyên và ví dụ về Picat

  • Khuyến nghị Prolog và MiniZinc

    • Prolog là ngôn ngữ dễ hiểu, đã trưởng thành, với chức năng giải ràng buộc
    • MiniZinc là giao diện để truy cập các solver tối ưu hóa cho nhiều mục đích
    • Prolog đòi hỏi sự hiểu biết đáng kể để tăng hiệu năng
    • Nên cân nhắc liệu có dễ dàng viết lại sang ngôn ngữ khác sau khi viết bằng Picat hay không

  • Bình luận liên quan phỏng vấn kỹ thuật Firebase

    • Phỏng vấn kỹ thuật Firebase sẽ dễ hơn nếu dùng công cụ như Picat
    • Vui mừng khi thấy Predrag xuất hiện với vai trò reviewer

  • So sánh hệ thống kiểu dữ liệu và ngôn ngữ lập trình

    • Tương tự hệ thống kiểu của TypeScript, nhưng cần xử lý trực tiếp
    • TypeScript chưa đủ mạnh để biểu diễn các ràng buộc
    • Nhấn mạnh sự gọn gàng và dễ dùng của lập trình theo phong cách lập kế hoạch

  • Đề cập đến GOAP (Goal-Oriented Action Planning)

    • GOAP, được dùng trong AI của đối thủ trong game F.E.A.R để tăng yếu tố thú vị
    • Bài báo của Jeff Orkin về GOAP được đánh giá là dễ đọc và hấp dẫn

  • Đánh giá tính năng lập kế hoạch của Picat

    • Giống Prolog nhưng có bổ sung tính năng lập kế hoạch
    • Dễ giải bài toán với chức năng planning của nó, nhưng hiệu năng cần được so sánh với lập trình thủ tục

  • Giấc mơ đưa trạng thái cuối cho máy tính để nó tự giải

    • Tạo mã và chuyển trạng thái bằng thuật toán A*
    • Dù chưa có nhiều kinh nghiệm với cộng đồng planning hay solver, nhưng có thử nghiệm với ortools
    • Nhìn lập trình giống như bài toán logistics, ví von như "trò đẩy khối" (sliding puzzle)

  • Bình luận bổ sung về cú pháp giống Prolog

    • Có cú pháp giống Prolog và đề xuất dùng true. để kết thúc thay vì 'comma first' như một giải pháp thanh lịch hơn

Tóm tắt này phản ánh nhiều ý kiến cá nhân và chuyển tải trung lập từng quan điểm. Nội dung kỹ thuật về ngôn ngữ lập trình được giải thích ngắn gọn để phù hợp với kỹ sư phần mềm mới bắt đầu.