处理多任务运行路径冲突的方法、装置、设备及介质

摘要

本申请涉及一种处理多任务运行路径冲突的方法、装置、设备及介质。其中方法包括：计算每一个任务在单独运行时的最优路径，作为初始最优路径，并记录初始路径对应的初始收益；构建初始为空的优先级队列，将所有任务放入优先级队列，并按照初始路径收益的大小排序；设置初始的最优方案的代价为正无穷，从优先级队列中，按优先级从高到低依次出队任务，对任务路径中的冲突点进行处理；当优先级队列中的冲突点全部处理完毕时，计算动态方案的代价；比较动态方案的代价与当前的最优方案的代价的大小，选择代价更小的方案，作为最优方案。采用本方法能够在对多任务同时规划路径时，处理任务路径间冲突的同时保证任务的总收益最大化。

权利要求

1.一种处理多任务运行路径冲突的方法，其特征在于，包括：

计算每一个任务在单独运行时的最优路径，作为初始最优路径，并记录初始路径对应的初始收益；所述最优路径为任务能够获得最大收益所对应的任务运行路径；

构建初始为空的优先级队列，将所有任务放入所述优先级队列，并按照所述初始路径收益的大小排序；所述任务的初始路径收益越高，所述任务的优先级越高；

设置初始的最优方案的代价为正无穷，所述最优方案的代价为所有任务的最优路径的路径代价之和；

从所述优先级队列中，按优先级从高到低依次出队任务，查找所述出队的任务对应的当前路径中是否存在冲突点；若不存在，则标记所述当前路径中所有互斥网络区域内的路径点；所述互斥网络区域为指定的运输载具在运行时的最小间隔距离作为半径的圆形区域；若存在，则对所述冲突点进行处理：去掉所述冲突点，计算所述出队的任务对应的最优路径作为所述备用路径，计算所述备用路径的路径代价；计算所述出队的任务对应的当前路径中，所述任务在所述冲突点上强制停留的停留代价；将所述备用路径的路径代价与所述当前的最优路径的路径代价作差，并将差值与所述停留代价进行比较；若所述差值小于所述停留代价，则选用备用路径；若所述差值大于或等于所述停留代价，则在所述冲突点强制停留；

当所述优先级队列中，所有任务对应的路径中的冲突点全部处理完毕时，计算所有任务对应的当前路径的路径代价之和，作为动态方案的代价；

比较所述动态方案的代价与当前的最优方案的代价的大小，选择代价更小的方案，作为最优方案。

2.根据权利要求1所述的处理多任务运行路径冲突的方法，其特征在于，对所述冲突点进行处理，还包括：若选用备用路径，则将所述备用路径的路径代价作为所述当前的最优路径的路径代价，并将所述备用路径作为当前的最优路径；若在所述冲突点强制停留，则在所述当前的最优路径中，添加在所述冲突点上强制停留的动作，将所述停留代价加入所述当前的最优路径的路径代价中，并更新所述当前的最优路径。

3.根据权利要求2所述的处理多任务运行路径冲突的方法，其特征在于，还包括：

构建初始为空的已完成任务列表；所述已完成任务列表用于存储已经处理完冲突点的任务；所述冲突点为至少两个任务进入相同的互斥网络区域的时间点；

当所述出队的任务对应的当前路径中不存在冲突点时，将所述任务添加到所述已完成任务列表的末尾。

4.根据权利要求2所述的处理多任务运行路径冲突的方法，其特征在于，还包括：

构建初始为空的强制停留字典；所述强制停留字典用于存储路径中的冲突点与在所述冲突点停留的任务的映射关系；所述强制停留字典中，一个冲突点对应一个任务冲突列表，所述任务冲突列表中存在一个或多个在所述冲突点强制停留的任务；

判断所述冲突点是否存在于所述强制停留字典中；若不存在，则将所述冲突点与所述出队的任务的映射关系，添加到所述强制停留字典的末尾；若存在，则将所述出队的任务，添加到所述强制停留字典中所述冲突点对应的任务冲突列表的末尾。

5.根据权利要求1所述的处理多任务运行路径冲突的方法，其特征在于，选择代价更小的方案，作为最优方案，包括：若所述动态方案的代价大于或等于所述当前的最优方案的代价，则当前的最优方案保持不变；

若所述动态方案的代价小于所述当前的最优方案的代价，则将所述动态方案作为所述当前的最优方案。

6.根据权利要求1所述的处理多任务运行路径冲突的方法，其特征在于，还包括：

在所述最优方案对应的强制停留字典中，遍历每一个冲突点及其对应的任务冲突列表，将所述冲突列表中的任务随机排序，计算所述当前的最优方案的竞争方案；

比较所述竞争方案的代价与所述当前的最优方案的代价的大小，选择代价更小的方案作为所述当前的最优方案。

7.根据权利要求6所述的处理多任务运行路径冲突的方法，其特征在于，计算所述当前的最优方案的竞争方案，包括：按加入所述强制停留字典的顺序，遍历所述强制停留字典中的每一个冲突点；按加入所述冲突点对应的任务冲突列表的顺序，遍历所述任务冲突列表中的每一个任务；若所述任务冲突列表中，排在任一冲突点之后的所有任务的所述初始收益之和，大于所述任务的所述初始收益，则将所述任务作为临界任务；

构建初始为空的随机子队列，将所述临界任务及之后的所有任务随机排序，加入所述随机子队列中；构建初始为空的已完成任务子列表，将所述临界任务之前的任务加入所述已完成任务子列表中；

