Conflict-Based Search (CBS): วางเส้นทางหลาย Agent ไม่ให้ชน

กริด 3×3 แสดงเส้นทางของ Agent A จากด้านบนลงล่างและ B จากซ้ายไปขวา ชนที่ช่องกลางเวลา 1; แล็บห้ามทั้งชนช่องเดียวกันและสวนสลับช่อง; ด้านล่างอธิบาย low-level ค้นราย Agent และ high-level ตรวจ conflict — **CBS แยกหาเส้นทางราย Agent และ conflict ร่วม** — ภาพเปิดบทความ: shortest paths ราย Agent ชนกันในแผนที่เดียวกัน · ต้นฉบับ 1 · ต้นฉบับ 2 · ต้นฉบับ 3

คำตอบโดยตรง

Conflict-Based Search (CBS) เป็นวิธีวางแผนเส้นทางให้ Agent หลายตัวบนกราฟ โดยแยกงานเป็นสองชั้น: ชั้นบนค้นหาข้อขัดแย้งระหว่างเส้นทาง ส่วนชั้นล่างหาเส้นทางให้ Agent ทีละตัวภายใต้ข้อจำกัดที่ชั้นบนเพิ่มเข้ามา วิธีนี้ยังหาคำตอบเหมาะที่สุดได้ภายใต้แบบจำลองและสมมติฐานที่กำหนด แต่ไม่ได้รับประกันว่าจะเร็วกว่า A* ทุกกรณี หรือแก้การเคลื่อนที่จริงที่มีความไม่แน่นอนโดยอัตโนมัติ

ในบทความนี้คำว่า Agent หมายถึงหน่วยเคลื่อนที่ในโจทย์ Multi-Agent Path Finding (MAPF) เช่น จุดแทนหุ่นยนต์บนแผนที่กริด ไม่ได้หมายถึง LLM หลายตัวที่เขียนคำตอบหรือส่งข้อความหากัน Lab เป็น SIMULATION บนกราฟเล็ก ไม่ได้รันระบบหุ่นยนต์หรือ benchmark ขนาดใหญ่

ทำไมการวางแผนทีละตัวจึงไม่พอ

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

CBS เริ่มจากหาเส้นทางสั้นของแต่ละตัว แล้วสร้างทางเลือกเมื่อพบ conflict เพื่อให้ Agent ฝ่ายหนึ่งหลีกเลี่ยงเหตุการณ์นั้น แนวทางนี้อาจมีประสิทธิภาพกับโจทย์บางโครงสร้าง แต่เมื่อ conflict มาก ต้นไม้ค้นหาอาจใหญ่และเสียเปรียบวิธีค้นสถานะร่วม

Sharon, Stern, Felner และ Sturtevant เสนอ CBS ใน AAAI 2012: ชั้นบนค้น CT จาก conflict ส่วนชั้นล่างหาเส้นทางรายตัว (บทความ AAAI, PDF). ฉบับวารสารปี 2015 ขยายรายละเอียดและกล่าวถึง Meta-Agent CBS (DOI และ PDF, author PDF). OJS ลงวันที่ระบบปี 2021 แต่ issue ของ AAAI ระบุปี 2012

รากฐาน: MAPF ต้องระบุกติกาให้ครบ

แบบจำลองคลาสสิกเริ่มจากกราฟ G=(V,E): จุดยอดคือสถานที่ เส้นเชื่อมคือการเคลื่อนที่ที่อนุญาต มี Agent k ตัว แต่ละตัวมีจุดเริ่ม s_i และเป้าหมาย g_i เวลาแบ่งเป็น step; ในหนึ่ง step Agent เคลื่อนไปจุดข้างเคียงหรือรออยู่ที่เดิมได้ คำตอบคือเส้นทางตามเวลาของ Agent ทุกตัว

งาน MAPF อาจห้ามการอยู่จุดเดียวกันพร้อมกัน (vertex conflict) หรือการสลับตำแหน่งบน edge เดียวกัน (swap conflict). Sharon et al. (2015, §4.2.5) นิยามทั้ง swap และ edge constraint; Stern et al. รวบรวมตัวเลือกอย่าง following และ cycle conflict เพิ่ม (Sharon et al., Stern et al.).

