一种应用于大型场景下的自动驾驶巡逻车的调度方法及系统

摘要

本发明公开了一种应用于大型场景下的自动驾驶巡逻车的调度方法，该方法包括：步骤1，根据实际场景的实际道路地图，建立场景路网图模型G，所述场景路网图模型G包括顶点和由两顶点之间的连接线段形成的边，顶点表示实际场景中的各个实际道路的交叉口，边表示实际场景中的各条实际道路，边长对应为该边的权重；步骤2，根据场景路网图模型G，确定实际场景所需车辆数量N；步骤3，采用不同划分方法将实际场景划分成N个区域，再评估各划分结果，并依此选出最优划分结果；步骤4，根据划分好的区域，规划每一个区域内的车辆的行驶路线。本发明可根据场景的实际情况，合理配置巡逻车数量，划分各自任务区域，并规划巡逻路线，可为景区、厂区或类似的大型场景下的自动驾驶车辆提供一套调度方案。

说明书

技术领域

本发明涉及自动驾驶技术技术领域，特别是关于一种应用于大型场景下的 自动驾驶巡逻车的调度方法及系统。

背景技术

在一些大型场景中，通常都需要巡逻机制来实现安保等功能，而这些场景往 往都具有路线固定的特点，因此自动驾驶车辆得到了越来越多的应用。然而，大 型场景的占地面积和路线总里程通常较大，受限于目前自动驾驶车辆的行驶速度 和续航里程，若单靠一辆自动驾驶车完成所有的巡逻任务，则效率较为低下，效 果明显欠佳。

发明内容

本发明的目的在于提供一种应用于大型场景下的自动驾驶巡逻车的调度方 法及系统来克服或至少减轻现有技术的上述缺陷中的至少一个。

为实现上述目的，本发明提供一种应用于大型场景下的自动驾驶巡逻车的调 度方法，该方法包括：

步骤1，根据实际场景的实际道路地图，建立场景路网图模型G，所述场景 路网图模型G包括顶点和由两顶点之间的连接线段形成的边，顶点表示实际场 景中的各个实际道路的交叉口，边表示实际场景中的各条实际道路，边的权重表 示对应实际道路的长度；

步骤2，根据场景路网图模型G，确定实际场景所需车辆数量N；

步骤3，采用不同划分方法将实际场景划分成N个区域，再评估各划分结果， 并依此选出最优划分结果；

步骤4，根据划分好的区域，规划每一个区域内的车辆的行驶路线。

进一步地，步骤3中，通过式(4)计算得到的最小化每个所划区域内里程 值的标准差值评估各划分结果：

式中，W

进一步地，步骤3采用环路划分法，具体包括如下步骤：

步骤a1，遍历步骤1的场景路网图模型G的所有顶点，同时记录遍历过程中所 经过的边；

步骤b1，判断场景路网图模型G中是否有步骤a1未记录的边，该边记为“回 边”，若判定有回边，说明有环路存在，则进入步骤c1；

步骤c1，按照步骤a1的遍历方向，将其中一条回边的前一个顶点遍历到该回 边的后一个顶点，即可得到一个环路；

按照步骤c1提供的方法，依次处理完毕步骤b1判定得到的其它回边，得到场 景路网图模型G中所有的环路。

进一步地，步骤3采用割边划分法，具体包括如下步骤：

步骤a2，遍历步骤1的场景路网图模型G的所有顶点，同时记录遍历过程中所 经过的边；

步骤b2，判断场景路网图模型G中是否有割边，若判定有割边，则进入步骤 c2；

步骤c2，通过删除其中一条割边，将场景路网图模型G拆分成两个可能封闭 区域；

按照步骤c2提供的方法，依次处理完毕步骤b2判定得到的其它割边，得到场 景路网图模型G中其它可能封闭区域。

进一步地，步骤3，采用环路划分法和割边划分法相结合的划分方法，其具 体包括如下步骤：

步骤a3，遍历步骤1的场景路网图模型G的所有顶点，同时记录遍历过程中所 经过的边；

步骤b3，判断场景路网图模型G中是否有割边，若判定有割边，则进入步骤 c3；

步骤c3，通过删除其中一条割边，将场景路网图模型G拆分成两个可能封闭 区域，并在各划分结果的评估值差异较大的情形下，进入步骤d3；

步骤d3，判断步骤c3中评估值较大的区域中是否有回边，若判定有回边，则 进入步骤e3；

步骤e3，按照步骤a3的遍历方向，将其中一条回边的前一个顶点遍历到该回 边的后一个顶点，即可得到一个环路；

