1. Local Repair A*(LRA*)
각각 agent들은 다른 agent들(현재 이웃한 agent 제외)을 무시하고 A* 를 사용해 destination 까지 route를 찾음
-> 이후 충돌이 발생하기 직전까지 각자의 route를 따라 감
-> 충돌 직전, 나머지 route를 다시 계산함 (이번에는 충돌 예정인 agent가 이웃 해 있으므로 고려함)
2. Cooperative A*(CA*)
Cooperative pathfinding problem를 일련의 single agent search로 decouple 시킴
-> individual search는 이미 plan 된 다른 agent들의 route들을 고려하여 수행됨
*각 route를 따르는 state들은 'reservation table' 에 기록 됨
- Reservation table
Agent들의 shared knowlendge about each other's planned routes
- Implementation
Treat the reservation table as a 3D grid (2 spatial + 1 temporal dimention)
-> Hash table을 통해 쉽게 적용됨, (x, y, t) key
* Heuristic : Manhattan distance
3. Hierachical Cooperative A*(HCA*)
Hierachical A*
A*의 Heuristic 을 개선하기 위해 state space에 abstraction을 수행하는 방법에는 2가지가 있음
- Approach 1 : precompute all distance in the abstract space and store them in a pattern database
- Approach 2 : 'Hierachical A*'
- The abstract distances are computed on demand
- 'Hierachy' : refers th a series of abstractions of the state space, each more general than the previous (not restricted to spatial hierarchy)
Hierachical Cooperative A*(HCA*)
HCA* : A single domain abstraction을 포함하는 a simple hierachy를 사용함
-> ignores both the time dimension and the reservation table
= The abstraction : a simple 2D map with all agents removed
->CA*와 비슷하지만 좀 더 sophisticate한 heuristic을 사용함 (RRA*를 사용해 abstract distance를 필요할 때마다 계산해냄)
Reverse Resumable A*(RRA*)
"To reuse search data in the abstraction domain for Hierachical A*"
A*를 거꾸로 수행함 (Goal G 에서 부터 시작해서 initial position O로 향함)
-> O에서 종료하는 대신, a specified node N 이 expanded 될 때 까지 수행함
--> Search가 반대로 수행되므로, RRA*가 완료되면 N -> G인 optimal distance가 알려짐 (A* with a consistent heuristic의 성질)
*Consistent heuristic
- N : Current node, P : Child node
- $H(N)\leq dist(N,P) + H(P)$
ex) Manhattan distance
4. Windowed Hierachical Cooperative A*(WHCA*)
3 Issues with HCA*
- 만약 한 agent가 목적지에 도착하면, 이 agent가 다른 agent들을 block off 할 수 있음
- Sensitivity of Agent ordering -> 모든 agen가 높은 priority를 짧은 시간 동안 가지면서 dynamic하게 순서를 바꾸는 것이 more robust solution
- HCA*에서는 반드시 전체 route를 큰 3D state space에서 계산해야 함 -> planning and plan execution을 interleave 시키면 더욱 효과적임
WHCA* : window the seach
- Cooperative search가 fixed depth로 제한됨
- 각 agentsms 각자의 destination을 향해 partial route를 계산하고, 해당 route를 따라 움직이는 특정 순간에 window를 앞으로 shift하고 새로운 partial route를 계산함
- agent들이 올바른 방향으로 향하게 하도록 하기 위해, cooperative search depth만을 특정 깊이로 제한하고, abstract search는 전체 depth에서 수행 됨
* Trick : w step이후에는 agent들을 무시함 = abstract search space와 동일해짐
* Agent의 목표는 더이상 destination에 도착하는 것이 아님, 대신에 window를 끝내는 것 -> 어떤 종류의 w move라도 goal에 도달 함
