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

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

องค์ประกอบของปัญหา MAPF แบบคลาสสิก^{[ 1 ]} มีดังต่อไปนี้:

• กลุ่มตัวแทน;${\displaystyle A=\{1,2,...,k\}}$${\displaystyle k}$
• กราฟ แบบไม่มีทิศทางโดยที่คือเซตของโหนด และคือเซตของขอบ โหนดแสดงถึงตำแหน่งที่เป็นไปได้ของตัวแทน ในขณะที่ส่วนโค้งแสดงถึงการเชื่อมต่อที่เป็นไปได้ระหว่างตำแหน่งเหล่านั้น${\displaystyle G=(V,E)}$${\displaystyle V}$${\displaystyle E}$
• แผนที่ที่เชื่อมโยงตัวแทนแต่ละตัวกับจุดเริ่มต้นของมัน${\displaystyle s:A\to V}$
• แผนที่ที่เชื่อมโยงตัวแทนแต่ละตัวกับจุดเป้าหมายของมัน${\displaystyle t:A\to V}$

ถือว่าเวลาเป็นช่วงเวลาที่ไม่ต่อเนื่อง และตัวแทนแต่ละตัวสามารถกระทำการได้หนึ่งครั้งในแต่ละช่วงเวลา การกระทำมีสองประเภทที่เป็นไปได้ ได้แก่ การรอ ซึ่งตัวแทนจะคงอยู่ในโหนดของตน และการเคลื่อนที่ ซึ่งอนุญาตให้ตัวแทนเคลื่อนที่ไปยังโหนดที่อยู่ติดกัน การกระทำถูกกำหนดเป็นฟังก์ชันหมายความว่าแทนการเคลื่อนที่จากไปยังถ้าอยู่ติดกับและแตกต่างจากหรือแทนการอยู่ในโหนดถ้าเป็นจริง ${\displaystyle a:V\to V}$${\displaystyle a(v)=v'}$${\displaystyle v}$${\displaystyle v'}$${\displaystyle v'}$${\displaystyle v}$${\displaystyle v'}$${\displaystyle v}$${\displaystyle v=v'}$

ตัวแทนจะทำการกระทำตามลำดับเพื่อไปยังตำแหน่งเป้าหมายจากจุดเริ่มต้น ลำดับการกระทำที่ตัวแทนทำจะถูกแทนด้วยและเรียกว่าแผน หากตัวแทนเริ่มต้นจากตำแหน่งของตนและไปถึงตำแหน่งเป้าหมายโดยทำตามแผนจะเรียกว่าแผนตัวแทนเดี่ยวสำหรับตัวแทน[ ^{1 ] วิธี}แก้ปัญหา MAPF ที่ถูกต้องคือชุดของแผนตัวแทนเดี่ยว (หนึ่งแผนสำหรับแต่ละตัวแทน) โดยที่แผนเหล่านั้นจะไม่ขัดแย้งกัน เมื่อตัวแทนไปถึงเป้าหมายแล้ว ตัวแทนสามารถอยู่ที่ตำแหน่งเป้าหมายหรือหายไปก็ได้^{[ 1 ]}${\displaystyle i}$${\displaystyle \pi _{i}=(a_{1},a_{2},...,a_{n})}$${\displaystyle i}$${\displaystyle s(i)}$${\displaystyle t(i)}$${\displaystyle \pi _{i}}$${\displaystyle \pi _{i}}$${\displaystyle i}$${\displaystyle k}$

เพื่อให้ได้วิธีแก้ปัญหา MAPF ที่ถูกต้อง จำเป็นต้องให้แผนตัวแทนเดี่ยวของตัวแทนไม่ชนกัน เมื่อกำหนดแผนนิพจน์ จะ ^ระบุตำแหน่งของตัวแทนหลังจากดำเนินการตามขั้นตอนของแผนสามารถแยกแยะการชนกันได้ 5 ประเภทที่แตกต่างกันระหว่างแผนสองแผนและ^{[ 1} ]${\displaystyle k}$${\displaystyle \pi _{i}}$${\displaystyle \pi _{i}[x]}$${\displaystyle i}$${\displaystyle x}$${\displaystyle \pi _{i}}$${\displaystyle \pi _{i}}$${\displaystyle \pi _{j}}$

• ความขัดแย้งของจุดยอด: เกิดความขัดแย้งของจุดยอดระหว่างแผนงานและเมื่อตัวแทนทั้งสองครอบครองตำแหน่งเดียวกันในเวลาเดียวกัน โดยทั่วไปแล้ว ความขัดแย้งของจุดยอดเกิดขึ้นเมื่อ...${\displaystyle \pi _{i}}$${\displaystyle \pi _{j}}$${\displaystyle \pi _{i}[x]=\pi _{j}[x]}$
• ความขัดแย้งที่ขอบ: ความขัดแย้งที่ขอบเกิดขึ้นเมื่อตัวแทนสองตัวข้ามขอบเดียวกันในทิศทางเดียวกันในเวลาเดียวกัน นั่นคือและหากไม่อนุญาตให้เกิดความขัดแย้งที่จุดยอด ความขัดแย้งที่ขอบก็ไม่สามารถเกิดขึ้นได้${\displaystyle \pi _{i}[x]=\pi _{j}[x]}$${\displaystyle \pi _{i}[x+1]=\pi _{j}[x+1]}$
• ความขัดแย้งที่ตามมา: ความขัดแย้งที่ตามมาเกิดขึ้นเมื่อในขั้นตอนเวลาหนึ่ง ตัวแทนหนึ่งเข้าครอบครองตำแหน่งที่ตัวแทนอื่นเคยครอบครองในขั้นตอนเวลาก่อนหน้า ในทางคณิตศาสตร์ ความขัดแย้งที่ตามมาสามารถอธิบายได้ดังนี้${\displaystyle \pi _{i}[x+1]=\pi _{j}[x]}$
• ความขัดแย้งแบบวงจร: ความขัดแย้งแบบวงจรเกิดขึ้นเมื่อกลุ่มของเอเจนต์ (อย่างน้อยสามตัว) เคลื่อนที่ราวกับกำลังหมุนวนเป็นวงจร นั่นหมายความว่าเอเจนต์แต่ละตัวจะเข้าไปอยู่ในตำแหน่งที่เอเจนต์อื่นเคยครอบครองอยู่ก่อนหน้านี้ โดยเลื่อนไปข้างหน้าหนึ่งขั้นในวงจร หากห้ามความขัดแย้งต่อไปนี้ ความขัดแย้งแบบวงจรก็จะไม่เกิดขึ้น
• ความขัดแย้งจากการสลับตำแหน่ง: ความขัดแย้งจากการสลับตำแหน่งคือกรณีที่ตัวแทนสองตัวสลับตำแหน่งกัน โดยผ่านขอบเดียวกันในเวลาเดียวกันแต่ในสองทิศทางที่แตกต่างกัน สามารถแสดงได้เป็นและ${\displaystyle \pi _{i}[x+1]=\pi _{j}[x]}$${\displaystyle \pi _{j}[x+1]=\pi _{i}[x]}$

เมื่อกำหนดรูปแบบปัญหา MAPF อย่างเป็นทางการ จะสามารถตัดสินใจได้ว่าความขัดแย้งใดที่อนุญาตและความขัดแย้งใดที่ห้าม ไม่มีมาตรฐานที่เป็นเอกภาพเกี่ยวกับความขัดแย้งที่อนุญาตและห้าม แต่โดยทั่วไปแล้วความขัดแย้งระหว่างจุดยอดและขอบจะไม่ได้รับอนุญาต^{[ 1 ]}

เมื่อคำนวณแผนตัวแทนเดี่ยว เป้าหมายคือการเพิ่มฟังก์ชันวัตถุประสงค์ที่ผู้ใช้กำหนดสูงสุด ไม่มีฟังก์ชันวัตถุประสงค์มาตรฐานที่จะนำมาใช้ อย่างไรก็ตาม ฟังก์ชันที่พบได้บ่อยที่สุดคือ: ^{[ 1 ]}

• เวลาไหล (flowtime): ค่านี้ได้มาจากการรวมจำนวนขั้นเวลาที่แต่ละเอเจนต์ใช้ในการไปถึงตำแหน่งเป้าหมาย ในทางทฤษฎีแล้ว จะเท่ากับ โดยที่แผนต่างๆเป็นแผนของเอเจนต์เดียวที่ไม่มีการชนกัน${\displaystyle \sum _{i\in A}|\pi _{i}|}$${\displaystyle \pi _{i},i\in A}$
• makespan: จำนวนขั้นตอนเวลาที่จำเป็นเพื่อให้เอเจนต์ทั้งหมดทำงานให้เสร็จสมบูรณ์ โดยกำหนดเป็น โดยที่เป็นส่วนหนึ่งของโซลูชันที่ถูกต้อง${\displaystyle \max _{i\in A}|\pi _{i}|}$${\displaystyle \pi _{i}}$${\displaystyle ,i\in A}$
• การเพิ่มจำนวนเป้าหมายที่บรรลุได้สูงสุดภายใต้กำหนดเวลา: จุดมุ่งหมายคือการค้นหาวิธีแก้ปัญหาที่ถูกต้องซึ่งจะเพิ่มจำนวนตัวแทนที่บรรลุเป้าหมายได้สูงสุดภายใต้กำหนดเวลา^{[ 2 ]}

มีการเสนออัลกอริทึมหลายตัวเพื่อแก้ปัญหา MAPF ปัญหาคือการค้นหาโซลูชัน makespan หรือ flow-time ที่เหมาะสมที่สุด นั้นเป็นปัญหา NP-hard ^{[ 3 ]}แม้ว่าจะพิจารณากราฟระนาบ^{[ 4 ]}กราฟที่คล้ายกับกริด^{[ 5 ]}กราฟต้นไม้^{[ 6 ]}แม้ว่าต้นไม้จะมีจำนวนใบที่จำกัดหรือจำนวนจุดยอดภายในที่จำกัดก็ตาม^{[ 7 ]}สำหรับโซลูชันที่ไม่เหมาะสมที่มีขอบเขตจำกัดนั้น พบว่าการค้นหาโซลูชัน makespan ที่เหมาะสมที่สุดโดยมีปัจจัยความไม่เหมาะสมน้อยกว่านั้นเป็นปัญหา NP-hard [ ^{8 ] ตัว}แก้ปัญหา MAPF ที่เหมาะสมที่สุดจะให้โซลูชันที่มีคุณภาพสูง แต่ประสิทธิภาพต่ำ ในทางกลับกัน ตัวแก้ปัญหาที่ไม่เหมาะสมที่มีขอบเขตจำกัดและตัวแก้ปัญหาที่ไม่เหมาะสมจะมีประสิทธิภาพมากกว่า แต่โซลูชันของพวกเขามีประสิทธิภาพน้อยกว่า นอกจากนี้ยัง มีการเสนอแนวทาง การเรียนรู้ของเครื่องเพื่อแก้ปัญหา MAPF ^{[ 9 ]}${\displaystyle {\tfrac {4}{3}}}$

แนวทางที่เป็นไปได้วิธีหนึ่งในการรับมือกับความซับซ้อนในการคำนวณคือการวางแผนลำดับความสำคัญ^{[ 10 ]}ซึ่งประกอบด้วยการแยกปัญหา MAPF ออกเป็นปัญหา การค้นหาเส้นทางของตัวแทนเดี่ยว${\displaystyle k}$

ขั้นตอนแรกคือการกำหนดหมายเลขเฉพาะให้กับเอเจนต์แต่ละตัวซึ่งหมายเลขนี้จะสอดคล้องกับลำดับความสำคัญที่มอบให้กับเอเจนต์นั้นๆ จากนั้นจึงคำนวณแผนการเดินทางไปยังเป้าหมายสำหรับเอเจนต์แต่ละตัวตามลำดับความสำคัญ ในระหว่างการวางแผน เอเจนต์จะต้องหลีกเลี่ยงการชนกับเส้นทางของเอเจนต์อื่นๆ ที่มีลำดับความสำคัญสูงกว่าและได้คำนวณแผนการของตนเสร็จแล้ว ${\displaystyle \{1,2,...,k\}}$

การค้นหาวิธีแก้ปัญหา MAPF ในการตั้งค่าดังกล่าวสอดคล้องกับปัญหาเส้นทางที่สั้นที่สุดในกราฟขยายเวลา^{[ 11 ]}กราฟขยายเวลาเป็นกราฟที่คำนึงถึงการผ่านไปของเวลา แต่ละโหนดประกอบด้วยรายการสองรายการโดยที่คือชื่อโหนด และคือขั้นตอนเวลา แต่ละโหนดเชื่อมโยงกับโหนดโดยที่อยู่ติดกับและไม่ถูกครอบครองในขั้นตอนเวลา ${\displaystyle (v,t)}$${\displaystyle v}$${\displaystyle t}$${\displaystyle (v,t)}$${\displaystyle (u,t+1)}$${\displaystyle u}$${\displaystyle v}$${\displaystyle u}$${\displaystyle t+1}$

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

สามารถแยกแยะตัวแก้ปัญหา MAPF ที่เหมาะสมที่สุดได้ 4 ประเภท: ^{[ 12 ]}

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

อัลกอริทึมย่อยที่จำกัดจะเสนอการแลกเปลี่ยนระหว่างความเหมาะสมและต้นทุนของโซลูชัน กล่าวได้ว่าอัลกอริทึมเหล่านี้ถูกจำกัดด้วยปัจจัยบางอย่าง เนื่องจากจะส่งคืนโซลูชันที่มีต้นทุนไม่เกินต้นทุนของโซลูชันที่เหมาะสมคูณด้วยปัจจัยนั้น ตัวแก้ปัญหาย่อยที่จำกัดของ MAPF สามารถแบ่งได้ตามการจัดหมวดหมู่แบบเดียวกันกับที่นำเสนอสำหรับตัวแก้ปัญหา MAPF ที่เหมาะสม^{[ 12 ]}

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

เป็นเวอร์ชันของ MAPF ที่มีชุดตำแหน่งเป้าหมาย แต่ตัวแทนไม่ได้ถูกกำหนดเป้าหมายเฉพาะเจาะจง^{[ 16 ]}ไม่สำคัญว่าตัวแทนจะไปถึงเป้าหมายหรือไม่ สิ่งสำคัญคือเป้าหมายต้องสำเร็จ การปรับเปลี่ยนเล็กน้อยของเวอร์ชันนี้คือเวอร์ชันที่ตัวแทนถูกแบ่งออกเป็นกลุ่ม และแต่ละกลุ่มต้องดำเนินการตามชุดเป้าหมาย^{[ 17 ]}

ปัญหา MAPF ไม่สามารถจับภาพบางแง่มุมที่เกี่ยวข้องกับการใช้งานในโลกแห่งความเป็นจริงได้ ตัวอย่างเช่น ในคลังสินค้าอัตโนมัติ หุ่นยนต์ต้องทำงานหลายอย่างต่อเนื่องกัน ด้วยเหตุนี้ จึงมีการเสนอเวอร์ชัน MAPF ที่ขยายเพิ่มเติม เรียกว่า Multi-Agent Pick-up and Delivery (MAPD) ^{​​[ 18 ]}ในการตั้งค่า MAPD ตัวแทนต้องทำงานหลายอย่างให้เสร็จ โดยแต่ละงานประกอบด้วยตำแหน่งรับสินค้าและตำแหน่งส่งสินค้า เมื่อวางแผนสำหรับการทำงานให้เสร็จ เส้นทางต้องเริ่มต้นจากตำแหน่งปัจจุบันของหุ่นยนต์และสิ้นสุดที่ตำแหน่งส่งสินค้า โดยผ่านจุดรับสินค้า MAPD ถือเป็นเวอร์ชัน "ตลอดชีพ" ของ MAPF ซึ่งงานจะมาถึงทีละน้อย^{[ 18 ]}

ข้อสมมติฐานที่ว่าตัวแทนอยู่ในสภาพแวดล้อมแบบตาราง ความเร็วคงที่ และเวลาไม่ต่อเนื่อง เป็นสมมติฐานที่ทำให้ง่ายขึ้น งานวิจัยหลายชิ้นคำนึงถึงข้อจำกัดทางจลนศาสตร์ของตัวแทน^{[ 19 ]}เช่น ความเร็วและทิศทาง หรือก้าวข้ามข้อสมมติฐานที่ว่าน้ำหนักของส่วนโค้งทั้งหมดเท่ากับ 1 ^{[ 20 ]}งานวิจัยอื่นๆ มุ่งเน้นไปที่การกำจัดข้อสมมติฐานเรื่องเวลาไม่ต่อเนื่อง และระยะเวลาของการกระทำเท่ากับหนึ่งขั้นตอนเวลาพอดี^{[ 21 ]}ข้อสมมติฐานอีกประการหนึ่งที่ไม่สะท้อนความเป็นจริงคือ ตัวแทนครอบครองเซลล์เพียงเซลล์เดียวในสภาพแวดล้อมที่พวกมันอยู่ มีการศึกษาวิจัยบางชิ้นที่ดำเนินการเพื่อเอาชนะข้อสมมติฐานนี้^{[ 22 ]}เป็นที่น่าสนใจที่จะสังเกตว่ารูปร่างและเรขาคณิตของตัวแทนอาจทำให้เกิดความขัดแย้งประเภทใหม่ เนื่องจากตัวแทนอาจชนกันได้แม้ว่าจะไม่ได้ทับซ้อนกันอย่างสมบูรณ์ก็ตาม

MAPF สามารถนำไปประยุกต์ใช้ได้ในสถานการณ์จริงหลายกรณี:

• คลังสินค้าอัตโนมัติ : โลจิสติกส์คลังสินค้าถือเป็นการประยุกต์ใช้ MAPF ในอุตสาหกรรมหลัก พบว่าระบบอัตโนมัติในคลังสินค้าช่วยเพิ่มระดับผลผลิตได้^{[ 23 ]}
• การดำเนินงานสนามบิน: อัลกอริทึม MAPF สามารถนำมาใช้ในสนามบินที่มีผู้คนหนาแน่นเพื่อประสานงานยานพาหนะลากจูงที่ขนส่งเครื่องบิน^{[ 24 ]}การสามารถเพิ่มประสิทธิภาพปัญหาประเภทนี้ยังเป็นประโยชน์ต่อสิ่งแวดล้อมอีกด้วย
• หุ่นยนต์บริการเคลื่อนที่อัตโนมัติ: หุ่นยนต์บริการคือตัวแทนอัตโนมัติที่ปฏิบัติงานอันตรายและซ้ำซากให้กับมนุษย์ในสภาพแวดล้อมที่ไม่ใช่อุตสาหกรรม^{[ 25 ]}เป้าหมายหลักของพวกมันคือการช่วยเหลือมนุษย์
• วิดีโอเกม: ประโยชน์ของ MAPF ในการตั้งค่าดังกล่าวสามารถพบได้เมื่อผู้เล่นต้องเคลื่อนย้ายทีมตัวแทนในสภาพแวดล้อมวิดีโอเกมที่แออัด^{[ 26 ]}

• ระบบหลายเอเจนต์
• การวางแผนแบบหลายเอเจนต์
• การค้นหาเส้นทาง
• ปัญหาเส้นทางที่สั้นที่สุด

• MAPF.info