随便写写记录一下
1. 2005-Cooperative Pathfinding
1.1. LRA*
local repair A*
- 依次做A*
- 即将开始碰撞时，replan
- a general replan solution: 每次重规划时，新增noise，按照比例加入\(h(n)\)，使他远离bottle neck
1.2. CA*
Cooperative A*
- 任务被分解成为一系列单个的A*算法
- 包含wait action
- 锁格子，\(f(t,x,y)\)做hash table
1.3. HCA*
Hierarchical Cooperative A*
- 基于CA*，改进启发式函数
- Hierarchical A*：将复杂路径稀疏为区域，之后再详细确定某一个区域内的具体路径。并不局限于空间层次。
- Abstract distances can thus be viewed as perfect estimates of the distance to the destination, ignoring any potential interactions with other agents.
- use a Reverse Resumable A* (RRA*) search in the abstract domain.
- RRA* 算法以反向执行修改后的 A* 搜索。搜索从代理的目标 G 开始，向代理的初始位置 O 进发。搜索不是在 O 处终止，而是一直持续到指定节点 N 展开。
1.4. WHCA*
Windowed Hierarchical Cooperative A*
-
三个问题：
- 代理停止
- 排序敏感
- 无需完整搜索过程
-
A simple solution to all of these issues is to window the search
-
At regular intervals (e.g. when an agent is half-way through its partial route) the window is shifted forwards and a new partial route is computed.
-
正确性保证？only the cooperative search depth is limited to a fixed depth, while the abstract search is executed to full depth.
-
一旦w步过后，agent将会被忽略，此时对于每个节点而言，其cost和abstract dist相等，即可以不用后续搜索。因此窗口可以被限制在w步内
-
如何解决问题1？一旦代理到达其目的地，窗口化搜索可以继续进行。agent的目标不再是到达目的地，but to complete the window via a terminal edge。因此，任何w步的序列都将达到目标，WHCA*搜索将有效地找到最低成本的序列。这个最优序列代表了将agent带到其目的地最近的局部路线，一旦到达那里就会尽可能长时间地停留在目的地。
-
能够减少重规划次数，By staggering the windows appropriately
-
the RRA* search results can be reused for each consecutive window. This requires each agent to store its own Open and Closed lists
-
注意RRA*细节：For consistency, it must continue to search towards the agent’s original position O, and not the agent’s current position.
-
超参数的选取：In general, the window size should be set to the duration of the longest predicted bottleneck.