นักวิจัยค้นพบโซลูชันมนการควบคุมฝูงหุ่นยนต์ให้สามารถทำงานที่มีความซับซ้อนร่วมกันได้ ด้วยการใช้ Logic Command ที่มีชื่อว่า STyLuS* หรือ Large-Scale optimal Temporal Logic Synthesis ซึ่งสามารถแก้ไขปัญหาจำนวนมหาศาลได้แตกต่างจาก Algorithm ทั่วไป ไม่ว่าจะเป็นหุ่นยนต์หลายร้อยตัว ในห้องกว่า 10,000 ห้อง และมีกิจกรรมที่มีความซับซ้อนสูง ก็สามารถดำเนินการได้ภายในเวลาชั่วอึดใจ
การควบคุมหุ่นยนต์จำนวนไม่กี่ตัวอาจเป็นเรื่องที่ยุ่งยากสับสน แต่สำหรับการควบคุมหุ่นยนต์หลักร้อยอาจกลายเป็นสิ่งที่เป็นไปไม่ได้หากไม่มี Logic Command ที่มีประสิทธิภาพมากพอ ซึ่งรูปแบบวิธีใหม่ที่ชื่อว่า STyLuS* หรือ Large-Scale Optimal Temporal Logic Synthesis สามารถแก้ปัญหาได้
ในการทำความเข้าใจพื้นฐานแนวคิดใหม่นี้ต้องทำความเข้าใจ Linear Temporal Logic เสียก่อน ซึ่งมันไม่ได้ฟังดูน่ากลัวอย่างที่เห็น สมมุติว่าคุณอยากตั้งโปรแกรมให้หุ่นยนต์จำนวนหนึ่งเก็ฐจดหมายจากเพื่อนบ้านและส่งมันไปยังที่ทำการไปรษณีย์ทุก ๆ วัน Linear Temporal Logic จะเป็นวิธีการเขียนคำสั่งที่ทำให้การทำงานดังกล่าวสำเร็จลุล่วงได้
ตัวคำสั่งอาจประกอบด้วยการไปที่บ้านแต่ละหลังตามลำดับและกลับไปยังที่ทกำารไปรษณีย์ จากนั้นจึงรอให้มีคนมาเก็บจดหมายไปจึงออกไปทำงานอีกครั้ง มันอาจฟังดูง่ายเวลาเราเขียนหรือพูดแบบภาษามนุษย์ แต่ในแง่มุมของคณิตศาสตร์แล้วเป็นเรื่องที่ยุ่งยาก Linear Temporal Logic สามารถดำเนินการสิ่งเหล่านี้ได้โดยใช้สัญลักษณ์ของตัวเอง มันอาจดูเหมือนภาษา Kilngon จาก Star Trek ในสายตาของผู้พบเห็นแต่มันมีประโยชน์อย่างมากในการจัดการกับปัญหาการควบคุมที่ซับซ้อน
สาเหตุที่ต้องใช้คำจำกัดความว่า Linear เพราะว่าแต่ละจุดในเวลานั้นมีอัตลักษณ์ในการรับช่วงต่อที่มีพื้นฐานมาจากโมเดลเวลาเชิงเส้นที่ไม่ต่อเนื่อง และ Temporal นั้นหมายถึงลักษณะของการทำงาน เช่น จนกระทั่ง ต่อไป ตลอดไป และ ในที่สุด เป็นต้น ด้วยการใช้รูปแบบทางคณิตศาสตร์เหล่านี้ทำให้สามารถสร้างคำสั่งที่มีความซับซ้อนได้ เช่น ‘ไปที่บ้านทุกหลังเว้นแต่บ้านหลังที่ 2’, ‘ไปบ้านหลังที่ 3 และ 4 ตามลำดับ’ และ ‘รอจนกระทั่งไปยังบ้านหลังที่ 1 ก่อนไปยังบ้านหลังที่ 5’
ในการเฟ้นหาการควบคุมหุ่นยนต์ที่มีความซับซ้อนเช่นนี้ ตำแหน่งของหุ่นยนต์แต่ละตัวต้องถูกกำหนดเอาไว้อย่างชัดเจนในแต่ละตำแหน่งข้อมูลที่เรียกว่า Node จากนั้น แต่ละ Node จะรวมกันเป็น Node จำนวนมากจนมีศักยภาพเพียงพอในการใช้งานขั้นต่อไปของหุ่นยนต์
ในการควบคุมทั่วไปนั้นมีการค้นหาผ่านแต่ละ Node ที่มีและเลือกเส้นทางที่มีศักยภาพในการเดินทางระหว่าง Node ก่อนที่จะค้นพบวิธีที่ดีที่สุดในการทำงาน แต่ด้วยจำนวนหุ่นยนต์และตำแหน่งที่ต้องทำงานเพิ่มขึ้น กฎของ Logic ที่ต้องทำตามคำสั่งก็ยิ่งมีความซับซ้อนยิ่งขึ้น พื้นที่โซลูชันที่เป็นไปได้ยิ่งทวีคูณมากยิ่งขึ้นในเวลาที่สั้นลงอย่างมาก
ปัญหาง่าย ๆในการใช้หุ่นยนต์ 5 ตัวกับบ้าน 10 หลังอาจต้องมี Node หลายล้านตำแหน่ง เพื่อจับตำแหน่งที่เป็นไปได้ของหุ่นยนต์รวมถึงพฤติกรรมการทำงานต่าง ๆ เพื่อให้หน้าที่สำเร็จลุล่วง สิ่งเหล่านี้ต้องการหน่วยความจำจำนวนมากในการจัดเก็บและประมวลผลในการค้นหาขั้นตอนวิธีการดำเนินการจริง
เพื่อจัดการกับปัญหาเหล่านี้ นักวิจัยได้พัฒนาวิธีแบบใหม่แทนที่จะสร้างกราฟความเป็นไปได้ขนาดใหญ่ที่ครอบคลุมทั้งหมด พวกเขาสร้างการประมาณการที่เล็กกว่าขึ้นมาในรูปแบบโครงสร้างของต้นไม้ ในทุกขั้นตอนของกระบวนการ Algorithm จะเลือก Node หนึ่งมาจากกราฟขนาดใหญ่เติมลงบนแผนภูมิต้นไม้และเชื่อมต่อเส้นทางข้อมูลระหว่าง Node ในต้นไม้เพื่อหาเส้นทางที่ตรงที่สุดตั้งแต่เริ่มต้นจนจบกระบวนการ
เมื่อ Algorithm เกิดความก้าวหน้าขึ้น แผนภูมิแบบต้นไม้นี้จะยิ่งโตขึ้นใกล้เคียงกับกราฟจริงมากยิ่งขึ้นโดยไม่ต้องลงแรงสร้างมันขึ้นมาทั้งหมด เมื่อกราฟที่เพิ่มขึ้นนั้นมีขนาดเล็กกว่ามากมันทำให้ง่ายที่จะจัดเก็บหน่วยความจำ ยิ่งไปกว่านั้น เมื่อเป็นแผนภูมิแบบต้นไม้ การค้นหาในกราฟซึ่งมักจะเป็นความซับซ้อนแบบ Exponential กลายเป็นอะไรที่ง่ายอย่างมาก เนื่องจากสิ่งที่ต้องทำมีเพียงการติดตามในแต่ละลำดับจาก Node แม่กลับไปยังรากเพื่อหาเส้นทางการทำงานที่ต้องการ
เป็นที่รู้กันมานานแล้วว่าแนวคิดแบบแผนภูมิต้นไม้ที่เติบโตได้นั้นไม่อาจใช้ในการค้นหาในพื้นที่ของความเป็นไปได้สำหรับโซลูชันการควบคุมหุ่นยนต์แบบนี้ แต่ในตัวเอกสารงานวิจัยเปิดเผยว่ามีการใช้งานลูกเล่นอันชาญฉลาด 2 ประการ ได้แก่
- Algorithm เลือก Node ต่อไปโดยอ้างอิงจากภารกิจที่อยู่ในมือ ทำให้แผนภูมิต้นไม้สามารถประมาณการโซลูชันสำหรับปัญหาได้อย่างรวดเร็ว
- แม้ว่า Algorithm จะทำให้แผนภูมิต้นไม้โตขึ้น แต่มันยังสามารถตรวจพบวงรอบของพื้นที่กราฟดั้งเดิมซึ่งจับอยู่กับโซลูชันภารกิจของ Temporal Logic
นักวิจัยแสดงให้เห็นว่าวิธีการนี้สามารถหาทางออกได้เสมอแม้ว่าโดยทั่วไปแล้วจะไม่มีทางออก และวิธีนี้จะหาทางออกที่ได้ที่สุดได้อีกด้วย ทั้งยังแสดงให้เห็นด้วยว่าวิธีการนี้นั้นสามารถไปถึงเป้าหมายได้แบบรวดเร็วปานสายฟ้า
การทำงานกับปัญหาของหุ่นยนต์ 10 ตัวที่หาวิธีทำงานในพื้นที่ตาราง 50 x 50 หน่วย กับบ้าน 250 หลังที่ต้องเก็บจดหมาย Algorithm ที่ถูกออกแบบมาระดับแนวหน้าใช้เวลากว่า 30 นาทีในการหาโซลูชันที่ดีที่สุด ในขณะที่ STyLuS* ใช้เวลาประมาณ 20 วินาทีเท่านั้น
นักวิจัยได้ทดลองแก้ปัญหาหุ่นยนต์ 200 ตัวในโลกขนาดพื้นที่ตาราง 100 x 100 หน่วย ซึ่งถือว่าเป็นพื้นที่ที่ใหญ่เกินกว่า Algorithm ในปัจจุบันสามารถรับมือได้ อาทิ การส่งพัสดุ แม้ว่าในปัจจุบันจะไม่มีการใช้งานสัดส่วนเช่นนี้ แต่ถือว่าเป็นเรื่องในอนาคตอันใกล้ที่กำลังจะเกิดขึ้น
ที่มา:
Pratt.duke.edu
