“互联网+”和“工业4.0”的提出带动了传统制造业往智能制造方面发展。各个物流企业纷纷引入自动引导车(Automated Guided Vehicle,AGV)来替代传统的“传送带+人工”,实现全自动智能分拣。用AGV来进行包裹的分拣,引发了多AGV路径规划问题,需要给场地中的所有AGV规划互不冲突的路径,并且尽可能地使分拣效率得到提升。这也就是本文所要研究的问题,针对该问题,本文主要完成了以下几方面的工作:依据应用特点,本文选用了已有的多Agent路径规划模型作为问题模型,并以最小化路径代价和为优化目标。在该模型下,本文提出了两种基于CBS算法改进的并行算法:PCBS与它的增强型EPCBS。并行算法理论上可以用任意多的线程来对问题进行求解,因此可以更好地利用实际环境提供的计算性能。通过登记正在扩展结点的代价值使得并行算法可以有条件选取待扩展结点,最终求得问题的近似最优解;利用随机化的冲突选择策略,让结点之间找到解的概率尽可能相互独立,使得并行算法带来实质上的效率提升。考虑到物流分拣场景的动态特性,本文提出了动态多Agent路径规划问题模型,在其中加入了对环境中执行任务的Agent数量变化的考虑。针对该问题,本文基于CBS设计了一种增量搜索算法LPCBS来求,并证明了其最优性。增量搜索通过复用CBS前一次搜索过程中产生的约束树实现了给“新到达”Agent规划路径的同时快速调整“在途中”Agent的路径。同时在LPCBS中我们给出了CBS中约束树的一种新的实现,该实现有效节省了搜索过程中所需要的内存。最后,本文在不同大小、不同Agent数量的场景下,将本文中设计的并行算法与改进前的串行算法在不同方面进行了对比。发现并行算法在应对Agent数量的增长上,搜索时间增长的幅度比串行算法更小,而且并行算法利用多个线程来搜索获得的效率提升明显。为了验证本文设计的增量搜索算法LPCBS,本文模拟了一个物流分拣的场景。通过模拟多个Agent在环境中进行任务分拣,实验结果从多方面解释了LPCBS在求解动态问题上比CBS效率要高,并且所求解的质量相对于典型的分布式求解器HCA*有着明显优势。