1. Multi Agent Path Finding
MAPF의 수학적 표현
- 에이전트 집합 ( A = {a_1, a_2, ..., a_n} )
- 시작 위치 ( S = {s_1, s_2, ..., s_n} ) 에이전트 ( a_i )의 시작 위치는 ( s_i )
- 목적지 위치 ( G = {g_1, g_2, ..., g_n} ) 에이전트 ( a_i )의 목적지는 ( g_i )
- 시간 단계 ( t ), 각 시간 단계에서 에이전트는 자신의 위치를 유지하거나 인접한 격자로 이동할 수 있습니다.
- 목표 함수는 대체로 경로의 최적성(예: 총 이동 시간의 최소화, 최단 경로 사용)과 충돌 회피를 모두 고려합니다.
- 충돌은 일반적으로 다음 두 가지 유형으로 구분됩니다:
- 위치 충돌: 두 에이전트가 동일한 시간에 같은 위치를 차지하려고 하는 경우
- 교차 충돌: 두 에이전트가 동일한 시간 단계에서 서로의 경로를 교차하는 경우
MAPF 문제 해결 방법
- MAPF 문제를 해결하는 방법에는 여러 가지가 있으며, 그중 일부는 다음과 같습니다:
- 중앙 집중식(Centralized) 방법: 모든 에이전트의 경로를 동시에 계획하여 최적의 해를 찾습니다. 이 방법은 정확도는 높지만 계산 복잡성이 매우 높을 수 있습니다.
- 분산형(Decentralized) 방법: 각 에이전트가 독립적으로 또는 지역적인 협력을 통해 자신의 경로를 계획합니다. 이 방법은 계산 복잡성을 줄일 수 있지만 최적해를 보장하기 어려울 수 있습니다.
- 하이브리드(Hybrid) 방법: 중앙 집중식과 분산형 방법의 장점을 결합합니다.
1. Conflict-Based Search (CBS)
- Conflict-Based Search (CBS) 중앙 집중식 알고리즘입니다.
- CBS는 특히 서로 충돌하지 않는 경로를 찾는 데 초점을 맞춘 알고리즘으로, 그 효율성과 단순성 때문에 널리 사용
- CBS의 핵심 아이디어는 충돌을 기반으로 경로를 반복적으로 개선
CBS 알고리즘의 기본 구조
- CBS는 두 개의 주요 단계로 구성됩니다: 하이 레벨과 로우 레벨.
하이 레벨(High-Level):
- 하이 레벨에서는 에이전트 간의 충돌을 감지하고, 충돌을 해결하기 위한 결정을 내립니다.
- 이 단계는 충돌을 해결하기 위해 경로에 어떤 제약 조건을 추가할지 결정하는 '충돌 트리'를 구성
- 각 노드는 특정 에이전트에 대한 경로에 대한 제약 조건의 집합을 나타내며,
- 루트 노드는 제약 조건이 없는 초기 상태를 나타냄
로우 레벨(Low-Level)
- 로우 레벨에서는 각 에이전트에 대해 하이 레벨에서 정의된 제약 조건을 만족하는 경로를 찾습니다.
- 이는 일반적으로
A*와 같은 경로 탐색 알고리즘을 사용하여 수행됩니다.
충돌 트리(Conflict Tree)
- 충돌 트리의 각 노드는 특정 제약 조건 하에 경로를 찾는 문제를 나타냅니다.
- 노드에서 충돌이 감지되면, 해당 충돌을 해결하기 위해 두 개의 자식 노드가 생성
- 각 자식 노드는 충돌하는 두 에이전트 중 하나에 대해 추가적인 제약 조건을 도입
- 이렇게 하여, 두 에이전트가 동일한 위치에서 동시에 출현하는 것을 방지
알고리즘의 수행 과정
- 초기화: 모든 에이전트에 대해 제약 조건이 없는 상태에서 최적의 경로를 찾습니다.
- 충돌 감지: 현재 경로 집합에서 충돌을 검사합니다. 충돌이 없으면 알고리즘을 종료합니다.
- 충돌 해결:
- 충돌이 감지되면, 충돌하는 각 에이전트에 대해 제약 조건을 추가하고, 이러한 제약 조건을 만족하는 새로운 경로를 찾습니다.
- 이 과정은 충돌 트리를 통해 이루어집니다.
- 반복: 새로운 경로가 찾아질 때까지 이 과정을 반복합니다.
2. cooperative a*
기본 원리
A*알고리즘은 시작 노드에서 목표 노드까지의 최소 비용 경로를 찾기 위해 휴리스틱을 사용하는 탐색 알고리즘- 각 노드는 g(n) (시작 노드부터 현재 노드까지의 비용), h(n) (현재 노드에서 목표 노드까지의 예상 비용), 그리고 f(n) = g(n) + h(n) (전체 예상 비용)의 값을 가집니다.
Cooperative A*의 핵심 개념
Cooperative A*에서는 기존A*알고리즘을 확장하여 다음과 같은 추가 요소를 포함합니다:
- 시간 확장 탐색 공간:
- 각 에이전트의 이동은 시간에 따라 계획되므로, 탐색 공간은 공간적 위치 뿐만 아니라 시간 차원을 포함합니다.
- 이를 통해 에이전트는 특정 시간에 특정 위치에 있게 됩니다.
- 에이전트 간 협력:
CA*는 각 에이전트가 다른 에이전트의 현재 및 예상 경로를 고려하여 자신의 경로를 계획- 이를 위해, 알고리즘은 다른 에이전트의 경로를 제약 조건으로 포함하여 충돌을 방지
- 경로 계획 및 조정:
- 알고리즘은 모든 에이전트의 경로를 동시에 계획하고 필요에 따라 조정
- 이 과정에서, 한 에이전트의 경로가 변경되면 이는 다른 에이전트의 경로 계획에도 영향을 미칠 수 있음
수학적 표현
- ( g(n) ): 시작 노드에서 노드 ( n )까지의 실제 이동 비용.
- ( h(n) ): 노드 ( n )에서 목표 노드까지의 휴리스틱 비용. 이는 일반적으로 유클리드 거리나 맨해튼 거리를 사용하여 추정됩니다.
- ( f(n) = g(n) + h(n) ): 노드 ( n )을 통해 목표에 도달하기 위한 전체 예상 비용.
- 여기서 주요 차이점은 각 에이전트가 자신의 ( g(n) )과 ( h(n) )을 계산할 때, 다른 에이전트의 예상 위치와 시간을 고려해야 한다는 점
추가적 내용
- 이 글에서는 그리드가 아닌 복잡하고 변화하는 환경에서 여러 에이전트가 충돌 없이 움직이게 하는 문제를 어떻게 해결할지에 대해 이야기하고 있어요.
- 그리고 이 문제를 해결하기 위해 새로운 알고리즘과 접근 방법을 모색해야 한다고 제안하고 있습니다.
Non-grid MAPF??
- MAPF는 일반적으로, 많은 연구에서는 에이전트들이 그리드 형태의 환경에서 움직인다고 가정
- 각 에이전트는 이 칸들을 따라서만 움직일 수 있어요.
- 이때 모든 칸을 이동하는 데 걸리는 시간이나 비용이 동일하다고 가정
- 그런데 실제 세계에서는 환경이 그리드로 나누어지지 않는 경우가 많아요. 이런 환경에서는 Quadtree 그래프 같은 다른 형태의 데이터 구조를 사용해서 환경을 표현하기도 합니다.
- 하지만, 이런 방식에서는 한 칸을 이동하는 데 필요한 시간이나 비용이 일정하지 않을 수 있어요. 왜냐하면 각 구역의 크기나 특성이 다를 수 있기 때문이죠.
실시간으로 환경이 변화하는 상황에서 MAPF
- 더군다나, 실시간으로 환경이 변화하는 경우도 있어요.
- 예를 들어, 건설 현장에서는 새로운 장애물이 생기거나 기존의 장애물이 제거되는 등 맵이 지속적으로 업데이트될 수 있어요.
- 이런 동적인 환경에서는 경로를 찾는 알고리즘도 이러한 변화를 실시간으로 반영할 수 있어야 합니다.
- 이와 같이 non-grid 혹은 동적 환경에서 MAPF 문제를 푸는 것은 더 복잡하며, 기존의 알고리즘들을 그대로 적용하기 어려울 수 있어요.
- 그래서 여기에서는 학습 기반의 partial planning 같은 새로운 접근 방법을 실험해보는 것이 좋을 것이라고 제안하고 있어요.
- 학습 기반 접근 방법에서는, 알고리즘이 경험을 통해 스스로 최적의 경로를 찾는 방법을 배우게 됩니다.
- 이는 알고리즘에게 더 유연성을 제공하여, 다양한 환경과 상황에 적응할 수 있게 해줄 수 있죠.
- Partial planning은 전체 맵을 한 번에 계획하는 대신, 필요에 따라 일부분만 계획하고 상황이 변하면 계획을 수정하는 방식을 의미해요.
- 이런 방법은 특히 맵이 크거나 동적으로 변하는 환경에서 유용할 수 있습니다.
새로운 것이 들어오면 이미 있는 것과 충돌을 시도하라.