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

—／ 计算 机工 程与 科学 第 卷 第 期 年 月
— ．．．．．
文章 编 号 ：—一—
改进 生成 树 算 法 的 多机 器 人 在 线 地 图覆 盖
陈 泽 涛 ，戴 学 丰
齐齐哈尔大学计算机与控制工程学院 ，黑龙 江 齐齐 哈尔
摘 要 ：研 究在 线 多机 器人 地 图覆盖 。在 单机 器人 生成 树 算 法基 础 上做 出改进 ，融入 了市场拍
卖算 法 ，使 机 器人 团体扩散 地 生成树 ，并沿各 自生成树 完 成地 图覆 盖 。通 过 两种 不 同环 境 地 图覆 盖仿 真 ，
结果验 证 改进后 的 算法 ，能 够使 机 器人 团队 在更 少的 时 间和重 复覆盖 区域情 况 下 完成在 线 覆 盖
地 图任 务 。
关键词 ：生成树 ；多机 器人 ；覆盖 ；市场拍 卖
中图分 类号 ： 文 献标 志码 ：
：．／．．．．．

。
—，—
，，，
： —．
，
． —

—
．
：； —；；
法 ，实现单 机 器 人 和 多 个 简 单 机 器 人 对 地 图 的 覆
引 言 盖 。但 是 ，算 法 在 每个 设 定 栅 格 区域 都
会产 生重 复覆