창고에서 쉬는 로봇 한 대가 길을 통째로 막아

에이전트 여러 대가 같은 창고를 도는 문제를 MAPD라고 불러. 픽업과 배송 작업이 시간 순서대로 계속 떨어지고, 로봇들이 그걸 나눠 맡아. 골치는 일이 없는 로봇이야. 1차선 통로와 막다른 길, 나뭇가지처럼 뻗은 경로로 채워진 창고에서는 비켜설 데가 없어서 남의 길을 막아버려.

지금까지의 완료 보장은 계획 경로가 피해 갈 수 있는 여분 대기 지점이 있거나, 어떤 두 칸이든 두 갈래로 이어져 있다는 가정에 기대. 촘촘한 창고는 둘 다 아닌 경우가 많고.

로봇마다 자기만 쓰는 칸을 하나 고정해 뒀어

8월 27일 arXiv에 올라온 원고가 내놓은 규칙은 단순해. 로봇마다 Safe Haven을 하나씩 정해 두는데 보통 자기 출발 칸이야. 그 칸은 주인만 들어갈 수 있고, 다른 로봇에겐 막힌 칸으로 보여.

저자들은 이 규칙이 지켜지면 유한하게 풀린 작업이 전부 끝난다는 걸 증명했다고 적었어. 조건은 Haven에 늘 도달할 수 있어야 한다는 것과 계획·진행에 관한 몇 가지 가정이야. 구현체 이름이 SHARP인데, 일하는 중이든 물러나는 중이든 모든 로봇을 자기 Haven에서 끝나는 충돌 없는 예약 경로 위에 둬.

완료율은 SHARP만 100%, 대신 계획 비용이 올라가

비교 대상은 Token Passing과 PIBT, PIBTTP-TA 셋이야. 견고성 스윕에서 테스트한 모든 설정을 100% 성공으로 통과한 건 SHARP뿐이었어. 다만 나뭇가지 모양 배치에서는 중앙에서 경로를 짜는 비용이 눈에 띄게 늘어. 공짜로 얻은 안정성은 아니야.

TP에 고정 복귀와 전체 경로 검증을 얹은 대조군도 같이 돌렸는데 이 변형도 견고성을 회복했어. 그래서 저자들은 나뭇가지 배치에서 실제로 작동한 장치를 고정 복귀라고 봐.

되돌아가는 규칙을 느슨하게 하면 바로 나빠져

물러나는 도중에 다른 작업을 다시 맡기는 걸 막은 변형도 재봤어. 부하가 높은 나뭇가지 조건에서 작업이 풀려 배달될 때까지 걸린 시간은 1.89배, 전체 작업이 끝나는 시간은 1.53배로 나빠졌어. 자리를 정해 두는 것만으로는 부족하고, 물러나는 중에도 계속 다시 배정할 수 있어야 한다는 얘기야.

로봇 얘기지만 에이전트를 여러 개 굴릴 때도 겹쳐

  • 아직 워크숍 원고야: 11페이지 분량이고 ICAPS 2026 부속 워크숍 PlanRob에 채택됐다고 적혀 있어. 학술지 동료 심사를 통과한 단계는 아니야.
  • 수치는 자체 측정이야: 성공률과 배수 모두 저자들이 직접 돌린 결과고, 제3자가 재현한 기록은 찾지 못했어.
  • 가져갈 관점: 자원 하나를 여러 에이전트가 나눠 쓸 때 누가 먼저 가느냐만 조정하면 물러설 데가 사라져. 각자에게 물러설 칸을 미리 떼어 두는 설계도 있다는 거야.