按照步骤e3提供的方法，依次处理完毕步骤d3判定得到的其它回边，得到评 估值较大的区域中所有的环路。

进一步地，步骤3中划分出的区域数量仍然无法等于步骤2中确定的所需车辆 数量N，则根据划分出的区域数量，按照如下两种情形分别进而二次处理：

第一种情形：若区域数量大于N，则合并具有公共边的相邻区域，使划分后 的区域数量达到N；

第二种情形：若区域数量小于N，则可对某些区域进行二次拆分，拆分方法 具体包括：

检查区域内部是否存在回边，若存在，则表示该区域内部还有环路，并继续 拆分出独立区域；若不存在，则表示该区域无法被继续拆分。

进一步地，步骤4具体包括：

在划分好的每个区域内，为巡逻车设置好初始点，并为每条边设置巡逻计数 器，均初始化为0；巡逻车从初始点出发，每经过一条边，该边的计数器加1；当 处于某一个顶点需要决定下一步去哪条边巡逻时，选择与该顶点相连的其余所有 边中计数器值最小的那条边，若与该顶点相连的其余所有边中计数器值都相等， 则选择所有边中上一次巡逻完成时间距离当前时间最长的一条边巡逻；上述过程 中，如果某个巡逻车经过公共边之后，该巡逻车所在区域和相邻区域的对应边计 数器都加1。

进一步地，N通过式(1)计算得到：

其中，round(*)函数代表四舍五入取整，W

本发明还提供一种应用于大型场景下的自动驾驶巡逻车的调度系统，该系统 包括：

模型建立装置，其用于根据实际场景的实际道路地图，建立场景路网图模型G，所述场景路网图模型G包括顶点和由两顶点之间的连接线段形成的边，顶点 表示实际场景中的各个实际道路的交叉口，边表示实际场景中的各条实际道路， 边的权重表示对应实际道路的长度；

车数计算装置，其用于根据场景路网图模型G，确定实际场景所需车辆数量 N；

区域划分装置，其用于采用不同划分方法将实际场景划分成N个区域，再评 估各划分结果，并依此选出最优划分结果；

路线规划装置，其用于根据划分好的区域，规划每一个区域内的车辆的行驶 路线。

进一步地，所述区域划分装置包括环路划分单元和/或割边划分单元，其中：

所述环路划分单元包括：

顶点搜索子单元，其用于采用DFS遍历场景路网图模型G的所有顶点，同时记 录遍历过程中所经过的边；

回边判断子单元，其用于判断场景路网图模型G中是否有步骤a1未记录的边， 该边记为“回边”，若判定有回边，说明有环路存在；

封闭区域获取子单元，其用于在环路存在的情形下，按照所述顶点搜索子单 元的遍历方向，将其中一条回边的前一个顶点遍历到该回边的后一个顶点，即可 得到一个环路；

所述封闭区域获取子单元依次处理完毕所述回边判断子单元判定得到的其 它回边，得到场景路网图模型G中所有的环路；

所述割边划分单元包括：

顶点搜索子单元，其用于遍历场景路网图模型G的所有顶点，同时记录遍历 过程中所经过的边；

割边判断子单元，其用于判断场景路网图模型G中是否有割边，若判定有割 边；

封闭区域获取子单元，其用于在割路存在的情形下，通过删除其中一条割边， 将场景路网图模型G拆分成两个可能封闭区域；

所述封闭区域获取子单元依次处理完毕所述割边判断子单元判定得到的其 它割边，得到场景路网图模型G中其它可能封闭区域。

本发明可根据场景的实际情况，合理配置巡逻车数量，划分各自任务区域， 并规划巡逻路线，可为景区、厂区或类似的大型场景下的自动驾驶车辆提供一套 调度方案。

附图说明

图1为本发明实施例提供的调度方法中的一场景路网图模型。

图2为本发明实施例提供的回边与环路示意图。

图3为本发明实施例提供的割边示例图。

图4为本发明实施例提供的划分区域合并示意图

图5为本发明实施例提供的车辆行驶路线规划示例。

图6为本发明实施例提供的自动驾驶车辆调度方法流程图。

图7为某大型场景的道路网络图模型。

图8为图7的DFS遍历结果。

图9为图7的区域划分结果。

具体实施方式

下面结合附图和实施例对本发明进行详细的描述。

如图6所示，本发明实施例提供的应用于大型场景下的自动驾驶巡逻车的 调度方法包括：