从所述随机子队列中依次出队任务，重新对所述随机子队列中的所有任务进行冲突处理，并将处理完毕的任务添加到所述已完成任务子列表的末尾；

当所述随机子队列中所有任务的冲突都处理完毕时，计算当前所有任务的最优路径的路径代价之和，作为所述竞争方案的代价。

8.一种处理多任务运行路径冲突的装置，其特征在于，包括：

初始收益计算模块，被配置为计算每一个任务在单独运行时的最优路径，作为初始最优路径，并记录初始路径对应的初始收益；所述最优路径为任务能够获得最大收益所对应的任务运行路径；

队列生成模块，被配置为构建初始为空的优先级队列，将所有任务放入所述优先级队列，并按照所述初始路径收益的大小排序；所述任务的初始路径收益越高，所述任务的优先级越高；

冲突处理模块，被配置为设置初始的最优方案的代价为正无穷，所述最优方案的代价为所有任务的最优路径的路径代价之和；从所述优先级队列中，按优先级从高到低依次出队任务，查找所述出队的任务对应的当前路径中是否存在冲突点；若不存在，则标记所述当前路径中所有互斥网络区域内的路径点；所述互斥网络区域为指定的运输载具在运行时的最小间隔距离作为半径的圆形区域；若存在，则对所述冲突点进行处理：去掉所述冲突点，计算所述出队的任务对应的最优路径作为所述备用路径，计算所述备用路径的路径代价；

计算所述出队的任务对应的当前路径中，所述任务在所述冲突点上强制停留的停留代价；

将所述备用路径的路径代价与所述当前的最优路径的路径代价作差，并将差值与所述停留代价进行比较；若所述差值小于所述停留代价，则选用备用路径；若所述差值大于或等于所述停留代价，则在所述冲突点强制停留；

代价计算模块，被配置为当所述优先级队列中，所有任务对应的路径中的冲突点全部处理完毕时，计算所有任务对应的当前路径的路径代价之和，作为动态方案的代价；

筛选模块，被配置为比较所述动态方案的代价与当前的最优方案的代价的大小，选择代价更小的方案，作为最优方案。

9.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，所述计算机程序被处理器执行时，实现如权利要求1至7任一所述的方法中的步骤。

10.一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，其特征在于，所述处理器执行所述计算机程序时，实现如权利要求1至7任一所述的方法的步骤。

说明书

处理多任务运行路径冲突的方法、装置、设备及介质

技术领域

[0001] 本申请涉及路径规划领域，特别是涉及一种处理多任务运行路径冲突的方法、装置、设备及介质。

背景技术

[0002] 路径规划在很多领域都具有广泛的应用。在运输领域的路径规划实践中，对于一个运输任务，已知该任务的起点和目的地，需要规划该任务从地点到目的地的最优路径。“最优”的标准根据任务的不同有所不同，如果仅仅计算任务起点与目的地的最短距离，在真实的场景中可能并不是最优的选择。例如，在运输任务场景中，选择红绿灯少并且几乎不会拥堵的高速环线执行运输任务，会比选择路程虽短，但是红绿灯多且经常性拥堵的市区内路段更快到达目的地。在这个过程中，对路径的不同选择可以看作是任务在路径中的不同的路径代价，而到达时间不同则可以看作任务完成后获得的不同的收益。在实际应用中，往往需要考虑任务的收益最大化来确定任务运行的最优路径。

[0003] 对单个任务的最优规划相对来说比较容易，但是当多个任务同时规划路径时，如果使用单个任务的路径规划方法，计算出的每个任务各自的路径之间可能会出现冲突。任务路径之间的冲突可能表现为多种形式，例如，多个任务路径之间对共同的路径网络节点同时占用，又或者两个任务之间存在一些运行规章限制带来的冲突，比如运输任务规定两个任务彼此的载具间隔不得小于100米，则某个时间点两个任务间隔小于100米即会产生冲突。因此，需要找到一种方法，在对多任务同时规划路径时，处理所有任务路径间冲突的同时尽量使所有任务的总收益最大化。

发明内容

[0004] 有鉴于此，本申请旨在提出一种处理多任务运行路径冲突的方法、装置、设备及介质，以解决传统的路径规划方法难以在处理多任务间冲突的同时保证任务收益的问题。

[0005] 为达到上述目的，本申请的技术方案是这样实现的：

[0006] 本申请实施例第一方面提供一种处理多任务运行路径冲突的方法，所述方法包括：

[0007] 计算每一个任务在单独运行时的最优路径，作为初始最优路径，并记录初始路径对应的初始收益；所述最优路径为任务能够获得最大收益所对应的任务运行路径；

[0008] 构建初始为空的优先级队列，将所有任务放入所述优先级队列，并按照所述初始路径收益的大小排序；所述任务的初始路径收益越高，所述任务的优先级越高；

[0009] 设置初始的最优方案的代价为正无穷，从所述优先级队列中，按优先级从高到低依次出队任务，查找所述出队的任务对应的当前路径中是否存在冲突点；若不存在，则标记所述当前路径中所有互斥网络区域内的路径点；若存在，则对所述冲突点进行处理；所述处理为执行以下任一动作：在冲突点强制停留或选用备用路径；所述最优方案的代价为所有任务的最优路径的路径代价之和；

[0010] 当所述优先级队列中，所有任务对应的路径中的冲突点全部处理完毕时，计算所有任务对应的当前路径的路径代价之和，作为动态方案的代价；

