专利名称：基于gps探测的贝叶斯路径规划装置及方法
技术领域：
本发明涉及一种适合于在实际的交通出行状况下基于先验的推断而采用的一种路径规划装置及方法，特别涉及一种基于GPS探测的贝叶斯路径规划装置及方法。
背景技术：
当前，全球定位系统(GlcAal Positioning System)已经广泛地在各种车辆上作为定位导航设备应用起来，比如车载导航系统，车辆的定位监控系统，交通部门的浮动车系统等等。另一方面，我们的各种导航系统中的路径优化方法得到的最优路径在实际使用中其规划出来的路径往往是在绝对的时间或者长度度量上的一种最短路径。然而，由于道路的实时交通路况的随机特性，这样在度量意义上的最优路径往往并不是那么符合司机的先验知识，这样的最优路径也往往不是我们真实世界的最优路径。专利(中国专利申请号200410103卯4. 1)是将车辆的时间和速度融合入路径规划的一种方法，专利(中国专利申请号200610036181. 9)是一种将路段权值设定为通行时间来实现的一种路径规划方法，从上面这几个专利申请书来看，目前已经有一些关于路径规划装置及方法的专利，现有的关于路径规划的专利仅仅是在度量(长度或者时间)上给出的一种路径最优化方法。这些方法都没有采用基于贝叶斯的先验推断方法来实现路径规划。《测绘学报》2010年8月39卷004-409页)中公布了一篇文献《出租车经验知识建模与路径规划算法》，虽然有些考虑了出租车的经验信息，但是仅仅是把一些信息用下面的计算公式归算到了道路所属权值上，Wi⑴=[μ, \ ( ) + μ^siIZu3-Ciw
本质上来说，该公式是将时间和速度信息通过这个公式，将w权值设定到对应的路段上，最后通过传统的dijkstra方法计算最优路径。将经验信息归算到道路权值上做路径规划的方法，在具备实时交通信息的情况下，与传统的最优路径方法的问题是一样的，其无法回避实时交通信息的随机性。该方法并不是一种先验推断方法，因而和采用度量上的最优路径规划的计算在方法上区别并不大。因此，该文献并未形成一种司机的先验信息并根据贝叶斯推断来分类道路集，并据此进行路径规划。从上面分析的现有的路径规划的技术方法来看，这些将速度，长度，通行时间等某种经验信息归化到道路权值的度量上的最优路径方法，并未真正将对路网交通状况非常熟悉的司机的一种先验推断方法纳入到路径规划系统中。
发明内容
本发明的目的就是针对现有技术存在的上述缺陷，提供一种基于GPS探测的贝叶斯路径规划装置及方法，本发明方法是采用先验知识推估后验信息的方法来模拟司机的一种先验找路方法；本装置利用贝叶斯分类器将司机的先验推断方法纳入到我们的路径规划装置中，其本身是基于分类器装置对路网做模式识别处理后而形成的路径规划方法。本发明的基于GPS探测的贝叶斯路径规划装置，主要分为探测端和中心处理端两个部分，其中探测端选择一些熟悉道路交通状况的司机，将GPS探测器分布在这些司机的车辆上；所述的中心处理端包括接收器、中心控制器、路径筛选器、贝叶斯分类器和最优路径计算器几个�？槠渲刑讲舛薌PS探测器，主要是用GPS采集器来对η个司机的行驶轨迹进行探测； 所述的中心处理端中心控制器，控制其它的�？橹涞氖荽停宦肪渡秆∑鳎饕莶杉降恼庑┧净盗镜腉PS轨迹点以及采集的出发点和终止点恢复出行驶的路径， 并筛选出通过速度快、耗费时间短的“好”路径；贝叶斯分类器，根据建立的“好”路径集训练贝叶斯分类器，根据训练好的贝叶斯分类器对道路做分类，形成优先道路集，次优道路集以及全部道路集；最优路径计算器，根据形成的三种优选道路，实施最优路径搜索计算，得到最优路径结果；路径存储器，存放路径筛选器建立的“好”路径集；道路分类存储器，存放贝叶斯分类器分类后形成的三种道路集。本发明的基于GPS探测的贝叶斯路径规划方法，包括以下步骤
(1)、探测端用GPS探测器来获取出行经验数据；
(2)、中心控制端从GPS探测器中得到轨迹数据并通过一系列地处理而实现路径规划， 包括以下步骤
(2. 1)用路径筛选器来得到先验上的“好”的路径集主要根据采集到的这些司机车辆的GPS轨迹点以及采集的出发点和终止点恢复出行驶的路径，并筛选出通过速度快、耗费时间短的“好”路径；
(2. 2)根据建立的“好”路径集训练贝叶斯分类器，根据训练好的贝叶斯分类器对道路做分类，形成优先道路集，次优道路集以及全部道路集；
(2. 3)最优路径计算器中计算最优路径，中心控制器将上述三类优先道路集看成三层道路网络输入到最优路径计算器，得到最优路径结果；
上述的路径筛选器主要由比较控制器、匹配计算模块以及缓存器三部分组成
a)在匹配计算�？橹校萏讲舛瞬杉玫降乃净腉PS轨�：图锹嫉某龇⒌愫椭罩沟悖玫赝计ヅ浞椒ń淦ヅ涞蕉杂Φ牡缆仿范危⒏菹嗔诘牡缆仿范蜗嘟拥玫矫扛龀龇⒌愫椭罩沟阒湫纬傻穆肪叮ヅ浼扑隳？榈玫降穆肪都淙氲奖冉霞扑闫髦校�
b)在比较控制器中，先根据每条路径的总长度和GPS记录的行程时间，可以得到单条路径上司机车辆行驶的平均通行速度通过与所有路径通行速度的平均值VpM
#相比较，根据v.》V 可以得到一条先验上“好”的路径，将其纳入”好”的路径集，并放入到路径存储器中。上述的贝叶斯分类器主要由数据分割器、道路特征生成器、贝叶斯分类控制器、道路拓扑器和缓存器构成；
a)将“好”路径输入给数据分割器，分割器根据路径的时间属性，将其分为高峰期的 “好”路径集Tl和非高峰期的“好”路径集T2 ；
b)在道路特征生成器中，对所有的“好”路径集，将所有路径经过同一道路路段e的频次作统计；
c)在道路特征生成器中，计算道路网络上的所有节点对之间的最短路径，并由此得到道路路段e的中介中心性。d)从道路网络数据中挑选一部分出来作为贝叶斯分类控制器的训练数据，利用贝叶斯分类控制器来对道路路段分类，得到优先道路集、次优道路集和一般道路集；
e)在道路拓扑检测器中，根据步骤d)得到的三个道路集，将其生成的这三类优先道路集放入到道路分类存储器中。
本发明的有益效果是本专利就是利用这种司机对道路网络的实时交通状况的先验推断，构造了贝叶斯分类器来形成对道路网络的优先识别，基于这种优先识别而形成的一种路径规划装置及方法，它可以根据高峰期、非高峰期的先验知识在不同的交通时段中分别给出不同的最优路径。该装置及方法具有良好的实用性，并可以灵活的集成到各种基于道路交通的导航系统中。
附图1是本发明的装置的原理示意附图2是本发明的路径筛选器的示意附图3是本发明的路径筛选器筛选“好”路径的流程附图4是本发明的贝叶斯分类器的示意附图5是本发明的道路集的贝叶斯分类流程示意附图6是本发明的最优路径计算流程图。
具体实施例方式
本装置的具体的实施方式如下 探测端的实施
用GPS探测器来获取出行经验数据。选择η个对需要做路径分析的区域道路网非常熟悉的司机，将GPS探测器装在这η个司机的车上，用GPS来记录其每天的出行数据，包
括其出行路径的出发点和终止点。这样累积记录他们的出行路径一段时间(比如一个月)后，根据这些对实时道路熟悉的司机车辆上的GPS探测器及其记录，得到η个经验司机的出行GPS轨迹数据。中心处理端实施步骤
整个中心处理端�？榧涞氖荽溆芍行目刂破骼纯刂疲诵械牟街枇鞒桃灿芍行目刂破骼纯刂啤Ｏ旅姘聪群笏承蚋鲋行拇矶耸迪值谋匆端孤肪豆婊椒�。1用路径筛选器来得到先验上的“好”的路径集，本�？橹饕杀冉峡刂破�、匹配计算�？橐约盎捍嫫魅糠肿槌桑浣峁故疽馔技按砦螅∥凑业揭迷�。”其流程图见“错误！未找到引用源。”
中心控制器从GPS探测器中得到采集的GPS轨迹数据。Ia )在匹配计算�？橹校萏讲舛瞬杉玫降乃净腉PS轨�：图锹嫉某龇⒌愫椭罩沟悖玫赝计ヅ浞椒ń淦ヅ涞蕉杂Φ牡缆仿范危⒏菹嗔诘牡缆仿范蜗嘟拥玫矫扛龀龇⒌愫椭罩沟阒湫纬傻穆肪�。匹配计算模块得到的路径集输入到比较计算器中。lb)在比较控制器中，先根据每条路径的总长度L和该路径从出发点到终止点之间的行程时间」t，由Vi^=L/」t，可以得到单条路径的平均通行速度然后计算某一时段T内GPS的所有行驶速度，根据该时段内所有路径的通行速度的均值V-^^设定一个阈值。比较、与关系。如果、》，则认为该路径为一条先验上“好”的路径，将其纳入”好”的路径集，并放入到路径存储器中；如果vy，则认为该路径不是一条先验上“好”的路径，将其舍弃。最后形成完了 “好”的路径集后，通知中心控制器将这些“好”的路径集存入路径存储器中。2用贝叶斯分类器对道路网络做分类，得到三种优选道路集。贝叶斯分类器主要由数据分割器、道路特征生成器、贝叶斯分类控制器、道路拓扑器和缓存器这几部分构成，其结构如“错误！未找到引用源”所示，其流程如“错误！未找到引用源”所示。中心控制器从路径存储器中得到的“好”路径集输入到贝叶斯分类器。2a)将“好”路径输入给数据分割器，分割器根据路径的时间属性，将其分为高峰期的“好”路径集Tl和非高峰期的“好”路径集T2。下面的步骤2b-je分别对Tl和T2实施，得到高峰期和非高峰期不同的三类优先道路集。2b)在道路特征生成器中，对所有的“好”路径集，将所有路径经过同一道路路段e 的频次作统计，即不同的路径每经过一次相同的道路路段，其频次属性f(e)加l，f(e)初始值为0。根据所有“好”路径经过道路路段的速度做平均，记为ν (e)。2c)在道路特征生成器中，计算道路网络上的所有节点对之间的最短路径，所有最短路径的总数为N。根据所有的最短路径经过每一个道路路段e的次数c (e)，计算路段e 的中介中心性B (e)= c(e)/N。2d)从道路网络数据中挑选一部分出来作为贝叶斯分类控制器的训练数据。按照 2b)和2c)中得到的道路e的特征f (e)、v(e)和B(e)来估计贝叶斯分类控制器的参数。确定好了贝叶斯分类控制器参数以后，将所有的道路根据其特征f(e)、v(e)和B(e)利用贝叶斯分类控制器来对道路路段分类，得到优先道路集E1、次优道路集氏和一般道路集&。2e)在道路拓扑检测器中，根据步骤2d)得到的三个道路集，从E1开始，计算得到 E1的最大强连通子网C1。将E1中不在C1的道路重新加入到氏中，计算得到氏的最大强连通子网C2。这样，我们令G1=C1作为优先道路集，令G=C^C2作为次优道路集，G3为全部道路网络作为全体道路集。这样，我们就得到由&、(；2、(；3形成的三类优先道路集。中心控制器在贝叶斯分类器的步骤完成后将其生成的这三类优先道路集放入到道路分类存储器中。3根据步骤2中形成的针对高峰期Tl和非高峰期T2的分类优先道路集，分别在最优路径计算器中计算最优路径。由于对于Tl和T2的道路集，其计算步骤都是一样的，这样，在下面的描述中对Tl和T2不作区分。其流程见“错误！未找到引用源。”
中心控制器将三类优先道路集看成三层道路网络输入到最优路径计算器。确定待确定的最优路径在路网中的起始点和终止点。在最优路径计算器中实施下面几个步骤 3a)从在第Gi层中分别从起始和终止点处开始正向和逆向搜索最优路径； 3b)如果在Gi层正向和逆向搜索中，最优子路径上的节点也存在于对应的Gp1层中，分别记为SifIV1，那么就跳回到步骤3a)，并且i减1，即在第Gh中执行步骤3a)。如果在正向与逆向搜索中，最优子路径上没有这样的节点，那么就执行步骤3c)；
3c)如果正向搜索的子路径和逆向搜索的子路径不能汇合于同一点，那么继续执行步骤北)，如果可以汇合于一点，那么执行步骤3d)；
3d)汇合每层计算的子路径形成最后的经验最优路径。本装置中，探测端设备GPS探测器以硬件的形式装配在所选择的司机车辆上，并可以保存其车辆的GPS轨迹数据。中心处理端装置可以在任何的操作系统平台下，利用任何一种编程语言，利用软件方式来实现，也可以采用合适的硬件来实现，具有良好的实用性，并可以灵活的集成到各种基于道路交通的导航系统中。
权利要求
1.一种基于GPS探测的贝叶斯路径规划装置，其特征是主要分为探测端和中心处理端两个部分，其中探测端选择一些熟悉道路交通状况的司机，将GPS探测器分布在这些司机的车辆上；所述的中心处理端包括接收器、中心控制器、路径筛选器、贝叶斯分类器和最优路径计算器几个�？槠渲刑讲舛薌PS探测器，主要是用GPS采集器来对η个司机的行驶轨迹进行探测；所述的中心处理端中心控制器，控制其它的模块之间的数据传送；路径筛选器，主要根据采集到的这些司机车辆的GPS轨迹点以及采集的出发点和终止点恢复出行驶的路径，并筛选出通过速度快、耗费时间短的“好”路径；贝叶斯分类器，根据建立的“好”路径集训练贝叶斯分类器，根据训练好的贝叶斯分类器对道路做分类，形成优先道路集，次优道路集以及全部道路集；最优路径计算器，根据形成的三种优选道路，实施最优路径搜索计算，得到最优路径结果；路径存储器，存放路径筛选器建立的“好”路径集；道路分类存储器，存放贝叶斯分类器分类后形成的三种道路集。
2.一种基于GPS探测的贝叶斯路径规划方法，其特征是包括以下步骤(1)、探测端用GPS探测器来获取出行经验数据；(2)、中心控制端从GPS探测器中得到的轨迹数据经过一系列处理而实现路径规划，包括以下步骤(2. 1)用路径筛选器来得到先验上的“好”的路径集主要根据采集到的这些司机车辆的GPS轨迹点以及采集的出发点和终止点恢复出行驶的路径，并筛选出通过速度快、耗费时间短的“好”路径；(2.2)根据建立的“好”路径集训练贝叶斯分类器，根据训练好的贝叶斯分类器对道路做分类，形成优先道路集，次优道路集以及全部道路集；(2. 3)最优路径计算器中计算最优路径，中心控制器将上述三类优先道路集看成三层道路网络输入到最优路径计算器，得到最优路径结果。
3.根据权利要求2所述的基于GPS探测的贝叶斯路径规划方法，其特征是所述的路径筛选器主要由比较控制器、匹配计算�？橐约盎捍嫫魅糠肿槌蒩)在匹配计算模块中，根据探测端采集得到的司机的GPS轨�：图锹嫉某龇⒌愫椭罩沟悖玫赝计ヅ浞椒ń淦ヅ涞蕉杂Φ牡缆仿范危⒏菹嗔诘牡缆仿范蜗嘟拥玫矫扛龀龇⒌愫椭罩沟阒湫纬傻穆肪叮ヅ浼扑隳？榈玫降穆肪都淙氲奖冉霞扑闫髦校籦)在比较控制器中，先根据每条路径的总长度和GPS记录的行程时间，可以得到其平均通行速度v，通过比较平均通行速度的关系，得到一条先验上“好”的路径，将其纳入”好” 的路径集，并放入到路径存储器中。
4.根据权利要求2所述的基于GPS探测的贝叶斯路径规划方法，其特征是所述的贝叶斯分类器主要由数据分割器、道路特征生成器、贝叶斯分类控制器、道路拓扑器和缓存器构成；a)将“好”路径输入给数据分割器，分割器根据路径的时间属性，将其分为高峰期的“好”路径集Tl和非高峰期的“好”路径集T2 ；b)在道路特征生成器中，对所有的“好”路径集，将所有路径经过同一道路路段e的频次作统计；c)在道路特征生成器中，计算道路网络上的所有节点对之间的最短路径，并由此得到道路路段e的中介中心性；d)从道路网络数据中挑选一部分出来作为贝叶斯分类控制器的训练数据，利用贝叶斯分类控制器来对道路路段分类，得到优先道路集、次优道路集和一般道路集；e)在道路拓扑检测器中，根据步骤d)得到的三个道路集，将其生成的这三类优先道路集放入到道路分类存储器中。
全文摘要
本发明涉及一种基于GPS探测的贝叶斯路径规划装置及方法。本发明方法是采用先验知识推估后验信息的方法来模拟司机的一种先验找路方法；本装置利用贝叶斯分类器将司机的先验推断方法纳入到我们的路径规划装置中，其本身是基于分类器装置对路网做模式识别处理后而形成的路径规划方法。本发明利用这种司机对道路网络的实时交通状况的先验推断，构造了贝叶斯分类器来形成对道路网络的优先识别，基于这种优先识别而形成的一种路径规划装置及方法，它可以根据高峰期、非高峰期的先验知识在不同的交通时段中分别给出不同的最优路径。该装置及方法具有良好的实用性，并可以灵活的集成到各种基于道路交通的导航系统中。
文档编号G01C21/34GK102278995SQ20111010664
公开日2011年12月14日 申请日期2011年4月27日 优先权日2011年4月27日
发明者万剑华, 曾喆, 李清泉 申请人:中国石油大学(华东)
专业数控铣床产品供应商
20年生产经验，实力工厂，精工品质，质量有保障
