论文部分内容阅读
任务分配是确保机器人高效地完成复杂和危险任务的前提。其中,规划单个或多个机器人的路径并使其在最短旅行时间/距离内遍历多个目标位置,是机器人任务分配中最重要的问题之一,可以广泛应用于物流运输、环境监测、灾难营救和军事打击等领域,具有重要的理论研究意义和工程应用价值。目前,机器人多点访问任务分配的研究主要存在以下几个问题。首先,当前研究大多假设无外界环境干扰,且机器人以直线运动于两个位置点之间。但在流场/风环境下,机器人以直线运动于两个位置点之间的路线一般不是能量或时间最优路径。另外,在强流场环境下,机器人可能无法从其初始位置直线运动到目标位置。其次,当前研究主要关注所有需要被访问的目标位置初始已知的静态任务分配问题。然而,新的需要被访问的目标位置可能随时间动态出现。此外,当前研究假设机器人能以任意顺序访问各个目标位置。然而,在物流运输或灾难营救中,一些目标位置因其紧急性或重要性可能要求先于其它目标位置被机器人服务。针对现有研究中存在的以上问题,本论文对复杂环境下的机器人任务分配问题进行研究。主要工作和创新点如下:(1)时序约束下的单机器人任务分配研究研究了时序约束下的单机器人任务分配问题:单个机器人需要在一定的先后时序约束下访问多个目标位置,任务分配的目的是使机器人访问所有目标位置的同时最小化其总旅行距离。首先,通过分析所研究优化问题的计算复杂度得知该问题是NP-hard问题。其次,针对如何验证一个任务分配算法表现性能的问题,利用图论方法给出了机器人最短总旅行时间的一个下界。最后,提出了一个拓扑排序机制和多个启发式任务分配算法以使机器人在访问所有目标位置的同时满足各个时序约束条件。仿真实验表明所提出的启发式算法相对于遗传算法而言,可以在较短的计算时间内获得较优的任务分配方案。(2)动态环境下的多机器人任务分配研究研究了动态环境下的多机器人任务分配问题。其中,多个机器人需要访问环境中多个初始已知和随时间动态出现的目标位置。任务规划的目的是最小化机器人遍历所有目标位置的总旅行时间。首先,为了确定何时对任务进行重分配,本论文提出了基于事件驱动和时间驱动的任务分配机制。其次,针对每种任务分配机制,设计了多种任务分配算法最小化机器人的总旅行时间。蒙特卡洛数值实验表明提出的规划算法是有效的,并且事件驱动机制下的任务分配算法比时间驱动机制下的任务分配算法有更好的性能。(3)流场环境下的多机器人任务分配研究论文研究了流场环境下多个机器人需要投递传感器到多个目标位置的任务分配问题。首先,针对流场环境下的机器人路径规划问题,设计了基于最优控制理论的路径规划算法。该路径规划算法可以使机器人以最短时间运动在时变流场环境中的两个位置点之间。其次,为了将目标位置分配给机器人,提出了跨种群交叉机制、多后代策略、虚拟编码技术和禁忌搜索策略,来构建一个多种群协同进化遗传算法。最后,通过整合提出的路径规划算法和多种群遗传算法,实现了对流场环境下多机器人任务分配问题的求解。仿真结果表明提出的算法在求解时不变和时变流场环境下的多机器人分配任务时,性能优于广泛采用的贪婪算法。(4)部分目标位置不可达情况下的多机器人任务分配研究在强流场/风环境下部分目标位置不可达情况下,研究了如何对多机器人进行任务分配以使最大数量的目标位置被最少数量的机器人访问,且最小化机器人的总旅行时间。首先,针对如何使得最大数量的目标位置被最少数量的机器人访问这一优化问题,提出了一个目标位置融合策略,并分析了最优求解该优化问题的计算复杂度:在可以调用多个机器人访问目标位置时,该优化问题是NP-hard问题。其次,设计了一个次优的任务分配算法,并给出该算法能最优求解上述优化问题的条件。最后,针对最小化机器人的总旅行时间问题,本论文提出的目标点插入策略可以使机器人在有限的总旅行时间内遍历所有选定访问的目标位置。当旅行代价矩阵对称时,该总旅行时间在最优总时间的二倍以内。数值实验表明所提出的算法可以得到接近最优的任务分配方案。