[0011] 比较所述动态方案的代价与当前的最优方案的代价的大小，选择代价更小的方案，作为最优方案。

[0012] 可选地，对所述冲突点进行处理，包括：

[0013] 去掉所述冲突点，计算所述出队的任务对应的最优路径，作为所述备用路径，计算所述备用路径的路径代价；

[0014] 计算所述出队的任务对应的当前路径中，所述任务在所述冲突点上强制停留的停留代价；

[0015] 将所述备用路径的路径代价与所述当前的最优路径的路径代价作差，并将差值与所述停留代价进行比较；若所述差值小于所述停留代价，则将所述备用路径的路径代价，作为所述当前的最优路径的路径代价，并将所述备用路径作为当前的最优路径；若所述差值大于或等于所述停留代价，则在所述当前的最优路径中，添加在所述冲突点上强制停留的动作，将所述停留代价加入所述当前的最优路径的路径代价中，并更新所述当前的最优路径。

[0016] 可选地，所述处理多任务运行路径冲突的方法，还包括：

[0017] 构建初始为空的已完成任务列表；所述已完成任务列表用于存储已经处理完冲突点的任务；所述冲突点为至少两个任务进入相同的互斥网络区域的时间点；所述互斥网络区域为指定的运输载具在运行时的最小间隔距离作为半径的圆形区域；

[0018] 当所述出队的任务对应的当前路径中不存在冲突点时，将所述任务添加到所述已完成任务列表的末尾。

[0019] 可选地，所述处理多任务运行路径冲突的方法，还包括：

[0020] 构建初始为空的强制停留字典；所述强制停留字典用于存储路径中的冲突点与在所述冲突点停留的任务的映射关系；所述强制停留字典中，一个冲突点对应一个任务冲突列表，所述任务冲突列表中存在一个或多个在所述冲突点强制停留的任务；

[0021] 判断所述冲突点是否存在于所述强制停留字典中；若不存在，则将所述冲突点与所述出队的任务的映射关系，添加到所述强制停留字典的末尾；若存在，则将所述出队的任务，添加到所述强制停留字典中所述冲突点对应的任务冲突列表的末尾。

[0022] 可选地，选择代价更小的方案，作为最优方案，包括：

[0023] 若所述动态方案的代价大于或等于所述当前的最优方案的代价，则当前的最优方案保持不变；

[0024] 若所述动态方案的代价小于所述当前的最优方案的代价，则将所述动态方案作为所述当前的最优方案。

[0025] 可选地，所述处理多任务运行路径冲突的方法，还包括：

[0026] 在所述最优方案对应的强制停留字典中，遍历每一个冲突点及其对应的任务冲突列表，将所述冲突列表中的任务随机排序，计算所述当前的最优方案的竞争方案；

[0027] 比较所述竞争方案的代价与所述当前的最优方案的代价的大小，选择代价更小的方案作为所述当前的最优方案。

[0028] 可选地，计算所述当前的最优方案的竞争方案，包括：

[0029] 按加入所述强制停留字典的顺序，遍历所述强制停留字典中的每一个冲突点；按加入所述冲突点对应的任务冲突列表的顺序，遍历所述任务冲突列表中的每一个任务；若所述任务冲突列表中，排在任一冲突点之后的所有任务的所述初始收益之和，大于所述任务的所述初始收益，则将所述任务作为临界任务；

[0030] 构建初始为空的随机子队列，将所述临界任务及之后的所有任务随机排序，加入所述随机子队列中；构建初始为空的已完成任务子列表，将所述临界任务之前的任务加入所述已完成任务子列表中；

[0031] 从所述随机子队列中依次出队任务，重新对所述随机子队列中的所有任务进行冲突处理，并将处理完毕的任务添加到所述已完成任务子列表的末尾；

[0032] 当所述随机子队列中所有任务的冲突都处理完毕时，计算当前所有任务的最优路径的路径代价之和，作为所述竞争方案的代价。

[0033] 根据本申请实施例的第二方面，提供一种处理多任务运行路径冲突的装置，用于实现本申请实施例的第一方面所提供的处理多任务运行路径冲突的方法，所述装置包括：

[0034] 初始收益计算模块，被配置为计算每一个任务在单独运行时的最优路径，作为初始最优路径，并记录初始路径对应的初始收益；所述最优路径为任务能够获得最大收益所对应的任务运行路径；

[0035] 队列生成模块，被配置为构建初始为空的优先级队列，将所有任务放入所述优先级队列，并按照所述初始路径收益的大小排序；所述任务的初始路径收益越高，所述任务的优先级越高；

[0036] 冲突处理模块，被配置为设置初始的最优方案的代价为正无穷，从所述优先级队列中，按优先级从高到低依次出队任务，查找所述出队的任务对应的当前路径中是否存在冲突点；若不存在，则标记所述当前路径中所有互斥网络区域内的路径点；若存在，则对所述冲突点进行处理；所述处理为执行以下任一动作：在冲突点强制停留或选用备用路径；所述最优方案的代价为所有任务的最优路径的路径代价之和；

[0037] 代价计算模块，被配置为当所述优先级队列中，所有任务对应的路径中的冲突点全部处理完毕时，计算所有任务对应的当前路径的路径代价之和，作为动态方案的代价；

[0038] 筛选模块，被配置为比较所述动态方案的代价与当前的最优方案的代价的大小，选择代价更小的方案，作为最优方案。

