一种基于改进鸽和分布式拍卖算法的多无人清扫车任务分配方法

阅读：评论：0

1.本发明涉及无人清扫车路径规划、任务分配技术领域，尤其涉及一种基于改进鸽和分布式拍卖算法的多无人清扫车任务分配方法。

背景技术：

2.无人清扫车，是近两年兴起的一项产业，深度融合了传统环卫车与互联网、人工智能等技术，在无需驾驶员的情况下，可自动识别避障，智能路径规划，自主开展喷洒、垃圾清扫等环卫工作。
3.虽然目前无人清扫车技术日益成熟，但仍然面临着依赖中央处理器时效性灵活性较低、分布式方法中因无人清扫车自身算力有限而导致的质量问题与收益损失、成本较高三大难题。

技术实现要素：

4.本发明提供了一种基于改进鸽和分布式拍卖算法的多无人清扫车任务分配方法。本发明的目的在于解决以下三个问题，为后续的多无人清扫车任务分配方法研究提供新的思路：解决传统算法在寻优过程中面对大量的计算易出现寻优速度慢甚至寻优失败的问题；解决多无人清扫车主副服务器之间计算量大，存在稳定性不足的问题；解决单辆无人清扫车价格高昂导致多无人清扫车共同工作下的高成本的问题。
5.为了解决上述问题，本技术提出了一种基于改进鸽和分布式拍卖算法的多无人清扫车任务分配方法，包括如下步骤：步骤s1：从鸽信息交换及分层传递的角度出发，提出了改进鸽。在同等探索次数下将鸽分为个层次并依次执行探索任务。
6.步骤s2：改进地磁算子，下层的鸽能够在彼此共享位置信息的同时，利用上一层鸽子的优质信息更新自身位置，减少了初期探索时的盲目性，提高了效率；同时，对于在特定位置重复盘旋的鸽子，上层鸽子的位置信息能够起到牵引作用，辅助摆脱局部最优的情况。
7.步骤s3：改进地标算子，由于信息的分层传递，最终的最优位置将会偏向下层鸽的搜索结果。信息的传递使得种有较好的多样性，并且随着地磁算子到地标算子阶段的过渡，全局搜索过程转化为局部搜索，鸽由多个小规模种逐步合成为统一的大体，加强了最终的局部搜索能力，能够有效提升种精度。
8.步骤s4：调节鸽搜索速度。
9.步骤s5：优化鸽算法中后期。
10.步骤s6：建立分布式拍卖算法模型，根据收益作出最优的任务分配方案。
11.优选地，从鸽信息交换及分层传递的角度出发，提出了改进鸽算法。在同等探索次数下将鸽分为个层次并依次执行探索任务。具体为：首先生成只鸽子组成的鸽系统，并随机分成个层级。鸽由上层至下层分层探索，用表示第层鸽子的第次探索过程，为对应的探索位置。每层的探索结束后生成该层最优位置单向传递到下层，用于指引下层鸽子的初期演化方向。
12.优选地，在地磁算子阶段，下层的鸽能够在彼此共享位置信息的同时，利用上一层鸽子的优质信息更新自身位置，减少了初期探索时的盲目性，提高了效率；同时，对于在特定位置重复盘旋的鸽子，上层鸽子的位置信息能够起到牵引作用，辅助摆脱局部最优的情况。具体为：基于步骤s1的概念，地磁算子更新如下：情况。具体为：基于步骤s1的概念，地磁算子更新如下：优选地，改进地标算子，由于信息的分层传递，最终的最优位置将会偏向下层鸽的搜索结果。信息的传递使得种有较好的多样性，并且随着地磁算子到地标算子阶段的过渡，全局搜索过程转化为局部搜索，鸽由多个小规模种逐步合成为统一的大体，加强了最终的局部搜索能力，能够有效提升种精度。具体为：进入地标算子阶段后，由于多层鸽的信息复杂度高，且明显存在上层信息劣于下层信息的情况，因此将每一次迭代中适应度低于阈值的鸽子加入集合中，集合中鸽子的信息将不作为鸽移动的有效信息源并受到更多优势体带来的影响，由此，地标算子更新如下：效信息源并受到更多优势体带来的影响，由此，地标算子更新如下：优选地，设定表示第次迭代的第个解，即第只鸽子在pio中的位置;优选地，设定表示第次迭代的第只鸽子的速度，反映了鸽更新的速率；优选地，设定为鸽规模；
优选地，设定表示第次迭代时的全局最优解；优选地，设定为0到1之间的随机系数；优选地，设定为影响地图和指南针因子的一个因素；优选地，设定表示第次迭代后置信度高的鸽位置中心；优选地，设定表示上一级鸽；优选地，调节鸽搜索速度。具体为：利用地图和指南针因子调节鸽搜索速度，影响鸽的搜索范围及收敛情况；优选地，优化鸽算法中后期。具体为：多层次方法希望上层鸽子开展广泛搜索，在较大的范围内对全局进行初步感知，并向下传递有价值信息；算法中后期，下层鸽子能够针对性搜索目标，在最优解附近进行精确的局部搜索，并具有良好快速的收敛性；优选地，建立分布式拍卖算法模型，根据整体收益作出最优的任务分配方案。具体为：建立模型之前预定义一些基本变量，如下：优选地，设定为投标者数量；优选地，设定为任务数量；优选地，设定为投标者集合；优选地，设定为任务集合；优选地，设定为投标者感兴趣任务的集合，如果各投标人对所有商品都有兴趣，则有；优选地，设定为分配情况集合；优选地，设定为投标者对于任务的收益集合；优选地，设定为号无人清扫车完成第个任务集合；优选地，得到分布式拍卖算法的流程描述如下：优选地，得到分布式拍卖算法的流程描述如下：
优选地，产生拍卖者，如果工作中的无人清扫车在完成任务的过程中发现收益更高的任务，则可以利用上述公式计算收益值并向通信范围内无人清扫车发出重分配请求；优选地，当存在无人清扫车，使得互换任务产生更高收益时，通过申请，无人清扫车成为拍卖者；优选地，投递标书。在无人清扫车发布拍卖信息后，收到请求的无人清扫车成为投标者，向投递标书申请进入指派环节；优选地，确认指派方案。无人清扫车收集参与指派的无人清扫车信息，以匈牙利法求解并通知给各无人清扫车，完成任务集所有权的更替；优选地，更替后的收益为通信范围内的整体最优，并非无人清扫车个体最优，因此分配后的无人清扫车易作为招标者对同范围重复招标，影响任务的顺利执行；优选地，设定招标限制，指派流程完成后，参与流程的无人清扫车在招标限制时间内，不得作为招标者组织指派任务，直至限制解除。
13.本发明专利创新性地提出了一种基于改进鸽和分布式拍卖算法的多无人清扫车任务分配方法。针对传统鸽算法在寻优过程中面对大量的计算易出现寻优速度慢甚至寻优失败的问题，改进了鸽算法，压缩了鸽每一层次的搜索时间，并将经验单向传递，使鸽有了一定学习能力。同时根据层数设计收敛速度，实现上层鸽广泛搜索，下层鸽精确导航的分工体系。从而丰富提取的特征信息，达到更好的分配效果。针对多无人清扫车主副服务器之间计算量大，存在稳定性不足的问题以及单辆无人清扫车价格高昂导致多无人清扫车共同工作下的高成本的问题。提出了分布式拍卖算法，提高了无人清扫车的局部分配效率，提升了调节通信负载的灵活性并且从经济层面降低了多无人清扫车编队完成清扫任务的成本。
14.为了使本发明的目的、技术方案和优点更加清楚，下面结合附图对本发明实施方案作进一步详细描述。
15.步骤一：从鸽信息交换及分层传递的角度出发，提出了改进鸽算法。在同等探索次数下将鸽分为个层次并依次执行探索任务。具体为：首先生成只鸽子组成的
鸽系统，并随机分成个层级。鸽由上层至下层分层探索，用表示第层鸽子的第次探索过程，为对应的探索位置。每层的探索结束后生成该层最优位置单向传递到下层，用于指引下层鸽子的初期演化方向。
16.步骤二：改进地磁算子，下层的鸽能够在彼此共享位置信息的同时，利用上一层鸽子的优质信息更新自身位置，减少了初期探索时的盲目性，提高了效率；同时，对于在特定位置重复盘旋的鸽子，上层鸽子的位置信息能够起到牵引作用，辅助摆脱局部最优的情况。基于步骤一的概念，地磁算子更新如下：况。基于步骤一的概念，地磁算子更新如下：步骤三：改进地标算子，由于信息的分层传递，最终的最优位置将会偏向下层鸽的搜索结果。信息的传递使得种有较好的多样性，并且随着地磁算子到地标算子阶段的过渡，全局搜索过程转化为局部搜索，鸽由多个小规模种逐步合成为统一的大体，加强了最终的局部搜索能力，能够有效提升种精度。具体为：进入地标算子阶段后，由于多层鸽的信息复杂度高，且明显存在上层信息劣于下层信息的情况，因此将每一次迭代中适应度低于阈值的鸽子加入集合中，集合中鸽子的信息将不作为鸽移动的有效信息源并受到更多优势体带来的影响，由此，地标算子更新如下：有效信息源并受到更多优势体带来的影响，由此，地标算子更新如下：设定表示第次迭代的第个解，即第只鸽子在pio中的位置;表示第次迭代的第只鸽子的速度，反映了鸽更新的速率；为鸽规模；表示第次迭代时的全局最优解；为0到1之间的随机系数；为影响地图和指南针因子的一个因素；表示第次迭代后置信度高的鸽位置中心；表示上一级鸽。
17.步骤四：调节鸽搜索速度。具体为：利用地图和指南针因子调节鸽搜索速度，影响鸽的搜索范围及收敛情况。
18.步骤五：优化鸽算法中后期。具体为：多层次方法希望上层鸽子开展广泛搜索，在较大的范围内对全局进行初步感知，并向下传递有价值信息；算法中后期，下层鸽子能够针对性搜索目标，在最优解附近进行精确的局部搜索，并具有良好快速的收敛性。
19.步骤六：建立分布式拍卖算法模型，根据整体收益作出最优的任务分配方案。具体为：建立模型之前预定义一些基本变量，如下：：投标者数量；：任务数量；：投标者集合；：任务集合；：投标者感兴趣任务的集合，如果各投标人对所有商品都有兴趣，则有；：分配情况集合；：投标者对于任务的收益集合；：号无人清扫车完成第个任务集合；则分布式拍卖算法的流程描述如下：则分布式拍卖算法的流程描述如下：则分布式拍卖算法的流程描述如下：则分布式拍卖算法的流程描述如下：步骤六还包括以下三个子步骤：1）产生拍卖者。如果工作中的无人清扫车在完成任务的过程中发现收益
更高的任务，则可以利用上述公式计算收益值并向通信范围内无人清扫车发出重分配请求；当存在无人清扫车，使得互换任务产生更高收益时，通过申请，无人清扫车成为拍卖者。
20.2）投递标书。在无人清扫车发布拍卖信息后，收到请求的无人清扫车成为投标者，向投递标书申请进入指派环节。
21.3）确认指派方案。无人清扫车收集参与指派的无人清扫车信息，以匈牙利法求解并通知给各无人清扫车，完成任务集所有权的更替；更替后的收益为通信范围内的整体最优，并非无人清扫车个体最优，因此分配后的无人清扫车易作为招标者对同范围重复招标，影响任务的顺利执行。设定招标限制，指派流程完成后，参与流程的无人清扫车在招标限制时间内，不得作为招标者组织指派任务，直至限制解除。
22.其中，附图1一种基于改进鸽和分布式拍卖算法的多无人清扫车任务分配方法总体流程图对应了步骤一至步骤六的所有步骤；附图2分布式拍卖算法总体流程图对应了步骤六。
23.考虑到无人清扫车集间信号传递延时及通信范围和通信量的限制，本节采用附图3所示的树形拓扑结构代替传统的一对多广播式通信方法，并设定最大转发次数以限制信息的传递范围。对于任何招标信息，其初始的剩余传递次数为，每次无人清扫车间的信息传递会使剩余次数减1直至次数为0时不再转发。
附图说明
24.附图1一种基于改进鸽和分布式拍卖算法的多无人清扫车任务分配方法总体流程图。
25.附图2分布式拍卖算法总体流程图。
26.附图3多无人清扫车集间通信拓扑网络。

