消解基于冲突搜索的多智能体路径规划算法中的对顶冲突

发布时间：2022-12-22 21:42

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

【文章页数】：66 页

【学位级别】：硕士

【文章目录】：
摘要
abstract
第1章 绪论
    1.1 研究背景
    1.2 相关知识介绍
        1.2.1 多智能体路径规划问题
        1.2.2 基于冲突搜索框架
        1.2.3 单机器人路径规划算法
    1.3 本文相关技术研究现状
    1.4 本文的结构与研究内容
第2章 基于冲突搜索的多智能体路径规划算法及其变种
    2.1 基于冲突搜索
    2.2 增强的基于冲突搜索
    2.3 本章小节
第3章 对顶冲突的定义和识别方法
    3.1 多值决策图
    3.2 基于冲突搜索的分析与不足
    3.3 冲突对顶的定义
    3.4 一个提升冲突对顶判定效率的技巧
    3.5 对顶冲突的定义
        3.5.1 对顶冲突(Head-on Conflict)
        3.5.2 半对顶冲突(Semi-head-on Conflict)
        3.5.3 非对顶冲突(Non-head-on Conflict)
    3.6 冲突分类算法的实现
    3.7 本章小结
第4章 对顶分析技术
    4.1 边对顶冲突的消解
        4.1.1 半对顶边冲突的消解
        4.1.2 对顶边冲突的消解
    4.2 点对顶冲突的消解
        4.2.1 半对顶点冲突的消解
        4.2.2 对顶点冲突的消解
        4.2.3 对顶冲突消解的案例和消解方法的原因
        4.2.4 对顶冲突的性质
    4.3 对顶分析技术算法的设计与实现
    4.4 本章小结
第5章 实验结果与分析
    5.1 标准地图
        5.1.1 标准地图上的成功率和运行时间结果
        5.1.2 标准地图成功率和运行时间结果
    5.2 随机生成小地图
        5.2.1 随机生成小地图上的成功率和运行时间结果
        5.2.2 对顶分析技术优化失效
    5.3 模拟自动仓储系统地图
    5.4 本章小结
第6章 总结与展望
    6.1 本文的工作总结
    6.2 本文的工作展望
参考文献
作者简介及在学期间取得的科研成果
致谢


【参考文献】：
期刊论文
[1]多机器人最优路径规划研究[J]. 舒翔翔.  信息与电脑(理论版). 2017(15)



本文编号：3724095