ระบบหุ่นยนต์หลายตัว

ตัวอย่างที่ 1 รถสองคัน จุดตรวจห้าจุด

รถ UGV-1 อยู่ที่ (0, 0) m รถ UGV-2 อยู่ที่ (100, 0) m มีจุดตรวจแผง A ถึง E ต้องการให้ระยะทางรวมของทั้งสองคันน้อยที่สุด (ไม่ต้องกลับจุดเริ่ม) (ข้อมูลจำลอง)

import itertools
import numpy as np

robots = {"UGV-1": np.array([0.0, 0.0]), "UGV-2": np.array([100.0, 0.0])}
tasks = {"A": (10, 40), "B": (30, 80), "C": (60, 20), "D": (90, 70), "E": (50, 60)}
tasks = {k: np.array(v, float) for k, v in tasks.items()}

def route_cost(start, order):
    pts = [start] + [tasks[t] for t in order]
    return sum(np.linalg.norm(pts[i+1] - pts[i]) for i in range(len(pts) - 1))

def best_insert(start, order, t):
    best = None
    for k in range(len(order) + 1):
        new = order[:k] + [t] + order[k:]
        c = route_cost(start, new)
        if best is None or c < best[0]:
            best = (c, new)
    return best

routes = {r: [] for r in robots}
left = list(tasks)
while left:                       # ประมูลทีละงาน: ผู้เสนอต้นทุนเพิ่มต่ำสุดชนะ
    bids = []
    for r in robots:
        base = route_cost(robots[r], routes[r])
        for t in left:
            c, new = best_insert(robots[r], routes[r], t)
            bids.append((c - base, r, t, new))
    bid, r, t, new = min(bids)
    routes[r] = new
    left.remove(t)
auction = sum(route_cost(robots[r], routes[r]) for r in robots)
print("auction:", {r: "".join(o) for r, o in routes.items()}, f"total {auction:.1f} m")

best = None                        # ค้นทุกทางเพื่อหาคำตอบดีที่สุด
for mask in itertools.product([0, 1], repeat=len(tasks)):
    groups = [[t for t, m in zip(tasks, mask) if m == g] for g in (0, 1)]
    total = 0
    for r, g in zip(robots, groups):
        total += min(route_cost(robots[r], list(p)) for p in itertools.permutations(g))
    if best is None or total < best:
        best = total
print(f"optimal total {best:.1f} m  auction is {100*(auction/best - 1):.1f}% worse")

auction: {'UGV-1': 'A', 'UGV-2': 'CDEB'} total 213.8 m
optimal total 200.2 m  auction is 6.8% worse

การประมูลให้ UGV-1 ทำเพียงจุด A ส่วน UGV-2 วิ่งอ้อมทำสี่จุด รวม 213.8 m คำตอบดีที่สุดจากการค้นทุกทางคือ UGV-1 ทำ A, B, E, D และ UGV-2 ทำเพียง C รวม 200.2 m การประมูลแย่กว่าราว 7% เพราะแต่ละรอบเลือกงานที่ถูกที่สุดตอนนั้นโดยไม่มองงานที่เหลือ ในงานจริงที่มีจุดตรวจหลายร้อยจุด การค้นทุกทางเป็นไปไม่ได้ ความต่างระดับนี้มักยอมรับได้แลกกับความเร็วและความยืดหยุ่น

ตัวอย่างที่ 2 โดรนกลับมาลงบนรถที่วิ่งตามถนนในฟาร์ม

รถวิ่ง 5 m/s ตามถนนแนว x เริ่มจาก x = 0 โดรนอยู่ที่ (300, 400) m บิน 10 m/s เหลือเวลาบิน 120 s (ข้อมูลจำลอง)

import numpy as np

vg, va = 5.0, 10.0                 # ความเร็วรถ UGV และโดรน m/s
drone = np.array([300.0, 400.0])   # ตำแหน่งโดรนเมื่อเริ่มกลับ m
battery_s = 120.0                  # เวลาบินที่เหลือ s

# รถวิ่งตามแนว x จาก 0: หาเวลา t ที่ |(vg t, 0) - drone| = va t
a = va**2 - vg**2
b = 2 * vg * drone[0]
c = -(drone @ drone)
t_meet = (-b + np.sqrt(b**2 - 4*a*c)) / (2*a)
print(f"earliest meeting t = {t_meet:.1f} s at x = {vg*t_meet:.1f} m")

p, t = drone.copy(), 0.0           # เทียบ: โดรนบินไล่ตำแหน่งปัจจุบันของรถ
while True:
    car = np.array([vg * t, 0.0])
    d = car - p
    if np.linalg.norm(d) < va * 0.1:
        break
    p += d / np.linalg.norm(d) * va * 0.1
    t += 0.1
print(f"pursuit t = {t:.1f} s")
print(f"battery left at meeting {battery_s - t_meet:.0f} s")

earliest meeting t = 41.1 s at x = 205.5 m
pursuit t = 46.6 s
battery left at meeting 79 s

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