论文部分内容阅读
机器人全覆盖问题是指利用移动机器人,在其物理接触范围或者在其传感器感知范围内遍历目标环境区域,并尽可能地满足任务完成时间短、重复路径少或未遍历区域小等优化目标。机器人的全覆盖应用出现在军事、农业、工业、商业、灾难救援、城市生活等各个方面,例如自动排雷、作物收割、空中交通巡查等。一般而言,全覆盖行动（mission）的各个任务（task）具有较为明显的空间并行性,能够并行地被处理。因此,随着全覆盖行动的规模越来越大,以及多机器人技术的发展等因素,多机器人系统被引入到了全覆盖行动中,期望能够加速行动的完成时间,从而取得更好的效益。多机器人系统处理全覆盖行动的过程中,需要经过若干个阶段,包括任务分解、任务指派（assignment）、任务调度等。任务分解阶段关注将整个行动分解成哪些任务或者将整个行动空间分解为哪些区域（region）,任务指派阶段关注将每个任务指派给哪一台机器人,而任务调度阶段关注每台机器人的任务执行顺序以避免路径冲突（如冲撞等）。这三个阶段在本研究中统称为任务分配（allocation）,任务分配是多机器人获得高效性能的核心。一个好的任务分配方案应该应对加速比、资源冲突性（例如路径冲突）、机器人数目不确定性（例如任务完成时间具有截止时限）或者环境的不确定性（例如环境概率性的转移）这三个挑战。寻找一个时间均衡性最优、冲撞少或者无冲撞、能处理数目或环境不确定性的分配方案,其搜索空间可能达到O（q N）,其中q是机器人的个数、N是任务的个数。一般地,N可达到成百上千,它指的是环境被分解为单机器人全覆盖直径为边长的方格的个数,或者环境被分解为其它原子类型区域的个数,因此最优分配方案的搜索空间十分巨大,大规模问题很难精确地求解,设计可行的、高效的近似最优分配算法是一个途径之一。本研究针对多机器人系统全覆盖任务分配中三种不同的情形（scenes）,每种情形带有了以上三个挑战中的不同组合,设计了三类算法。这些算法所基于的系统是同构的机器人组且带有中心计算通信节点的多机器人系统。本研究的贡献如下:（1）已知环境且已知机器人数目的情形下,两种均衡且无冲撞的多机器人任务分配算法。针对这一情形,本研究提出了适用于中小问题规模的基于混合整数线性规划（MILP）的精确算法milpflow和适用于较大问题规模的基于生成树切割进化的近似算法STED。其中,milpflow是学术界第一个解决均衡连通q-分割的精确（exact）算法,且其在2-分割上,能比现存的MILP多解决100个区域的任务指派(问题空间增大了2100倍);STED,也是学界第一个针对一般图的q-分割的近似算法,它能解决规模至3000个区域的分割问题,是已有算法能解决规模的10倍,并且它能通过进化几千个生成树个体,就能获得非常近似于理想最优值的解。（2）已知环境但未知机器人数目,而完成时间具有截止时限的情形下,一种优化机器人数目并给出具体分配方案的任务分配算法。本研究根据截止时限,预先计算出所需机器人数目的较紧的上下界b和a。不同于枚举机器人数目并优化对应数目的（近似）最优方案的传统算法,本研究提出了一个基于遗传算法的多目标优化算法,它能求得（近似）最少的机器人数目,并能给出机器人数目在范围[a,b]内的所有（近似）最优分配方案。实验结果显示,算法求出来的最小机器人数目是现存算法的0.6倍。该多目标转化方法具有较优秀的普适性,因此也被扩展应用到机器人拓扑覆盖任务分配等其它问题上,实验结果展现了求解的有效性和高效性。（3）非确定性环境情形下,一种基于强化学习的均衡任务分配算法。强化学习通过马尔可夫决策过程（MDP）建模,在全覆盖问题中能处理确定性环境的规划问题和非确定性环境下的学习问题,因此强化学习未来是迈向动态未知环境中全覆盖问题的一条可行途径。本研究将多机器人的均衡任务分配过程(状态空间达到236*36!≈1050)建模成MDP,并使用深度Q网络学习算法（即DQN算法）进行任务分配。实验结果表明,DQN算法在该问题上,通过部分的样本学习（样本数约108）,就能获得比常用的启发式算法更优越的解,并且能够优化未训练过的样本,展示出了良好的解的精度和泛化性能。在非确定性环境中,实验结果显示,该强化学习算法对大多数环境配置的平均步数是常用启发式最优步数的一半左右,并且强化学习算法与已知环境模型时的常用启发式结果相近,展示出了良好的对环境的学习能力。以上三部分工作共同服务于全覆盖任务分配,但关注了不同的情形,因此三部分内容是并列之关系。在每一部分内容中,都包含了一至两个具体研究点,形成了较完整的技术体系,适用于同构多机器人在二维环境中全覆盖问题的任务分配问题。