ต้องระบุด้วยว่า Agent ค้างที่เป้าหมายหรือหายออกจากระบบ และใช้ objective ใด Sum-of-costs คือผลรวมจำนวน step ที่ Agent แต่ละตัวใช้จนถึงเป้าหมายของตัวเองครั้งสุดท้ายแล้วไม่ออกอีก ส่วน makespan คือค่าสูงสุดของเวลาไปถึงเป้าหมายเหล่านั้น สอง objective นี้อาจเลือกแผนต่างกัน

FACT: ชื่อ “CBS แบบ optimal” จึงต้องอ่านคู่กับ objective, conflict rules, ความหมายของ wait, การจัดการเป้าหมาย และสมมติฐานของ low-level search ไม่ควรนำคำว่า optimal จากงานหนึ่งไปใช้กับทุกระบบโดยไม่ระบุเงื่อนไข

สถาปัตยกรรมสองชั้น

ผังแสดง graph/start-goal/assumptions, low-level space-time BFS, CT node ที่เก็บ constraints paths และ sum of costs, conflict validation ทั้ง vertex และ swap, branching เป็นสอง constraints ตาม conflict, replanning เฉพาะ Agent ที่ถูกจำกัด, และ OPEN เรียง cost — **ลำดับการทำงานของ CBS จากโจทย์สู่คำตอบ** — ขั้นตอน CBS และข้อมูลที่เก็บในแต่ละ CT node · ต้นฉบับ 1 · ต้นฉบับ 2 · ต้นฉบับ 3

CBS รับกราฟ, จุดเริ่มและเป้าหมายของ Agent, กติกาการเคลื่อนที่, conflict ที่ห้าม, นโยบายเป้าหมาย, objective และ low-level path planner ข้อมูลนี้เป็นสถานะ planner ภายนอก ไม่ใช่น้ำหนักโมเดลหรือ context ของ LLM

ชั้นล่าง — constrained single-agent search: A* หรือ breadth-first search ในกริด unit-cost หาเส้นทางต้นทุนต่ำสุดที่เคารพ constraints โดยใช้สถานะ space-time เช่น (vertex, time) และอาจมี action wait

ชั้นบน — Constraint Tree (CT): แต่ละโหนดเก็บ constraints, เส้นทางปัจจุบัน และ cost รวม โหนดรากเริ่มด้วย constraints ว่างและเส้นทางสั้นสุดรายตัว ซึ่งอาจชนกัน CT จัดลำดับตาม objective เช่น priority queue แบบ best-first สำหรับ sum-of-costs

เมื่อหยิบโหนด ระบบตรวจ conflict; ถ้าไม่พบ โหนดนั้นเป็นคำตอบ หาก A และ B อยู่ช่องกลางพร้อมกันที่เวลา t=1, สร้างลูกหนึ่งห้าม A อยู่ที่นั่น และอีกลูกห้าม B จากนั้นค้นใหม่เฉพาะ Agent ที่ถูกจำกัด

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

ขั้นตอนปฏิบัติ

Root มี A จากด้านบนลงล่างและ B จากซ้ายไปขวา; shortest path ของแต่ละคน cost 2 รวม cost 4 แต่ทั้งคู่ชนตรงกลางเวลา 1; child A ห้าม A ที่กลางเวลา 1 แล้ว replan A ด้วยการรอ ส่วน child B ทำเช่นเดียวกันกับ B; ทั้งคู่ได้ cost 5 และไม่ชน — **Root conflict แตกเป็นสอง CT child และ replan ราย Agent** — กริด crossing และ CT branching พร้อมข้อจำกัดของแต่ละ child · ต้นฉบับ 1 · ต้นฉบับ 2 · ต้นฉบับ 3

