여러 로봇 조율 - 충돌 회피와 작업 분배

이 장에서 배우는 것

창고 로봇 한 대가 자기 경로를 잘 따라가더라도 여러 대가 함께 움직이면 새로운 문제가 생긴다. 같은 교차로에 동시에 도착할 수 있고, 가까운 작업을 여러 로봇이 함께 선택할 수도 있다. 앞 장에서 한 로봇의 미래 움직임을 예측해 제어 입력을 정했다면, 여기서는 로봇 사이의 작업과 이동 시간을 조율한다.

이 장에서는 작업을 먼저 나누고, 정해진 경로에 이동 시간을 붙인 다음, 로봇 사이의 거리를 검사한다. 위치 추정이나 경로 탐색을 다시 구현하지 않는다. 로봇의 현재 위치와 이동 가능한 경로가 주어졌다고 가정하고, 여러 로봇을 함께 움직일 때 필요한 판단에 집중한다.

• 탐욕 알고리즘(greedy algorithm)으로 작업의 중복 할당을 막는다.
• 우선순위 계획(prioritized planning)으로 높은 순위 로봇의 이동 시간을 먼저 예약한다.
• 출발 대기와 이동 속도를 시간표에 반영한다.
• 시간 표본 사이의 움직임까지 검사해 로봇 간 최소 거리를 계산한다.

문제 상황

창고의 가로 통로를 이용하는 로봇 A와 세로 통로를 이용하는 로봇 B가 있다. 두 로봇은 서로 다른 선반에서 물건을 싣지만 이동 중 같은 교차로를 지난다. 각자 만든 경로에는 장애물이 없다. 그러나 둘이 동시에 출발하면 교차로 중심에 같은 시각에 도착한다. 개별 경로의 유효성과 여러 로봇의 동시 이동 가능성은 서로 다른 조건이다.

로봇 C는 위쪽 통로에서 별도 작업을 수행한다. C는 취급 중인 물건 때문에 이동 속도를 낮춰야 한다. 통로가 서로 다르게 보이더라도 C와 B의 도착 지점이 가까우므로, 경로 그림만 보고 충돌 여부를 판단해서는 안 된다. 언제 어느 위치에 있는지를 함께 비교해야 한다.

작업에는 물건을 싣는 위치와 내려놓는 위치가 있다. 이번 예제에서는 작업을 한 번 배정하고 모두 끝낼 때까지 변경하지 않는다. 상하차 시간은 0초로 두며, 좌표의 단위는 미터다. 통로의 정적 장애물 검사는 이미 끝났다고 가정한다.

세 로봇과 각 로봇 가까이에 놓인 작업의 초기 조건

로봇과 시작점	작업	적재점 → 하역점	속도 상한
A: (-3, 0)	T1	(-2, 0) → (2, 0)	1.0 m/s
B: (0, -3)	T2	(0, -2) → (0, 2)	1.0 m/s
C: (-3, 3)	T3	(-2, 3) → (2, 3)	0.5 m/s

로봇은 반지름 0.3m인 원으로 나타낸다. 차체 사이에 0.2m의 여유를 두려면 중심 간 거리는 0.8m 이상이어야 한다. 이 값은 센서가 측정하는 거리와 다르다. 시뮬레이션 속 두 중심 좌표로 계산하는 기하학적 조건이다. 위치 오차나 통신 지연은 이번 실행에 넣지 않는다.

작업을 하나씩 확정하는 탐욕 할당

작업 할당은 누가 어느 물건을 옮길지 결정하는 과정이다. 여기서는 로봇의 현재 위치에서 작업의 적재점까지 가는 거리를 비용으로 쓴다. 이동 경로가 가로와 세로 방향으로만 이어지므로 비용은 두 좌표 차이의 절댓값을 더한 맨해튼 거리(Manhattan distance)다.

아직 배정되지 않은 모든 로봇과 작업의 조합을 만들고, 비용이 가장 작은 조합 하나를 선택한다. 선택한 로봇과 작업을 후보에서 제거한 뒤 같은 과정을 반복한다. 로봇마다 독립적으로 가장 가까운 작업을 고르는 방식과 달리, 이미 선택된 작업이 다시 배정되지 않는다.

비용이 같을 때의 규칙도 필요하다. 예제에서는 비용, 로봇 이름, 작업 이름 순서로 비교한다. A와 T1의 비용, B와 T2의 비용, C와 T3의 비용이 모두 1이므로 A부터 확정된다. 입력 자료의 나열 순서가 달라져도 이름과 비용이 같으면 같은 결과를 얻는다.

