1. Contribiution
Token Passing(TP)에 SIPPwRT(Safe Interval Path Planning with Reservation Table)을 적용
2. SIPPwRT
2.1 Reservation Table and Safe Interval
SIPP : 각각의 dynamic obstacle들의 path를, 시간순으로 정렬된 dynamic obstacle에 차지된 cell들의 리스트로 나타냄
-> 주어진 한 cell의 모든 safe interval을 계산하기 위해 이 리스트들을 모두 interate 해야함 -> 비효율적
Space Time A* : reservation table을 유지하여 주어진 cell의 safe interval 계산을 효율적으로 할 수 있음
2.2 Time Offsets
특정 cell의 Safe interval은 해당 cell이 차지되지 않은 시간을 나타내지만, 이것이 충돌이 없음을 보장해주지는 않음(해당 cell을 막 떠난 dynamic obstacle 혹은 막 도착한 dynamic obstacle과 충돌 할 수 있음)
-> Safe interval 의 lower and upper bound는 time offset을 이용해 좀 더 좁혀져야 함
-> Time offset : the minimum amount of time the center of some agent $a_1$ needs to depart from cell $l$ before the center of some unkown agent $a_2$ arrives at $l$ (coming from some cell $l'$ )
*Time offset 계산 위해 아래와 같은 크게 2가지 상황을 고려
2.3 Admissible H-Values
A*를 위한 admissible heuristic
-> minimum heuristic (Stern et al) 사용, $h(cfg, cfg')$ : 2개의 configuration들 사이의 time-minimal path의 계산된 시간