คำนวณเส้นทางสั้นสุดรายตัวภายใต้ constraints ว่าง แล้วใส่รากในคิว CT
หยิบโหนด cost ต่ำสุด ตรวจเส้นทางทุกคู่ตาม conflict rules
ถ้าไม่พบ conflict ให้คืนชุดเส้นทางนี้
ถ้าพบ conflict ให้แยกเป็นลูกด้วย constraints ที่ครอบคลุม แล้วค้นใหม่เฉพาะเส้นทางของ Agent ที่ถูกจำกัด
คำนวณ cost ของแต่ละลูกที่ยังมี path แล้วใส่กลับเข้าคิว
ทำซ้ำจากโหนด cost ต่ำสุด จนได้คำตอบหรือ OPEN ว่าง

Pseudocode — แนวคิดเพื่ออธิบาย ไม่ใช่ implementation ของ CBSH2-RTC:

root.constraints = empty
root.paths = shortest_path_for_each_agent(root.constraints)
root.cost = objective(root.paths)
OPEN = priority queue ordered by root.cost

while OPEN is not empty:
    node = pop_lowest_cost(OPEN)
    conflict = first_conflict(node.paths, model.conflict_rules)
    if conflict does not exist:
        return node.paths

    for constraint in split_conflict(conflict):
        child.constraints = node.constraints plus constraint
        child.paths = copy(node.paths)
        child.paths[affected_agent] = low_level_search(
            affected_agent, child.constraints, model
        )
        if a constrained path exists:
            child.cost = objective(child.paths)
            push(OPEN, child)

return NO_SOLUTION_WITHIN_SEARCH_MODEL

ตัวอย่าง constraint คือ “A ห้ามอยู่ v ณ เวลา t” หรือ “ห้ามเริ่มเดิน edge u→v ในช่วง t→t+1”. Paper 2015 index เวลา edge ตอนเริ่มเดิน; Lab ใช้เวลาถึงปลายทาง จึงต่างกันหนึ่ง step ตาม API

ต้องแยกการคืนคำตอบจากการพิสูจน์ว่าไม่มีคำตอบด้วย CBS พื้นฐานอาจค้นต่อไปไม่สิ้นสุดในโจทย์ที่แก้ไม่ได้ ตามการวิเคราะห์ใน Sharon et al. (2015), §5.2 บรรทัดท้าย pseudocode ใช้เมื่อ OPEN ว่างจริงหลังค้นชั้นล่างครบตามแบบจำลอง ส่วนการหยุดเพราะงบค้นหาของ Lab ให้ UNKNOWN_LIMIT หากปัญหารายตัวไม่มีเส้นทางตั้งแต่ราก จึงรายงาน NO_SOLUTION ได้จากการตรวจนั้น ไม่ต้องสร้าง CT ต่อ

Lab: conflict หนึ่งจุดทำให้เกิดทางเลือกอย่างไร

CBS: สำรวจการแตกกิ่งจากความขัดแย้ง

เลือกสถานการณ์ แล้วกดทีละโหนด CT เพื่อดูข้อจำกัดที่เพิ่มขึ้นและการหาเส้นทางใหม่ของเอเจนต์ที่ถูกจำกัด

สถานการณ์งบขยาย CT

แผนที่และเส้นทางของ CT node

สถานะการค้นหา

OPEN ตามลำดับ best-first

ความขัดแย้งที่จะจัดการ

ต้นไม้ข้อจำกัด

โหนด	พ่อ	ต้นทุน	สถานะ	ข้อจำกัดที่เพิ่ม	เส้นทาง A/B

อ่านการเปลี่ยนสถานะจริง

วงจรในมุมสำรวจแสดง CT node ที่เลือก, conflict, branch constraints และผล low-level replanning ที่บันทึกโดย engine ตัวเดียวกับที่แก้โจทย์อยู่

ขอบเขตแบบจำลอง

นี่คือการจำลอง CBS เชิงการเรียนรู้บนกริดเล็กแบบสองเอเจนต์ ไม่ใช่การควบคุมหุ่นยนต์หรือ benchmark. งานปี 2012 อธิบายตัวอย่าง vertex conflicts; บทความวารสารปี 2015 อธิบาย edge constraints รวมถึงการห้ามสลับช่อง. paper ใช้เวลา t เป็นเวลาที่ออกจากช่อง ส่วน lab ใช้ t เป็นเวลาที่ไปถึงช่อง: paper t = lab t − 1. ใช้ผลรวมจำนวนก้าว, อนุญาต wait, และให้เอเจนต์ค้างที่เป้าหมายหลังถึงเป้าหมายตามนิยาม stay-at-target. เมื่อถึงงบขยายจะรายงาน UNKNOWN_LIMIT ซึ่งยังไม่ใช่หลักฐานว่าไม่มีคำตอบ.