가까운 적재점을 먼저 고른다고 전체 작업 시간이 최소가 되는 것은 아니다. 이 비용에는 하역점까지의 거리, 상하차 시간, 다른 로봇 때문에 기다리는 시간이 빠져 있다. 이번 예제는 작업 할당과 충돌 회피의 역할을 구분하기 위해 비용을 단순하게 정한다.

특히 첫 선택이 다음 선택을 불리하게 만들 수 있다. 어떤 작업을 두 로봇이 모두 쉽게 맡을 수 있지만 다른 작업은 한 로봇만 가까운 경우가 그렇다. 탐욕 할당은 선택을 되돌리지 않으므로 전체 조합을 비교하는 최적화 방법과 결과가 다를 수 있다. 대신 결정 규칙을 이해하고 구현하기 쉽다.

완성 코드는 로봇 수와 작업 수가 같고, 각 로봇에 작업 하나를 배정하는 경우만 다룬다. 작업이 더 많으면 남은 작업을 보관하는 대기열이 필요하고, 작업이 더 적으면 쉬는 로봇을 표현해야 한다. 이 차이는 충돌 검사보다 먼저 할당 자료 구조에서 처리해야 한다.

우선순위로 이동 시간을 예약한다

작업을 배정한 다음에는 로봇마다 시작점, 적재점, 하역점을 연결한다. 각 구간에서 x좌표를 먼저 맞추고 y좌표를 맞춘다. 이 규칙은 경로 탐색을 대신하는 예제용 경로 생성 규칙이다. 실제 선반을 통과하지 않는다는 보장은 주어진 통로 조건에 의존한다.

이제 A, B, C 순서로 시간표를 만든다. 먼저 A의 시간별 위치를 확정하고, B는 A의 예약과 충돌하지 않는 출발 시각을 고른다. C는 A와 B의 예약을 모두 확인한다. 한 번 확정한 높은 순위 로봇의 시간표는 낮은 순위 로봇을 계획하면서 변경하지 않는다.

이번 구현에서 조정하는 변수는 출발 전 대기 시간이다. 대기 시간이 0초인 후보부터 검사하고, 충돌하면 1초씩 늘린다. 출발한 뒤에는 지정된 속도로 경로를 끝까지 이동한다. 경로 중간에서 기다리거나 다른 통로로 우회하는 후보는 만들지 않는다.

아직 계획하지 않은 로봇도 창고 안에 존재한다. 따라서 높은 순위 로봇을 계획할 때 낮은 순위 로봇의 시작 위치를 비어 있다고 취급하지 않는다. 아직 계획하지 않은 로봇은 전체 검사 시간 동안 시작점에 정지해 있다고 가정한다. 이는 안전 검사를 보수적으로 만들지만, 나중에 비워질 장소도 계속 점유된 것으로 취급한다는 제약이 있다.

작업을 끝낸 로봇은 하역점에 머문다. 완료 시각 뒤의 예약을 지우면 다른 로봇이 그 자리를 통과할 수 있다고 잘못 판단하게 된다. 모든 시간표는 같은 종료 시각까지 만들고, 도착한 로봇의 마지막 위치를 그 시각까지 반복한다.

검사 시간은 20초다. 그 안에 이동을 끝내는 출발 후보만 만든다. 후보가 모두 거절되면 예외를 발생시켜 계획을 종료한다. 이 결과는 현재 경로, 우선순위, 대기 방식, 검사 시간으로 해를 찾지 못했다는 뜻이다. 창고 전체에 가능한 이동 방법이 없다는 뜻은 아니다.

우선순위를 계속 고정하면 반복 운용에서 특정 로봇이 오래 기다릴 수 있다. 작업 대기 시간에 따라 순위를 올리거나, 완료된 작업 이후 순위를 순환시키는 정책을 고려할 수 있다. 다만 순위를 바꿀 때는 기존 예약과 실제 위치를 기준으로 다시 계획해야 한다. 이름 목록만 바꾸고 이전 시간표를 함께 쓰면 예약의 의미가 깨진다.

속도와 표본 사이의 충돌을 함께 다룬다

