改进生成树算法的多机器人在线地图覆盖

J4 ›› 2016, Vol. 38 ›› Issue (01): 95-101.

改进生成树算法的多机器人在线地图覆盖

陈泽涛，戴学丰

（齐齐哈尔大学计算机与控制工程学院，黑龙江齐齐哈尔 161006）

收稿日期:2014-11-03 修回日期:2015-05-20 出版日期:2016-01-25 发布日期:2016-01-25
基金资助:
黑龙江省自然科学基金（F201331）

An improved spanning tree covering algorithm
for multirobot online map coverage

CHEN Zetao,DAI Xuefeng

(College of Computer and Control Engineering,Qiqihar University,Qiqihar 161006,China)

Received:2014-11-03 Revised:2015-05-20 Online:2016-01-25 Published:2016-01-25

摘要/Abstract

摘要：

研究在线多机器人地图覆盖。在单机器人生成树STC算法基础上做出改进，融入了市场拍卖算法，使机器人团体扩散地生成树，并沿各自生成树完成地图覆盖。通过两种不同环境地图覆盖仿真，结果验证改进后的IMPSTC算法，能够使机器人团队在更少的时间和重复覆盖区域情况下完成在线覆盖地图任务。

关键词: 生成树, 多机器人, 覆盖, 市场拍卖

Abstract:

We discusses multirobot online map coverage. We introduce the market auction algorithm to improve the spanning tree covering algorithm of a single robot, make robot team diffuse a spanning tree and cover the map completely along their own spanning trees. Two simulation experiments are conducted and the results of two different environment map coverage show that the improved spanning tree covering algorithm can make the robot team accomplish online map coverage with less time and less repeated coverage.

Key words: spanning tree;multirobot;coverage;market auction

陈泽涛，戴学丰. 改进生成树算法的多机器人在线地图覆盖[J]. J4, 2016, 38(01): 95-101.

CHEN Zetao,DAI Xuefeng. An improved spanning tree covering algorithm
for multirobot online map coverage [J]. J4, 2016, 38(01): 95-101.

[1]	罗莉, 石伟, 何鸿君, 潘国腾, 王蕾, 龚锐. 一种面向IO Die的敏捷验证方法[J]. 计算机工程与科学, 2023, 45(04): 571-576.
[2]	白耀文, 杜亚江, 李宗刚, . 基于多步长的多机器人分布式巡逻算法研究[J]. 计算机工程与科学, 2023, 45(02): 313-320.
[3]	李辉, 巨鹏锦, 计永兴. 多路系统Cache一致性验证中的错误追踪定位技术[J]. 计算机工程与科学, 2022, 44(07): 1171-1180.
[4]	张孟健, 汪敏, 王霄, 覃涛, 杨靖, . 混合粒子群-蝴蝶算法的WSN节点部署研究[J]. 计算机工程与科学, 2022, 44(06): 1013-1022.
[5]	骆公志, 陈佳馨. 多源覆盖信息系统下的加权广义多粒度粗糙集模型及其应用[J]. 计算机工程与科学, 2021, 43(12): 2231-2237.
[6]	张晶, 魏淼, . 基于Delaunay三角划分策略的WSN区域覆盖优化研究[J]. 计算机工程与科学, 2021, 43(11): 1944-1951.
[7]	胡海霞, 贾向东, 叶佩文, 纪澎善, 敬乐天. 混合频谱分配的三层异构网络覆盖概率分析[J]. 计算机工程与科学, 2021, 43(07): 1226-1235.
[8]	王慧丽, 郭阳. 一种基于参考模型的GPDSP指令流控自动验证方法[J]. 计算机工程与科学, 2021, 43(04): 652-661.
[9]	刘向婷, 曹小鹏. 基于改进鲸鱼优化的覆盖表生成算法[J]. 计算机工程与科学, 2020, 42(08): 1374-1382.
[10]	欧永东，谢小鹏. 基于改进Census变换的多特性立体匹配算法[J]. 计算机工程与科学, 2020, 42(06): 1030-1036.
[11]	李楷，陈永府,金志勇，刘田，王振庭，郑迥之. 基于回溯法的全覆盖路径规划算法[J]. 计算机工程与科学, 2019, 41(07): 1227-1235.
[12]	张晓冰1,2，杨启亮1，薛广通1. 语音驱动自适应协同系统的决策方法[J]. 计算机工程与科学, 2019, 41(05): 948-954.
[13]	黄洪涛1，武继刚1，郑露露1，缪裕青2. 面向无线内容分发网络的树形拓扑生成算法[J]. 计算机工程与科学, 2018, 40(12): 2133-2140.
[14]	郑露露,武继刚,陈辉. 网络可存活生成树的快速恢复算法[J]. 计算机工程与科学, 2018, 40(11): 1967-1973.
[15]	崔丽珍，李晓宇，胡海东，高丽丽. WSN的极坐标最小能耗覆盖空洞修复算法[J]. 计算机工程与科学, 2018, 40(10): 1766-1771.