기술 요약: 최적화되고 운동학적으로 실현 가능한 다중 에이전트 운동 계획

문제 정의

본 논문은 복잡한 운동학을 가진 자율 시스템, 특히 트랙터-트레일러 시스템을 위한 다중 에이전트 운동 계획 (MAMP) 문제를 다룹니다. 단순화된 동역학을 가진 이산 그리드 위의 점 에이전트를 가정하는 표준 다중 에이전트 경로 찾기 (MAPF) 와 달리, 본 연구는 $\dot{x}_i(t) = f_i(x_i(t), u_i(t))$로 기술된 비선형 동역학 시스템으로서의 에이전트를 고려합니다. 목표는 장애물 $O$가 포함된 작업 공간 $W$ 내에서 $k$개의 에이전트가 초기 상태 $x_{i,0}$에서 최종 상태 $x_{i,f}$로 이동할 때, 실현 가능하고 충돌이 없으며 최적화된 궤적 집합을 찾는 것입니다.

최적화 문제는 다음 조건을 만족하면서 개별 비용 함수 $J_i = \int_{t_0}^{t_f} l(x_i(t), u_i(t)) dt$의 합을 최소화하는 것을 목표로 합니다:

1. 시스템 동역학 제약.
2. 상태 제약 (장애물 및 작업 공간 경계 회피).
3. 제어 제약.
4. 에이전트 간 충돌 회피 ($R_i(x_i) \cap R_j(x_j) = \emptyset$).

저자들은 경로 선택의 조합적 성질과 시스템의 비선형성, 그리고 에이전트 간의 우선순위 충돌이 복합적으로 작용하여 전역 최적 해를 찾는 것이 NP-완전 문제라고 지적합니다.

방법론

제안된 프레임워크는 계산적 실현 가능성과 해의 품질 및 운동학적 실현 가능성 사이의 균형을 맞추도록 설계된 2 단계 접근법입니다.

1 단계: 초기 실현 가능 해

첫 번째 단계는 이산 탐색 방법을 사용하여 초기 실현 가능하고 충돌이 없는 해를 생성합니다.

• 다중 에이전트 탐색: 본 프레임워크는 충돌 기반 탐색 (CBS) 또는 우선순위 기반 탐색 (PBS) 중 하나를 활용합니다. 이러한 방법들은 MAMP 문제를 단일 에이전트 계획 문제로 분해하여, 제약 조건을 추가 (CBS) 하거나 우선순위 순서를 탐색 (PBS) 함으로써 충돌을 해결합니다.
• 단일 에이전트 계획기: 저자들은 두 가지 단일 에이전트 계획기를 평가합니다:
  1. 확장된 SIPP-IP (구간 투영을 통한 안전 구간 경로 계획): 일반 비용 함수와 더 큰 에이전트 (여러 그리드 셀) 를 처리하도록 수정되었습니다. 이는 안전 상태를 나타내기 위해 시간 구간을 사용합니다.
  2. 격자 기반 계획기: 시간으로 확장된 이산화된 상태 공간에서 그래프 탐색 (A*) 을 사용합니다.
• 운동 원시 (Motion Primitives): 중요한 구성 요소는 시간 동기화된 운동 원시를 생성하는 것입니다. 저자들은 모든 원시의 지속 시간이 고정된 샘플 시간 $t_s$의 배수가 되도록 하는 최적의 운동학적으로 실현 가능한 원시를 생성하는 방법을 제안합니다. 이러한 동기화는 SIPP-IP 및 격자 계획기에서 효율적인 충돌 검사를 위해 필요합니다.

2 단계: 연속적 개선

두 번째 단계는 수치 최적 제어를 사용하여 이산 해를 정제합니다.

• 다단계 최적 제어 문제 (OCP): 초기 이산 해는 다단계 최적 제어 문제 (OCP) 에 대한 수치 솔버를 '워밍업 (warm-start)'하는 데 사용됩니다.
• 단계 구조: 서로 다른 도착 시간 ($t_{i,f}$) 을 가진 에이전트를 처리하기 위해, 문제는 $M=k$개의 단계로 나뉩니다. 단계 $m$은 에이전트 $m-1$의 목표 달성 시간과 에이전트 $m$의 목표 달성 시간 사이의 시간 구간을 다룹니다. 이 구조는 충돌 검사를 위해 각 단계 내에서 일관된 시간 이산화를 허용하면서도 서로 다른 에이전트에 대해 서로 다른 총 지속 시간을 가능하게 합니다.
• 최적화: 솔버는 연속 궤적과 제어 입력을 최적화하여 이산화 아티팩트를 제거하고 엄격한 운동학적 실현 가능성을 보장합니다.

