论文《Suboptimal Variants of the Conflict-Based Search Algorithm for the Multi-Agent Pathfinding Problem》
文章作者relax了上层或下层的搜索，分别提出了:
- Greedy-CBS ：快速找到解，越快越好（不保证质量）
- Bounded-CBS：focal-list in 上下层
- Enhanced-CBS：有界的次优
1.Bounded Suboptimal Solvers
通过参数来衡量次有的界限（在求解时间和质量之间权衡）：
求得次优解的cost :
理论最优解:
2.Greedy-CBS (GCBS): Suboptimal CBS：
为了保证最优性，CBS的上层和下层都是一个best-first search。
GCBS允许一个更flexible search in 上层和下层，使得搜索时扩展的节点能够快速的得到解（那就是放大Heuristic吗？）。
2.1 Relaxing 上层
核心思想：对CT节点排序，使得它们更接近目标节点。
我们提出了一些conflict heuristics(hc)，使得less conflict的CT nodes能够更可能到达终点node。
我们尝试了下边几种启发值：
- h1:冲突个数
- h2:至少有一个冲突的agent的个数
- h3:至少有一个冲突的agent对数
- h4:Vertex cover 定义了一个graph，agents是nodes，如果agents之间存在conflict，则存在一个edge。实际上，h2识别出nodes，h3识别出graph的edge.
- h5:Alternating heuristic 当存在多种heuristics时，在一个“round robin fashion”，交替使用不同的heuristics可以得到更好的效果。这个方法就是著名的“Alternating Search”，需要几个heuristic函数并且维护一个unique open list for each,使得很难写代码。
经过实验：
- h5的performance最好；
- h4的解质量最高，但是需要更大的计算量；
- h2在某些问题中计算很快，但是在某些问题又计算很慢（这个在我尝试时，也出现过这个现象）
- h1计算的比h3稍微快一些，但是h3在不同的例子中，鲁棒性更高。
我们选择h3作为hc，因为h3在是权衡简单性和性能最好的。
注意，这些启发值都不是admissible的，所以它们的解自然不是最优，也不是bounded solution。
2.2 Relaxing 下层
relax CBS的另一个方法就是下层采用一个次优化求解器，比如weighted A*和greedy-BFS。
虽然可以快速得到解，但是得到的路径更长，包含了未来的很多冲突，这会导致上层的效率降低。
所以我们在下层，依然采用conflict heuristics。在CBS中，下层搜索返回的是满足当前agent的冲突的最短路径，
这里修改为，返回的是，返回的路径不仅仅是满足当前约束的最短路径，而是跟其他agent冲突最少的更优先。（路径短和冲突少的权衡）
这样，下层返回了一条跟其他agent之间冲突最少的路径。（也就是不管路径最短了吧）
2.3 GCBS的完备性
完备的
2.4 实验
1. GCBS-H which uses h c for choosing CT nodes at the high level but the low level runs ordinary A*.
2. GCBS-L which, similar to the original CBS, uses the g-values for choosing CT nodes at the high level but the low level uses h c for its expansions.
3. GCBS-HL which uses h c for both levels.
在5x5的栅格地图上，非常稠密，冲突非常多，下层无法对单车找到一个无冲突路径，这个时候，上层的性能就至关重要啦，需要将搜索引导至冲突少的地方，
这个时候，CBS效果最差，GCBS-HL效果最好。
在32x32的栅格地图上，地图非常大，即使冲突很多，但是分布在时间和空间中，因此下层搜索压力并不大。这个时候，GCBS-HL就不如CCBS-H了，因为它的下层为了避免冲突，返回了很长的路径，这导致在远处的约束可能导致上层的冲突。反而是GCBS-H性能最好。当然，CBS依然是最差的。
对比cost，感觉这个次优性是可以接受的呀，与最优cost，差别并不大，多数在5%内。
总的来说，GCBS-HL性能好于GCBS-H和GCBS-L，推荐作为一般使用。
3.Bounded Suboptimal CBS
常用的bounded-suboptimal search是Weighted A*。但是CBS上层没有启发值，所以这里不能采用WA*，而是采用Focal search。
3.1 FOCAL search
维护OPEN-list和FOCAL-list。FOCAL-list是OPEN-list的子集。
函数f1，用于从OPEN-list中筛选一些节点放入FOCAL-list中。f1min是f1的最小值 in OPEN-list
给定次优系数w，将OPEN-list中满足下式的节点都添加到FOCAL-list中：
函数f2，用于从FOCAL-list中选出节点来扩展。
3.2 BCBS
上层和下层均采用focal search，focal-search(f1, f2)
上层：
采用focal-search(g, hc)。将CT树中节点cost < w*g的节点都加入到focal-list中，然后在根据hc对focal-list中的节点排序，选出冲突启发值最小的（这里用的是h3??）
下层:
采用focal-search(f, hc)。
分别表示上层和下层的次优系数
分别表示只在上层次优化，和只在下层次优化。
就变成了
，此时FCOAL和OPEN是相同的。
4.Enhanced CBS
4.1
在BCBS中，上层和下层的次优系数是固定的，但是这个可能导致低效率。为了解决这个问题，我们提出了ECBS。
ECBS的下层：
跟BCBS(1, w)的下层相同。
ECBS的上层：
对于上层节点n，定义一个LB(n)：
其中i表示第i个agent,
fmin(i) 表示，第i个agent，其下层OPEN-list中（不是FOCAL-list），最小的值，下层的次优系数w。
每产生一个CT node，下层返回两个值给上层：
1.n.cost
2.LB(n)
n.cost与LB(n)有啥区别？
,
代表上层的openlist。
上层的FOCAL list:
相比于BCBS，ECBS在保持下层相同的情况下，都提供了w的*度，在上层也提供了额外的灵活性。
4.2 实验
对比了5个设置：
（5）CBS作为baseline，相当于BCBS(1, 1)
对比结果：
1.ECBS由于其他
2.对于BCBS之间， BCBS(w, 1)在5x5和32x32栅格地图上，表现的最好；而BCBS(1, w)在DAO地图上表现的最好。
还是那个结论，在稠密和小的地图中，适合给上层设置w。
3.GCBS经常返回比较低的cost，虽然在理论上GCBS是unbounded。 GCBS通常返回接近最优解的cost，但是方差比bounded solver大；
5.如何选择求解器：
对于设计者，如果主要目的是时间，而偶尔的高cost可以接受，那么GCBS作为选择，因为它通常比ECBS快。
如果stability，reliability，bounded是重要的，那ECBS更合适。