시간 간격은 1초다. 경로의 한 칸은 1m이므로 A와 B는 한 칸을 한 번의 시간 간격에 이동한다. C는 같은 칸을 두 번의 시간 간격에 나누어 이동한다. 지정한 속도가 정확히 나누어떨어지지 않으면 필요한 시간 간격 수를 올림한다. 따라서 실제 이동 속도는 지정한 상한을 넘지 않는다.

예를 들어 속도 상한이 0.8m/s라면 1m 이동에 필요한 시간은 1.25초다. 이를 1초 간격 두 개로 표현하므로 구현상의 속도는 0.5m/s가 된다. 시간 간격을 줄이면 표현은 세밀해지지만 검사할 위치 배열이 길어진다. 속도 상한과 실제 시간표에서 실현되는 속도를 구분해야 한다.

출발을 기다리는 동안 속도는 0이다. 출발 후에는 각 직선 구간에서 일정한 속도를 사용한다. 이 예제의 속도 조정은 출발 전 정지와 이동 구간의 속도 설정으로 이루어진다. 정지 상태에서 이동 상태로 즉시 바뀌는 운동학적 모형이며, 가속도와 회전 시간을 포함하지 않는다.

충돌 검사는 정수 시각의 좌표만 비교해서는 부족하다. 두 로봇이 한 시간 간격 동안 서로의 위치를 교환하면 양 끝 시각에서는 떨어져 있어도 중간에 만날 수 있다. 교차로에서 직각으로 지나는 경우에도 가장 가까워지는 순간이 표본 사이에 있을 수 있다.

한 시간 간격의 시작 상대 위치를 r, 그 간격 동안 상대 위치의 변화량을 q라고 하자. 간격 내부의 위치는 r + uq로 나타낼 수 있다. 여기서 u는 0부터 1까지 변하는 무차원 비율이다. 두 로봇은 같은 u에서 비교해야 하며, 서로 다른 시각의 경로 지점을 비교하는 것이 아니다.

u* = clip(-(r · q) / (q · q), 0, 1)
최소 거리 = ||r + u*q||

q가 0이면 상대 위치가 변하지 않으므로 시작 거리를 쓰면 된다. 완성 코드에서는 분모가 양수인 구간에만 나눗셈을 적용한다. 이 방식은 0으로 나누는 경고를 피하면서, 두 로봇이 함께 정지하거나 같은 속도로 나란히 움직이는 경우를 처리한다.

A와 B를 동시에 출발시키면 3초에 중심이 겹친다. B를 1초 늦춰도 충분하지 않다. 3초와 4초 사이에 A는 (0, 0)에서 (1, 0)으로, B는 (0, -1)에서 (0, 0)으로 움직인다. 양 끝의 중심 거리는 모두 1m지만 중간 최소 거리는 약 0.707m다. 필요한 0.8m보다 작으므로 이 후보도 거절한다.

B를 2초 늦추면 A와 B의 최소 거리는 약 1.414m가 된다. C까지 포함한 전체 최소 거리는 별도로 계산해야 한다. 충돌 검사를 통과한 로봇이 추가될 때마다 비교 대상이 늘어나기 때문이다. 출발 시각이 다르다는 사실 자체가 안전 조건을 대신하지는 않는다.

완성 코드

다음 프로그램을 multi_robot.py로 저장한다. Python 3와 numpy가 준비된 환경에서 실행한다. 난수 시드는 11로 고정하며, 현재 계산에는 난수를 사용하지 않는다. 외부 파일이나 화면 출력 장치가 필요하지 않다.

import numpy as np

DT = 1.0
HORIZON = 20
RADIUS = 0.3
CLEARANCE = 0.2
REQUIRED = 2.0 * RADIUS + CLEARANCE

ROBOTS = {
    "A": (-3, 0),
    "B": (0, -3),
    "C": (-3, 3),
}
TASKS = {
    "T1": ((-2, 0), (2, 0)),
    "T2": ((0, -2), (0, 2)),
    "T3": ((-2, 3), (2, 3)),
}
SPEEDS = {"A": 1.0, "B": 1.0, "C": 0.5}
PRIORITY = ("A", "B", "C")


def greedy_assign(robots, tasks):
    if len(robots) != len(tasks):
        raise ValueError("robot and task counts must match")
    free_robots = set(robots)
    free_tasks = set(tasks)
    assigned = {}
    while free_robots:
        candidates = []
        for rid in sorted(free_robots):
            for tid in sorted(free_tasks):
                start = np.array(robots[rid], dtype=float)
                pickup = np.array(tasks[tid][0], dtype=float)
                cost = float(np.abs(start - pickup).sum())
                candidates.append((cost, rid, tid))
        cost, rid, tid = min(candidates)
        assigned[rid] = (tid, cost)
        free_robots.remove(rid)
        free_tasks.remove(tid)
    return assigned