[0039] 根据本申请实施例的第三方面，提供一种计算机可读存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时，实现如本申请第一方面所述的方法中的步骤。

[0040] 根据本申请实施例的第四方面，提供一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行所述计算机程序时，实现如本申请第一方面所述的方法中的步骤。

[0041] 采用本申请所提供的处理多任务运行路径冲突的方法，分别计算每个任务在单独运行情况下收益最大时对应的初始最优路径，按照任务在初始最优路径中单独运行的情况下对应的收益，划分任务的优先级，按照优先级从高到低排序。从优先级最高的任务开始，一次出队任务进行冲突处理，其中，任务在冲突点上有两种选择，原地等待或者绕道行进。通过对任务在每个冲突点上的路径代价进行比较，选择路径代价更小的作为优选方案，当所有任务中的冲突点都处理完毕后，获取多任务同时规划路径下保证路径收益最大化的最优方案。

[0042] 本申请提供的处理多任务运行路径冲突的方法，根据任务的初始路径收益划分任务的优先级，让优先级高的任务在冲突点上先行进，优先级低的任务在冲突点上后行进，通过比较冲突点上任务选择等待或是绕道的选择所对应的路径代价的大小，最终选择路径代价最小的方案作为最优方案。本申请的方案克服了目前多任务的路径规划中，传统的路径规划方法难以在处理多任务间冲突的同时保证任务收益的困难，在对多任务同时进行路径规划时，能够在合理处理任务路径间冲突的同时保证所有任务的总收益最大化。

附图说明

[0043] 为了更清楚地说明本申请实施例的技术方案，下面将对本申请实施例的描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本申请的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以根据这些附图获得其他的附图。

[0044] 图1是本申请一实施例提出的处理多任务运行路径冲突的方法的流程图；

[0045] 图2是本申请一实施例提出的处理多任务运行路径冲突的装置的示意图；

[0046] 图3是本申请一实施例提出的冲突点处理的流程图。

具体实施方式

[0047] 下面将结合本申请实施例中的附图，对本申请实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本申请一部分实施例，而不是全部的实施例。基于本申请中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本申请保护的范围。

[0048] 应理解，说明书通篇中提到的“一个实施例”或“一实施例”意味着与实施例有关的特定特征、结构或特性包括在本申请的至少一个实施例中。因此，在整个说明书各处出现的“在一个实施例中”或“在一实施例中”未必一定指相同的实施例。此外，这些特定的特征、结构或特性可以任意适合的方式结合在一个或多个实施例中。

[0049] 在本申请的各种实施例中，应理解，下述各过程的序号的大小并不意味着执行顺序的先后，各过程的执行顺序应以其功能和内在逻辑确定，而不应

[0050] 对本申请实施例的实施过程构成任何限定。

[0051] 这里将详细地对示例性实施例进行说明，其示例表示在附图中。下面的描述涉及附图时，除非另有表示，不同附图中的相同数字表示相同或相似的要素。以下示例性实施例中所描述的实施方式并不代表与本申请相一致的所有实施方式。相反，它们仅是与如所附权利要求书中所详述的、本申请的一些方面相一致的装置和方法的例子。

[0052] 需要说明的是，在不冲突的情况下，本申请中的实施例及实施例中的特征可以相互组合。

[0053] 本申请的方案建立在以下认知上：

[0054] (1)各个任务有能力衡量时间变化所带来的成本变化(路径代价变化)；

[0055] (2)成本变大即代价变大，一般意味着任务收益的下降；

[0056] (3)每个任务的一条具体路径对应了一个路径代价，它反映的是选择这条路径所需要付出的代价；

[0057] (4)两条路径冲突意味着在路径中至少存在一个时间冲突点，即相同在这个时间冲突点上，两个任务预期访问相同的互斥网络区域。

[0058] 互斥网络区域指任务之间规定的最小间隔区域。例如，两个运输任务规定彼此载具间距不得小于100米，那么对于前一个任务来说，其行进过程中100米半径的圆形区域内即为互斥网络区域，后一个任务首次进入这个区域的时间点即为首个冲突点。

[0059] 在进行运输任务的路径规划时，考虑任务在路径中运行的代价与收益，任务选择不同的路径行进，代表了任务运行过程中存在不同的路径代价，而任务到达目的地的时间，则反映了任务完成后获得的收益，任务完成的时间越早则收益越大，即该路径越优。当任务的价值固定时，任务在路径中运行的的收益为：

[0060] 收益＝任务最大价值‑任务运行中的路径代价

[0061] 从上述表达式可知，路径代价越大导致收益越小。任务在运行过程中，存在停留和行进两种状态，任务的路径代价可分为在路径中的停留代价，和行进代价。当两个任务之间存在冲突时，后一个任务有两种处理冲突的选择：在冲突点处停留(称为强制停留点)等待通行，在原有路径代价上付出额外的停留代价；或者绕开冲突点，选择备用路径，需要付出的路径代价变为备用路径的路径代价。

[0062] 任务在行进时的路径代价包括：路径本身的成本以及任务在路径中运行产生的动态路径代价。路径代价与任务在路径中的通行时间有关，因此将上述表达式转换为：

