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

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

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

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

การกำหนดค่า (Configuration) อธิบายถึงท่าทางของหุ่นยนต์ และปริภูมิการกำหนดค่า C คือเซตของการกำหนดค่าที่เป็นไปได้ทั้งหมด ตัวอย่างเช่น:

• ถ้าหุ่นยนต์เป็นจุดเดียว (ขนาดเป็นศูนย์) ที่เคลื่อนที่ในระนาบ 2 มิติ (พื้นที่ทำงาน) C ก็คือระนาบ และการกำหนดค่าสามารถแสดงได้โดยใช้พารามิเตอร์สองตัว (x, y)
• ถ้าหุ่นยนต์เป็นรูปทรง 2 มิติที่สามารถเคลื่อนที่และหมุนได้ พื้นที่ทำงานก็ยังคงเป็น 2 มิติ อย่างไรก็ตาม C คือกลุ่มยูคลิดพิเศษSE (2) = R ² SO (2) (โดยที่SO (2) คือกลุ่มออร์โธโกนอลพิเศษของการหมุน 2 มิติ) และสามารถแสดงการกำหนดค่าโดยใช้พารามิเตอร์ 3 ตัว (x, y, θ)${\displaystyle \times }$
• ถ้าหุ่นยนต์เป็นรูปทรง 3 มิติแข็งที่สามารถแปลและหมุนได้ พื้นที่ทำงานจะเป็น 3 มิติ แต่ C เป็นกลุ่มยุคลิดพิเศษSE(3) = R ³ SO (3) ดังนั้นการกำหนดค่าจะต้องใช้พารามิเตอร์ 6 ตัว: (x, y, z) สำหรับการแปล และมุมออยเลอร์ (α, β, γ)${\displaystyle \times }$
• ถ้าหุ่นยนต์เป็นหุ่นยนต์แบบฐานคงที่ที่มีข้อต่อหมุนได้ N ข้อ (และไม่มีวงปิด) ค่า C จะมีมิติ N
• หากไม่ สามารถยอมรับ ปัญหา gimbal lock ได้ (เช่น ในR ^Nที่N ≥ 3 ) อาจจำเป็นต้องใช้ควอเทอร์เนียนหรือ วิธีการแก้ไข อื่นๆซึ่งจะทำให้มิติการหมุนหรือความซับซ้อนของวิธีการแก้ปัญหาเพิ่มขึ้น

เซตของการจัดเรียงที่หลีกเลี่ยงการชนกับสิ่งกีดขวางเรียกว่า พื้นที่ว่าง C _freeส่วนเติมเต็มของ C _freeใน C เรียกว่า สิ่งกีดขวาง หรือ บริเวณต้องห้าม

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

พื้นที่เป้าหมาย (Target space) คือพื้นที่ย่อยของพื้นที่ว่างที่บ่งบอกถึงตำแหน่งที่เราต้องการให้หุ่นยนต์เคลื่อนที่ไป ในการวางแผนการเคลื่อนที่แบบทั่วโลก (Global motion planning) พื้นที่เป้าหมายสามารถสังเกตได้ด้วยเซ็นเซอร์ของหุ่นยนต์ อย่างไรก็ตาม ในการวางแผนการเคลื่อนที่แบบเฉพาะที่ (Local motion planning) หุ่นยนต์ไม่สามารถสังเกตพื้นที่เป้าหมายได้ในบางสถานะ เพื่อแก้ปัญหานี้ หุ่นยนต์จึงเคลื่อนที่ผ่านพื้นที่เป้าหมายเสมือนหลายแห่ง ซึ่งแต่ละแห่งตั้งอยู่ภายในพื้นที่ที่สามารถสังเกตได้ (รอบตัวหุ่นยนต์) พื้นที่เป้าหมายเสมือนนี้เรียกว่าเป้าหมายย่อย (Sub-goal)

พื้นที่สิ่งกีดขวาง คือพื้นที่ที่หุ่นยนต์ไม่สามารถเคลื่อนที่เข้าไปได้ พื้นที่สิ่งกีดขวางไม่ใช่สิ่งที่ตรงข้ามกับพื้นที่โล่ง

ปัญหาที่มีมิติต่ำสามารถแก้ไขได้ด้วยอัลกอริธึมแบบกริดที่วางกริดทับซ้อนบนพื้นที่การกำหนดค่า หรืออัลกอริธึมเชิงเรขาคณิตที่คำนวณรูปร่างและการเชื่อมต่อของ C ที่ เป็น _{อิสระ}

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

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

