[Algorithm][Path Planning] 경로 교착(Dead Lock)과 Push Algorithm

순서

I. 경로 교착(Dead Lock)
II. Push Algorithms

 

---

I. 경로 교착(Dead Lock)

 

모든 Agent가 정상적으로 이동한다고 했을 때 각자 갈 길을 시간 + 공간에 따라 예측하고 이동하기에,
이론상으로 공간 Conflict가 생긴다 한들, 시간상에서 서로 기다렸다가 이동하는 관점으로 보면
길이 완전히 꽉 막히는 DeadLock은 발생할 수 없다(CBS)

하지만 현실에서는 실제 Agent(로봇)에 문제가 생길 수도 있고, 가려던 길 도중에 멈출수도 있다.

예를 들면 2차선 길이 있는데 2차선을 나란히 지나가는 로봇이 둘다 제자리에 갑자기 서 버린다면?
그 뒤에 탐색하는 Agent들은 경로가 없다고 판단할 것이다.

정확히 서로가 서로를 잇는 Graph가 닫힌 모양으로 경로 탐색이 안되어 이동할 수 없는 상황이다.
(ex. 두 Agent의 출발지 / 목적지가 서로를 향해버리는 상황 등등)

 이를 보통 ACS에서 DeadLock이라고 생각하곤 한다.

 

---

II. Push Algorithms

 

위 문제와 같이 길이 막혀버리는 DeadLock 상황을 풀어주어야 하는데,
Search Algorithm은 "나"의 경로를 찾는데 초점이고, Push는 상위 관제에서 타 Agent를 건드려야한다.

이 때, 상위 관제 시스템에서 주로 사용하는 알고리즘으로 Push And Swap / Push And Rotate Algorithm이 있다.
이름 그대로 Push : 타 Agent를 다른 곳으로 밀어내는 것이 중요하다.

1. Push 단계

- Agent가 타 Agent를 밀어내어 경로를 확보한다.
- 이 과정에서 이동하고자 하는 Agent의 경로를 막지 않는 위치로 이동한다.
- Push 단계를 위해 추가적인 Search가 필요할 수 있다.

 

2. Swap / Rotate 단계

- 두 Agent의 위치를 서로 교환하여 경로를 조정한다.
- 다수 Agent가 되어 서로가 서로의 위치로 이동하며 확장된 형태가 Rotate이다.

A(x1, y1) B(x2, y2)라고 가정 한다면.
1. A -> B(Pushed) 의 결과로 B(x0, y0)으로 비켜줌.
2. A(x2,y2)로 이동
3. B(x1, y1)으로 이동.

 

나는 Swap / Rotate 까지 사용하진 않고 관제를 통한 Push만 사용하여 경로를 확보하는데에만 사용한다.