路径规划问题一直是智能体研究领域中的热门问题。随着社会的发展人们的需求已经不局限于使用单一机器人完成任务。越来越多的场景中需要多个机器人共同合作来实现同一目标,例如机场自动飞机牵引车、自动化仓库系统、办公机器人和游戏中的角色等等。因为机器人之间不能够发生碰撞,所以这些问题并不能通过简单的为每个机器人规划路径来解决。多机器人路径规划旨在解决这一问题,让成队的机器人能高效安全的移动到指定位置,从而提升整体完成任务的效率。基于冲突搜索方法是多智能体路径规划的热门方法之一,它构建一棵二叉搜索树查找解。在根节点为所有智能体单独规划路径,之后通过添加限制的方式消解冲突,每个节点规划路径时只考虑自己被添加的限制并忽略其他智能体。但是通过实验可以发现在某些情况下消解掉第一个冲突后有一个可预见的冲突发生在该节点的子树中。换句话说现有的消解冲突的方式并不能彻底消解这一类冲突,针对这一现象,我对基于冲突搜索的多智能体路径规划算法进行优化。针对上述问题,本文做了如下工作:(一)分析基于冲突搜索的多智能体路径规划方法的不足,证明在某些条件下消解冲突会引发另一个可预见的冲突。在此基础上定义了冲突的对顶属性。(二)定义了对顶冲突和半对顶冲突,重新排列了冲突消解的优先级,并讨论对顶冲突的性质。(三)针对对顶冲突和半对顶冲突提出对应的消解方法,并证明各种消解方法的完备性。进而提出对顶分析技术,并证明其最优性。(四)通过实验验证对顶分析技术在标准地图、随机地图、仿真地图中的效果。将该技术与一类似的分析技术——矩形分析技术进行对比,实验结果表明使用对顶分析技术在运行时间和成功率上都有提升,且其优化效果略优于矩形分析技术。