[0063] 收益＝任务最大价值‑(路径本身的成本+单位时间的动态路径代价×通行时间)[0064] 将上述表达式中，任务在行进时的路径代价表示为a+bk的形式，其中a表示路径本身的成本，b表示任务在路径中的通行时间，k表示单位时间内任务在行进过程中的动态路径代价，由于任务最大价值与路径本身的成本通常是固定的，因此k也反映了单位时间内收益的变化。根据上述收益的表达式构造函数曲线时，所述k就是该收益函数曲线的斜率k。实际的任务运输过程中，斜率k并不是完全不变的，任务在每个路段中运行的斜率k是实时变化的，在本实施例中为了方便计算，将任务在路径中的斜率当作一个固定值，即任务在所有的路段上行进时的斜率k都以这个固定值计算，基于斜率k进行路径权重的比较，计算最优路径。

[0065] 在选择最优路径时，需要在不同的路径之间比较，路径代价更小的路径更优。具体地，当某条路径1的路径代价小于路径2的路径代价，即表达式a1+b1k

[0066] 下面将参考附图并结合实施例来详细说明本申请。

[0067] 图1是本申请一实施例提出的处理多任务运行路径冲突的方法的流程图。如图1所示，所述处理多任务运行路径冲突的方法包括：

[0068] S11：计算每一个任务在单独运行时的最优路径，作为初始最优路径，并记录初始路径对应的初始收益；所述最优路径为任务能够获得最大收益所对应的任务运行路径。

[0069] 本实施例中，在初始时将所有任务单独进行最优路径的计算，即根据单个任务的收益和成本，在路径网络中选择收益最大的一条路径，作为该任务的初始最优路径，并记录下任务在初始路径中运行能够获得的收益，该任务的初始收益，将其记为m0，此时该任务当前的最优路径的路径代价记为r0。需要明确的是，初始最优路径是没有处理过冲突点的最优路径，本实施例中，通过初始最优路径对应的收益来确定任务的优先级。

[0070] S12：构建初始为空的优先级队列，将所有任务放入所述优先级队列，并按照所述初始路径收益的大小排序；所述任务的初始路径收益越高，所述任务的优先级越高；

[0071] S13：设置初始的最优方案的代价为正无穷，从所述优先级队列中，按优先级从高到低依次出队任务，查找所述出队的任务对应的当前路径中是否存在冲突点；若不存在，则标记所述当前路径中所有互斥网络区域内的路径点；若存在，则对所述冲突点进行处理；所述处理为执行以下任一动作：在冲突点强制停留或选用备用路径；所述最优方案的代价为所有任务的最优路径的路径代价之和。

[0072] 图3是本申请一实施例提出的冲突点处理的流程图。

[0073] 如图3所示，将所有任务按照初始收益从高到低进行优先级排序，即初始收益高的任务的优先级更高，初始收益低的任务的优先级更低。将所有任务放入初始为空的优先级队列S中，从优先级最高的任务开始，依次出队进行冲突点的处理，计算路径代价最小的方案，即为最优方案。在初始时，将最优方案的代价F0默认设为正无穷，最优方案的代价F0为所有任务的最优路径的路径代价之和。

[0074] 对每一个出队的任务n进行冲突点查找，如果该任务n当前的最优路径中不存在冲突点，则将当前路径中互斥网络区域内的路径点进行标记。所述互斥网络区域可以根据规章限制调整，例如，规定两个运输载具之间的间隔距离不得小于100米，则可将互斥网络区域的半径设为100米。如果任务n当前的最优路径中存在冲突点，则在冲突点上对任务n进行冲突处理，令任务n在冲突点处强制停留，或选择备用路径绕开该冲突点。例如，第一个出队的任务n1的最优路径中不存在冲突点，则标记任务n1的最优路径中被互斥网络区域覆盖的路径点(即其他任务在该互斥网络区域可能会出现冲突)，第二个出队的任务n2的最优路径中出现与任务n1的冲突点(在某时间点任务n2进入任务n1的互斥网络区域)，则在冲突点上对任务n2进行冲突处理：让任务n2原地强制停留，或者让任务n2绕道选择备用路径。

[0075] S14：当所述优先级队列中，所有任务对应的路径中的冲突点全部处理完毕时，计算所有任务对应的当前路径的路径代价之和，作为动态方案的代价；

[0076] S15：比较所述动态方案的代价与当前的最优方案的代价的大小，选择代价更小的方案，作为最优方案。

[0077] 本实施例中，当优先级队列S中所有任务的冲突都处理完毕后，获得一个多任务同时运行的路径规划方案，将该方案称为动态方案，计算该方案中所有任务对应的当前路径的路径代价之和，即该动态方案的代价F1。将动态方案的代价F1和当前的最优方案的代价F0比较，如果该动态方案的代价更小，则说明该动态方案能够获得的任务总收益更大，将该动态方案作为最优方案；如果当前的最优方案的代价F0更小，则保持当前的最优方案。

[0078] 可选地，对所述冲突点进行处理，包括：

[0079] 去掉所述冲突点，计算所述出队的任务对应的最优路径，作为所述备用路径，计算所述备用路径的路径代价；

[0080] 本实施例中，对于任务n的冲突点处理有两种方式，其中一种方式为：绕开该冲突点使用任务的备用路径。具体地，对于任务n当前路径中的冲突点a，计算任务n绕开a点的备用路径，即在路径网络中去掉路径点a，计算任务n收益最大时对应的最优路径，即为任务n的备用路径，此时根据该备用路径可以计算出备用路径的路径代价ra(n)：

[0081] ra(n)＝备用路径中所有路段的路径代价之和

[0082] 计算所述出队的任务对应的当前路径中，所述任务在所述冲突点上强制停留的停留代价。