步骤1，根据实际场景的实际道路地图，建立场景路网图模型G。其中，场 景路网图模型G为无向图，包括顶点和由两顶点之间的连接线段形成的边。顶点 表示实际场景中的各个实际道路的交叉口，边表示实际场景中的各条实际道路， 边的权重表示对应实际道路的长度。

如图1所示，图1示出的是一个简单的路网图模型G，其包括第一顶点V

步骤2，确定实际场景所需车辆数量N。

作为步骤2的一种优选实施方式，可以通过式(1)计算得到：

(1)

W

其中，round(*)函数代表四舍五入取整，其可以理解为：理想状况下将场景 均分为N个区域，即为所需的车辆数量，每个区域的里程为W

需要指出的是，也可以根据实际情况选择其它实现方式，比如：从成本角度 出发，购车预算为B，巡逻车单价为P，则所需车辆数量N表示为式(3)：

诸如此类的实现方式，在此不一一列举。

步骤3，采用不同划分方法将实际场景划分成N个区域，再通过式(4)计算 得到的最小化每个所划区域内里程值的标准差值评估各划分结果，并依此选出最 优划分结果：

式中，

通过这种划分方式，可以使得划分的N个区域里程值

其中，划分好的各个区域应尽量为由环路所包围的封闭区域。

在一个实施例中，其采用环路划分法，具体包括如下步骤：

步骤a1，采用DFS(深度优先搜索)遍历步骤1的场景路网图模型G的所有顶 点，同时记录遍历过程中所经过的边。

步骤b1，判断场景路网图模型G中是否有步骤a1未记录的边，该边记为“回 边”，若判定有回边，说明有环路存在，则进入步骤c1。

步骤c1，按照步骤a1的遍历方向，将其中一条回边的前一个顶点遍历到该回 边的后一个顶点，即可得到一个环路。

按照步骤c1提供的方法，依次处理完毕步骤b1判定得到的其它回边，得到场 景路网图模型G中所有的环路。

例如：如图2所示，根据DFS遍历方法，各顶点遍历顺序为V

在另一个实施例中，其采用割边划分法，具体包括如下步骤：

步骤a2，采用DFS(深度优先搜索)遍历步骤1的场景路网图模型G的所有顶 点，同时记录遍历过程中所经过的边。

步骤b2，判断场景路网图模型G中是否有割边，若判定有割边，则进入步骤 c2。其中，在场景路网图模型G中，如果删除割边后，所有的顶点无法连通。

步骤c2，通过删除其中一条割边，将场景路网图模型G拆分成两个可能封闭 区域。

按照步骤c2提供的方法，依次处理完毕步骤b2判定得到的其它割边，得到场 景路网图模型G中其它可能封闭区域。

利用割边划分法，搜索场景路网图模型G中的割边，并根据割边将整个图模 型G分为各个完全独立的区域，可以减少各区域之间的耦合，即重合路段。

例如：如图3所示，图中E

在一个实施例中，同时结合环路划分法和割边划分法，将实际场景划分成N 个区域。

也就是说，划分区域时，可根据实际场景情况和划分效果选择其中一种划分 方法或两种方法的组合。对于没有割边的实际场景，则仅能使用环路；对于可能 没有环路的实际场景，则仅能使用割边；对于同时有割边和环路的实际场景，则 使用环路和割边，最后根据计算得到的区域里程值的标准差进行评估，选出最优 划分结果。比如：如下实现步骤3的方法：

步骤a3，采用DFS遍历步骤1的场景路网图模型G的所有顶点，同时记录遍历 过程中所经过的边；

步骤b3，判断场景路网图模型G中是否有割边，若判定有割边，则进入步骤c3；

步骤c3，通过删除其中一条割边，将场景路网图模型G拆分成两个可能封闭 区域，并在各划分结果的评估值差异较大的情形下，进入步骤d3；

步骤d3，判断步骤c3中评估值较大的区域中是否有回边，若判定有回边，则 进入步骤e3；

步骤e3，按照步骤a3的遍历方向，将其中一条回边的前一个顶点遍历到该回 边的后一个顶点，即可得到一个环路；

按照步骤e3提供的方法，依次处理完毕步骤d3判定得到的其它回边，得到评 估值较大的区域中所有的环路。

在一个实施例中，在利用上述实施例中的环路划分法或割边划分法划分出的 区域数量仍然无法等于步骤2中确定的所需车辆数量N，则根据划分出的区域数 量，按照如下两种情形分别进而二次处理：

第一种情形：若区域数量大于N，则合并具有公共边的相邻区域，使划分后 的区域数量达到N。例如：如图4所示，E