วิธีการแบบตารางจะวางตารางลงบนพื้นที่การกำหนดค่า และสมมติว่าแต่ละการกำหนดค่าถูกระบุด้วยจุดตาราง ในแต่ละจุดตาราง หุ่นยนต์สามารถเคลื่อนที่ไปยังจุดตารางที่อยู่ติดกันได้ ตราบใดที่เส้นระหว่างจุดเหล่านั้นอยู่ภายใน_{ขอบเขต} C อย่างสมบูรณ์ (ซึ่งทดสอบด้วยการตรวจจับการชน) วิธีนี้จะแบ่งชุดการกระทำออกเป็นส่วนย่อยๆ และ ใช้ อัลกอริธึมการค้นหา (เช่นA* ) เพื่อหาเส้นทางจากจุดเริ่มต้นไปยังเป้าหมาย

วิธีการเหล่านี้จำเป็นต้องกำหนดความละเอียดของตารางกริด การค้นหาจะเร็วขึ้นเมื่อใช้ตารางกริดที่หยาบกว่า แต่ขั้นตอนวิธีจะไม่สามารถค้นหาเส้นทางผ่านส่วนแคบๆ ของ C _freeได้ นอกจากนี้ จำนวนจุดบนตารางกริดจะเพิ่มขึ้นแบบทวีคูณตามมิติของปริภูมิการกำหนดค่า ซึ่งทำให้ไม่เหมาะสมสำหรับปัญหาที่มีมิติสูง

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

วิธีการแบบใช้ตารางมักต้องค้นหาซ้ำๆ เช่น เมื่อความรู้ของหุ่นยนต์เกี่ยวกับพื้นที่การกำหนดค่าเปลี่ยนแปลง หรือพื้นที่การกำหนดค่าเองเปลี่ยนแปลงไปในระหว่างการติดตามเส้นทาง อัลกอริ ทึม การค้นหาแบบฮิวริสติกแบบเพิ่มขึ้นจะวางแผนใหม่ได้อย่างรวดเร็วโดยใช้ประสบการณ์จากปัญหาการวางแผนเส้นทางที่คล้ายกันก่อนหน้านี้เพื่อเร่งความเร็วในการค้นหาสำหรับปัญหาปัจจุบัน

แนวทางเหล่านี้คล้ายกับแนวทางการค้นหาแบบกริด ยกเว้นว่าจะสร้างการปูพื้นครอบคลุมพื้นที่การกำหนดค่าทั้งหมดแทนที่จะเป็นกริด^{[ 1 ]}การปูพื้นจะถูกแบ่งออกเป็นสองส่วนย่อย X ⁻ ,X ⁺ที่สร้างขึ้นด้วยกล่อง โดยที่ X ⁻ ⊂ C _free ⊂ X ⁺การกำหนดลักษณะของ C _freeเทียบเท่ากับการแก้ปัญหาการผกผันเซต ดังนั้น การวิเคราะห์ช่วงเวลาจึงสามารถใช้ได้เมื่อ C _freeไม่สามารถอธิบายได้ด้วยอสมการเชิงเส้นเพื่อให้มีการล้อมรอบที่รับประกันได้

ดังนั้นหุ่นยนต์จึงสามารถเคลื่อนที่ได้อย่างอิสระใน X ⁻และไม่สามารถออกไปนอก X ⁺ได้ สำหรับพื้นผิวย่อยทั้งสอง จะมีการสร้างกราฟเพื่อนบ้าน และสามารถค้นหาเส้นทางได้โดยใช้อัลกอริธึม เช่นDijkstraหรือA*เมื่อเส้นทางเป็นไปได้ใน X ⁻ เส้นทาง นั้นก็จะเป็นไปได้ใน C _free ด้วยเช่นกัน เมื่อไม่มีเส้นทางใน X ⁺จากการกำหนดค่าเริ่มต้นหนึ่งไปยังเป้าหมาย เราจะรับประกันได้ว่าไม่มีเส้นทางที่เป็นไปได้ใน C _freeสำหรับวิธีการแบบตาราง วิธีการแบบช่วงนั้นไม่เหมาะสมสำหรับปัญหาที่มีมิติสูง เนื่องจากจำนวนกล่องที่จะสร้างนั้นเพิ่มขึ้นแบบทวีคูณเมื่อเทียบกับมิติของพื้นที่การกำหนดค่า