[0083] 对于任务n的冲突点处理的另一种方式为：使任务n在路径点a处强制停留。此时，根据任务n强制停留的时间可以计算出路径点a处的停留代价ta(n)。

[0084] 将所述备用路径的路径代价与所述当前的最优路径的路径代价作差，并将差值与所述停留代价进行比较；若所述差值小于所述停留代价，则将所述备用路径的路径代价，作为所述当前的最优路径的路径代价，并将所述备用路径作为当前的最优路径；若所述差值大于或等于所述停留代价，则在所述当前的最优路径中，添加在所述冲突点上强制停留的动作，将所述停留代价加入所述当前的最优路径的路径代价中，并更新所述当前的最优路径。

[0085] 本实施例中，将计算得到的任务n的备用路径代价ra(n)与任务n当前的最优路径的路径代价r0(n)作差，然后将差值与停留代价ta(n)比较：

[0086] 若ra(n)‑r0(n)

[0087] r0(n)＝ra(n)

[0088] 若ra(n)‑r0(n)≥ta(n)，则令任务n在冲突点a处强制停留，此时

[0089] r0(n)＝r0(n)+ta(n)

[0090] 对优先级队列S中的所有任务n的路径上的所有冲突点a都进行处理，直到所有任务对应的当前路径中不存在冲突为止,，即所有冲突点都处理完毕。

[0091] 可选地，所述处理多任务运行路径冲突的方法，还包括：

[0092] 构建初始为空的已完成任务列表；所述已完成任务列表用于存储已经处理完冲突点的任务；所述冲突点为至少两个任务进入相同的互斥网络区域的时间点；所述互斥网络区域为指定的运输载具在运行时的最小间隔距离作为半径的圆形区域；

[0093] 当所述出队的任务对应的当前路径中不存在冲突点时，将所述任务添加到所述已完成任务列表的末尾。

[0094] 本实施例中，构建了初始为空的已完成任务列表U，将当前处理完冲突点的任务n放入列表U中。

[0095] 可选地，所述处理多任务运行路径冲突的方法，还包括：

[0096] 构建初始为空的强制停留字典；所述强制停留字典用于存储路径中的冲突点与在所述冲突点停留的任务的映射关系；所述强制停留字典中，一个冲突点对应一个任务冲突列表，所述任务冲突列表中存在一个或多个在所述冲突点强制停留的任务；

[0097] 判断所述冲突点是否存在于所述强制停留字典中；若不存在，则将所述冲突点与所述出队的任务的映射关系，添加到所述强制停留字典的末尾；若存在，则将所述出队的任务，添加到所述强制停留字典中所述冲突点对应的任务冲突列表的末尾。

[0098] 本实施例中，构建强制停留字典T，用于存储所有的冲突点(例如，冲突点a)以及在该冲突点上停留的任务的映射关系。例如，冲突点a与在a点处强制停留的任务n1、n2、n3的映射，冲突点b与在b点处强制停留的任务n2、n6、n8的映射......强制停留字典T中以列表的形式存储该映射关系，一个冲突点对应一个任务冲突列表slist，该列表中包括所有在该冲突点上停留的任务。当任务n在路径点a上强制停留时，将任务n添加到字典T中，冲突点a对应的任务冲突列表slist的末尾；如果字典T中还没有冲突点a，则先将冲突点a加入字典T中，再将任务n添加到冲突点a对应的任务冲突列表slist中。

[0099] 值得注意的是，由于处理冲突时按照任务的优先级依次出队，因此任务冲突列表slist中的任务也是按照任务优先级的顺序排列的，通过查看强制停留字典T可以看到当前的每个冲突点上任务通行的先后顺序。

[0100] 可选地，选择路径代价更小的方案，作为最优方案，包括：

[0101] 若所述动态方案的代价大于或等于所述当前的最优方案的代价，则当前的最优方案保持不变；

[0102] 若所述动态方案的代价小于所述当前的最优方案的代价，则将所述动态方案作为所述当前的最优方案。

[0103] 本实施例中，在优先级队列S中所有任务的冲突都处理完毕后，计算得到当前所有任务的最优路径的路径代价之和，即为动态方案的代价F1。将F1与当前的最优方案的代价进行比较：

[0104] 若F1≥F0则保持当前的最优方案；

[0105] 若F1

[0106] 可选地，所述处理多任务运行路径冲突的方法，还包括：

[0107] 在所述最优方案对应的强制停留字典中，遍历每一个冲突点及其对应的任务冲突列表，将所述冲突列表中的任务随机排序，计算所述当前的最优方案的竞争方案；

[0108] 比较所述竞争方案的代价与所述当前的最优方案的代价的大小，选择代价更小的方案作为所述当前的最优方案。

[0109] 本实施例中，当优先级队列S中的任务冲突全部处理完毕后，获得了一个基于任务收益优先级的最优方案。在此基础上，本申请还考虑一种小概率的运输场景。在字典T内，任务按照其在列表slist中的排序确定通行的顺序。例如，排在第一的任务j收益为x，排在第2以及之后的任务收益均为0.4x。在按照优先级高的任务优先通行时，任务j先通行，后面的所有任务停留等待。但是，当出现任务j之后的任务的总收益之和大于x时，也许让后面的任务先通行能获得更大的总收益。

