로봇 관제

MAPF 기본 정리 - 다중 에이전트 경로탐색

탄생 2024. 3. 11. 18:05

❖ MAPF란?

MAPF는 여러 에이전트가 각자의 목표 위치까지 충돌없이 이동하는 가장 효율적인 경로를 찾는 문제입니다.

로봇의 경로 계획, 비디오 게임에서의 캐릭터 이동, 공항 또는 항구에서의 차량 관리등 다양한 분야에서 활용됩니다.

MAPF의 주된 도전 과제는 '충돌'입니다. 두 에이전트가 동시에 같은 시간에 동일한 경로를 사용할 수 없습니다. 따라서 각 에이전트의 이동 경로는 다른 에이전트와 상호 작용을 고려하여 계획되어야 합니다.

 

이 문제를 해결하기 위한 다양한 접근 방법이 존재합니다.

  • 최적화 기반 접근법: 최적의 해결책을 찾는 것을 목표로 합니다. A* 알고리즘과 같은 기존의 단일 에이전트 경로 찾기 알고리즘을 확장하여 사용합니다.
  • 충돌 회피 기반 접근법: 충돌을 최소화하는 것을 목표로 합니다. 에이전트가 동시에 경로를 계획하고, 충돌이 발생하면 경로를 재조정하는 방식을 사용합니다.

❖ 로봇 경로 계획 이론과 현실, 해결 전략

    • 로봇 경로 계획에서의 이론과 현실의 괴리
      로봇 경로 계획(Multi-Agent Path Finding, MAPF) 문제는 이론적으로 완벽한 해결 방안을 제시해주지만, 실제 로봇을 운영해보면 예상한 대로 움직이지 않는다. 로봇의 실제 움직임과 실시간 공간 정보 간의 정확한 일치를 이루기 어렵기 때문에 생깁니다.
    • 실시간 경로 재계산의 필요성
      로봇이 처음 계산된 경로를 끝까지 따르는 것보다, 오류가 예상되는 시점에 경로를 새롭게 탐색하고 그 결과를 따르게 하는 것이 여러 로봇을 장시간 운영하는데 있어 더욱 유리합니다. 하지만 이러한 접근 방식도 연산 시간의 제약을 받으며, 교착 상태의 발생 가능성을 완전히 배제할 수 없습니다.
    • 교착 상태의 회피 전략
      교착 상태 발생 시, 로봇을 임의의 가까운 위치로 이동시켜 회피시켜 교착 상황을 해결 할 수 있지만 해당 이동으로 실제 로봇 위치와 계획된 경로 사이에 더 큰 차이를 발생시킬 수 있으며, 이는 결국 부정확한 결과를 초래할 수 있습니다.
    • 공간 구성
      • 격자 형태(그리드)
        특히 로봇이 활동하는 공간이 좁은 통로나 높은 밀도의 장애물로 구성된 경우, 공간을 격자 형태의 그래프로 구성하는 것이 경로 계산의 복잡도를 높여 알고리즘의 빈번한 수행을 어렵게 만듭니다.
        이는 로봇 경로 계획의 호율성과 정확성을 저하시키는 주된 요인 중 하나입니다.
      • 토폴로지 형태(점과 선)
        그래프 내의 탐색 노드가 적어지기 때무에 경로 계산에 필요한 연상량을 줄일 수 있지만, 이동 중간에 재 경로 계획이 필요한 경우 정확한 위치에서 경로 탐색을 하기 어렵습니다.

❖ 온라인 알고리즘, 오프라인 알고리즘

  • 온라인 알고리즘
     입력 데이터가 순차적으로 주어지며, 각 단계에서 새로운 데이터를 받아 처리합니다.
    이전에 내린 결정을 바탕으로 현재의 결정을 내리며, 이후에 받게 될 데이터에 대해선 알 수 없습니다.
    따라서 실시간으로 변화하는 환경에 빠르게 대응할 수 있어야 합니다.
  • 오프라인 알고리즘
    모든 입력 데이터를 미리 알고 있습니다.
    이를 바탕으로 최적의 결정을 내리기 위해 전체 데이터를 고려할 수 있습니다.
    이러한 특성 때문에 오프라인 알고리즘은 계획을 세우는 데 있어 효과적일 수 있습니다.

- 온라인 알고리즘은 빠르게 변화하는 상황에 유연하게 대응 할 수 있는 반면 오프라인 알고리즘은 전체 데이터를 고려하여 정확한 계획을 세울 수 있는 장점이 있습니다.

