室内环境下多机器人协调探索算法研究

摘要

多机器人协调是机器入学研究的热点。多个机器人通过协调与协作，机器人之间的能力可以得到互补，从而提高工作效率，或者完成单个机器人不能完成的任务。移动机器人在一个未知的环境中要完成某些具体的任务，例如未知环境下的觅食、搜索与救援、监督与监控、导航等，首先要对该环境进行探索，需要获得一个全局地图，因此如何协调多机器人系统完成未知环境的探索任务显得尤为重要。本文将分别从全局地图的拼接、探索任务的协调分配和检测障碍物的能力、以及机器人间的避免碰撞几个方面来研究多机器人探索未知环境的问题，具体工作如下:
　　首先，全局地图拼接方法的研究。根据全局地图合并前与合并后分为两部分研究工作。在全局地图合并前，机器人需要先在完成自己的同时定位和地图构建(Simultaneous Localization and Mapping，SLAM)任务时构建局部子地图的匹配。现有的子地图匹配算法计算比较复杂，本文提出了通过构建签名元素向量的方法来完成子地图匹配，在该方法中结合了基于路标进行定位的技术，从而实现可靠的回路闭合确认计算。另外，针对在获得全局地图的后处理过程中存在两个或多个的闭合回路共享部分路径的问题，研究并实现了全局优化算法中限制条件的修改问题。对于全局地图的拼接方法，提出了基于地图集的全局地图的合并算法。包括子地图的划分，拓扑节点处子坐标系的建立，基于签名向量重复探索的避免等，通过仿真实验验证，本文提出的基于地图集的地图拼接算法与目前典型的基于相遇情况下的地图拼接及基于栅格地图的拼接方法相比，具有探索时间短和探索重复率小的性能。
　　其次，基于情感和聚类的拍卖探索任务协调算法研究。为了解决基于拍卖协调算法存在的问题，分别从探索效率、最优目标选择以及对孤岛的探索几个方面，提出了相应的解决方案。应用于多机器人探索任务最广泛的是基于拍卖的协调算法。通过机器人对任务进行投标，获得标的的机器人执行相应的探索任务，但该类协调算法，会产生较多的重复路径，降低机器入团队的探索效率。本文通过在基于拍卖的协调算法中引入机器人的情感状态，可以有效地减少探索路径的重复，从而提高探索效率。另外，为了解决探索过程中出现的非最优目标选择的问题，提出了改进的单回路聚类方法，将边缘格进行聚类;最后，为了解决多机器人探索任务拍卖协调算法中，经常出现的孤岛（即未被探索的小面积区域）问题，提出了情感的切换策略。在该策略中，机器人发现孤岛要优先探索。通过仿真和实验验证，本文提出的算法与经典的拍卖算法相比，有更大的覆盖率，更好的探索效率。
　　再次，基于情感和行走规则的拍卖探索任务协调算法研究。针对多机器人系统在探索过程中对障碍物具有一定的识别能力的问题，提出基于情感和行走规则的拍卖探索任务协调算法。通过对情感模型的研究，提出了基于马尔可夫情感模型的情感产生系统，同时对环境中的静止障碍物和动态障碍物、凸形障碍物和非凸形障碍物给出了具体的避障行走规则。通过仿真实验与经典的拍卖协调算法比较，提出的基于情感和行走规则的拍卖探索任务协调算法的重复探索率较低，探索效率得到了提高，而且有较好的障碍物形态的检测能力。
　　最后，基于效益的多机器人避碰协调策略研究。为了解决多机器人在执行探索任务时，机器人之间的避碰问题，提出了一种基于效益的多机器人避碰协调策略。多移动机器人系统在执行探索任务时，机器人之间常常存在相互碰撞的问题，而这种碰撞的避免又不同于一般的避障，因为避障问题中的障碍物一般是不动的。传统的方法虽然能解决机器人与障碍物之间的碰撞问题，但是不能解决机器人之间的碰撞问题。为此，本文提出的基于效益的多机器人避碰协调策略，以提高多机器人系统探索效率为主，确定机器人通过交叉路口的顺序。同时考虑了动态协调避碰的情况，给出了确定机器人通过交叉路口顺序的算法。通过机器人在交叉路口实现避碰协调算法的仿真示例，对仿真中机器人和目标位置的空间关系给出了合理的假设。通过仿真示例，与无交通灯交叉路口为模型的避碰协调算法相比，能够较好解决多个机器人通过交叉路口的冲突问题。

目录

声明

摘要

第1章绪论

1．1研究背景和意义

1．2多机器人协调探索算法的国内外研究现状

1．2．1全局地图拼接算法的研究现状

1．2．2探索任务分配的协调算法的研究现状

1．2．3避免碰撞的协调算法的研究现状

1．2．4情感算法的研究进展

1．3探索协调算法中存在的若干问题

1．3．1全局地图拼接算法中出现的探索效率低的情况

1．3．2探索任务协调分配算法中存在的问题

1．3．3探索过程中的碰撞问题

1．4论文主要研究内容

1．5本论文的组织结构

第2章全局地图的拼接

2．1引言

2．2机器人的定位

2．3地图的表示方法

2．3．1度量地图

2．3．2拓扑地图

2．3．3混合地图

2．4基于签名向量和路标的子地图匹配算法

2．4．1基于签名向量的子地图匹配

2．4．2匹配算法的改进

2．4．3共享路径的处理

2．4．4算例说明

2．5基于地图集的全局地图拼接算法

2．5．1基于签名向量重复探索的避免

2．5．2拓扑节点在不同坐标系间的转换

2．5．3基于地图集的地图拼接算法示例

2．5．4仿真实验及结果分析

2．6本章小结

第3章基于情感和聚类的拍卖探索协调算法

3．1引言

3．2多机器人探索未知环境任务的性质

3．2．1动态任务和静态任务

3．2．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拍卖算法中影响探索效率的情况

3．5．2基于情感和拍卖的协调算法

3．5．3仿真实验与分析

3．6基于情感和聚类的拍卖探索任务协调算法

3．6．1未探索孤岛的定义

3．6．2两种低效率的探索情况

3．6．3非最优目标的选择

3．6．4改进的单回路聚类计算目标点的探索回报

3．6．5基于情感和聚类的拍卖探索任务协调算法

3．6．6仿真实验及结果分析

3．7实验

3．8本章小结

第4章基于情感和行走规则的拍卖探索任务协调算法

4．1引言

4．2考虑通信受限的多机器人探索任务协调算法

4．2．1目标单元格的选择

4．2．2分布式的拍卖算法

4．2．3仿真验证

4．3基于行走规则的拍卖探索协调算法

4．4基于情感和行走规则的拍卖探索任务协调算法

4．4．1情感模型

4．4．2情感状态的生成

4．4．3机器人具体的执行过程与情感状态的关系

4．4．4仿真实验及结果分析

4．5本章小结

第5章基于效益的多机器人避碰协调策略

5．1引言

5．2拍卖与线性规划相结合的探索任务分配策略

5．2．1基于线性规划的探索任务分配策略

5．2．2示例说明

5．3基于效益的多机器人避碰协调策略

5．4仿真示例及结果分析

5．5本章小结

结论

参考文献

攻读博士学位期间发表的论文和取得的科研成果

致谢