基于冲突的搜索算法（CBS）个人笔记
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
CBS
-
实例
-
以下将通过一个简单的实例体现CBS的基本过程
-
讲解
-
上层
-
结点指的是每个”小方格“
-
节点树的节点
-
(ai, aj, s, t)ai与aj在t时刻都在s结点上
-
OPENcbs存放待探测的状态与下层的OPEN意思一样都是将下一步某时刻可能要走的结点存放进来
-
N为结点
-
N.constraints一个约束集包含对问题中所有 Agent 的约束我们要做的就是在某个结点上给定的约束集中帮Agent规划避开在该结点的约束集后的其最佳路线
-
N.solution问题的一个解这个解可能不是有效的但是这个解中所有 的 Agent 的路径都满足该结点 的约束集中的约束看例子在节点1我们发现他们在3结点冲突了于是得到了节点2和节点3这两个节点均得到了3结点的解满足了该结点的约束集但是整条路径下来两个还是会撞上因此不是有效的
-
N.cost该结点解的代价。我们避开该结点的约束集可能有很多解所以我们需要求解的代价然后得到该结点的解中代价最小的那个
-
-
下层
-
A*算法
-
流程
CBS算法流程即初始化上层的时候先计算出所有的Agent的解和其对应的总cost令约束树为空解释第一步我们无视其他Agent得到每个Agent到指定位置的路线其路线cost最优小然后每一轮弹出约束树的cost最小的结点N从OPEN队列中弹出判断N中是否存在一个冲突只需要找到一个即可用ai,aj,s,t表示冲突然后生成两个子结点N1,N2并且都值传递继承节点N的内容存进OPEN接着将冲突ai,aj,s,t分成约束结点(ai,s,t)和(aj,s,t)一个加入到N1约束树中一个加入到N2约束树中解释我们以一个Agent为视角走到s时发生冲突那我退回去上个结点然后此时我继承了s点冲突的信息也就是说也保留了约束集所以这台Agent会重新规划最优路线cost最小以保证自己在t时间内避开s即约束集对于N1而言ai的约束发生了变化因此需要对ai进行重新规划规划时需要在约束树下进行规划最后更新ai的路径和cost值并插入到上层优先队列中OPEN中接着对N2进行同样的操作直到取出的N检测没有冲突时返回结点N即可。
个人理解环节
个人理解环节上层其实和下层一样都是A*都是我为一台Agent走一步计算一步每一步都是最优的然后上层呢就是我在某个结点和其他Agent撞上了就记录下该时间该结点我不能走这个结点于是我就重新规划绕开走这里相当是发配命令给下层让下层通过A*得到这台Agent一条路径然后将这条路径反馈给上层上层将其放入解中分析这个解是否有效然后因为我们是多台Agent那么就产生了分支树也就建出来了我们假设是两台a1a2一条分支a1动a2不动一条分支a2动a1不动但是呢我绕开了这个结点也不能保证在绕开该结点后我这台Agent就不撞上了所以下一步就会继续寻找撞上的结点再次进行避开操作于是又产生了分支以此类推最终找到所有Agent不碰撞的解路径。