❖ 대표적인 온라인 알고리즘, 오프라인 알고리즘

  • Conflict-Based Search (CBS) - 오프라인 알고리즘
    CBS는 고도의 효율성과 정밀성을 자랑하는 계층적 경로 계획 알고리즘으로, 복잡한 멀티 에이전트 환경에서 충돌 없는 경로를 찾는데 특화되어 있습니다.
    • cbs의 구조
      1. High-Level Search: 이 단계의 주요 목표는 충돌 감지 및 해결입니다. 알고리즘은 여러 에이전트의 경로에 대한 메타 정보를 분석하여 충돌을 감지하고, 어떤 경로가 수정되어야 하는지를 결정합니다. 여기서는 충돌 해결에 중점을 두고, 효율적인 경로 수정 방안을 모색합니다.
      2. Low-Level Search: High-level 단계에서 정의된 제약 조건을 바탕으로, 각 에이전트는 충돌 없이 목표 지점까지 도달할 수 있는 최적의 경로를 계산합니다. 이 단계는 실제 경로 계산에 초점을 맞추며, 에이전트 간의 충돌이 해결된 상태에서 최적의 경로를 찾아냅니다.
    • CBS에서 다루는 충돌 유형
      1. 위치 충돌: 두 에이전트가 동시에 같은 위치에 있으려고 할 때 발생합니다.
      2. 경로 충돌: 두 에이전트의 경로가 교차하여 충돌할 가능성이 있을 때 발생합니다.
    • 충돌 해결 메커니즘
      CBS는 충돌을 해결하기 위해 Constraint Tree(CT)라는 구조를 사용합니다. CT의 각 노드는 특정 충돌에 대한 해결책을 제시하며, 에이전트의 경로에 특정 경로 제약 조건을 적용합니다.
      1. 충돌이 발생한 에이전트의 경로를 재계획하여 충돌을 회피합니다.
      2. 충돌을 발생시킨 에이전트 중 하나에게 우선순위를 부여하여 충돌을 회피합니다.
  • Receding Horizon Collision(RHC) - 온라인 알고리즘
    각 에이전트가 자신의 경로를 독립적으로 계획하고, 충돌을 피하기 위해 다른 에이젠트의 경로를 고려합니다. 
    "Receding Horizon"이란 용어는 각 에이전트가 미래의 일정 시간 동안만 경로를 계획하고, 그 이후는 무시한다는 개념을 나타냅니다. 이 방식은 실시간 환경에서 유용하며, 계산 복잡성을 줄일 수 있습니다.
    • 충돌 해결 전략
      RHC 알고리즘은 충돌이 발생하면 조기 결정(early commitment) 전략을 통해 충돌을 해결합니다. 
      각 에이전트가 미래의 경로를 미리 확정하고, 그 경로를 따르도록 다른 에이전트에게 알리는 것을 의미합니다. 이 방식은 충돌을 더욱 효과적으로 피할 수 있게 해주지만, 에이전트가 자신의 경로를 변경하기 어려워질 수 있습니다 이는 충돌이 발생하기 전에 이미 결정된 움직임을 유지하는 것을 중점으로 합니다. 충돌이 예상되는 시점에 경로를 재계획하여 새로운 경로를 따르도록 함으로써 충돌을 효과적으로 회피합니다.

❖ 개인 목표

커다란 맵에 많은 로봇을 움직일 때 RHC 방식이 빠른 연산 속도와 충돌 발생시 유연하게 대처할 것으로 판단되어 해당 알고리즘으로 로봇 경로 계획 프로젝트를 진행해 보려고 합니다.
RHC 알고리즘의 계산 효율성을 향상시키고, 다양한 충돌 상황에 효과적인 회피전략을 연구하는 기반을 마련할 수 있을 것입니다.

  • 전략
    1. 로봇이 움직이는 노드의 사이즈를 작게 하여 충돌 기회를 줄이고, 자주 경로계획을 합니다.
      예) 로봇은 2~3번 움직일 만큼의 경로계획을 진행하여 로봇에게 이동 명령을 진행합니다.
    2. 경로 계획시 해당 로봇과 가까운 로봇의 예상경로만 참조한다.
      예) x,y축이 (1,1)의 로봇이 2회 이동할 경우 이동 경로는 (3,1), (3,1), (2,2) 가 될것입니다.
      이 경우, 경로 계획은 (4,4) 범위 이내에 위치한 로봇들에 대해서만 충돌 가능성을 고려하며, 그 외의 로봇들은 경로 계획시 고려대상에서 제외합니다.
    3. 길찾기 알고리즘은 JPS를 적용해 본다.
      JPS알고리즘은 모든 경로가 동일하다는 가정하에 길을 찾는것을 전제조건으로 하기 때문에 가중치 적용에는 적합하지 못한 알고리즘으로 다익스트라 알고리즘을 활용한다.

❖ 참고 사이트

저작자표시