多智能体路径规划问题是为多个智能体在地图上寻找它们从各自不同的起始位置到目标位置的无冲突路径集合的问题，属于NP-hard问题。该问题作为人工智能领域的重要问题之一，在物流仓储、交通控制、机器人等领域中也有非常多的应用。在研究该问题的历程中，产生了次维扩展、代价增长树路径搜索和基于冲突的路径搜索等求解方法。次维扩展作为其中表现最好的方法之一，是一种具备完整性和最优性的多智能体路径规划问题求解框架。基于次维扩展而发展出的M*算法及其衍生算法极大地提高了对该问题的求解能力。次维扩展在求解问题的过程中通过维护冲突集合来更新求解空间。这种方法降低了问题的整体空间维度并且缩小了智能体行动的分支因子，但是它没有充分利用智能体最优路径可能具备的非唯一性，其冲突集合的更新方式可能会带来大量的冗余计算。
　　本文通过在次维扩展中引入旁路思想，发展出旁路次维扩展这一新的多智能体路径规划问题求解框架。旁路次维扩展的核心思路是，在路径规划的过程中，当没有发生智能体之间冲突的时候，每个智能体按照各自预计算出的独立最优策略行动，而当遭遇冲突时，首先尝试通过旁路方法来避免冲突，只有在旁路避免冲突失败时才更新冲突集合来提高相关搜索子空间的维度。旁路次维扩展在继承了次维扩展方法的完整性和最优性的基础上，通过改进冲突集合的更新方式，减少了冗余计算。
　　在提出旁路次维扩展框架的基础上，本文还实现了一种基于该框架的多智能体路径规划算法BPM*。在完成BPM*的算法设计之后，证明了该算法具备完整性和最优性，并且在理论上分析了算法的性能。借鉴已有的对M*算法的一些优化方法，本文提出了相关的衍生算法rBPM*、ODrBPM*和EPErBPM*，其中rBPM*是以BPM*为基础的递归算法，ODrBPM*和EPErBPM*则是在rBPM*的基础上对节点扩展方式的优化。在将上述算法和M*及其衍生算法进行实验对比后，结果表明，无论是在求解问题的成功率上还是在求解问题的速度上，采用旁路次维扩展方法来求解多智能体路径规划问题比单纯地采用次维扩展方法的效果要好。