[0110] 本实施例对于上述情况，提出了一种竞争方案的计算方法，随机打乱列表slist中任务j及其之后任务的排列顺序，计算打乱顺序以后的方案的任务通行顺序，与当前的最优方案比较是否出现了代价更小的方案。在字典T中，每一个冲突点对应的任务冲突列表slist都可能存在竞争方案。

[0111] 可选地，计算所述最优方案的竞争方案，包括：

[0112] 按加入所述强制停留字典的顺序，遍历所述强制停留字典中的每一个冲突点；按加入所述冲突点对应的任务冲突列表的顺序，遍历所述任务冲突列表中的每一个任务；若所述任务冲突列表中，排在任一冲突点之后的所有任务的所述初始收益之和，大于所述任务的所述初始收益，则将所述任务作为临界任务。

[0113] 本实施例中，从字典T中依次遍历所有冲突点，对于某个冲突点a，在其对应的列表slist中遍历每一个任务，如果出现某个任务j，排在任务j之后的任务的初始收益之和(记为M0(i))大于任务j的初始收益(记为m0(j))时，即M0(i)>m0(j)时，则将任务j作为临界任务。

[0114] 构建初始为空的随机子队列，将所述临界任务及之后的所有任务随机排序，加入所述随机子队列中；构建初始为空的已完成任务子列表，将所述临界任务之前的任务加入所述已完成任务子列表中。

[0115] 本实施例中，将任务j及排在其后的所有任务，通过每次生成不同的随机数r_use打乱排序，生成打乱顺序后的随机子队列S1，即S1＝sort(slist[j:])；并且将任务j之前的任务按照现有的顺序，加入初始为空的已完成任务子列表U1中，即U1＝U[:j‑1]。

[0116] 从所述随机子队列中依次出队任务，重新对所述随机子队列中的所有任务进行冲突处理，并将处理完毕的任务添加到所述已完成任务子列表的末尾；

[0117] 当所述随机子队列中所有任务的冲突都处理完毕时，计算当前所有任务的最优路径的路径代价之和，作为所述竞争方案的代价。

[0118] 本实施例中，根据队列S1中打乱排序后的任务顺序，对队列S1中的任务冲突重新处理，将处理完冲突的任务加入任务子列表U1的末尾。在队列S1中所有冲突处理完毕后，获得队列S1的最优子方案，此时将队列S1的最优子方案的代价记为b(1)，根据该最优子方案的代价计算竞争方案的代价F2：

[0119] F2＝队列S1之外的所有任务当前的最优路径的路径代价之和+b(1)

[0120] 比较竞争方案的代价F2与当前的最优方案F0的代价：若F2≥F0则保持当前的最优方案；若F2

[0121] 当字典T中所有的冲突点遍历完毕后，结束竞争方案的计算，获取当前的最优方案及最优方案的代价F0。

[0122] 基于同一发明构思，本申请一实施例提供一种处理多任务运行路径冲突的装置。参考图2，图2是本申请一实施例提出的处理多任务运行路径冲突的装置200的示意图。如图
2所示，该装置包括：

[0123] 初始收益计算模块201，被配置为计算每一个任务在单独运行时的最优路径，作为初始最优路径，并记录初始路径对应的初始收益；所述最优路径为任务能够获得最大收益所对应的任务运行路径；

[0124] 队列生成模块202，被配置为构建初始为空的优先级队列，将所有任务放入所述优先级队列，并按照所述初始路径收益的大小排序；所述任务的初始路径收益越高，所述任务的优先级越高；

[0125] 冲突处理模块203，被配置为设置初始的最优方案的代价为正无穷，从所述优先级队列中，按优先级从高到低依次出队任务，查找所述出队的任务对应的当前路径中是否存在冲突点；若不存在，则标记所述当前路径中所有互斥网络区域内的路径点；若存在，则对所述冲突点进行处理；所述处理为执行以下任一动作：在冲突点强制停留或选用备用路径；所述最优方案的代价为所有任务的最优路径的路径代价之和；

[0126] 代价计算模块204，被配置为当所述优先级队列中，所有任务对应的路径中的冲突点全部处理完毕时，计算所有任务对应的当前路径的路径代价之和，作为动态方案的代价；

[0127] 筛选模块205，被配置为比较所述动态方案的代价与当前的最优方案的代价的大小，选择代价更小的方案，作为最优方案。

[0128] 可选地，所述冲突处理模块203，还包括：

[0129] 备用方案计算模块，被配置为去掉所述冲突点，计算所述出队的任务对应的最优路径，作为所述备用路径，计算所述备用路径的路径代价；

[0130] 停留方案计算模块，被配置为计算所述出队的任务对应的当前路径中，所述任务在所述冲突点上强制停留的停留代价；

[0131] 第一比较子模块，被配置为将所述备用路径的路径代价与所述当前的最优路径的路径代价作差，并将差值与所述停留代价进行比较；若所述差值小于所述停留代价，则将所述备用路径的路径代价，作为所述当前的最优路径的路径代价，并将所述备用路径作为当前的最优路径；若所述差值大于或等于所述停留代价，则在所述当前的最优路径中，添加在所述冲突点上强制停留的动作，将所述停留代价加入所述当前的最优路径的路径代价中，并更新所述当前的最优路径。

[0132] 可选地，所述冲突处理模块203，还包括：

[0133] 列表添加子模块，被配置为构建初始为空的已完成任务列表；所述已完成任务列表用于存储已经处理完冲突点的任务；所述冲突点为至少两个任务进入相同的互斥网络区域的时间点；所述互斥网络区域为指定的运输载具在运行时的最小间隔距离作为半径的圆形区域；

