การเขียนโปรแกรมแบบ Planner ที่น่าทึ่ง

 (hillelwayne.com)
2 คะแนน โดย GN⁺ 2024-02-22 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

ความสามารถอันเสมือนเวทมนตร์ของภาษาโปรแกรม Picat

  • Picat เป็นภาษาเชิงวิจัยที่พยายามผสมผสานการเขียนโปรแกรมเชิงตรรกะ การเขียนโปรแกรมเชิงคำสั่ง และการแก้ปัญหาข้อจำกัดเข้าด้วยกัน
  • โมดูล planner ของ Picat เป็นหนึ่งในโมเดลการเขียนโปรแกรมที่น่าสนใจอย่างยิ่ง

คำอธิบายสั้น ๆ เกี่ยวกับการเขียนโปรแกรมเชิงตรรกะ

  • ในการเขียนโปรแกรมเชิงคำสั่งและเชิงฟังก์ชัน เราเขียนอัลกอริทึมที่รับอินพุตแล้วสร้างเอาต์พุต
  • ในการเขียนโปรแกรมเชิงตรรกะและการแก้ปัญหาข้อจำกัด เราจะกำหนดระบบสมการชุดหนึ่งแล้วหาการกำหนดค่าที่ทำให้ความสัมพันธ์เหล่านี้เป็นจริง

การกำหนดปัญหา

  • พิจารณาปัญหาที่ใส่ marker บนกริด และต้องเคลื่อนที่จากจุดเริ่มต้น (จุดกำเนิด) ไปยังพิกัดเป้าหมาย
  • ในแต่ละขั้นเราสามารถเดินได้หนึ่งช่องในสี่ทิศทางและห้ามออกนอกขอบเขตของกริด
  • เมื่อ marker อยู่ที่พิกัดเป้าหมาย โปรแกรมจึงถือว่าสำเร็จ

การใช้งานครั้งแรก

  • ต้องมีการกำหนดสถานะเริ่มต้น Start ชุดฟังก์ชัน action ที่แทนการเปลี่ยนแปลงสถานะ และฟังก์ชัน final(S) เพื่อกำหนดสถานะสุดท้าย
  • เรียก best_plan(Start, Plan) เพื่อกำหนดลำดับขั้นตอนที่สั้นที่สุดที่ต้องใช้ในการไปถึงสถานะสุดท้ายลงใน Plan

เพิ่มหลายเป้าหมาย

  • ตัววางแผนต้องไปถึงทุกเป้าหมายตามลำดับ
  • เพิ่มฟังก์ชัน action ใหม่ที่เมื่อถึงเป้าหมายแล้วจะเอาเป้าหมายที่ถึงนั้นออกจากคิว

การลดต้นทุนให้น้อยที่สุด

  • การไปเยือนเป้าหมายตามลำดับเท่านั้นไม่ได้หมายถึงเส้นทางรวมที่สั้นที่สุดเสมอไป
  • หากต้องการค้นหาเส้นทางสั้นที่สุดโดยไม่ยึดลำดับของเป้าหมาย ให้แก้ไข action เพื่อให้ตัววางแผนสามารถเลือกเป้าหมายถัดไปและลดความยาวเส้นทางรวมให้ต่ำสุดได้

ตัวแปรอื่น ๆ

  • Picat รองรับตัวแปรการวางแผนมากมาย
  • best_plan(S, Limit, Plan) กำหนดเพดานต้นทุนสูงสุดเป็น Limit
  • sequence(P, Action) จำกัดพฤติกรรมที่เป็นไปได้ตามแผนย่อยปัจจุบัน

การใช้งาน Picat หรือไม่

  • Picat เป็นภาษาเชิงวิจัย และอาจขาดความสะดวกสบายบางอย่าง เช่น การมีเอกสารที่ดีหรือข้อความแจ้งข้อผิดพลาดที่ชัดเจน
  • Picat จะมีประโยชน์มากขึ้นเมื่อใช้เป็นภาษา "เครื่องมือ" สำหรับการแก้ปัญหาคำนวณเฉพาะทาง

ภาคผนวก: ภาษาแผนอื่น ๆ

  • แม้ว่า "planning" จะถูกพัฒนาขึ้นเพื่อใช้กับหุ่นยนต์และ AI แต่โดยหลักนิยมแล้วจะถูกใช้เป็น Goal-Oriented Action Planning (GOAP) ใน AI ของเกมวิดีโอ
  • PDDL เป็นภาษาอธิบายการวางแผนที่ตัววางแผนอิสระใช้เป็นอินพุต