第二种情形：若区域数量小于N，则可对某些区域进行二次拆分，拆分方法 具体包括：

检查区域内部是否存在回边，若存在，则表示该区域内部还有环路，可以继 续拆分出独立区域；若不存在，则表示该区域无法被继续拆分，那么可以减少巡 逻车数量，或者，在权值之和较大的区域内投放一辆以上的巡逻车，本发明实施 例暂不涉及这种情况。

步骤4，根据划分好的区域，规划每一个区域内的车辆的行驶路线。

在划分好的每个区域内，为巡逻车设置好初始点，并为每条边设置巡逻计数 器，均初始化为0。巡逻车从初始点出发，每经过一条边，该边的计数器加1。当 处于某一个顶点需要决定下一步去哪条边巡逻时，选择与该顶点相连的其余所有 边中计数器值最小的那条边，若与该顶点相连的其余所有边中计数器值都相等， 则选择所有边中上一次巡逻完成时间距离当前时间最长的一条边巡逻。由于各个 区域之间还存在着公共边界，因此各个巡逻车之间还必须要建立通信，以同步各 自区域的公共边的计数器值，即如果某个巡逻车经过公共边之后，该巡逻车所在 区域和相邻区域的对应边计数器都应加1。

如图4所示，当区域A内的自动驾驶巡逻车处于顶点V

使用这种路线规划策略的合理性在于，巡逻车即能选择当前巡逻次数较少的 道路进行巡逻，避免某些道路长时间未得到巡逻，又能提供各区域之间公共边界 的巡逻效率，同时也能避免各区域内部复杂的路线规划。

下面以某大型场景的道路网络为具体实施例，说明自动驾驶巡逻车的调度方 法。

步骤1，根据实际场景的实际道路地图，建立场景路网图模型G：图7为根据 该大型场景建立的路网图模型。从图中可以看出，共有9个顶点(路口)和11条 边(道路)，每条道路的权值即为其长度。

步骤2，确定实际场景所需车辆数量N：路网图模型中所有边的权值之和为 59，本实施例假设自动驾驶车辆的续航里程为18，一天之内只需要充电一次，则 所需车辆数量为N＝round(59/(18*1))＝3。

步骤3，采用不同划分方法将实际场景划分成N个区域，再通过式(4)计算 得到的最小化每个所划区域内里程值的标准差值评估各划分结果，并依此选出最 优划分结果：

不管是环路划分法还是割边划分法，都需要先对图模型进行DFS(深度优先 搜索)。则对图7进行DFS，结果如图8所示。

从图8的遍历结果可以看出，E

环路1：V

环路2：V

环路3：V

环路4：V

分别计算4个环路的权值之和可得，环路1为20，环路2为22，环路3为36，环 路4为17。由于上一步Step2中确定了车辆数量为3，因此需要从这4条环路中选出 3条环路。容易看出，环路3应该被舍弃，因为若选用环路3，则整个图模型则仅 仅被分为环路3和环路4两部分，且环路3的权值之和为36，使得划分出的两部分 区域的标准差值较大，显然无法满足要求。因此按照环路划分法，整个图模型应 被划分为环路1、环路2和环路4三个区域。若根据割边划分法，则割边E

综上，整个图模型G的划分结果如图9所示，环路1构成区域A，环路2构成区 域B，环路4构成区域C。

步骤4，根据划分好的区域，规划每一个区域内的车辆的行驶路线：

首先，确定各区域内自动驾驶巡逻车的起始点，本实施例选V1为区域A的起 始点，选V5为区域B的起始点，选V8为区域C的起始点。

然后，将各区域内的所有边的计数器值均初始化为0。另外从图9可以看出， 道路E

表1自动驾驶巡逻车路线规划模拟表

本发明实施例提供一种应用于大型场景下的自动驾驶巡逻车的调度系统，该 系统包括模型建立装置、车数计算装置、区域划分装置和路线规划装置，其中：

模型建立装置用于根据实际场景的实际道路地图，建立场景路网图模型G， 所述场景路网图模型G包括顶点和由两顶点之间的连接线段形成的边，顶点表 示实际场景中的各个实际道路的交叉口，边表示实际场景中的各条实际道路，边 的权重表示对应实际道路的长度。

如图1所示，图1示出的是一个简单的路网图模型G，其包括第一顶点V

车数计算装置用于根据场景路网图模型G，确定实际场景所需车辆数量N。

作为车数计算装置的一种优选实施方式，可以通过式(1)计算得到：