ภาพประกอบแสดงรูปสามรูปทางด้านขวา ซึ่งแสดงให้เห็นว่าขอเกี่ยวที่มีองศาอิสระสององศาจะต้องเคลื่อนที่จากซ้ายไปขวา โดยหลีกเลี่ยงส่วนแนวนอนเล็กๆ สองส่วน

Nicolas Delanoueได้แสดงให้เห็นว่าการแยกส่วนด้วยการปูพื้นย่อยโดยใช้การวิเคราะห์ช่วงเวลายังทำให้สามารถกำหนดลักษณะโทโพโลยีของ C ได้ อย่าง _{อิสระ}เช่น การนับจำนวนส่วนประกอบที่เชื่อมต่อกัน^{[ 2 ]}

หุ่นยนต์แบบจุดเคลื่อนที่ท่ามกลางสิ่งกีดขวางรูปหลายเหลี่ยม

• กราฟการมองเห็น
• การสลายตัวของเซลล์
• แผนภาพโวโรนอย

การเคลื่อนย้ายวัตถุผ่านสิ่งกีดขวาง

• ผลรวมมินคอฟสกี

การหาทางออกจากอาคาร

• การติดตามรังสีที่ไกลที่สุด

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

แนวทางหนึ่งคือการพิจารณาการกำหนดค่าของหุ่นยนต์เป็นจุดในสนามศักย์ที่รวมแรงดึงดูดไปยังเป้าหมายและแรงผลักจากสิ่งกีดขวาง วิถีที่ได้จะถูกส่งออกเป็นเส้นทาง แนวทางนี้มีข้อดีตรงที่วิถีถูกสร้างขึ้นโดยใช้การคำนวณน้อย อย่างไรก็ตาม อาจติดอยู่ในจุดต่ำสุดเฉพาะที่ของสนามศักย์และไม่สามารถหาเส้นทางได้ หรืออาจพบเส้นทางที่ไม่เหมาะสม สนามศักย์เทียมสามารถพิจารณาได้ว่าเป็นสมการต่อเนื่องคล้ายกับสนามศักย์ไฟฟ้าสถิต (โดยพิจารณาหุ่นยนต์เหมือนประจุจุด) หรือการเคลื่อนที่ผ่านสนามสามารถแบ่งย่อยได้โดยใช้ชุดกฎทางภาษา^{[ 3 ]}ฟังก์ชันการนำทาง^{[ 4 ]}หรือฟังก์ชันการนำทางเชิงความน่าจะเป็น^{[ 5 ]}เป็นฟังก์ชันศักย์เทียมประเภทหนึ่งที่มีคุณสมบัติที่ไม่มีจุดต่ำสุดยกเว้นจุดเป้าหมาย

อัลกอริทึมแบบใช้การสุ่มตัวอย่างจะแสดงพื้นที่การกำหนดค่าด้วยแผนที่เส้นทางของการกำหนดค่าที่สุ่มมา อัลกอริทึมพื้นฐานจะสุ่มตัวอย่างการกำหนดค่า N รายการใน C และเก็บการกำหนดค่าเหล่านั้นไว้ใน C _{ที่ว่างอยู่}เพื่อใช้เป็นจุดสำคัญจากนั้นจะสร้างแผนที่เส้นทางที่เชื่อมต่อจุดสำคัญสองจุด P และ Q หากส่วนของเส้นตรง PQ อยู่ใน C _{ที่ว่างอยู่} ทั้งหมด การตรวจจับการชนกันจะใช้เพื่อทดสอบการรวมอยู่ใน C _{ที่ว่างอยู่}เพื่อค้นหาเส้นทางที่เชื่อมต่อ S และ G จะเพิ่ม S และ G ลงในแผนที่เส้นทาง หากเส้นทางในแผนที่เส้นทางเชื่อมโยง S และ G ตัววางแผนจะทำงานสำเร็จและส่งคืนเส้นทางนั้น หากไม่สำเร็จ สาเหตุไม่แน่ชัด อาจไม่มีเส้นทางใน C _{ที่ว่างอยู่}หรือตัววางแผนไม่ได้สุ่มตัวอย่างจุดสำคัญมากพอ

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

