北京理工大学高冠强等：A-STC：一种基于拍卖的多机器人协同螺旋生成树覆盖运动规划方法
摘要
多机器人覆盖运动规划问题是多机器人领域常见问题，要求任务区域内每个点都被机器人传感器或者执行器覆盖一次。提出一种新的有效离线运动规划方法，即基于拍卖的螺旋生成树覆盖（A-STC）算法，解决多机器人覆盖运动规划问题。首先，将布局空间分解为机器人最小覆盖半径两倍的大栅格。基于大栅格之间的连通关系，生成一个无向连接图。机器人可利用巡航无向图中的生成树得到覆盖的运动轨迹。其次，A-STC算法采用拍卖机制构造每个机器人的生成树。在该拍卖机制下，每个机器人都可成为拍卖机器人和竞价机器人。拍卖机器人通过启发式规则从自身生成树的邻居节点中选择一个节点作为拍卖物品。竞价机器人根据拍卖节点的连通关系和运动轨迹的估计长度确定竞标价格。运动轨迹的估计长度主要取决于生成树中的节点和边的类型。最高出价的竞价机器人被选为中标机器人。拍卖过程后，可接受的覆盖运动轨迹可被快速规划生成。计算实验证明了A-STC算法和运动轨迹估计方法的有效性。将提出的算法与前沿算法进行比较，结果显示，所提运动规划方法运行时间和计算结果在大规模算例上具有明显优势。
关键词
覆盖运动规划；多机器人系统；拍卖算法；螺旋生成树覆盖算法
作者
高冠强，辛斌 单位 北京理工大学自动化学院，中国北京市，100081；复杂系统智能控制与决策国家重点实验室，中国北京市，100081；北京智能机器人与系统高精尖创新中心，中国北京市，100081. 引用格式 Guan-qiang Gao, Bin Xin, 2019. A-STC: auction-based spanning tree coverage algorithm for motion planning of cooperative robots. Frontiers of Information Technology & Electronic Engineering, 20(1): 18-31. https://doi.org/10.1631/FITEE.1800551 |
为方便广大科研人员交流讨论，本平台建有以下学科微信群。有需要加群的用户，请加小编个人微信号fitee_xb，并留言想要加入的群，小编会拉您进群。营销广告人员请勿扰。
计算机科学与技术学术群 | 光学工程与技术学术群 |
控制科学与技术学术群 | 信息与通信学术群 |
电力电子学术群 | 人工智能学术 |
本公众号为中国工程院院刊《信息与电子工程前沿（英文）》（SCI-E、EI检索期刊）官方微信，功能包括：传播期刊的学术文章；为刊物关联学人（读者、作者、评审人、编委，等）提供便捷服务；发布学术写作、评审、编辑、出版等相关资讯；介绍信息与电子工程领域学术人物、学术思想、学术成果，展示该领域科学研究前沿进展；为该领域海内外学者提供友好互动平台。