주요 기여

1. 2 단계 MAMP 프레임워크: 전역 실현 가능성을 위한 이산 탐색 (CBS/PBS) 과 지역 최적화 및 운동학 평활화를 위한 연속 최적 제어 (OCP) 를 결합한 하이브리드 접근법.
2. 시간 동기화된 원시 생성: 공통 샘플 시간의 정수 배수로 지속 시간이 제한된 최적 운동 원시를 생성하는 새로운 알고리즘 (알고리즘 1). 이는 동기화된 충돌 검사를 용이하게 합니다.
3. SIPP-IP 확장: 단일 점뿐만 아니라 복잡한 기하학적 구조 (여러 그리드 셀을 차지하는) 를 가진 에이전트와 일반 비용 함수를 지원하도록 SIPP-IP 알고리즘을 수정.
4. 다단계 OCP 공식화: 문제를 순차적 시간 단계로 분할하여 이질적인 에이전트 도착 시간을 처리하는 MAMP 개선 단계에 대한 특정 공식화.

실험 결과

본 프레임워크는 장애물이 없는 환경과 장애물이 풍부한 환경 모두에서 트랙터-트레일러 시스템 (2-트레일러 구성) 에 대해 평가되었습니다.

• 단일 에이전트 성능:
  • 장애물이 없는 환경에서 격자 기반 계획기는 확장된 SIPP-IP 보다 훨씬 빠르며 (0.008 초 대 0.12 초), 약간 더 낮은 비용을 생성했습니다.
  • 장애물이 있는 환경에서 격자 기반 계획기는 여전히 더 빠르며 약 14% 낮은 비용을 가진 해를 생성했습니다. 저자들은 SIPP-IP 의 더 높은 비용과 낮은 성공률을 그리드 셀 기반의 "보수적인" 충돌 검사로 귀인시켰으며, 이는 격자 계획기 (원 - 원 충돌 검사 사용) 가 허용하는 실현 가능한 경로를 폐기한다고 설명했습니다.
• 다중 에이전트 성능 (CBS 대 PBS):
  • 성공률: 장애물이 없는 환경에서 PBS 는 CBS 보다 더 많은 문제를 해결했습니다. 그러나 장애물이 있는 환경에서는 CBS 가 더 높은 성공률과 더 낮은 평균 실행 시간을 달성했습니다.
  • 해의 품질: 개선 단계를 거친 후 두 계획기 모두 유사한 품질의 해를 생성했습니다. CBS 는 최적성 보장으로 인해 초기에 약간 더 낮은 비용의 해를 찾았지만, 연속 개선 단계는 종종 이러한 우위를 평준화하거나 약간 반전시켰습니다.
  • 확장성: 에이전트 수가 증가함에 따라 두 계획기 모두 성공적으로 해결된 문제의 수가 감소했지만, CBS 는 복잡하고 장애물로 가득 찬 시나리오에서 성능 우위를 유지했습니다.

중요성 및 주장

본 논문은 트랙터-트레일러와 같은 복잡한 운동학 시스템을 위해 격자 기반 계획기를 CBS 나 PBS 와 결합한 접근법이 덜 보수적인 충돌 검사로 인해 이론적으로 더 견고한 SIPP-IP 접근법보다 우수하다고 주장합니다. 제안된 2 단계 프레임워크는 합리적인 시간 내에 실현 가능한 해를 찾는 것과 운동학적으로 실현 가능하고 최적화된 궤적을 달성하는 것 사이의 간극을 성공적으로 연결합니다.

저자들은 PBS 는 열린 공간에서 더 많은 문제를 해결할 수 있지만, CBS 는 혼잡한 환경에서 더 우월하다는 점을 겸손하게 지적합니다. 그들은 초기 이산 해의 품질이 최종 최적화 비용을 엄격하게 결정하지는 않으며, 연속 개선 단계가 결과를 크게 바꿀 수 있다고 결론지었습니다. 향후 연구는 분산 최적화를 통해 개선 단계의 계산 효율성을 높이고 교통 규칙을 통합하는 데 초점을 맞출 것으로 제안됩니다.