แหล่งหลัก: Sharon et al. 2012 paper PDF; Sharon et al. 2015 journal PDF, §4.2.5; Stern et al. 2019 MAPF definitions.

SIMULATION: กริด 3×3 ไม่มีสิ่งกีดขวาง พิกัด [row,col]; A เดิน [0,1]→[2,1], B เดิน [1,0]→[1,2]. ทุก move/wait cost 1, รอได้, อยู่ที่ goal หลังถึง และ objective คือ sum-of-costs เส้นทางสั้นสุดรวม cost 4 แต่ทั้งคู่ใช้ [1,1] ที่เวลา 1 จึงเกิด vertex conflict

CBS แตกเป็นสองกรณี: ห้าม A หรือ B อยู่ [1,1] ที่เวลา 1 แล้วค้นใหม่ให้ Agent ที่ถูกจำกัด การรอเป็น action ที่อนุญาต ผล conflict-free มี sum-of-costs 5 และ CT ขยาย 2 โหนดใน fixture นี้ ตัวเลขไม่ใช่ benchmark หรือเวลารัน CBS ทั่วไป

Lab ห้ามทั้ง vertex และ swap conflict หาก A เคลื่อน u→v และ B เคลื่อน v→u พร้อมกัน จะเกิด swap และแยกด้วย edge constraints อีก fixture ให้ A [1,0]→[1,1] และ B กลับทิศ: root cost 2 แต่รออย่างเดียวทำให้ชน vertex จึงต้องมี Agent หนึ่งอ้อมสาม step; คำตอบมี cost 4 ตาม fixture

LIMIT: งบหนึ่ง CT pop ที่เหลือลูกในคิวให้ UNKNOWN_LIMIT, ไม่ใช่ NO_SOLUTION; หมดงบไม่ได้พิสูจน์ว่าไม่มีแผน ค่าเริ่มต้นจำกัด 200 pops จึงเป็น simulator เพื่อการศึกษา

CBS เทียบกับวิธีที่คุ้นเคย

สามคอลัมน์แสดง Joint A* ที่ค้นตำแหน่งของทุก Agent ร่วมกัน; prioritized planning ที่วางเส้นทางตามลำดับและจองพื้นที่; CBS ที่เก็บ paths/constraints ใน CT และแตกเมื่อเกิด conflict — **Joint A*, prioritized planning และ CBS ตามโครงสร้างการค้น** — เปรียบเทียบ state, expansion, จุดเด่น และข้อจำกัดของสามแนวทาง · ต้นฉบับ 1 · ต้นฉบับ 2 · ต้นฉบับ 3

วิธี	แนวทาง	จุดแข็ง	ข้อจำกัด
Joint-state A*	ค้นสถานะที่บรรจุตำแหน่งของทุก Agent	ความขัดแย้งอยู่ในสถานะเดียวและใช้ heuristic กับระบบรวมได้	สถานะรวมโตเร็วตามจำนวน Agent และสาขาการเคลื่อนที่
Prioritized planning	วางเส้นทางตามลำดับ แล้วให้ Agent ภายหลังเคารพเส้นทางที่จองไว้	เรียบง่ายและทำงานได้เร็วในหลายสถานการณ์	ลำดับที่เลือกอาจทำให้ไม่มีแผน ทั้งที่ยังมีแผนร่วม หรือได้แผนที่ไม่เหมาะที่สุด
CBS	วางเส้นทางรายตัว แล้วค้น CT เพื่อแก้ conflict ด้วย constraints	แยก low-level search; เมื่อใช้เงื่อนไขครบจะรับประกันคำตอบเหมาะที่สุดตาม objective	จำนวน conflict/โหนด CT อาจมาก; low-level ค้นซ้ำ; ประสิทธิภาพขึ้นกับโครงสร้างโจทย์