技术特征：

1.一种基于改进鸽和分布式拍卖算法的无人清扫车任务分配方法，其特征在于所述基于改进鸽和分布式拍卖算法的无人车清扫车任务分配方法包括：改进鸽，在同等探索次数下将鸽分为多个层次并依次执行探索任务；改进地磁算子，下层的鸽在彼此共享位置信息的同时，利用上一层鸽子的优质信息更新自身位置；改进地标算子，由于信息的分层传递，最终的最优位置将会偏向下层鸽的搜索结果；优化鸽算法中后期；建立分布式拍卖算法模型，根据收益作出最优的任务分配方案。2.根据权利要求1所述的方法，其特征在于所述的改进鸽：从鸽信息交换及分层传递的角度出发改进鸽算法，生成鸽系统并随机分成多个层级，鸽由上层至下层分层探索，每层探索结束后生成该层最优位置单向传递到下层，用于指引下层各自的初期演化方向。3.根据权利要求1所述的方法，其特征在于所述的改进地磁算法：在地磁算子阶段，下层的鸽能够在彼此共享位置信息的同时，利用上一层鸽子的优质信息更新自身位置，减少了初期探索时的盲目性，提高了效率；同时，对于在特定位置重复盘旋的鸽子，上层鸽子的位置信息能够起到牵引作用，辅助摆脱局部最优的情况。4.根据权利要求1所述的方法，其特征在于所述的改进地标算子：信息的传递使得种有较好的多样性，并且随着地磁算子到地标算子阶段的过渡，全局搜索过程转化为局部搜索，鸽由多个小规模种逐步合成为统一的大体，加强了最终的局部搜索能力，能够有效提升种精度。5.根据权利要求1所述的方法，其特征在于所述的优化鸽算法中后期：算法中后期，下层鸽子能够针对性搜索目标，在最优解附近进行精确的局部搜索，并具有良好快速的收敛性。6.根据权利要求1所述的方法，其特征在于所述的建立分布式拍卖算法模型：预设基本变量投标者、任务数量、投标者集合、任务集合、投标者感兴趣任务集合、分配情况集合、投标者对任务的收益集合、无人清扫车完成任务的集合，具体流程为：无人清扫车在任务过程中发现收益更高的任务，根据分布式拍卖算法计算收益值并向通信范围内无人清扫车发出重分配请求；若无人清扫车与原任务所属无人清扫车任务互换产生收益更高，无人清扫车通过申请使无人清扫车成为拍卖者；无人清扫车收集参与指派的无人清扫车信息，以匈牙利法求解并通知给各无人清扫车，完成任务集所有权的更替；更替后的收益为通信范围内的整体最优，并非无人清扫车个体最优，因此分配后的无人清扫车易作为招标者对同范围重复招标，影响任务的顺利执行；设定招标限制，指派流程完成后，参与流程的无人清扫车在招标限制时间内，不得作为招标者组织指派任务，直至限制解除。

技术总结

本发明提供一种基于改进鸽和分布式拍卖算法的多无人清扫车任务分配方法，属于无人清扫车路径规划、任务分配技术领域。所述方法是利用改进鸽算法，从全局角度使无人清扫车获得最优初始目标任务，并在运动中利用分布式拍卖算法进行调整。解决了传统算法的寻优问题、服务器计算量大存在稳定性不足的问题，以及多辆无人清扫车共同工作下高成本问题。及多辆无人清扫车共同工作下高成本问题。