ภายใต้เงื่อนไขการมองเห็น พื้นฐานบน C _{ที่เป็นอิสระ ได้}มีการพิสูจน์แล้วว่าเมื่อจำนวนการกำหนดค่า N เพิ่มมากขึ้น ความน่าจะเป็นที่อัลกอริทึมข้างต้นจะพบวิธีแก้ปัญหาจะเข้าใกล้ 1 แบบเลขชี้กำลัง^{[ 6 ]}การมองเห็นไม่ได้ขึ้นอยู่กับมิติของ C อย่างชัดเจน เป็นไปได้ที่จะมีพื้นที่มิติสูงที่มีการมองเห็น "ดี" หรือพื้นที่มิติต่ำที่มีการมองเห็น "แย่" ความสำเร็จในการทดลองของวิธีการตามตัวอย่างชี้ให้เห็นว่าพื้นที่ที่พบเห็นได้บ่อยที่สุดมีการมองเห็นที่ดี

รูปแบบพื้นฐานนี้สามารถปรับเปลี่ยนได้หลายแบบ:

• โดยทั่วไปแล้ว การทดสอบเฉพาะส่วนระหว่างจุดสำคัญที่อยู่ใกล้เคียงกันจะเร็วกว่าการทดสอบทุกคู่มาก
• การกระจายตัวของการสุ่มตัวอย่างที่ไม่สม่ำเสมอ มีจุดมุ่งหมายเพื่อวางจุดสำคัญต่างๆ ในพื้นที่ที่ช่วยปรับปรุงการเชื่อมต่อของแผนงานให้ดียิ่งขึ้น
• โดยทั่วไปแล้ว ตัวอย่างแบบ กึ่งสุ่มจะให้การครอบคลุมพื้นที่การกำหนดค่าที่ดีกว่า ตัวอย่าง แบบสุ่มเทียมแม้ว่างานวิจัยล่าสุดบางชิ้นจะโต้แย้งว่าผลกระทบของแหล่งที่มาของความสุ่มนั้นมีน้อยมากเมื่อเทียบกับผลกระทบของการกระจายตัวของการสุ่มตัวอย่าง
• ใช้การสุ่มตัวอย่างแบบโลคอล^{[ 7 ]}โดยดำเนินการเดินสุ่มแบบมอนเตคาร์โลของลูกโซ่มาร์คอฟ แบบมีทิศทาง ด้วยการกระจายข้อเสนอแบบโลคอลบางอย่าง
• เป็นไปได้ที่จะลดจำนวนหลักไมล์ที่จำเป็นในการแก้ปัญหาที่กำหนดลงอย่างมากโดยการอนุญาตให้มองเห็นแบบโค้ง (ตัวอย่างเช่นโดยการคลานบนสิ่งกีดขวางที่ขวางทางระหว่างหลักไมล์สองหลัก^{[ 8 ]} )
• หากต้องการเพียงคำถามวางแผนเพียงหนึ่งหรือสองคำถาม ก็ไม่จำเป็นต้องสร้างแผนที่เส้นทางของพื้นที่ทั้งหมดเสมอไป โดยทั่วไปแล้ว วิธีการขยายโครงสร้างแบบต้นไม้จะเร็วกว่าในกรณีนี้ (การวางแผนสำหรับคำถามเดียว) แผนที่เส้นทางยังคงมีประโยชน์หากต้องถามคำถามหลายคำถามในพื้นที่เดียวกัน (การวางแผนสำหรับหลายคำถาม)

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

• เส้นทางดูบินส์
• อุปสรรคด้านความเร็ว
• กราฟการมองเห็น

