一种基于解空间裁剪的改进方法

本发明提供一种基于解空间裁剪的改进的方法(Clip Solution Space with CBS,CBS‑CSP)，属于多智能体路径规划领域；该方法包括四个主要步骤：首先，CBS‑CSP需要对解空间重新进行初始化，得出不同节点n.paths(从起始节点到目标节点通过节点n的路径个数)的值；其次，通过输入为MDDi和MDDj(表示智能体ai和aj的MDD)；然后从MDDj中获取启发值，在MDDi中来搜索出一条对MDDj所构成的解空间影响最小的路径；然后，根据完成搜索的情况判断两智能体冲突所对应的种类；最后，为智能体aj添加约束；CBS‑CSP可以通过约束集合快速地为智能体aj找到一条和智能体ai已得到的解无冲突的路径；该方法能够有效地推理出对称性冲突，在对称性冲突频发的场景中能够显著的节省算法的计算资源，并缩短得到最优无冲突路径集合的时间。