多机器人全覆盖问题的任务分配算法研究

发布时间：2023-03-11 01:48

　　机器人全覆盖问题是指利用移动机器人,在其物理接触范围或者在其传感器感知范围内遍历目标环境区域,并尽可能地满足任务完成时间短、重复路径少或未遍历区域小等优化目标。机器人的全覆盖应用出现在军事、农业、工业、商业、灾难救援、城市生活等各个方面,例如自动排雷、作物收割、空中交通巡查等。一般而言,全覆盖行动(mission)的各个任务(task)具有较为明显的空间并行性,能够并行地被处理。因此,随着全覆盖行动的规模越来越大,以及多机器人技术的发展等因素,多机器人系统被引入到了全覆盖行动中,期望能够加速行动的完成时间,从而取得更好的效益。多机器人系统处理全覆盖行动的过程中,需要经过若干个阶段,包括任务分解、任务指派(assignment)、任务调度等。任务分解阶段关注将整个行动分解成哪些任务或者将整个行动空间分解为哪些区域(region),任务指派阶段关注将每个任务指派给哪一台机器人,而任务调度阶段关注每台机器人的任务执行顺序以避免路径冲突(如冲撞等)。这三个阶段在本研究中统称为任务分配(allocation),任务分配是多机器人获得高效性能的核心。一个好的任务分配方案应该应对加速比、资源冲突性(...

【文章页数】：137 页

【学位级别】：博士

【文章目录】：
摘要
Abstract
第一章 绪论
    1.1 研究背景和意义
        1.1.1 全覆盖问题
        1.1.2 多机器人全覆盖问题
        1.1.3 多机器人任务分配
    1.2 本文主要工作
        1.2.1 本文主要研究内容
        1.2.2 主要结果与贡献
    1.3 本文组织架构
第二章 预备知识
    2.1 机器人全覆盖问题的概况
    2.2 数学规划
    2.3 遗传算法
    2.4 多目标优化
    2.5 强化学习
    2.6 小结
第三章 机器人数目恒定的全覆盖任务分配算法
    3.1 问题描述与建模
    3.2 相关工作
    3.3 精确算法
        3.3.1 思路原理
        3.3.2 顶点标记
        3.3.3 流量模型
    3.4 近似算法
        3.4.1 思路原理
        3.4.2 算法
    3.5 实验对比与讨论
        3.5.1 milpflow的结果
        3.5.2 STED的结果
        3.5.3 集成应用
    3.6 小结
第四章 带时限的最优机器人数目任务分配算法
    4.1 问题描述和相关工作
    4.2 多目标的方法
        4.2.1 时间限制版本CCP的形式化
        4.2.2 机器人数目的界
        4.2.3 多目标的转化式
    4.3 Mofint算法
        4.3.1 编码
        4.3.2 两个优化目标
        4.3.3 初始化
        4.3.4 交叉算子
        4.3.5 变异算子
        4.3.6 协同进化适应度值
        4.3.7 算法伪代码
    4.4 数值结果
        4.4.1 小示例结果
        4.4.2 数据集
        4.4.3 实验对比与讨论
    4.5 Mucard的进一步研究与扩展应用
        4.5.1 扩展应用到多机器人拓扑覆盖评估问题
        4.5.2 扩展应用到3-目标优化问题
    4.6 小结
第五章 非确定性环境下基于强化学习的均衡任务分配算法
    5.1 问题
    5.2 相关工作
    5.3 问题的数学建模与算法实现
    5.4 实验与讨论
        5.4.1 算法
        5.4.2 参数的设置
        5.4.3 确定性环境结果与讨论
        5.4.4 非确定性环境结果与讨论
    5.5 小结
第六章 总结和展望
    6.1 总结
    6.2 下一步研究展望
致谢
参考文献
作者在学期间取得的学术成果



本文编号：3758960