一种异构多无人车对多目标的融合任务与路径规划方法
本发明涉及无人系统自主规划领域，具体涉及一种异构多无人车对多目标的融合任务与路径规划方法。
背景技术：
1、车辆路径问题(vehicle routing problem，vrp)是一种典型的np-hard任务规划问题，近年来吸引了众多专家学者们的关注，其中，针对vrp问题求解的任务规划技术是当前在无人系统自主规划领域内较为热门的研究方向。vrp问题可以定义为给定一组无人车和多个目标点，如何合理地为每辆车进行目标分配，以使得在满足给定的约束条件下，最小化相应的路程和函数来输出任务目标分配的最优规划结果。典型的vrp问题包括异构多无人车vrp问题(heterogeneous fleet vehicle routing problem，hfvrp)等多种问题形式，异构多无人车对多目标的任务规划问题可以很好地抽象成hfvrp问题即为的主要特点在于，给定多个异构无人车，并且异构无人车的种类有严格限制，每种无人车所对应的能力以及完成不同任务的性能也是给定的，因此这构成限制每种类型车辆的数目的hfvrp问题(heterogeneous fixed fleet vehicle routing problem，hffvrp)，针对hffvrp问题，目前解决方法的实现主要分为两个方向，即搜索算法与优化算法。搜索算法的优点在于可以通过暴力搜索或者启发式搜索对所有可能的决策方案进行比较，以得到最优方案，但是算力要求高，算法复杂度大(常见的二分图搜索需要到达o(n3)的算法复杂度)，并且决策权重的评估以及启发式的构造存在先验性。优化算法可以通过迭代计算，在相对较短的时间内得到一个较优的决策解，但是无法给出最优解，并且根据不同的先验参数(如模拟退火算法中的接受概率、遗传算法中的初始种群等)，算法效果差异较大，存在难以复现的问题。
2、针对已经得到的任务分配结果，如何得到每辆无人车的具体车辆路径才是想要得到的最终解。因此路径规划算法作为无人车导航中的重要环节，主要是指无人车在相应区域内自动规划一条从起始点至目标点的路径，在这个过程中，需要保证不发生碰撞，并且寻路代价较低。针对这个问题，目前常用的路径规划算法以搜索算法为主，其中包括最小化起点移动代价的dijkstra算法、最小化终点移动代价的最佳优先搜索算法、最小化综合代价的a*算法。但是传统的路径搜索算法有算法收敛素速度慢、容易陷入局部最优解等问题。
3、针对以上所列出的缺点，提出不同的解决方案，针对任务分配算法和路径规划算法，已有的解决方案有如下几种：
4、任务分配方案1：文献(lu duan,yang zhan,haoyuan hu,yu gong,jiangwen wei,xiaodong zhang,and yinghui xu.2020.efficiently solving the practical vehiclerouting problem:a novel joint learning approach.in proceedings of the26th acmsigkddinternational conference on knowledge discovery&；data mining(kdd'20).association for computing machinery,new york,ny,usa,3054–3063.)文献设计了一个深度模型，来学习一个类启发式策略，最终生成车辆排线。模型基于gcn，把节点特征(坐标、需求量)、边特征(节点之间的真实物理距离)作为输入来做embedding。用separatedecoders来编码这两种特征的表达。一个decoder的输出是另一个decoder的supervision，结合强化学习和监督学习的方式来得到一组较优的决策解。但是通过学习方法得到的决策解无法保证其稳定性与鲁棒性，并且对计算能力要求过高。
5、任务分配方案2：文献(agatz n,bouman p,schmidt m.optimization approachesfor the traveling salesman problem with drone[j].transportation science,2018,52(4):965-981.)提出了一个整数规划模型tsp-d(traveling salesman problemwithdrone)，用于解决dtco问题。该模型允许ugv和uav同时执行配送任务，还提出了一些启发式规则来构造该数学问题的规划方案。但是其中的规划方案只适用于障碍物较少的宽阔地形，面对有较多障碍物的复杂环境时，算法的搜索速度明显减慢，并且无法得到较优的分配结果。
6、路径规划方案：文献(kurzer,karl.(2016).path planning in unstructuredenvironments:areal-time hybrid a*implementation for fast and deterministicpath generation for the kth research concept vehicle.10.13140/rg.2.2.10091.49444.)提出了一种在假设无人车有充分的感知和定位能力的情况下，能够在线重新规划，生成障碍物地图，并且能够在未知环境中行驶的方法。算法分为两个阶段，第一阶段通过改进a*算法在连续坐标系下进行启发式搜索，第二个阶段用数值非线性优化的方法(即共轭梯度下降法)对生成路径的“质量”进行提升，使其至少是局部最优的。但是仍然存在a*算法所固有的openlist过长，搜索过程中维护单调队列所花费的算力较大，算法复杂度较高等问题。
技术实现思路
1、有鉴于此，本发明提供了一种基于时间窗口约束下多无人车对多目标的融合任务与路径规划方法，本发明的方法能够实现输出任务目标点分配结果的同时，针对每辆无人车给出可执行的路径级规划结果。
2、本发明的技术解决方案是：
3、一种异构多无人车对多目标的融合任务与路径规划方法，该方法的步骤包括：
4、第一步，对当前工作区域结构地图进行栅格化操作，得到二值化的栅格地图矩阵；
5、第二步，将目标要求的参数和无人车的参数进行统一化编码；
6、第三步，按照第二步的统一化编码对无人车和目标进行初始化方案分配，得到多个分配方案，得到的多个分配方案形成初始分配结果，根据初始分配结果和第一步得到的二值化的栅格地图矩阵调用jps算法计算当前路径和当前初始分配结果的路程和，将该路程和标记为p1；
7、第四步，按照第二步的统一化编码交换初始分配结果中的一组分配方案，交换后的多个分配方案形成第二次分配结果，根据第二次分配结果和第一步得到的二值化的栅格地图矩阵调用jps算法计算当前路径和第二次分配结果的路程和，将该路程和标记为p2，将p1和p2进行比较，如果p2小于p1，则交换有效，保留第二次分配结果，如果p2不小于p1，则交换无效，保留初始分配结果；
8、第五步，重复第四步，当迭代次数达到设定阈值或是迭代n次后的路程和变化量小于设定精度，得到路径和分配结果，完成异构多无人车对多目标的融合任务与路径规划，n小于设定阈值。
9、所述第一步中，进行栅格化操作时，当前栅格内存在障碍物时标记为+∞，当前栅格在危险区域内标记为+∞，当前栅格可通行时标记为1。
10、有益效果
11、本发明的方法针对任务分配和路径规划两个任务，在考虑目标点与无人车任务分配方案的前提下，同时计算目标点与无人车之间的真实路径，采用真实路径而非估算路径来计算路程和，进行分配方案的迭代更新，使结果更加准确。并且能够实现输出目标点分配结果的同时，针对每辆无人车给出可执行的路径级规划结果，完成了由输入的地图信息、车辆信息与目标点信息直接得到每辆无人车的具体行驶路径，解决了端到端的多无人车路径规划问题。
技术特征：
1.一种异构多无人车对多目标的融合任务与路径规划方法，其特征在于该方法的步骤包括：
2.根据权利要求1所述的一种异构多无人车对多目标的融合任务与路径规划方法，其特征在于：
3.根据权利要求1所述的一种异构多无人车对多目标的融合任务与路径规划方法，其特征在于：
技术总结
本发明涉及无人系统自主规划领域，具体涉及一种异构多无人车对多目标的融合任务与路径规划方法。本发明的方法针对任务分配和路径规划两个任务，设计了耦合的算法，通过计算出当前分配结果的路径和路程和，以此进行分配结果的迭代，保证得到的是真实路程和而不是估计路程和。同时，在生成每个分配方案时，都可以得到与之对应的路径，而不需要在最终方案生成后继续计算最终分配方案的路径。
技术研发人员：方浩,毛雨辰,魏语劼,徐伯辰,梁昕恺,杨庆凯,曾宪琳
受保护的技术使用者：北京理工大学
技术研发日：
技术公布日：2024/9/23