การวางแผนการเคลื่อนที่

ตัวอย่างของพื้นที่งาน (workspace)

การวางแผนการเคลื่อนที่ (แม่แบบ:Langx) เป็นคำที่ใช้ในวิทยาการหุ่นยนต์ โดยมีความสำคัญต่อการพัฒนาหุ่นยนต์อัตโนมัติเป็นอย่างมาก ตัวอย่างของการวางแผนการเคลื่อนที่ได้แก่ ในกรณีของหุ่นยนต์เคลื่อนที่ได้ (mobile robot) เมื่อได้รับคำสั่งให้เดินทางจากห้องหนึ่งไปยังห้องถัดไปในอาคารสำนักงาน หุ่นยนต์จะมีวิธีการเดินทางอย่างไรเพื่อไปถึงจุดหมายโดยไม่ชนกับสิ่งกีดขวาง และไม่ตกบันได เป็นต้น ในกรณีของแขนกล (robot arm) ที่ใช้ในอุตสาหกรรม การวางแผนการเคลื่อนที่อาจสนใจว่าแต่ละข้อต่อ (joint) จะเคลื่อนไหวอย่างไรเพื่อไปหยิบจับวัตถุ และในกรณีของหุ่นยนต์ฮิวแมนนอยด์ หุ่นยนต์จะทำอย่างไรเพื่อก้มเก็บของที่อยู่ใต้โต๊ะ หรือจะก้าวเดินอย่างไร (footstep planning) โดยไม่ให้เหยียบสิ่งกีดขวางที่พื้น เป็นต้น

หลักการ

ปริภูมิโครงแบบของหุ่นยนต์ที่มีขนาดเป็นจุด โดย สีขาว = C_free และสีเทา = C_obs

ปริภูมิโครงแบบของหุ่นยนที่มีรูปร่างสี่เหลี่ยมเคลื่อนที่โดยการเลื่อนตำแหน่ง (สีแดงในรูป) โดย สีขาว = C_free และสีเทา = C_obs (สีเทาเข้ม = สิ่งกีดขวาง, สีเทาอ่อน = โครงแบบที่หุ่นยนต์เกิดการสัมผัสหรือชนสิ่งกีดขวางหรือออกจากพื้นที่งาน)

ตัวอย่างของเส้นทางเดินที่ดี

ตัวอย่างของเส้นทางเดินที่ไม่ดี

ตัวอย่างของ road map

ปัญหาพื้นฐานของการวางแผนการเคลื่อนที่คือการสร้างการเคลื่อนไหวอย่างต่อเนื่องตั้งแต่จุดเริ่มต้นไปยังจุดเป้าหมายโดยไม่ชนสิ่งกีดขวาง (obstacle) โดย ณ ตำแหน่งเริ่มต้น ท่าทางหรือโครงแบบ (configuration) ของหุ่นยนต์มักเขียนแทนด้วย S (starting configuration) ในขณะที่โครงแบบเป้าหมายนั้นแทนด้วย G (goal configuration) ปัญหาการวางแผนการเคลื่อนที่ของหุ่นยนต์ที่ง่ายที่สุด คือกรณีทราบตำแหน่งของสิ่งกีดขวางอยู่แต่แรก โดยปกติ เรขาคณิตของหุ่นยนต์และสิ่งกีดขวางอยู่ในปริภูมิ 2 มิติ หรือ 3 มิติ ที่เราเรียกว่า พื้นที่งาน (workspace) อย่างไรก็ตามเส้นทาง (path) การเคลื่อนที่ของหุ่นยนต์จะถูกอธิบายในปริภูมิโครงแบบ (configuration space) ซึ่งโดยปกติเป็นปริภูมิสูง

ปริภูมิโครงแบบ

ท่าทางหนึ่งๆ (pose) ของหุ่นยนต์ถูกเรียกว่าเป็น "โครงแบบ" (configuration) ของหุ่นยนต์ เซ็ตของโครงแบบที่เป็นไปได้ทั้งหมดเรียกว่า ปริภูมิโครงแบบ (configuration space) และมักนิยมเขียนแทนด้วยเซต C ยกตัวอย่างเช่น