REPORTED CLAIM: บทความ AAAI 2012 รายงาน speedup สูงสุดถึงระดับหนึ่ง order of magnitude เมื่อเทียบแนวทางก่อนหน้า แต่คำว่า “สูงสุดถึง” เป็นผลในชุดการทดลองของผู้เขียน ไม่ใช่การรับประกันว่า CBS เร็วกว่าเสมอ ฉบับวารสาร 2015 ทดลองกับกริดเปิด 8×8 ที่มี 3–21 Agent และจำกัดเวลา 5 นาที รวมถึงแผนที่เกม DAO เช่น den520d ที่มีพื้นที่เปิดมาก และ brc202d ที่มีทางแคบ/คอขวดมาก ผู้เขียนรายงานผลผสม: CBS ทำได้ดีกับแผนที่ bottleneck-heavy แต่ด้อยกว่าบนแผนที่เปิดบางชุด จึงไม่มีผู้ชนะสากล (AAAI 2012, Sharon et al., 2015, §6). เราไม่ได้รันซ้ำตัวเลขเหล่านั้น

benchmark ก็ต้องระบุว่าเป็น solver รุ่นใดและกติกาอะไร ตัวอย่างเช่นงานรวบรวม MAPF ปี 2019 รายงาน ICBS บนกริด 4 ทิศ โดยห้าม vertex, edge และ swap conflicts, อนุญาต following กับ cycle conflicts, ใช้ sum-of-costs, stay-at-target และจำกัดเวลา 30 วินาที นี่เป็น baseline ของ benchmark นั้น ไม่ใช่ผลของ Lab นี้ และไม่ใช่คำอธิบายทุกงาน MAPF (Stern et al., 2019).

มีโค้ด CBS แบบใดให้ศึกษา

Jiaoyang-Li/CBSH2-RTC เป็น repository จริงสำหรับ optimal MAPF solver ที่ระบุฐานเป็น CBS พร้อมเทคนิคพัฒนาต่อหลายอย่าง เช่น prioritized conflicts, bypassing, heuristic ชั้นบน, symmetry reasoning, mutex propagation และ disjoint splitting (README). จึงควรใช้เป็นตัวอย่างของ CBS รุ่นปรับปรุง ไม่เรียกว่าโค้ด “CBS พื้นฐานดั้งเดิม”

README แสดงคำสั่ง build ด้วย CMake และต้องใช้ Boost; ตัวอย่างเรียก solver กับไฟล์ random-32-32-20 ใช้ k=30 และ runtime limit 60 วินาที โดยเปิดชุดเทคนิค enhanced variant ตามที่ README ระบุ ตัวอย่างนี้บอกวิธีเริ่มใช้งาน ไม่ได้เป็นตัวเลข benchmark ที่เราวัด และการนับตัวเลือกในคำสั่งขึ้นกับไฟล์ scenario ด้วย

ก่อนนำไปใช้ ควรอ่านสิทธิ์ของโค้ดด้วย README ระบุ USC Research License และ ไฟล์ license อนุญาตเพื่อการศึกษา วิจัย และไม่แสวงหากำไรเมื่อรักษาข้อความแจ้งสิทธิ์ตามเงื่อนไข ส่วนการใช้เชิงพาณิชย์ต้องติดต่อ USC นี่ไม่ใช่ MIT หรือ Apache license และบทความนี้ไม่ได้ build หรือตรวจความเข้ากันได้กับ environment ของผู้อ่าน

งานที่เกี่ยวข้องและสิ่งที่ยังไม่รองรับ

MAPF มีความเกี่ยวข้องกับการวางเส้นทางในคลังอัตโนมัติ รถอัตโนมัติ และหุ่นยนต์ตามงานทบทวนคำจำกัดความ แต่ความเกี่ยวข้องของโจทย์ไม่ได้พิสูจน์ว่าองค์กรใดติดตั้ง CBS ต้นฉบับในระบบจริง (Stern et al., 2019). หลักฐานของ CBS ที่พูดได้ชัดในที่นี้คือบทความวิจัยทดลอง solver บนกราฟและ benchmark maps ส่วนการนำไปใช้งานจริงต้องอ้างระบบเฉพาะและหลักฐานของระบบนั้นแยกต่างหาก

