Multi-robot systems

Example 1 Two vehicles, five inspection points

UGV-1 is at (0, 0) m and UGV-2 at (100, 0) m. Panel inspection points A to E must be visited with the smallest total distance for both vehicles (no return to start) (simulated data).

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:                       # auction one task at a time: lowest added cost wins
    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                        # exhaustive search for the optimal answer
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

The auction gives UGV-1 only point A, while UGV-2 detours through four points, 213.8 m in total. The optimum from exhaustive search is UGV-1 doing A, B, E, D and UGV-2 doing only C, 200.2 m in total. The auction is about 7% worse because each round takes the cheapest task at that moment without looking at the rest. In real work with hundreds of points, exhaustive search is impossible, and a gap of this size is usually acceptable in exchange for speed and flexibility.

Example 2 A drone returning to land on a vehicle driving along a farm road

The UGV drives at 5 m/s along a road on the x axis from x = 0. The drone is at (300, 400) m, flies at 10 m/s and has 120 s of flight time left (simulated data).

import numpy as np

vg, va = 5.0, 10.0                 # UGV and drone speeds m/s
drone = np.array([300.0, 400.0])   # drone position when it starts returning m
battery_s = 120.0                  # remaining flight time s

# UGV drives along x from 0: find t where |(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           # compare: drone chases the current UGV position
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

Flying to intercept at the meeting point takes 41.1 s, 5.5 s faster than pursuit, leaving 79 s of battery as margin. A real system must keep sending the vehicle’s speed plan to the drone, and if the vehicle changes speed or communication fails, there must be a backup meeting point where the vehicle stops and waits.