障碍环境中多机器人路径规划及任务分配

摘要

相比单机器人系统，多机器人系统可以更可靠地、更快速地、更经济地完成指定任务。目前，多机器人系统主要应用在智能安防、搜索与救援、监视巡逻和环境监测等领域。然而，多机器人系统也面临着诸多难题与挑战，其中任务分配就是多机器人研究领域中一个难点问题。本文针对障碍环境中多机器人路径规划及任务分配问题展开了深入的研究。
　　在障碍环境中为了解决多机器人任务分配问题，必须先获取机器人到各个任务点的路径信息，即完成移动机器路径规划。路径规划的目的是找到一条从起点到终点安全的、无碰的可行路径。本文提出了一种改进 A*路径规划算法:首先采用栅格法建立机器人工作空间的二维栅格模型，并使用传统的A*算法得到原始路径；然后，以较小的分割步长分割原始路径得到一系列路径节点；最后从起点开始用直线依次连接终点，如果直线没有穿过障碍物，则剔除中间路径节点，以此减小路径长度和转折角度。实验结果表明，本文提出的改进A*路径规划算法可以获得一条安全无碰的可行路径，并能有效减少路径长度和转折角度，进一步优化原始路径，也为多机器人任务分配提供更优的路径信息。
　　在获得了准确的路径信息后，本文提出了一种改进果蝇优化算法来解决障碍环境中多机器人任务分配问题。为了将连续优化算法应用到离散问题中，本文使用整数环形码完成了解的编码。采用随机单物品拍卖机制启发式地初始化种群位置，产生相对好的初始解，以便更快地搜索到全局最优解。在果蝇优化算法嗅觉搜索阶段，基于问题的背景知识设计了三种操作算子：操作算子一旨在调整机器人任务序列，产生领域解；操作算子二是调整任务的分配，以跳出局部最优陷阱；操作算子三的作用是修复不可行解；这些操作算子将引导算法向更优的解空间趋近。在视觉搜索阶段，采用精英策略来保护当前最优的种群位置。如果产生比初始位置更好的个体，则种群飞向该果蝇个体位置；否则不更新种群位置。采用正交实验法完成了算法的参数整定；对比实验证明了种群位置启发式初始化机制的可行性和有效性；最终，对比实验结果表明本文算法可以有效地解决障碍环境中多机器人任务分配问题。

目录

声明

第1章 绪论

1.1 研究背景及意义

1.2多机器人系统的主要研究内容

1.3路径规划研究现状

1.4多机器人任务分配研究现状

1.5本文的主要研究内容和章节安排

第2章 问题描述及数学建模

2.1机器人路径规划和任务分配分层框架

2.2 路径规划问题描述

2.3 任务分配问题描述

2.4 本章小结

第3章 基于改进A*的路径规划算法

3.1 环境栅格模型建立

3.2 A*路径规划算法

3.3改进A*路径规划算法

3.4实验与讨论

3.5 本章小结

第4章 基于改进果蝇优化的多机器人任务分配算法

4.1果蝇优化算法

4.2 改进的果蝇优化任务分配算法

4.3 实验与讨论

4.4 本章小结

结论与展望

参考文献

致谢

附录A攻读学位期间所发表的学术成果