แบบจำลองกริดคลาสสิกแทน Agent เป็นจุดที่ไม่มีรูปร่าง เคลื่อนตาม step บนกราฟ และใช้กติกาความขัดแย้งที่กำหนดไว้ ในพื้นที่จริง ตัวแทนมีขนาดและข้อจำกัดทางกายภาพ อาจเลี้ยวหรือเร่งได้ไม่ทันเวลา มีความคลาดเคลื่อนจากเซนเซอร์ การสื่อสาร หรือการควบคุม ระบบอาจต้องแปลงแผนกริดเป็น trajectory ที่ทำได้ ตรวจความปลอดภัย ประสานเวลา และวางแผนใหม่เมื่อข้อมูลเปลี่ยน CBS เพียงชั้นเดียวไม่ได้แก้เรื่องเหล่านี้ทั้งหมด

ข้อจำกัดสำคัญอีกข้อคือการหาคำตอบ optimal บน MAPF ยากมากในกรณีทั่วไป และ CBS ยังอาจต้องสำรวจ CT จำนวนมากเมื่อ conflict ซับซ้อน การใช้ heuristic, conflict prioritization, symmetry reasoning หรือ meta-agent เป็นการพัฒนาวิธีค้นหา แต่มีผลต่อความซับซ้อนและ configuration ควรรายงานชื่อ variant, objective, conflict model, ข้อมูล benchmark, ขอบเวลา/หน่วยความจำ และ solver version ทุกครั้ง

ANALYSIS: ในระบบ Agent ที่รับคำสั่งเป็นภาษาธรรมชาติ อาจมีชั้นแปลงคำสั่งเป็น graph, starts/goals และ constraints ก่อนส่ง planner แล้วมี verifier ตรวจผลอีกชั้น CBS ไม่ได้ทำความเข้าใจข้อความ ไม่ได้ตรวจว่าคำสั่งมีสิทธิ์ และไม่ปรับ model weights ระหว่างคำนวณเส้นทาง constraints, คิว CT และ paths เป็นข้อมูลค้นหาภายนอกที่ planner เก็บไว้

Context Window คือข้อความที่โมเดลเห็นในรอบปัจจุบัน; Retrieved Context คือข้อมูลที่ค้นแล้วนำเข้ามาในรอบนั้น; External Memory อาจเก็บกราฟ, ข้อจำกัด หรือ execution trace ไว้ใช้ภายหลัง ส่วน weight updates เปลี่ยนพารามิเตอร์จากการฝึก โมเดลที่บรรยายเหตุผลของตนไม่ได้แสดงว่า CBS รันแล้ว: ให้แยกคำบรรยาย (reasoning narrative) ออกจาก trace ของเครื่องมือหรือ planner ที่บันทึกการขยาย CT, constraints และผลตรวจจริง

Practical Takeaways

ระบุกราฟ จุดเริ่ม–เป้าหมาย objective, กติกา vertex/swap/edge conflict, wait และ stay/disappear at goal ก่อนพูดว่าแผน optimal
แยก CT ชั้นบนซึ่งตัดสิน conflict ออกจาก low-level planner ซึ่งหาเส้นทางภายใต้ constraints
ใช้ joint-state A* เป็นคู่เทียบเมื่อสถานะรวมยังจัดการได้ และใช้ prioritized planning เมื่อความเร็ว/ความง่ายสำคัญกว่าความครบถ้วนหรือ optimality
อ่านผลทดลองว่าเป็นของ paper หรือ solver variant ใด ตรวจ map, scenario, จำนวน Agent, timeout, hardware และ objective
ถ้าใช้ repository ให้ตรวจ USC Research License กับข้อกำหนดสำหรับการใช้เชิงพาณิชย์
มองผลจากกริดจำลองว่าเป็น SIMULATION เพื่อเรียนรู้แนวคิด ไม่ใช่หลักฐานความปลอดภัยหรือการใช้งานจริง