ความเห็นของ GN⁺

  • นวัตกรรมในโมเดลการเขียนโปรแกรม: โมดูล planner ของ Picat เพิ่มมิติเพิ่มเติมให้กับการเขียนโปรแกรม โดยเฉพาะอย่างยิ่งมีพลังมากเมื่อแก้ปัญหาที่ซับซ้อนเช่นการหาทางที่ดีที่สุด
  • คุณค่าด้านการศึกษา: Picat มีความสำคัญเชิงการศึกษาในด้านภาษาการเขียนโปรแกรม เนื่องจากช่วยในการทำความเข้าใจแนวคิดของการเขียนโปรแกรมเชิงตรรกะและการแก้ปัญหาข้อจำกัด
  • การแก้ปัญหาเฉพาะทาง: Picat มีคุณค่าในฐานะแบบเครื่องมือในการแก้ปัญหาคำนวณเฉพาะทาง โดยเสนอวิธีการใหม่สำหรับปัญหาที่แก้ได้ยากโดยภาษาเขียนโปรแกรมทั่วไป

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-02-22
ความคิดเห็นจาก Hacker News

  • ตัวอย่างการนำโหมดการวางแผนของ Picat ไปใช้ในงานจริง

    • พัฒนาต้นแบบระบบสำหรับการบำรุงรักษาอุปกรณ์
    • สั่งให้ระบบเพียงว่า "อยากได้อะไร" ไม่ใช่สั่งว่า "ทำอย่างไร"
    • ใช้ Picat เพื่อสร้างแผนที่เหมาะสมที่สุด แต่เกิดปัญหาเมื่อขยายขนาดใหญ่
    • เนื่องจากการวางแผนมีความซับซ้อนแบบ EXPTIME จึงมีข้อจำกัดด้านการขยายตัวตามที่คาด
    • แม้มีการกำหนด heuristic, ตัวจำแนก Naive Bayes และข้อจำกัดความสมมาตร ก็ยังต้องการการดูแลอย่างมาก
    • ในพื้นที่ปัญหา GOFAI แบบคลาสสิก ยังอยู่ในภาวะ "AI winter"

  • ข้อมูลผู้ให้ทรัพยากรและตัวอย่างของ Picat

    • ตัวอย่างและเนื้อหา Picat มาจากเว็บไซต์ของ Hakan Kjellerstrand สมาชิกที่มีส่วนร่วมอย่างแข็งขันในชุมชนโปรแกรมเชิงข้อจำกัด

  • การแนะนำ Prolog และ MiniZinc

    • Prolog เป็นภาษาที่เข้าใจง่ายและค่อนข้างมีความสมบูรณ์ พร้อมความสามารถในการแก้ปัญหาด้วยข้อจำกัด
    • MiniZinc เป็นอินเทอร์เฟซที่เข้าถึงตัวแก้ปัญหาที่เหมาะสมกับจุดประสงค์ที่หลากหลาย
    • Prolog ต้องการความเข้าใจค่อนข้างมากเพื่อเพิ่มประสิทธิภาพ
    • แนะนำให้พิจารณาว่าสามารถนำไปเขียนด้วยภาษาอื่นได้ง่ายหลังจากเขียนด้วย Picat หรือไม่

  • ความคิดเห็นเกี่ยวกับการสัมภาษณ์เชิงเทคนิคของ Firebase

    • การสัมภาษณ์เชิงเทคนิคของ Firebase คงจะง่ายขึ้นหากใช้เครื่องมือแบบ Picat
    • ยินดีมากที่เห็น Predrag ปรากฏตัวมาเป็น reviewer

  • การเปรียบเทียบระบบประเภทข้อมูลกับภาษาโปรแกรม

    • คล้ายกับ type system ของ TypeScript แต่ต้องแก้ปัญหาด้วยตัวเองโดยตรง
    • TypeScript ไม่ได้เข้มแข็งพอสำหรับการแสดงข้อจำกัด
    • เน้นความกระชับและความง่ายแบบการเขียนโปรแกรมเชิง planner

  • การกล่าวถึง GOAP (Goal-Oriented Action Planning)

    • GOAP ที่ใช้กับ AI ของศัตรูในเกม F.E.A.R. ทำให้ความสนุกเพิ่มขึ้น
    • งานของ Jeff Orkin เกี่ยวกับ GOAP ได้รับการประเมินว่าอ่านง่ายและน่าสนใจ

  • การประเมินความสามารถของตัววางแผนใน Picat

    • Prolog ที่มีฟีเจอร์การวางแผนเสริมเพิ่มขึ้นมา
    • ความสามารถวางแผนทำให้แก้ปัญหาได้ง่ายขึ้น แต่ประสิทธิภาพยังต้องเปรียบเทียบกับการเขียนโปรแกรมเชิง imperative

  • ความฝันที่บอกสถานะสุดท้ายให้คอมพิวเตอร์แล้วให้มันแก้เอง

    • สร้างโค้ดและเปลี่ยนสถานะด้วยอัลกอริทึม A*
    • แม้ประสบการณ์กับชุมชน planning/solver ยังน้อย แต่ได้ทดลองด้วย ortools
    • มองว่าการเขียนโปรแกรมเป็นเหมือนโลจิสติกส์ และเปรียบเทียบกับ "Sliding Puzzle"

  • ข้อคิดเห็นเพิ่มเติมเกี่ยวกับไวยากรณ์ที่คล้าย Prolog

    • ใช้ไวยากรณ์ใกล้เคียง Prolog และเสนอ true. ให้จบบรรทัดแทน comma first ว่าเป็นคำตอบที่สง่างามกว่า

สรุปนี้สะท้อนความคิดเห็นจากผู้คนหลากหลายและถ่ายทอดแต่ละมุมมองอย่างเป็นกลาง โดยเนื้อหาทางเทคนิคที่เกี่ยวข้องกับภาษาโปรแกรมถูกอธิบายอย่างกระชับเพื่อให้วิศวกรซอฟต์แวร์ระดับต้นเข้าใจได้ง่าย