[0134] 当所述出队的任务对应的当前路径中不存在冲突点时，将所述任务添加到所述已完成任务列表的末尾。

[0135] 可选地，所述冲突处理模块203，还包括：

[0136] 字典构建子模块，被配置为构建初始为空的强制停留字典；所述强制停留字典用于存储路径中的冲突点与在所述冲突点停留的任务的映射关系；所述强制停留字典中，一个冲突点对应一个任务冲突列表，所述任务冲突列表中存在一个或多个在所述冲突点强制停留的任务；

[0137] 判断所述冲突点是否存在于所述强制停留字典中；若不存在，则将所述冲突点与所述出队的任务的映射关系，添加到所述强制停留字典的末尾；若存在，则将所述出队的任务，添加到所述强制停留字典中所述冲突点对应的任务冲突列表的末尾。

[0138] 可选地，所述筛选模块205，还被配置为执行以下步骤：

[0139] 若所述动态方案的代价大于或等于所述当前的最优方案的代价，则当前的最优方案保持不变；

[0140] 若所述动态方案的代价小于所述当前的最优方案的代价，则将所述动态方案作为所述当前的最优方案。

[0141] 可选地，所述处理多任务运行路径冲突的装置200，还包括：

[0142] 竞争方案计算模块，被配置为在所述最优方案对应的强制停留字典中，遍历每一个冲突点及其对应的任务冲突列表，将所述冲突列表中的任务随机排序，计算所述当前的最优方案的竞争方案；

[0143] 第二比较子模块，被配置为比较所述竞争方案的代价与所述当前的最优方案的代价的大小，选择代价更小的方案作为所述当前的最优方案。

[0144] 可选地，所述竞争方案计算模块还包括：

[0145] 临界任务查找模块，被配置为按加入所述强制停留字典的顺序，遍历所述强制停留字典中的每一个冲突点；按加入所述冲突点对应的任务冲突列表的顺序，遍历所述任务冲突列表中的每一个任务；若所述任务冲突列表中，排在任一冲突点之后的所有任务的所述初始收益之和，大于所述任务的所述初始收益，则将所述任务作为临界任务；

[0146] 子队列排序模块，被配置为构建初始为空的随机子队列，将所述临界任务及之后的所有任务随机排序，加入所述随机子队列中；构建初始为空的已完成任务子列表，将所述临界任务之前的任务加入所述已完成任务子列表中；

[0147] 子队列冲突处理模块，被配置为从所述随机子队列中依次出队任务，重新对所述随机子队列中的所有任务进行冲突处理，并将处理完毕的任务添加到所述已完成任务子列表的末尾；

[0148] 代价计算子模块，被配置为当所述随机子队列中所有任务的冲突都处理完毕时，计算当前所有任务的最优路径的路径代价之和，作为所述竞争方案的代价。

[0149] 基于同一发明构思，本申请另一实施例提供一种可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现如本申请上述任一实施例所述的处理多任务运行路径冲突的方法中的步骤。

[0150] 基于同一发明构思，本申请另一实施例提供一种电子设备，包括存储器、处理器及存储在存储器上并可在处理器上运行的计算机程序，所述处理器执行时实现本申请上述任一实施例所述的处理多任务运行路径冲突的方法中的步骤。

[0151] 关于上述实施例中的装置，其中各个模块执行操作的具体方式已经在有关该方法的实施例中进行了详细描述，此处将不做详细阐述说明。

[0152] 以上所述仅为本申请的较佳实施例而已，并不用以限制本申请，凡在本申请的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本申请的保护范围之内。

[0153] 对于方法实施例，为了简单描述，故将其都表述为一系列的动作组合，但是本领域技术人员应该知悉，本申请并不受所描述的动作顺序的限制，因为依据本申请，某些步骤可以采用其他顺序或者同时进行。其次，本领域技术人员也应该知悉，说明书中所描述的实施例均属于优选实施例，所涉及的动作和部件并不一定是本申请所必须的。

[0154] 本领域内的技术人员应明白，本申请实施例可提供为方法、装置、或计算机程序产品。因此，本申请实施例可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本申请实施例可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD‑ROM、光学存储器等)上实施的计算机程序产品的形式。

[0155] 本申请实施例是参照根据本申请实施例的方法、终端设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理终端设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理终端设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。

[0156] 这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理终端设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。

[0157] 这些计算机程序指令也可装载到计算机或其他可编程数据处理终端设备上，使得在计算机或其他可编程终端设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程终端设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。

[0158] 尽管已描述了本申请实施例的优选实施例，但本领域内的技术人员一旦得知了基本创造性概念，则可对这些实施例做出另外的变更和修改。所以，所附权利要求意欲解释为包括优选实施例以及落入本申请实施例范围的所有变更和修改。

[0159] 最后，还需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。而且，术语“包括”、“包含”或者其任何其他变体意在涵盖非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者终端设备不仅包括那些要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者终端设备所固有的要素。在没有更多限制的情况下，由语句“包括一个……”限定的要素，并不排除在包括所述要素的过程、方法、物品或者终端设备中还存在另外的相同要素。

[0160] 以上对本申请所提供的处理多任务运行路径冲突的方法、装置、设备及介质进行了详细介绍，本文中应用了具体个例对本申请的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本申请的方法及其核心思想；同时，对于本领域的一般技术人员，依据本申请的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本申请的限制。