W

其中，round(*)函数代表四舍五入取整，其可以理解为：理想状况下将场景 均分为N个区域，即为所需的车辆数量，每个区域的里程为W

需要指出的是，也可以根据实际情况选择其它实现方式，比如：从成本角度 出发，购车预算为B，巡逻车单价为P，则所需车辆数量N表示为式(3)：

诸如此类的实现方式，在此不一一列举。

区域划分装置用于采用不同划分方法将实际场景划分成N个区域，再评估各 划分结果，并依此选出最优划分结果。

路线规划装置用于根据划分好的区域，规划每一个区域内的车辆的行驶路线。

在一个实施例中，所述区域划分装置包括环路划分单元和/或割边划分单元 和评估单元，其中：

评估单元用于通过式(4)计算得到的最小化每个所划区域内里程值的标准 差值评估各划分结果，并依此选出最优划分结果：

式中，

通过这种划分方式，可以使得划分的N个区域里程值

其中，划分好的各个区域应尽量为由环路所包围的封闭区域。

所述环路划分单元包括顶点搜索子单元、回边判断子单元和封闭区域获取子 单元，其中：

顶点搜索子单元用于采用DFS遍历场景路网图模型G的所有顶点，同时记录遍 历过程中所经过的边。

回边判断子单元用于判断场景路网图模型G中是否有步骤a1未记录的边，该 边记为“回边”，若判定有回边，说明有环路存在。

封闭区域获取子单元用于在环路存在的情形下，按照所述顶点搜索子单元的 遍历方向，将其中一条回边的前一个顶点遍历到该回边的后一个顶点，即可得到 一个环路。

所述封闭区域获取子单元依次处理完毕所述回边判断子单元判定得到的其 它回边，得到场景路网图模型G中所有的环路。

例如：如图2所示，根据DFS遍历方法，各顶点遍历顺序为V

所述割边划分单元包括顶点搜索子单元、割边判断子单元和封闭区域获取子 单元，其中：

顶点搜索子单元用于采用DFS遍历场景路网图模型G的所有顶点，同时记录遍 历过程中所经过的边。

割边判断子单元用于判断场景路网图模型G中是否有割边，若判定有割边。

封闭区域获取子单元，其用于在割路存在的情形下，通过删除其中一条割边， 将场景路网图模型G拆分成两个可能封闭区域。

所述封闭区域获取子单元依次处理完毕所述割边判断子单元判定得到的其 它割边，得到场景路网图模型G中其它可能封闭区域。

例如：如图3所示，图中E

在一个实施例中，在利用上述实施例中的环路划分单元和/或割边划分单元划分出的区域数量仍然无法等于车数计算装置中确定的所需车辆数量N，则根据划分 出的区域数量，按照如下两种情形分别进而二次处理：

第一种情形：若区域数量大于N，则合并具有公共边的相邻区域，使划分后 的区域数量达到N。例如：如图4所示，E

第二种情形：若区域数量小于N，则可对某些区域进行二次拆分，拆分方法 具体包括：

检查区域内部是否存在回边，若存在，则表示该区域内部还有环路，可以继 续拆分出独立区域；若不存在，则表示该区域无法被继续拆分，那么可以减少巡 逻车数量，或者，在权值之和较大的区域内投放一辆以上的巡逻车，本发明实施 例暂不涉及这种情况。

路线规划装置在划分好的每个区域内，为巡逻车设置好初始点，并为每条边 设置巡逻计数器，均初始化为0。巡逻车从初始点出发，每经过一条边，该边的 计数器加1。当处于某一个顶点需要决定下一步去哪条边巡逻时，选择与该顶点 相连的其余所有边中计数器值最小的那条边，若与该顶点相连的其余所有边中计 数器值都相等，则选择所有边中上一次巡逻完成时间距离当前时间最长的一条边 巡逻。由于各个区域之间还存在着公共边界，因此各个巡逻车之间还必须要建立 通信，以同步各自区域的公共边的计数器值，即如果某个巡逻车经过公共边之后， 该巡逻车所在区域和相邻区域的对应边计数器都应加1。

如图4所示，当区域A内的自动驾驶巡逻车处于顶点V

最后需要指出的是：以上实施例仅用以说明本发明的技术方案，而非对其限 制。本领域的普通技术人员应当理解：可以对前述各实施例所记载的技术方案进 行修改，或者对其中部分技术特征进行等同替换；这些修改或者替换，并不使相 应技术方案的本质脱离本发明各实施例技术方案的精神和范围。