def make_motion(start, pickup, dropoff, speed):
    if not np.isfinite(speed) or speed <= 0.0:
        raise ValueError("speed must be positive and finite")
    ticks = int(np.ceil(1.0 / (speed * DT)))
    position = np.array(start, dtype=float)
    samples = [position.copy()]
    for target_xy in (pickup, dropoff):
        target = np.array(target_xy, dtype=float)
        for axis in range(2):
            while position[axis] != target[axis]:
                next_position = position.copy()
                next_position[axis] += np.sign(
                    target[axis] - position[axis]
                )
                for k in range(1, ticks + 1):
                    fraction = k / ticks
                    samples.append(
                        position + fraction * (next_position - position)
                    )
                position = next_position
    return np.array(samples)


def stationary(position):
    point = np.array(position, dtype=float)
    return np.repeat(point[None, :], HORIZON + 1, axis=0)


def with_delay(motion, delay):
    finish = delay + len(motion) - 1
    if delay < 0 or finish > HORIZON:
        raise ValueError("trajectory exceeds the horizon")
    trajectory = stationary(motion[-1])
    trajectory[:delay] = motion[0]
    trajectory[delay:finish + 1] = motion
    return trajectory


def minimum_distance(first, second):
    relative = first[:-1] - second[:-1]
    change = (first[1:] - second[1:]) - relative
    denominator = np.sum(change * change, axis=1)
    fraction = np.zeros_like(denominator)
    moving = denominator > 0.0
    numerator = -np.sum(relative * change, axis=1)
    fraction[moving] = np.clip(
        numerator[moving] / denominator[moving], 0.0, 1.0
    )
    closest = relative + fraction[:, None] * change
    return float(np.min(np.linalg.norm(closest, axis=1)))


def plan(assigned):
    reserved = {}
    timing = {}
    for rank, rid in enumerate(PRIORITY):
        tid, _ = assigned[rid]
        pickup, dropoff = TASKS[tid]
        motion = make_motion(
            ROBOTS[rid], pickup, dropoff, SPEEDS[rid]
        )
        blockers = list(reserved.values())
        blockers.extend(
            stationary(ROBOTS[other])
            for other in PRIORITY[rank + 1:]
        )
        for delay in range(HORIZON - len(motion) + 2):
            candidate = with_delay(motion, delay)
            if all(
                minimum_distance(candidate, other) >= REQUIRED
                for other in blockers
            ):
                reserved[rid] = candidate
                timing[rid] = (delay, delay + len(motion) - 1)
                break
        else:
            raise RuntimeError(f"no schedule found for {rid}")
    return reserved, timing


def main():
    np.random.seed(11)
    assigned = greedy_assign(ROBOTS, TASKS)
    reserved, timing = plan(assigned)
    for rid in PRIORITY:
        tid, cost = assigned[rid]
        print(f"assign {rid} -> {tid} cost={cost:.1f}")
    for rid in PRIORITY:
        delay, finish = timing[rid]
        print(
            f"plan {rid} speed_limit={SPEEDS[rid]:.2f} "
            f"wait={delay * DT:.1f}s finish={finish * DT:.1f}s"
        )
    distances = [
        minimum_distance(reserved[first], reserved[second])
        for i, first in enumerate(PRIORITY)
        for second in PRIORITY[i + 1:]
    ]
    minimum = min(distances)
    print(f"minimum_distance={minimum:.3f}m")
    print(f"required_distance={REQUIRED:.3f}m")
    print(f"safe={minimum >= REQUIRED}")


if __name__ == "__main__":
    main()

줄별 해설

DT는 위치 표본 사이의 시간이고 HORIZON은 검사할 시간 간격의 개수다. 따라서 위치 배열에는 0초를 포함해 21개 표본이 들어간다. 검사 종료 시각은 두 값을 곱한 20초다. REQUIRED는 두 반지름과 차체 사이의 여유 거리를 합친 값이다.

ROBOTS와 TASKS는 기하학적 입력이다. SPEEDS는 로봇별 속도 상한이고, PRIORITY는 시간표를 확정하는 순서다. 작업을 고르는 순서와 이동 예약의 우선순위는 다른 개념이다. 이번 자료에서는 둘 다 A부터 시작하지만 서로 같아야 하는 조건은 없다.

