PUSH AND ROTATE

• "PUSH AND ROTATE" 알고리즘은 다중 에이전트 경로 찾기(Multi-Agent Path Finding, MAPF) 문제를 해결하기 위해 고안된 알고리즘
• 다중 에이전트 시스템에서 간단한 상황에 효율적으로 적용가능
• 복잡한 계산이나 대규모 데이터 처리 없이 적용 가능
• 알고리즘의 이름은 두 가지 작업 단계인 'Push'와 'Rotate'에서 유래했습니다.
  • 'Push' 단계에서는 한 에이전트가 다른 에이전트를 목적지 쪽으로 밀어내는 작업을 수행
  • 'Rotate' 단계에서는 에이전트들이 회전하거나 움직여, 서로의 위치를 바꾸는 방식으로 충돌 없이 경로를 조정
• 좁은 통로나 한정된 공간에서 에이전트들이 서로의 길을 막고 있을 때 유용
• grid와 같은 구조화된 환경에서 잘 작동

PUSH AND ROTATE 알고리즘의 기본 단계

1. 초기화: 에이전트들은 그리드 기반의 환경에서 시작합니다. 각 에이전트에는 시작 위치와 목적지가 주어집니다.

2. 단일 에이전트 경로 찾기: 각 에이전트는 초기에 자신의 목적지까지의 경로를 독립적으로 계산합니다. 이때, 다른 에이전트의 존재는 고려하지 않습니다.

3. 충돌 감지: 에이전트들이 이동하면서 서로의 경로가 교차하는 지점을 찾습니다. 이러한 교차 지점이 충돌 가능성을 나타냅니다.

4. Push 단계: 충돌이 감지되면, 'Push' 단계가 시작됩니다. 이 단계에서 한 에이전트가 다른 에이전트를 '밀어내는' 방식으로 충돌을 해결합니다. 예를 들어, 한 에이전트가 다른 에이전트의 경로를 가로막고 있다면, 가로막힌 에이전트는 잠시 다른 위치로 이동하여 길을 터줍니다.

5. Rotate 단계: 필요한 경우 'Rotate' 단계가 수행됩니다. 여기서 에이전트들은 자리를 바꾸거나 회전하여 서로의 길을 막지 않도록 합니다. 이는 특히 좁은 공간이나 복잡한 환경에서 유용합니다.

6. 반복적인 조정: Push와 Rotate 단계는 모든 에이전트가 충돌 없이 목적지에 도달할 때까지 반복적으로 수행됩니다.