ภาพ crossing แสดง A จากด้านบนลงล่างและ B จากซ้ายไปขวา พร้อมรายการตรวจ objective, action/time cost, conflict definition, CT node contents และ joint validator; โมเดลแล็บห้ามทั้ง vertex conflict และ pairwise edge swap — **ห้าข้อก่อนกำหนดและตรวจโจทย์หลาย Agent** — รายการตรวจสมมติฐานและ validator ก่อนนำเส้นทางไปใช้ · ต้นฉบับ 1 · ต้นฉบับ 2 · ต้นฉบับ 3

เกมจำลอง: อ่าน constraint ก่อนเลือกทางแยก

เกมจำลอง CBS: 6 ภารกิจ

อ่าน state ที่มาจาก engine แล้วเลือกคำตอบ การตอบผิดไม่เปลี่ยน state หรือคะแนน; แต่ละภารกิจเริ่มจาก fixture แยกกัน

คำตอบ

แผนที่และเส้นทาง

ข้อมูลที่เครื่องให้

ผลจากการกระทำจริง

ยังไม่มีการส่งคำตอบที่ถูกต้อง

เป้าหมาย

ทำครบหกภารกิจด้วยการจำแนก vertex conflict, ตรวจ branch, เปรียบเทียบเส้นทางที่ถูก replan, ตรวจ swap, อ่านผล stay-at-target และแยกงบหมดออกจากการพิสูจน์ว่าไม่มีคำตอบ

SIMULATION: เกมมีภารกิจสั้นที่ใช้ core CBS เดียวกับ Explorer: ระบุ vertex conflict, เลือกหนึ่งในสอง branch, ตรวจว่า low-level ค้นใหม่เฉพาะ Agent ที่ถูกจำกัด, ระบุ swap conflict, ตรวจเส้นทางที่ padding ให้ Agent อยู่ที่ goal และแยก UNKNOWN_LIMIT ออกจาก NO_SOLUTION แต่ละภารกิจทดสอบการอ่านกติกากับ trace ที่ระบุ ไม่ใช่การประเมิน model หรือสมรรถนะหุ่นยนต์

คำถามวิจัยต่อไป

การเลือก conflict ใดช่วยลดจำนวน CT expansions โดยยังรักษา optimality ใน benchmark ที่กำหนด? เมื่อเพิ่ม obstacle, ความหนาแน่น Agent หรือทางแคบ ประสิทธิภาพเปลี่ยนอย่างไรเมื่อเทียบกับ joint-state A* และ prioritized planning? ควรวัดเวลา, หน่วยความจำ, success rate และ solution cost บน map/scenario, seed, compiler, hardware และ timeout เดียวกัน รวมถึงตรวจ sensitivity ต่อ tie-breaking และเป้าหมายที่อยู่ค้างหลัง arrival

อีกคำถามคือจะเชื่อม graph-based MAPF กับ continuous-time motion planner อย่างไรให้ constraints สะท้อนรูปร่าง, velocity และความไม่แน่นอนของ Agent จริง การแปลงแผนระหว่างชั้นต้องตรวจว่า feasibility ที่พิสูจน์บนกริดยังคงจริงหลังสร้าง trajectory หากมีการเปลี่ยนแผนระหว่าง execution ต้องนิยามเวลาใหม่และตรวจ conflict กับสถานะจริง ไม่ใช่ถือว่าแผนเดิมยังใช้ได้ต่อโดยอัตโนมัติ

FAQ

CBS หมายถึง AI หลายตัวคุยกันหรือไม่?

ไม่ ในบทความนี้ Agent คือหน่วยเคลื่อนที่แต่ละตัวบนแผนที่ ส่วน CBS คือ planner ที่หาชุดเส้นทางให้ ตัวแทนเหล่านั้นอาจเป็นหุ่นยนต์ในแอปพลิเคชัน แต่คำว่า Agent ใน MAPF ไม่ได้แปลว่า LLM หรือระบบสนทนาโดยอัตโนมัติ

ทำไม CBS ถึงบอกว่าเป็น optimal ได้?

