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

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

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

## หลักการ
thumb|ปริภูมิโครงแบบของหุ่นยนต์ที่มีขนาดเป็นจุด โดย สีขาว = ''C<sub>free</sub>'' และสีเทา = ''C<sub>obs</sub>''
thumb|ปริภูมิโครงแบบของหุ่นยนที่มีรูปร่างสี่เหลี่ยมเคลื่อนที่โดยการเลื่อนตำแหน่ง (สีแดงในรูป) โดย สีขาว = ''C<sub>free</sub>'' และสีเทา = ''C<sub>obs</sub>'' (สีเทาเข้ม = สิ่งกีดขวาง, สีเทาอ่อน = โครงแบบที่หุ่นยนต์เกิดการสัมผัสหรือชนสิ่งกีดขวางหรือออกจากพื้นที่งาน)
thumb|ตัวอย่างของเส้นทางเดินที่ดี
thumb|ตัวอย่างของเส้นทางเดินที่ไม่ดี
thumb|ตัวอย่างของ 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**2 \times **SO**(2) (โดยที่ **SO**(2) เป็น special orthogonal group ของการหมุนใน 2 มิติ) และโครงแบบในกรณีนี้สามารถอธิบายได้ด้วยพารามิเตอร์ 3 ค่า ได้แก่ (x, y, θ)
* ถ้าหุ่นยนต์มีรูปร่างเพียง 2 มิติที่สามารถเลื่อนตำแหน่งและหมุนได้ พื้นที่งานในกรณีนี้จะเป็น 3 มิติ แต่ปริภูมิโครงแบบ C จะเป็นยูคลิเดียนกรุปแบบพิเศษ (special Euclidean group) **SE(3)** = **R**3 \times **SO**(3) และโครงแบบในกรณีนี้สามารถอธิบายได้ด้วยพารามิเตอร์ 6 ค่า ได้แก่ (x, y, z) สำหรับการเลื่อนตำแหน่ง และ มุมออยเลอร์ (Euler_angles) (α, β, γ)
* ถ้าหุ่นยนต์เป็นหุ่นยนต์แบบแขนกลยึดติดอยู่กับที่ และมีข้อต่อจำนวน N ปริภูมิโครงแบบ C ในกรณีนี้จะเป็นปริภูมิ N มิติ

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

โดยปกติการคำนวณหา Cfree อยู่ตรงไหนในพื้นที่งานบ้างทำได้ยากมาก อย่างไรก็ตามปัจจุบันนี้การทดสอบว่าโครงแบบของหุ่นยนต์อยู่ใน Cfree หรือไม่ สามารถทำได้โดยค่อนข้างมีประสิทธิภาพ กล่าวคือเริ่มต้นจากการใช้ 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
* *[http://planning.cs.uiuc.edu 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

ผการวางแผนการเคลื่อนที่
ผการวางแผนการเคลื่อนที่
ผการวางแผนการเคลื่อนที่
หมวดหมู่:วิทยาการคอมพิวเตอร์เชิงทฤษฎี