• สมมติหุ่นยนต์มีขนาดเป็นเพียงจุด (ไม่มีขนาด) เคลื่อนที่บนพื้นที่งานที่เป็นระนาบ 2 มิติ ในกรณีนี้ปริภูมิโครงแบบ C คือระนาบ และโครงแบบของหุ่นยนต์สามารถเขียนอธิบายได้ด้วยพารามิเตอร์ 2 ค่าคือ (x, y)
• ถ้าหุ่นยนต์มีรูปร่างเพียง 2 มิติที่สามารถเลื่อนตำแหน่งและหมุนได้ พื้นที่งานในกรณีนี้จะยังคงเป็น 2 มิติ แต่ปริภูมิโครงแบบ C จะเป็นยูคลิเดียนกรุปแบบพิเศษ (special Euclidean group) SE(2) = R² $\times$ SO(2) (โดยที่ SO(2) เป็น special orthogonal group ของการหมุนใน 2 มิติ) และโครงแบบในกรณีนี้สามารถอธิบายได้ด้วยพารามิเตอร์ 3 ค่า ได้แก่ (x, y, θ)
• ถ้าหุ่นยนต์มีรูปร่างเพียง 2 มิติที่สามารถเลื่อนตำแหน่งและหมุนได้ พื้นที่งานในกรณีนี้จะเป็น 3 มิติ แต่ปริภูมิโครงแบบ C จะเป็นยูคลิเดียนกรุปแบบพิเศษ (special Euclidean group) SE(3) = R³ $\times$ SO(3) และโครงแบบในกรณีนี้สามารถอธิบายได้ด้วยพารามิเตอร์ 6 ค่า ได้แก่ (x, y, z) สำหรับการเลื่อนตำแหน่ง และ มุมออยเลอร์ (Euler_angles) (α, β, γ)
• ถ้าหุ่นยนต์เป็นหุ่นยนต์แบบแขนกลยึดติดอยู่กับที่ และมีข้อต่อจำนวน N ปริภูมิโครงแบบ C ในกรณีนี้จะเป็นปริภูมิ N มิติ

ปริภูมิว่าง

เซตของปริภูมิโครงแบบที่ไม่เกิดการชนกันกับสิ่งกีดขวาง เรียกว่า ปริภูมิว่าง (free space) เขียนแทนด้วย C_free ส่วนเติมเต็มของ C_free ในปริภูมิโครงแบบ C เรียกว่า obstacle region หรือ forbidden region เขียนแทนด้วย C_obs

โดยปกติการคำนวณหา C_free อยู่ตรงไหนในพื้นที่งานบ้างทำได้ยากมาก อย่างไรก็ตามปัจจุบันนี้การทดสอบว่าโครงแบบของหุ่นยนต์อยู่ใน C_free หรือไม่ สามารถทำได้โดยค่อนข้างมีประสิทธิภาพ กล่าวคือเริ่มต้นจากการใช้ forward kinematics เพื่อหาตำแหน่งทางเรขาคณิตของหุ่นยนต์ จากนั้นใช้การทดสอบการชนกัน (collision detection) เพื่อทดสอบว่าหุ่นยนต์ชนกับสิ่งกีดขวางหรือไม่

ขั้นตอนวิธี

• Grid-Based Search
• Geometric Algorithms
  • Visibility Graph
  • Cell Decomposition
• Potential Fields
• Sampling-Based Algorithms
  • Probabilistic Roadmap (PRM)
  • Lazy PRM
  • Rapidly-exploring random tree (RRT)

การประยุกต์ใช้งาน

• การเคลื่อนที่ของหุ่นยนต์ (Robot navigation)
• ระบบอัตโนมัติ (Automation)
• รถไร้คนขับ (Driverless car)
• หุ่นยนต์ศัลยกรรม (Robotic surgery)
• แอนิเมชัน
• protein folding

ดูเพิ่ม

• kinodynamic planning

แหล่งข้อมูลอื่น

• Robot Motion Planning โดย Jean-Claude Latombe สำนักพิมพ์ Kluwer Academic Publishers
• Planning Algorithms โดย Steven M. LaValle สำนักพิมพ์ Cambridge University Press (ISBN 0-521-86205-1)
• Principles of Robot Motion: Theory, Algorithms, and Implementation โดย H. Choset, W. Burgard, S. Hutchinson, G. Kantor, L. E. Kavraki, K. Lynch, และ S. Thrun สำนักพิมพ์ MIT Press จัดพิมพ์เมื่อ เมษายน ค.ศ. 2005