เพราะภายใต้แบบจำลองที่ระบุ การค้นชั้นบนจัดลำดับ CT ตามต้นทุน และแต่ละ low-level search หาคำตอบต้นทุนต่ำสุดตาม constraints; การแบ่ง conflict ต้องครอบคลุมทางแก้ที่เป็นไปได้ เมื่อเงื่อนไขเหล่านี้และนิยามเป้าหมายตรงกัน โหนดต้นทุนต่ำสุดที่ถูกดึงออกจาก OPEN แล้วพบว่า conflict-free จึงเป็นคำตอบที่เหมาะที่สุดในแบบจำลองนั้น หากเปลี่ยน objective หรือใช้ bounded-suboptimal variant การรับประกันก็เปลี่ยน

CBS เร็วกว่า joint-state A* ไหม?

ไม่ทุกครั้ง CBS มีโอกาสได้เปรียบเมื่อแบ่งเป็นปัญหาเดี่ยวได้และ conflict ไม่ทำให้ CT โตมาก ส่วน joint-state A* อาจเหมาะกว่าในบางโครงสร้าง บทความต้นฉบับรายงานผลเฉพาะชุดทดลองและอภิปรายข้อเสีย ไม่ควรแปลงเป็นกฎสากล

Conflict คือมี Agent สองตัวอยู่ช่องเดียวกันเท่านั้นหรือ?

ไม่จำเป็น ต้องอ่าน conflict model บางระบบห้าม vertex conflict และการ swap บน edge ด้วย กติกาต่างกันทำให้คำตอบที่ถือว่าปลอด conflict ต่างกันตามไปด้วย

CBS ใช้กับหุ่นยนต์จริงได้ทันทีหรือไม่?

แผนที่กริดอย่างเดียวไม่ยืนยันว่าการเคลื่อนไหวจริงทำได้หรือปลอดภัย ต้องเพิ่มการแทนเรขาคณิตและ dynamics, การตรวจ trajectory, การรับมือความล่าช้า/ความไม่แน่นอน และระบบ execution/replanning ตามงานจริง งานวิจัยที่ใช้ CBS เป็นฐานอาจมีชั้นเสริมเหล่านี้ แต่ต้องตรวจหลักฐานของระบบเฉพาะ

Lab นี้วัดประสิทธิภาพจริงไหม?

ไม่ Lab เป็น SIMULATION บนกริดเล็กที่กำหนดไว้ ตัวเลขต้นทุนมาจากกติกา step ของตัวอย่าง ไม่ใช่ runtime, benchmark, การทดลองกับหุ่นยนต์ หรือการทำซ้ำผลของ paper

References

Sharon, G., Stern, R., Felner, A., & Sturtevant, N. (2012). “Conflict-Based Search For Optimal Multi-Agent Path Finding.” Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, 563–569. AAAI record · full paper PDF. A related SoCS entry (3(1), 190) is an extended abstract of a paper presented elsewhere, so it is not cited here as the full original.
Sharon, G., Stern, R., Felner, A., & Sturtevant, N. R. (2015). “Conflict-based search for optimal multi-agent pathfinding.” Artificial Intelligence, 219, 40–66. DOI · author-hosted full PDF · author-institution record.
Stern, R., et al. (2019). “Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks.” Proceedings of SoCS 2019. arXiv:1906.08291.
Li, J., et al. CBSH2-RTC source repository · README · USC Research License. Reviewed commit a834df1e16c1668a677b68fef6699371c4233d33 (2024-07-24); enhanced solver, not built or run for this article.
บทความ Hybrid Mind ที่เกี่ยวข้อง: LPA*: ซ่อมเส้นทางเมื่อกราฟเปลี่ยน โดยใช้ผลค้นหาเดิม, Constraint-Aware Planning, และ 3D Scene Graphs.

ขอบเขตหลักฐาน: ข้อเท็จจริงอ้างตามแหล่งปฐมภูมิข้างต้น; ผล benchmark เป็น REPORTED CLAIM จากผู้เขียน; การวิเคราะห์การออกแบบระบุ ANALYSIS; กระดานและตัวเลข cost ใน Lab เป็น SIMULATION ที่กำหนดตายตัว ไม่มีการรันโค้ด CBSH2-RTC, ทำซ้ำ benchmark, หรือทดลองกับหุ่นยนต์จริง