greedy_assign의 첫 조건문은 일대일 배정이라는 입력 조건을 확인한다. 두 집합에는 아직 선택하지 않은 이름만 남긴다. 중첩 반복문은 남은 모든 조합을 만들고, np.abs(start - pickup).sum()은 적재점까지의 비용을 계산한다.

min(candidates)는 튜플의 첫 항목인 비용부터 비교한다. 비용이 같으면 로봇 이름, 그마저 같으면 작업 이름으로 순서를 정한다. 이어지는 두 remove 호출은 선택한 로봇과 작업을 함께 제거한다. 반환값에는 작업 이름뿐 아니라 출력과 확인에 사용할 선택 당시 비용도 저장한다.

make_motion은 대기 시간을 제외한 위치 배열을 만든다. 좌표는 이 예제처럼 정수 격자점이어야 한다. ticks는 1m를 이동하는 데 필요한 시간 간격 수이며, 올림을 사용하므로 속도 상한을 넘지 않는다. 부동소수점 좌표로 바꾸려면 한 칸 이동을 반복하는 조건부터 수정해야 한다.

samples의 첫 원소는 출발 위치다. 적재점과 하역점을 차례로 방문하면서 축 번호 0, 1의 순서로 좌표를 맞춘다. np.sign은 다음 한 칸의 방향을 결정한다. 내부 반복문의 fraction은 그 한 칸을 여러 시간 간격으로 나누는 비율이다. C에서는 0.5와 1.0이 차례로 사용된다.

stationary는 같은 위치를 21번 반복한다. point[None, :]는 좌표 두 개짜리 배열에 행 축을 하나 추가한다. 이 함수는 아직 움직이지 않는 로봇을 표현할 때도 쓰고, 도착한 로봇의 위치로 전체 배열을 초기화할 때도 쓴다.

with_delay는 도착 위치로 채운 배열 위에 출발 전 대기와 이동 구간을 덮어쓴다. delay는 초가 아니라 시간 간격의 개수다. 이동 배열의 첫 원소가 출발점이므로 완료 인덱스에는 len(motion) - 1을 더한다. 완료 이후의 값은 처음 채운 도착 위치로 남는다.

minimum_distance의 relative는 각 구간 시작 시각의 상대 위치다. change는 다음 시각까지 상대 위치가 얼마나 변하는지 나타낸다. moving으로 상대 운동이 있는 구간만 골라 나눗셈을 수행하고, 구간 밖에 있는 최소점은 np.clip으로 양 끝에 제한한다. 마지막 두 줄은 모든 구간의 최소 거리 중 가장 작은 값을 반환한다.

plan은 이미 확정한 예약과 아직 계획하지 않은 로봇의 정지 배열을 검사 대상으로 모은다. 출발 대기는 작은 값부터 시도한다. 반복 범위의 끝에는 완료 표본이 종료 시각에 놓이는 마지막 후보도 포함된다. 이동 자체가 검사 시간보다 길면 후보 반복은 비어 있게 된다.

all은 모든 검사 대상과 필요한 거리를 유지할 때만 참이다. 후보를 채택하면 예약과 대기·완료 인덱스를 저장한 뒤 반복을 끝낸다. 여기서 for에 붙은 else는 break 없이 반복이 끝났을 때 실행된다. 성공한 후보가 없으면 부분 계획을 실행하지 않고 오류를 알린다.

main은 할당과 계획이 모두 성공한 뒤 결과를 출력한다. 마지막 목록 구성은 A-B, A-C, B-C를 한 번씩 검사한다. 계획 단계와 같은 거리 계산 함수를 사용하므로 이 검사는 시간표의 일관성 확인이다. 거리 계산식 자체를 독립적으로 검증하는 시험까지 대신하지는 않는다.

실행 결과

첫 명령은 경고를 오류로 취급해 문법 컴파일을 확인한다. 두 번째 명령은 numpy 실행 중 발생하는 경고도 드러내도록 같은 옵션을 사용한다. 컴파일이 성공하면 첫 명령은 별도 출력을 남기지 않는다.

python3 -W error -m py_compile multi_robot.py
python3 -W error multi_robot.py

예상 출력은 다음과 같다.

