基于组合拍卖的多移动机器人任务分配研究

作     者：姜来浩 

作者单位：齐齐哈尔大学 

学位级别：硕士

导师姓名：戴学丰

授予年度：2015年

学科分类：080202[工学-机械电子工程] 08[工学] 0804[工学-仪器科学与技术] 0802[工学-机械工程] 

主      题：多机器人 任务组合 任务分配 改进K-means 拍卖算法 

摘      要：多移动机器人目标任务搜索是多机器人系统研究中重要方向之一,环境地图大致可分为已知、未知或部分未知三种情况,其中任务的分配问题是整个搜索过程中的难点问题。若以路程作为多移动机器人系统消耗来评价任务分配的性能指标,多移动机器人搜索多个任务目标可以归结为MTSP(Multiple Traveling Salesmen Problem)问题。不同的任务分配对整个系统产生的消耗往往不同。本文充分考虑任务之间的相关性和替代性,采用任务组合方式对其进行预处理,然后再把生成的组合任务簇拍卖给相应机器人。采用任务组合拍卖的方法可以产生较小的系统消耗,多移动机器人系统更具有鲁棒性。本文采用的组合方法是基于改进的K-means聚类算法,因为K-means聚类是一种在线的基于划分的聚类算法。本文针对于多机器人任务搜索问题提出了算法:第一种算法是带有即时拍卖的K-means聚类捆绑式拍卖算法(KCA-I),该算法重新定义了任务的属性向量,根据各机器人完成本簇内任务的情况判断是否产生即时拍卖。仿真证明相较于KCA可以有效减少闲置消耗和系统总消耗。第二种算法是改进K-means聚类的组合算法,引入了公共子簇的思想,公共子簇内的任务可以被任何一个移动机器人搜索,该思想可以解决k值选取问题,同时仿真证明可以在一定程度上降低系统闲置消耗和总消耗。第三种算法主要针对复杂办公环境下的多机器人的搜索问题,改进了最大距离法选取初始簇中心的K-means任务聚类算法,选用的彼此最大距离的任务点作为初始聚类中心可以有效地产生合理的任务子簇,改进的任务组合算法产生的任务子簇分别拍卖给相应的机器人。基于栅格法的路径规划算法上引入门栅格概念。仿真证明移动机器人在搜索过程中不会发生任务死锁,系统总消耗低于基于KCA产生的消耗,并且充分分析了移动机器人在不同坐标下产生的系统消耗。