กล่าวได้ว่าโปรแกรมวางแผนการเคลื่อนที่นั้นสมบูรณ์หากโปรแกรมวางแผนนั้นสามารถสร้างคำตอบได้ภายในเวลาจำกัด หรือรายงานได้อย่างถูกต้องว่าไม่มีคำตอบ อัลกอริทึมที่สมบูรณ์ส่วนใหญ่เป็นแบบที่ใช้เรขาคณิตเป็นพื้นฐาน ประสิทธิภาพของโปรแกรมวางแผนที่สมบูรณ์จะถูกประเมินจากความซับซ้อนในการคำนวณเมื่อพิสูจน์คุณสมบัตินี้ทางคณิตศาสตร์ จำเป็นต้องแน่ใจว่าเกิดขึ้นภายในเวลาจำกัด ไม่ใช่เพียงแค่ในขีดจำกัดเชิงอะซิมโทติกเท่านั้น นี่เป็นปัญหาอย่างยิ่งหากเกิดลำดับอนันต์ (ซึ่งลู่เข้าเฉพาะในกรณีลิมิต) ในระหว่างเทคนิคการพิสูจน์เฉพาะ เนื่องจากในทางทฤษฎีแล้ว อัลกอริทึมจะไม่หยุดทำงาน "กลเม็ด" ที่เข้าใจง่าย (มักอิงตามการอุปมาน) มักถูกเข้าใจผิดว่าลู่เข้า ซึ่งจริงๆ แล้วลู่เข้าเฉพาะในขีดจำกัดอนันต์เท่านั้น กล่าวอีกนัยหนึ่งคือ คำตอบมีอยู่ แต่โปรแกรมวางแผนจะไม่รายงานคำตอบนั้น คุณสมบัตินี้จึงเกี่ยวข้องกับความสมบูรณ์ของทัวริงและในกรณีส่วนใหญ่ทำหน้าที่เป็นพื้นฐาน/แนวทางทางทฤษฎี โปรแกรมวางแผนที่ใช้แนวทางแบบใช้กำลังทั้งหมด (brute force) นั้นสมบูรณ์เสมอ แต่จะใช้งานได้จริงเฉพาะกับการตั้งค่าที่มีจำนวนจำกัดและไม่ต่อเนื่องเท่านั้น

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

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

ความสมบูรณ์ของความละเอียด (Resolution completeness)คือคุณสมบัติที่รับประกันว่าตัววางแผนจะสามารถหาเส้นทางได้หากความละเอียดของตารางกริดพื้นฐานมีความละเอียดเพียงพอ ตัววางแผนที่มีความสมบูรณ์ของความละเอียดส่วนใหญ่จะใช้ตารางกริดหรือช่วงเวลาเป็นพื้นฐาน ความซับซ้อนในการคำนวณของตัววางแผนที่มีความสมบูรณ์ของความละเอียดขึ้นอยู่กับจำนวนจุดในตารางกริดพื้นฐาน ซึ่งคือ O(1/h ^d ) โดยที่ h คือความละเอียด (ความยาวด้านหนึ่งของเซลล์กริด) และ d คือมิติของพื้นที่การกำหนดค่า

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

แผนงาน ที่ไม่สมบูรณ์ไม่ได้สร้างเส้นทางที่เป็นไปได้เสมอไป แม้ว่าจะมีเส้นทางที่เป็นไปได้อยู่ก็ตาม (ดูย่อหน้าแรก) บางครั้งแผนงานที่ไม่สมบูรณ์ก็ทำงานได้ดีในทางปฏิบัติ เนื่องจากมันจะหยุดลงหลังจากเวลาที่กำหนดไว้ และปล่อยให้ขั้นตอนอื่นๆ ดำเนินต่อไป

มีการพัฒนาอัลกอริธึมมากมายเพื่อจัดการกับปัญหาพื้นฐานนี้ในรูปแบบต่างๆ

โฮโลโนมิก

• แขนกล (พร้อมระบบกลไก)

นอนโฮโลโนมิก

• โดรน
• รถยนต์
• จักรยานล้อเดียว
• เครื่องบิน
• ระบบที่มีขอบเขตความเร่ง
• สิ่งกีดขวางที่เคลื่อนที่ได้ (เวลาไม่สามารถย้อนกลับได้)
• เข็มปลายเฉียงที่สามารถปรับทิศทางได้
• หุ่นยนต์ขับเคลื่อนแบบดิฟเฟอเรนเชียล

ระบบไฮบริดคือระบบที่ผสมผสานพฤติกรรมแบบไม่ต่อเนื่องและแบบต่อเนื่อง ตัวอย่างของระบบดังกล่าวได้แก่:

• การควบคุมหุ่นยนต์
• การประกอบเชิงกล
• การเคลื่อนที่ของหุ่นยนต์ขาเดิน
• หุ่นยนต์ที่ปรับเปลี่ยนโครงสร้างได้

• ความไม่แน่นอนของการเคลื่อนไหว
• ข้อมูลที่ขาดหายไป
• การตรวจจับเชิงรุก
• การวางแผนแบบไร้เซ็นเซอร์
• ระบบควบคุมเครือข่าย^{[ 9 ]}