assign A -> T1 cost=1.0
assign B -> T2 cost=1.0
assign C -> T3 cost=1.0
plan A speed_limit=1.00 wait=0.0s finish=5.0s
plan B speed_limit=1.00 wait=2.0s finish=7.0s
plan C speed_limit=0.50 wait=0.0s finish=10.0s
minimum_distance=1.118m
required_distance=0.800m
safe=True

A와 B의 이동 거리는 각각 5m다. A는 즉시 출발해 5초에 끝나고, B는 2초를 기다린 뒤 같은 거리를 이동해 7초에 끝난다. C도 5m를 이동하지만 속도가 절반이므로 10초에 끝난다. 낮은 순위라는 이유만으로 C가 앞선 로봇들이 끝날 때까지 기다리지는 않는다. 예약과 충돌하지 않으면 동시에 이동한다.

전체 최소 거리는 B와 C 사이에서 나온다. 7초에 B는 (0, 2), C는 (0.5, 3)에 있다. 두 중심의 거리는 √1.25m로 약 1.118m다. 이는 요구 거리 0.8m보다 크다. 모든 로봇은 이후 하역점에 머물므로 검사 종료 뒤에도 위치가 그대로라면 거리 조건이 유지된다.

safe=True는 정해진 위치 배열과 구간 내 직선 운동 가정에서 중심 거리 조건을 만족한다는 뜻이다. 실제 로봇의 추종 오차나 제동 지연까지 검증한 결과는 아니다. 실행 중 위치가 시간표에서 벗어나면 실제 위치를 바탕으로 남은 예약을 다시 검토해야 한다.

실무에서 자주 틀리는 것

정수 시각의 거리만 확인한다

다음 코드는 위치 표본에서만 거리를 잰다. B가 1초 늦게 출발하는 후보에서 표본 사이의 접근을 놓친다.

# 틀린 코드: 시간 표본 사이를 검사하지 않는다.
distance = np.min(np.linalg.norm(first - second, axis=1))
safe = distance >= REQUIRED

# 고친 코드: 각 시간 구간 내부의 최소 거리도 검사한다.
distance = minimum_distance(first, second)
safe = distance >= REQUIRED

구간 내부 검사는 실제 운동이 그 구간에서 직선이라는 가정에 기대고 있다. 곡선 이동이나 가속 운동으로 모형을 바꾸면 검사식도 함께 바꿔야 한다.

도착한 로봇을 예약에서 없앤다

작업 완료와 공간 점유 종료는 다르다. 도착 직후 로봇을 삭제하면 하역점이 비어 있다고 판단하게 된다.

# 틀린 코드: 완료 이후 위치를 예약에서 제외한다.
reservation = motion.copy()

# 고친 코드: 출발 대기와 완료 이후 정지를 함께 기록한다.
reservation = with_delay(motion, delay)

로봇이 하역점에서 대기 장소로 이동한다면 그 이동도 예약에 넣어야 한다. 화면에서 보이지 않게 만드는 것은 점유 상태를 변경하는 물리적 동작이 아니다.

예약한 뒤 실행 속도만 낮춘다

속도를 낮추면 언제나 다른 로봇과 더 멀어지는 것은 아니다. 교차로를 빠져나가는 시각이 늦어지면 뒤에 예약된 로봇과 겹칠 수 있다.

# 틀린 코드: 기존 예약을 둔 채 속도만 바꾼다.
reserved, timing = plan(assigned)
SPEEDS["A"] = 0.5

# 고친 코드: 출발 전에 변경한 속도로 예약을 다시 만든다.
SPEEDS["A"] = 0.5
reserved, timing = plan(assigned)

고친 코드는 아직 출발하지 않았을 때의 수정이다. 이미 움직이고 있다면 최초 시작점으로 돌아가 계획해서는 안 된다. 현재 시각, 현재 위치, 진행 중인 작업을 새 계획의 입력으로 사용해야 한다.

각 로봇이 작업을 독립적으로 고른다

로봇별 최솟값만 고르면 같은 작업이 여러 로봇에 배정될 수 있다. 이름으로 동률을 풀어도 중복 선택 자체는 해결되지 않는다.

# 틀린 코드: 선택한 작업이 다음 로봇의 후보에도 남는다.
chosen = {}
for rid in ROBOTS:
    chosen[rid] = min(
        TASKS,
        key=lambda tid: (
            np.abs(
                np.array(ROBOTS[rid]) - np.array(TASKS[tid][0])
            ).sum(),
            tid,
        ),
    )

