1. Contribution
기존의 MAPF 알고리즘은 Space-time search를 위해 time interval 개념을 사용함
-> 제안하는 Contiguous safe interval의 수는 기존의 time interval의 수보다 훨씬 적음
-> Safe interval을 사용하여 optimality를 보장함과 동시에 search space가 훨씬 작아져 빠른 계산이 가능
2. Algorithm
연속적인 collision free timestep들을 safe interval으로 묶음
각각의 state : (configuration, safe interval) pair로 표현됨
Safe interval : "a contiguous period of time for a configuration, during which there is no collision and it is in collision one timestep prior and one timestep after the priod"
-> Each spatical configuration : has a timeline, altering between safe and collision interval.
Dynamic Obstacle Representation
Dynamic obstacle들의 future trajectory들을 예측해주는 외부 시스템이 존재한다고 가정
a trajectory : just a list of points, where each point has state variables. its configuration, time and some measure of the point's uncertainty
2.1 Planning with safe intervals
Graph Construction
Planner가 initialize 될 때, Predicted dynamic obstacle trajectory들을 이용해 각각의 spatial configuration에 해당하는 timeline을 만듬
Graph Search
A* 수행
1) Successor s' 추가
-> 현재 state s에서 실행 가능한 motion들에 대해 resultant configuration 및 the time of execution을 계산함
-> New configuration에 있는 각각의 time interval에 대해 충돌하지 않으면서 최대한 빠른 도착 시간을 가지는 successor를 만듬 (successor를 만들 때 wait and move motion을 사용해야 할 수도 있음 <- safe interval이 올 때까지 기다리기 위해)
2) A*를 수행하며 s' 에 도착할 수 있는 더 짧은 경로가 발견 될 경우 cost를 해당하는 더 작은 값으로 update
-> s'가 expand될 때 s'에 도달 가능한 가장 빠른 시간을 찾은 것이 보장됨
3. Example
B에 있는 로봇은 위(A) 혹은 아래(C)로 움직일 수 있음
- A로 움직일 경우
$S_{A0}$ : 위로 움직이는 Obstacle이 지나가기 전의 safe interval -> 즉각 움직임
$S_{A1}$ : 위로 움직이는 Obstacle이 지나갈 때까지 기다린 다음의 safe interval 중 하나에 들어가야함 -> 충돌로 인해 invalid
- C로 움직일 경우
$S_{C0}$ : 왼쪽으로 움직이는 Obstacle이 지나가기 전의 safe interva -> 즉시 이동
$S_{C1}$ : 왼쪽으로 움직이는 Obstacle이 지나간 후, 위로 움직이는 Obstacle이 지나가기 전 사이의 safe interval -> timestep 2개 기다리고 이동
$S_{C2}$ : 위로 움직이는 Obstacle이 지나갈 때까지 기다린 다음의 safe interval -> 충돌로 인해 Invalid