• แผนที่ของพลวัต^{[ 10 ]}

• การนำทางหุ่นยนต์
• ระบบอัตโนมัติ
• รถยนต์ไร้คนขับ
• การผ่าตัดด้วยหุ่นยนต์
• แอนิเมชั่นตัวละครดิจิทัล
• การพับโปรตีน^{[ 11 ]}
• ความปลอดภัยและการเข้าถึงได้ในงานออกแบบสถาปัตยกรรมโดยใช้คอมพิวเตอร์ช่วย

• ระบบล็อกแกนหมุน – ปัญหาที่พบได้ทั่วไปในงานวิศวกรรมเครื่องกลเช่นกัน
• การวางแผนจลนพลศาสตร์  – ประเภทของปัญหา
• ปัญหาการปีนเขา  – ปัญหาทางคณิตศาสตร์
• รายชื่อซอฟต์แวร์หุ่นยนต์
• ปัญหาการเคลื่อนย้ายโซฟา – ปัญหาทางคณิตศาสตร์เกี่ยวกับการหาวัตถุสองมิติที่มีขนาดใหญ่ที่สุดที่สามารถเคลื่อนย้ายไปรอบมุมได้
• OMPL – คลังข้อมูลการวางแผนการเคลื่อนไหวแบบเปิด
• OpenRAVE — การทดสอบ พัฒนา และใช้งานอัลกอริธึมการวางแผนการเคลื่อนที่ในแอปพลิเคชันหุ่นยนต์ในโลกแห่งความเป็นจริง
• การค้นหาเส้นทาง  – การวางแผนเส้นทางโดยใช้โปรแกรมคอมพิวเตอร์
• ปัญหาการเคลื่อนที่ของก้อนหิน – การวางแผนการเคลื่อนที่ของหุ่นยนต์หลายตัว
• ปัญหาเส้นทางที่สั้นที่สุด  – ปัญหาการคำนวณในทฤษฎีกราฟ

• Latombe, Jean-Claude (2012). การวางแผนการเคลื่อนที่ของหุ่นยนต์ . Springer Science & Business Media. ISBN 978-1-4615-4022-9.
• อัลกอริทึมการวางแผน , สตีเวน เอ็ม. ลาวาลล์, 2006, สำนักพิมพ์มหาวิทยาลัยเคมบริดจ์, ISBN 0-521-86205-1.
• หลักการเคลื่อนที่ของหุ่นยนต์: ทฤษฎี อัลกอริทึม และการนำไปใช้โดย H. Choset, W. Burgard, S. Hutchinson, G. Kantor, LE Kavraki , K. Lynch และ S. Thrun สำนักพิมพ์ MIT Press เมษายน 2548
• มาร์ค เดอ เบิร์ก; มาร์ค ฟาน เครเวลด์; มาร์ค โอเวอร์มาร์สและออตฟรีด ชวาร์สคอฟ (2000) เรขาคณิตเชิงคำนวณ (แก้ไขครั้งที่ 2) สปริงเกอร์-แวร์แล็ก . ไอเอสบีเอ็น 978-3-540-65620-3.บทที่ 13: การวางแผนการเคลื่อนที่ของหุ่นยนต์: หน้า 267–290

วิกิมีเดียคอมมอนส์มีสื่อที่เกี่ยวข้องกับการวางแผนการเคลื่อนไหว

• "สภาพแวดล้อมเสมือนจริงสำหรับการทำงานอัตโนมัติของหุ่นยนต์แบบเปิด" http://openrave.org/
• ฌอง-คล็อด ลาทอมบ์ กล่าวถึงงานวิจัยของเขาเกี่ยวกับหุ่นยนต์และการวางแผนการเคลื่อนที่ เมื่อวันที่ 5 เมษายน 2543
• "Open Motion Planning Library ( OMPL )", http://ompl.kavrakilab.org
• "คลังกลยุทธ์การเคลื่อนไหว" http://msl.cs.uiuc.edu/msl/
• "ชุดเครื่องมือวางแผนการเคลื่อนไหว" https://ai.stanford.edu/~mitul/mpk
• "Simox", http://simox.sourceforge.net
• "การวางแผนและควบคุมการเคลื่อนที่ของหุ่นยนต์", http://www.laas.fr/%7Ejpl/book.html