[Algorithm][Path Planning] Multi-Agent의 Conflict 해결 방법들

순서

I. 접근법 종류
IV. 내가 선택한 방법 (Time-Table)

---

Multi-Agent Path Planning에서 Path Schedule Conflict를 해결하는 방법은 다양하다.

간단히 그 종류만 정리하는 용도.

현재 나는 Time-Table 접근법 중 예약 방식을 사용하는 중...

 

I. 접근법 종류

 

1. Discrete Time Approach

- Conflict-Based Search(CBS)

 

2. Continuous Time Approach

로봇의 속도와 방향을 고려하여 서로 충돌을 피할 수 있는 최적의 속도 공간을 계산하여 진행.

1. Velocity Obstacles(VO)
2. Optimal Reciprocal Collision Avoidance (ORCA)

 

3. Time-Table Based Approach

내가 사용하는 방식으로 각 로봇의 Trajectory를 통해 TimeDomain을 생성하여 RealTime Time Table을 활용한다.

1. Time-Expanded Graphs
  - 각 로봇의 위치와 시간을 실시간으로 고려함

2. Reservation Table
  - 각 로봇이 지나갈 길을 예약함.

3. Mixed-Integer Linear Grogramming(MILP)
  - 경로 계획 문제를 수학적 최적화 문제로 변환함(..?)

4. Reinforcement Learning(RL)
  -강화학습

 

---

IV. 내가 선택한 방법 (Time-Table)

Time-Table 중 Reservation Table을 사용하였다. 이미 쓰고 있던 것도 맞고 쉽기도하고... 사실 다른 것들은 잘 모르겠다...

1. 로봇의 주행에 대한 Trajectory를 계산한다.
  각 경로에 대해, Param 값에 대해 Trapezoidal, S-Curve, MPF등 시간을 계산하여 경로 시간 계산.

2. RealTime으로 각 Path, Node에 해당 Agent가 결정된 Planning의 시간 정보를 입력해둠.(예약)

3. 타 Agent가 다른 경로를 사용할지, 공간은 같지만 다른 시간대를 사용할지 선택하며 CBS 탐색 진행.

* 실제 로봇의 주행 시간에 대한 오차, 환경의 불확실성을 고려하여 공간/시간의 Constraint를 결정하자.

위 방법은 A*의 G값을 RealTime으로 저장하고,
G값을 결정할때 동시에 TimeTable을 확인하며 Conflict를 계산할 수 있어서 효율적이다.