# 고친 코드: 선택한 로봇과 작업을 함께 후보에서 제거한다.
assigned = greedy_assign(ROBOTS, TASKS)

이번 초기 조건에서는 잘못된 방식도 우연히 서로 다른 작업을 고른다. 오류가 드러나는지 확인하려면 두 로봇을 같은 적재점 가까이에 놓아야 한다. 정상 예제의 출력만 보고 중복 방지 규칙이 있다고 판단해서는 안 된다.

한눈에 보기

작업 배정부터 충돌 검사까지 각 단계가 결정하는 것

단계	사용하는 정보	결정하는 것	남는 제약
탐욕 할당	현재 위치와 적재점	로봇별 작업 하나	전체 비용 최소는 보장하지 않음
경로 구성	시작점·적재점·하역점	축 방향 이동 순서	장애물 탐색은 별도
속도 반영	속도 상한과 시간 간격	시간별 위치	가속도·회전 시간 생략
우선순위 예약	앞선 예약과 정지 위치	출발 전 대기 시간	경로 변경과 중간 대기 없음
거리 검사	같은 시각의 두 궤적	구간 내 최소 중심 거리	구간 내 직선 운동 가정

작업 할당은 목적지를 정하고, 시간 예약은 그 목적지로 이동하는 시점을 정한다. 두 단계가 사용하는 비용과 조건은 다르다. 다음 장에서 창고 시뮬레이터에 연결할 때도 작업 상태, 예약 위치, 실제 위치를 구분해 저장하면 어느 단계에서 지연이 생겼는지 추적하기 쉽다.

연습 문제

1. 두 로봇의 한 구간 위치를 각각 [(-1, 0), (1, 0)], [(1, 0), (-1, 0)]으로 두라. 표본에서만 구한 최소 거리와 minimum_distance로 구한 최소 거리를 비교하라.
2. 초기 조건에서 PRIORITY만 ("B", "A", "C")로 바꾸라. 각 로봇의 대기 시간과 완료 시각을 구하고, 작업 배정도 바뀌는지 설명하라.
3. 로봇 P와 Q, 작업 U와 V의 할당 비용이 각각 P-U=1, P-V=2, Q-U=2, Q-V=100이라고 하자. 탐욕 할당의 총비용과 가능한 다른 배정의 총비용을 비교하라.
4. 다른 조건은 그대로 두고 검사 시간 간격 수를 6으로 줄이라. 어느 로봇에서 계획이 실패하는지, 그 실패를 창고의 이동 불가능으로 해석할 수 없는 이유를 설명하라.

정답과 해설

1. 두 표본 시각의 거리는 모두 2m다. 그러나 두 로봇은 구간의 절반이 지난 시각에 원점에서 만나므로 구간 내부 최소 거리는 0m다. 다음 코드는 2.0 0.0을 출력한다.

   first = np.array([[-1.0, 0.0], [1.0, 0.0]])
   second = np.array([[1.0, 0.0], [-1.0, 0.0]])
   sampled = float(np.min(np.linalg.norm(first - second, axis=1)))
   print(sampled, minimum_distance(first, second))

2. B는 대기 없이 출발해 5초에 완료한다. A는 2초를 기다려 7초에 완료한다. C는 대기 없이 출발해 10초에 완료한다. 할당 함수는 이동 우선순위를 사용하지 않으므로 A-T1, B-T2, C-T3 배정은 유지된다. 이 경우 C가 6초에 (0, 3)을 지날 때 B는 (0, 2)에 정지해 있어 전체 최소 거리는 1m다.

3. 가장 작은 비용인 P-U를 먼저 고르면 Q에는 V만 남는다. 총비용은 101이다. P-V와 Q-U를 선택하면 총비용은 4다. 첫 선택의 비용이 작다는 사실은 모든 배정의 합이 작다는 것을 보장하지 않는다. 이번 코드의 탐욕 할당도 같은 한계를 가진다.

4. A는 5초에 완료하므로 예약된다. B는 이동에 5초가 필요하므로 대기 0초와 1초만 시도할 수 있다. 두 후보 모두 A와 필요한 거리를 유지하지 못해 RuntimeError: no schedule found for B가 발생한다. C까지 계획이 진행되지 않는다. 검사 시간을 늘리면 원래의 2초 대기 후보를 쓸 수 있으므로, 실패 원인은 적어도 현재 시간 제한과 후보 구성에 있다.