一种车辆运动规划方法和无人车的制作方法
一种车辆运动规划方法和无人车的制作方法
【技术领域】
[0001 ]本发明涉及无人车领域，特别涉及一种无人车运动规划。
【背景技术】
[0002] 无人车/机器人的运动规划模块将抽象的运动目标(起点/终点）、限制(速度/障碍 物）以及其它的指令转化成机器人/无人车可以具体执行的轨迹(从起点到终点，其间满足 各种限制和要求)和实现这个轨迹所对应的控制参数。
[0003] 无人车的运动规划模块需要在所有可以实现的状态中寻找一条最优的路径。所有 可以实现的状态的维度可能很大，因此搜寻最佳路径的算法的搜索空间非常大，受时间和 车载计算机计算能力的限制，寻找最优路径一般不现实。
[0004] 在现有的运动规划算法比如RRT(基于随机采样的算法），无法处理一些危险区域 的回避和安全区域信息，而且区域的危险/安全对应于自动驾驶可以包括各种不能直接表 示的路况经验。
【发明内容】
[0005] 以下给出对一个或更多个方面的简化概述以力图提供对此类方面的基本理解。此 概述不是所有构想到的方面的详尽综览，并且既非旨在指认出所有方面的关键性或决定性 要素亦非试图界定任何或所有方面的范围。其唯一的目的是要以简化形式给出一个或更多 个方面的一些概念以作为稍后给出的更加具体的说明之序。
[0006] 为此，需要提供一种结合经验区域的路径规划方法，让运动规划模块充分利用这 些经验知识提高搜索效率。
[0007] 为实现上述目的，发明人提供了一种车辆运动规划方法，根据η个行走路径更新 经验区域的概率分布，在车辆运动过程中，根据更新后的经验区域的概率分布结合车辆状 态转换的概率计算转移到相邻栅格的概率;根据转移到相邻栅格的概率预扩展随机树，并 作碰撞检验，若通过碰撞检测，则用对应的栅格扩展随机树，并更新当前状态;直至尝试所 有的栅格都无法通过碰撞检测或已到达目的栅格。
[0008] 进一步，所述根据η个实际行走路径更新经验区域的概率分布为：
[0009] 根据η个实际行走路径，获得经验区域内各个栅格s = [sl，...，sK]以及对应的分 布概率μ=[μ1，. . .，yk]，k为经验区域内的栅格个数，取值为1-n;
[0010] 从狄利克雷后验分布取样，然后进行归一化，得到更新后的经验区域的概率分布， 对于栅格k更新后的概率为：
[0012]进一步，所述车辆状态转换的概率，通过下述方法计算：
[0013]状态s转移到状态Y的概率是：
[0015] 其中T(x，y)为从状态x到状态y进行状态转换的次数，为状态栅格x的每个相邻 的状态，N(Xs^ Xs的所有相邻状态的集合，Xs为处于栅格X并且车辆状态为s。
[0016] 进一步，车辆状态转换的概率的计算还包括评估相邻栅格之间的互信息MI，将互 信息MI相对于其相邻栅格是低于设定阈值的状态删除；
[0017] 所述互信息MI为：
[0019] 进一步，所述η个行走路线可以是从行驶日志中获取样本;或人为手工在经验区域 内设定生成的。
[0020] 发明人还提供一种使用上述运动规划方法的无人车，其包括运动规划模块和碰撞 检验t吴块；
[0021] 所述运动检测模块用于根据η个行走路径更新经验区域的概率分布，用于根据根 据更新后的经验区域的概率分布结合车辆状态转换的概率计算转移到相邻栅格的概率;根 据转移到相邻栅格的概率预扩展随机树；
[0022] 所述碰撞检验模块用于碰撞检验。
[0023] 区别于现有技术，上述技术方案本方法将η各实际路径转换为概率表示，并应用于 路径规划方法中，以及根据车辆的状态信息计算转换到对应栅格的概率，让运动规划模块 充分利用这些经验知识提高搜索效率。
【附图说明】
[0024]以下将结合附图来描述所公开的方面，提供附图是为了说明而非限定所公开的方 面，附图中相似的标号标示相似要素，并且在其中：
[0025] 图1为【具体实施方式】的一个实施例中的随机树与现有技术的随机树对比图；
[0026] 图2(a)为一个实施例中的经验区域根据由少至多个的实际路径作为训练样本，分 别对应得到如图从上到下的栅格概率分布图；
[0027] 图2(b)为一个实施例中的经验区域根据由少至多个的实际路径作为训练样本，分 别对应得到如图从上到下的栅格概率分布图；
[0028] 图3为根据经验区域的概率分布为路径规划所需的栅格，空白的栅格表示选中的 栅格，曲线表示最优规划路径；
[0029]图4中左图为未经过互信息筛选的经验区域的概率分布图，图右为经过互信息筛 选后的经验区域的概率分布图，颜色越浅表示概率越大。
【具体实施方式】
[0030]为详细说明技术方案的技术内容、构造特征、所实现目的及效果，以下结合具体实 施例并配合附图详予说明。在以下描述中，出于解释目的阐述了众多的具体细节以提供对 一个或更多个方面的透彻理解。但是显而易见的是，没有这些具体细节也可实践此类方面。
[0031] 为了便于理解本发明，在描述本发明前将以下概念说明：
[0032] 贝叶斯网络：每个状态只跟与之直接相连的状态有关，而跟与它间接相连的状态 没直接关系。在有向图上，两个状态有通路连接，就说明这两个状态是有关的，可能是间接 相关。其可更准确的描述事件之间的相关性。
[0033] 随机树:代表搜索路径，其用于预测车辆在经验区域内的行走路径，随机树由各搜 索节点(栅格)构成，节点具有对应的车辆状态。
[0034] 发明人提供一种车辆运动规划方法，其根据η个行走路径更新经验区域的概率分 布，在车辆运动过程中，根据更新后的经验区域的概率分布结合车辆状态转换的概率计算 转移到相邻栅格的概率;根据转移到相邻栅格的概率预扩展随机树，并作碰撞检验，若通过 碰撞检测，则用对应的栅格扩展随机树，并更新当前状态;直至尝试所有的栅格都无法通过 碰撞检测或已到达目的栅格。如图1所示，图中左图为采用现有技术得到的随机树搜索节 点，右图为采用本方法的搜索节点
[0035]该方法用伪代码表示如下：
[0036] 经验区域随机树算法(β)
[0037] 树.初始化随机树〇
[0038] 当计数器〈最大采样数运行 [0039] 米样-生成随机米样0
[0040] 节点-树.找到最近节点(采样）
[0041] 如果节点在经验区域内（节点）那么
[0042] 采样-生成经验区域采样(节点）> 丢弃原有采样 [0043]完成如果
[0044]新状态-树·扩展(米样）
[0045] 如果无碰撞(新状态）那么 >碰撞检测 [0046]树.添加新节点(新状态）
[0047]完成如果
[0048]如果到达目标(新状态）那么 [0049] 状态-成功 [0050]返回（状态，树）
[0051 ]完成如果
[0052] 计数器-计数器+1
[0053] 完成当
[0054] 状态-失败 [0055]返回（状态，空）
[0056] 完成程序
[0057] 区别于现有技术，本方法将η各实际路径转换为概率表示，并应用于路径规划方法 中，以及根据车辆的状态信息计算转换到对应栅格的概率，让运动规划模块充分利用这些 经验知识提高搜索效率。
[0058] 在初始化时，若有足够多个的采样路径，则执行本方法。经验区域为具有经验路径 的区域，也为待预测行走路径的区域。对于在经验区域内，已知具有η个经过区域的实例路 径（即η个经验路径）。将经验区域栅格化，设其具有k各栅格，则经验区域内的栅格具有k个 状态的随机变量。
[0059]栅格s=[S1，. . .，sk]其对应的出现概率为μ=[μL，. . .，M]，经验区域内各栅格的 数量分布是一个多项分布：
[0061]多项分布的共辄先验分布为狄利克雷分布，其定义为：
[0063] 其中，azlicn，...，ακ]是随机变量出现的"频数"。α为归一化项(概率分布的总和为 1)，α的初始值满足狄氏参数的先验分布。η个经验路径的状态分布集合表示为Ζ= [Ζ1，...， ζκ]。其中zk对应于状态k的出现次数。
[0064] 后验分布(最终在运动规划中使用的分布函数）：
[0065] ρ(μ|Ζ，α) (3)
[0066]其中Ζ为η各实际路径中各个栅格所出现次数所组成的数据集合，将先验分布与似 然函数相乘。
[0068] 最终后验分布概率符合狄利克雷分布：
[0069] p(y|Z,a)=Dir(y|a+Z) (5)
[0070] 从狄利克雷后验分布取样，使用单位的伽玛分布得出的K个独立的随机样本：
[0071] yk= Γ (ak+zk，l) (6)
[0072] 并进行归一化，可以得到：
[
[0074] 用上述μ'我们就可以将其应用在多项分布中，以此抽取所需要的所要的 栅格，图2 (a)和图2(b)分别展示了两个不同的区域随着训练样本的增加(从上到下，训练样本逐渐增 加），狄利克雷后验分布变化的情况，颜色深的代表低概率区域，颜色浅的代表高概率区域。 一个具体的例子中，经验区域的训练过程。
[0075] 根据经验区域的概率分布，以此抽取所需要的栅格，如图3所示，空白区域为路径 规划所需的栅格。
[0076] 在实际运用中，必须考虑路径的空间和时间的一致性。从经验区域的静态分布进 行抽样能得到更好的空间规划，为了模拟参考路径的在时间上状态改变，我们假设经验区 域内格子会和周边的四个方格相连，在经验区域内，状态s转移到状态s'的概率是：
[0078] 其中T(x，y)为从状态x到状态y进行状态转换的次数，为栅格x的每个相邻的状 态，N(Xs^Xs的所有相邻状态的集合， Xs为处于栅格X并且车辆状态为s。
[0079] 随机树中的一个节点是经验区域的下生成的，而且节点会作为进一步生长的基准 节点，那么下一个采样点就会根据状态转换的概率和更新后的经验区域的概率分布，生成 邻近的采样点，进一步扩展随机树，直到达到目的地或当前四周具有路障(无法通过碰撞检 测)。
[0080] 在一些实施例中，如果训练数据不足(实际行走路径数据不足)从而没有观察到 某个特定的转换，转移矩阵里的对应项就会为〇。为了预测的状态转移概率不那么极端，我 们假设毎个转换概率都有一个狄利克雷先验分布：
[0082] 其中α对应状态转换的观察。因此，对μ的计算如前所述，为：
[0083] yk= Γ (ak-l) (10)
[0084] 在一些实施例中，还通过评估在栅格相邻状态之间的互信息(MI)来删除一些无效 的状态转移，互信息(MI):
[0086] 将其信息相对于其相邻栅格低于某一设置值的状态删除。如图3所示的一个实施 例中，图左边为未经修正的经验区域，而右边经过修正的经验区域边缘的互信息(MI)低的 单元格被去除了。
[0087] 经验区域有其给定的边界，在经验区域某些部分的信息量可能不大，在规划期间， 该信息量低的区域通过上述规划方法得出的规划路线可能不是最优的。在这种情况下，利 用经验区域几乎没有获得任何好处，因此采用互信息剔除无经验信息的区间。这样可以进 一步减低计算量级，提高检索效率。
[0088] 本发明还提供一种使用上述方法的设备，包括运动规划模块和碰撞检验模块;所 述运动检测模块用于根据η个行走路径更新经验区域的概率分布，用于根据根据更新后的 经验区域的概率分布结合车辆状态转换的概率计算转移到相邻栅格的概率;根据转移到相 邻栅格的概率预扩展随机树;所述碰撞检验模块用于碰撞检验。
[0089] 需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实 体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存 在任何这种实际的关系或者顺序。而且，术语"包括"、"包含"或者其任何其他变体意在涵盖 非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者终端设备不仅包括那些 要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者终 端设备所固有的要素。在没有更多限制的情况下，由语句"包括……"或"包含……"限定的 要素，并不排除在包括所述要素的过程、方法、物品或者终端设备中还存在另外的要素。此 外，在本文中，"大于"、"小于"、"超过"等理解为不包括本数；"以上"、"以下"、"以内"等理解 为包括本数。
[0090] 本领域内的技术人员应明白，上述各实施例可提供为方法、装置、或计算机程序产 品。这些实施例可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例 的形式。上述各实施例涉及的方法中的全部或部分步骤可以通过程序来指令相关的硬件来 完成，所述的程序可以存储于计算机设备可读取的存储介质中，用于执行上述各实施例方 法所述的全部或部分步骤。所述计算机设备，包括但不限于:个人计算机、服务器、通用计算 机、专用计算机、网络设备、嵌入式设备、可编程设备、智能移动终端、智能家居设备、穿戴式 智能设备、车载智能设备等;所述的存储介质，包括但不限于:RAM、R0M、磁碟、磁带、光盘、闪 存、U盘、移动硬盘、存储卡、记忆棒、网络服务器存储、网络云存储等。
[0091] 上述各实施例是参照根据实施例所述的方法、设备（系统）、和计算机程序产品的 流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每 一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机 程序指令到计算机设备的处理器以产生一个机器，使得通过计算机设备的处理器执行的指 令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的 功能的装置。
[0092] 这些计算机程序指令也可存储在能引导计算机设备以特定方式工作的计算机设 备可读存储器中，使得存储在该计算机设备可读存储器中的指令产生包括指令装置的制造 品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指 定的功能。
[0093] 这些计算机程序指令也可装载到计算机设备上，使得在计算机设备上执行一系列 操作步骤以产生计算机实现的处理，从而在计算机设备上执行的指令提供用于实现在流程 图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
[0094]尽管已经对上述各实施例进行了描述，但本领域内的技术人员一旦得知了基本创 造性概念，则可对这些实施例做出另外的变更和修改，所以以上所述仅为本发明的实施例， 并非因此限制本发明的专利保护范围，凡是利用本发明说明书及附图内容所作的等效结构 或等效流程变换，或直接或间接运用在其他相关的技术领域，均同理包括在本发明的专利 保护范围之内。
【主权项】
1. 一种车辆运动规划方法，其特征在于，包括步骤： S110、根据η个行走路径更新经验区域的概率分布； S120、在车辆运动过程中，根据更新后的经验区域的概率分布结合车辆状态转换的概 率计算车辆转移到相邻栅格的概率； S130、根据转移到相邻栅格的概率预扩展当前车辆行走路径对应的随机树，并对车辆 作碰撞检验，若通过碰撞检验，则用对应的栅格扩展随机树，车辆移动到对应栅格并更新当 前车辆的状态， S140、继续通过上述步骤S120至S130扩展当前车辆行走路径对应的随机树，直至尝试 车辆所处栅格的周围的所有栅格都无法通过碰撞检测或已到达目的栅格。2. 如权利要求1所述的一种车辆运动规划方法，其特征在于，所述根据η个行走路径更 新经验区域的概率分布，为： 根据η个实际行走路径，获得经验区域内各个栅格s = [S1，...，sk]以及对应的分布概率 μ=[μι, . . .，yk]，k为经验区域内的栅格个数，取值为[l，n]; 从经验区域的狄利克雷后验分布取样，然后进行归一化，得到更新后的经验区域的概 率分布，对于栅格k更新后的概率为：3. 如权利要求1所述的一种车辆运动规划方法，其特征在于，所述车辆状态转换的概 率，通过下述方法计算： 车辆位于栅格X，则车辆从状态S转移到状态Y的概率是：其中T(x，y)为从状态X到状态y进行状态转换的次数，为栅格X的每个相邻的状态，N (Xs)为Xs的所有相邻状态的集合，Xs为处于栅格X并且车辆状态为s。4. 如权利要求1所述的一种车辆运动规划方法，其特征在于，车辆状态转换的概率的计 算还包括评估相邻栅格之间的互信息MI，将互信息MI相对于其相邻栅格是低于设定阈值的 状态删除； 所述车辆状态从X转移为车辆状态y的互信息MI为：5. 如权利要求1所述的一种车辆运动规划方法，其特征在于，所述η个行走路线为从行 驶日志中获取样本;或人为手工在经验区域内设定生成的。6. -种无人车，其特征在于，包括运动规划模块和碰撞检验模块； 所述运动检测模块用于根据η个行走路径更新经验区域的概率分布，用于根据更新后 的经验区域的概率分布结合车辆状态转换的概率计算转移到相邻栅格的概率，用于根据转 移到相邻栅格的概率预扩展随机树;所述碰撞检验模块用于碰撞检验。
【专利摘要】发明人提供一种车辆运动规划方法和无人车；本发明涉及无人车领域，特别涉及一种无人车运动规划；其根据n个行走路径更新经验区域的概率分布，在车辆运动过程中，根据更新后的经验区域的概率分布结合车辆状态转换的概率计算转移到相邻栅格的概率；根据转移到相邻栅格的概率预扩展随机树，并作碰撞检验，若通过碰撞检测，则用对应的栅格扩展随机树，并更新当前状态；直至尝试所有的栅格都无法通过碰撞检测或已到达目的栅格。本方法将n各实际路径转换为概率表示，并应用于路径规划方法中，以及根据车辆的状态信息计算转换到对应栅格的概率，让运动规划模块充分利用这些经验知识提高搜索效率。
【IPC分类】G05D1/02
【公开号】CN105487537
【申请号】CN201510750059
【发明人】潘晨劲, 赵江宜
【申请人】福州华鹰重工机械有限公司
【公开日】2016年4月13日
【申请日】2015年11月6日
【技术领域】
[0001 ]本发明涉及无人车领域，特别涉及一种无人车运动规划。
【背景技术】
[0002] 无人车/机器人的运动规划模块将抽象的运动目标(起点/终点）、限制(速度/障碍 物）以及其它的指令转化成机器人/无人车可以具体执行的轨迹(从起点到终点，其间满足 各种限制和要求)和实现这个轨迹所对应的控制参数。
[0003] 无人车的运动规划模块需要在所有可以实现的状态中寻找一条最优的路径。所有 可以实现的状态的维度可能很大，因此搜寻最佳路径的算法的搜索空间非常大，受时间和 车载计算机计算能力的限制，寻找最优路径一般不现实。
[0004] 在现有的运动规划算法比如RRT(基于随机采样的算法），无法处理一些危险区域 的回避和安全区域信息，而且区域的危险/安全对应于自动驾驶可以包括各种不能直接表 示的路况经验。
【发明内容】
[0005] 以下给出对一个或更多个方面的简化概述以力图提供对此类方面的基本理解。此 概述不是所有构想到的方面的详尽综览，并且既非旨在指认出所有方面的关键性或决定性 要素亦非试图界定任何或所有方面的范围。其唯一的目的是要以简化形式给出一个或更多 个方面的一些概念以作为稍后给出的更加具体的说明之序。
[0006] 为此，需要提供一种结合经验区域的路径规划方法，让运动规划模块充分利用这 些经验知识提高搜索效率。
[0007] 为实现上述目的，发明人提供了一种车辆运动规划方法，根据η个行走路径更新 经验区域的概率分布，在车辆运动过程中，根据更新后的经验区域的概率分布结合车辆状 态转换的概率计算转移到相邻栅格的概率;根据转移到相邻栅格的概率预扩展随机树，并 作碰撞检验，若通过碰撞检测，则用对应的栅格扩展随机树，并更新当前状态;直至尝试所 有的栅格都无法通过碰撞检测或已到达目的栅格。
[0008] 进一步，所述根据η个实际行走路径更新经验区域的概率分布为：
[0009] 根据η个实际行走路径，获得经验区域内各个栅格s = [sl，...，sK]以及对应的分 布概率μ=[μ1，. . .，yk]，k为经验区域内的栅格个数，取值为1-n;
[0010] 从狄利克雷后验分布取样，然后进行归一化，得到更新后的经验区域的概率分布， 对于栅格k更新后的概率为：
[0012]进一步，所述车辆状态转换的概率，通过下述方法计算：
[0013]状态s转移到状态Y的概率是：
[0015] 其中T(x，y)为从状态x到状态y进行状态转换的次数，为状态栅格x的每个相邻 的状态，N(Xs^ Xs的所有相邻状态的集合，Xs为处于栅格X并且车辆状态为s。
[0016] 进一步，车辆状态转换的概率的计算还包括评估相邻栅格之间的互信息MI，将互 信息MI相对于其相邻栅格是低于设定阈值的状态删除；
[0017] 所述互信息MI为：
[0019] 进一步，所述η个行走路线可以是从行驶日志中获取样本;或人为手工在经验区域 内设定生成的。
[0020] 发明人还提供一种使用上述运动规划方法的无人车，其包括运动规划模块和碰撞 检验t吴块；
[0021] 所述运动检测模块用于根据η个行走路径更新经验区域的概率分布，用于根据根 据更新后的经验区域的概率分布结合车辆状态转换的概率计算转移到相邻栅格的概率;根 据转移到相邻栅格的概率预扩展随机树；
[0022] 所述碰撞检验模块用于碰撞检验。
[0023] 区别于现有技术，上述技术方案本方法将η各实际路径转换为概率表示，并应用于 路径规划方法中，以及根据车辆的状态信息计算转换到对应栅格的概率，让运动规划模块 充分利用这些经验知识提高搜索效率。
【附图说明】
[0024]以下将结合附图来描述所公开的方面，提供附图是为了说明而非限定所公开的方 面，附图中相似的标号标示相似要素，并且在其中：
[0025] 图1为【具体实施方式】的一个实施例中的随机树与现有技术的随机树对比图；
[0026] 图2(a)为一个实施例中的经验区域根据由少至多个的实际路径作为训练样本，分 别对应得到如图从上到下的栅格概率分布图；
[0027] 图2(b)为一个实施例中的经验区域根据由少至多个的实际路径作为训练样本，分 别对应得到如图从上到下的栅格概率分布图；
[0028] 图3为根据经验区域的概率分布为路径规划所需的栅格，空白的栅格表示选中的 栅格，曲线表示最优规划路径；
[0029]图4中左图为未经过互信息筛选的经验区域的概率分布图，图右为经过互信息筛 选后的经验区域的概率分布图，颜色越浅表示概率越大。
【具体实施方式】
[0030]为详细说明技术方案的技术内容、构造特征、所实现目的及效果，以下结合具体实 施例并配合附图详予说明。在以下描述中，出于解释目的阐述了众多的具体细节以提供对 一个或更多个方面的透彻理解。但是显而易见的是，没有这些具体细节也可实践此类方面。
[0031] 为了便于理解本发明，在描述本发明前将以下概念说明：
[0032] 贝叶斯网络：每个状态只跟与之直接相连的状态有关，而跟与它间接相连的状态 没直接关系。在有向图上，两个状态有通路连接，就说明这两个状态是有关的，可能是间接 相关。其可更准确的描述事件之间的相关性。
[0033] 随机树:代表搜索路径，其用于预测车辆在经验区域内的行走路径，随机树由各搜 索节点(栅格)构成，节点具有对应的车辆状态。
[0034] 发明人提供一种车辆运动规划方法，其根据η个行走路径更新经验区域的概率分 布，在车辆运动过程中，根据更新后的经验区域的概率分布结合车辆状态转换的概率计算 转移到相邻栅格的概率;根据转移到相邻栅格的概率预扩展随机树，并作碰撞检验，若通过 碰撞检测，则用对应的栅格扩展随机树，并更新当前状态;直至尝试所有的栅格都无法通过 碰撞检测或已到达目的栅格。如图1所示，图中左图为采用现有技术得到的随机树搜索节 点，右图为采用本方法的搜索节点
[0035]该方法用伪代码表示如下：
[0036] 经验区域随机树算法(β)
[0037] 树.初始化随机树〇
[0038] 当计数器〈最大采样数运行 [0039] 米样-生成随机米样0
[0040] 节点-树.找到最近节点(采样）
[0041] 如果节点在经验区域内（节点）那么
[0042] 采样-生成经验区域采样(节点）> 丢弃原有采样 [0043]完成如果
[0044]新状态-树·扩展(米样）
[0045] 如果无碰撞(新状态）那么 >碰撞检测 [0046]树.添加新节点(新状态）
[0047]完成如果
[0048]如果到达目标(新状态）那么 [0049] 状态-成功 [0050]返回（状态，树）
[0051 ]完成如果
[0052] 计数器-计数器+1
[0053] 完成当
[0054] 状态-失败 [0055]返回（状态，空）
[0056] 完成程序
[0057] 区别于现有技术，本方法将η各实际路径转换为概率表示，并应用于路径规划方法 中，以及根据车辆的状态信息计算转换到对应栅格的概率，让运动规划模块充分利用这些 经验知识提高搜索效率。
[0058] 在初始化时，若有足够多个的采样路径，则执行本方法。经验区域为具有经验路径 的区域，也为待预测行走路径的区域。对于在经验区域内，已知具有η个经过区域的实例路 径（即η个经验路径）。将经验区域栅格化，设其具有k各栅格，则经验区域内的栅格具有k个 状态的随机变量。
[0059]栅格s=[S1，. . .，sk]其对应的出现概率为μ=[μL，. . .，M]，经验区域内各栅格的 数量分布是一个多项分布：
[0061]多项分布的共辄先验分布为狄利克雷分布，其定义为：
[0063] 其中，azlicn，...，ακ]是随机变量出现的"频数"。α为归一化项(概率分布的总和为 1)，α的初始值满足狄氏参数的先验分布。η个经验路径的状态分布集合表示为Ζ= [Ζ1，...， ζκ]。其中zk对应于状态k的出现次数。
[0064] 后验分布(最终在运动规划中使用的分布函数）：
[0065] ρ(μ|Ζ，α) (3)
[0066]其中Ζ为η各实际路径中各个栅格所出现次数所组成的数据集合，将先验分布与似 然函数相乘。
[0068] 最终后验分布概率符合狄利克雷分布：
[0069] p(y|Z,a)=Dir(y|a+Z) (5)
[0070] 从狄利克雷后验分布取样，使用单位的伽玛分布得出的K个独立的随机样本：
[0071] yk= Γ (ak+zk，l) (6)
[0072] 并进行归一化，可以得到：
[
[0074] 用上述μ'我们就可以将其应用在多项分布中，以此抽取所需要的所要的 栅格，图2 (a)和图2(b)分别展示了两个不同的区域随着训练样本的增加(从上到下，训练样本逐渐增 加），狄利克雷后验分布变化的情况，颜色深的代表低概率区域，颜色浅的代表高概率区域。 一个具体的例子中，经验区域的训练过程。
[0075] 根据经验区域的概率分布，以此抽取所需要的栅格，如图3所示，空白区域为路径 规划所需的栅格。
[0076] 在实际运用中，必须考虑路径的空间和时间的一致性。从经验区域的静态分布进 行抽样能得到更好的空间规划，为了模拟参考路径的在时间上状态改变，我们假设经验区 域内格子会和周边的四个方格相连，在经验区域内，状态s转移到状态s'的概率是：
[0078] 其中T(x，y)为从状态x到状态y进行状态转换的次数，为栅格x的每个相邻的状 态，N(Xs^Xs的所有相邻状态的集合， Xs为处于栅格X并且车辆状态为s。
[0079] 随机树中的一个节点是经验区域的下生成的，而且节点会作为进一步生长的基准 节点，那么下一个采样点就会根据状态转换的概率和更新后的经验区域的概率分布，生成 邻近的采样点，进一步扩展随机树，直到达到目的地或当前四周具有路障(无法通过碰撞检 测)。
[0080] 在一些实施例中，如果训练数据不足(实际行走路径数据不足)从而没有观察到 某个特定的转换，转移矩阵里的对应项就会为〇。为了预测的状态转移概率不那么极端，我 们假设毎个转换概率都有一个狄利克雷先验分布：
[0082] 其中α对应状态转换的观察。因此，对μ的计算如前所述，为：
[0083] yk= Γ (ak-l) (10)
[0084] 在一些实施例中，还通过评估在栅格相邻状态之间的互信息(MI)来删除一些无效 的状态转移，互信息(MI):
[0086] 将其信息相对于其相邻栅格低于某一设置值的状态删除。如图3所示的一个实施 例中，图左边为未经修正的经验区域，而右边经过修正的经验区域边缘的互信息(MI)低的 单元格被去除了。
[0087] 经验区域有其给定的边界，在经验区域某些部分的信息量可能不大，在规划期间， 该信息量低的区域通过上述规划方法得出的规划路线可能不是最优的。在这种情况下，利 用经验区域几乎没有获得任何好处，因此采用互信息剔除无经验信息的区间。这样可以进 一步减低计算量级，提高检索效率。
[0088] 本发明还提供一种使用上述方法的设备，包括运动规划模块和碰撞检验模块;所 述运动检测模块用于根据η个行走路径更新经验区域的概率分布，用于根据根据更新后的 经验区域的概率分布结合车辆状态转换的概率计算转移到相邻栅格的概率;根据转移到相 邻栅格的概率预扩展随机树;所述碰撞检验模块用于碰撞检验。
[0089] 需要说明的是，在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实 体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存 在任何这种实际的关系或者顺序。而且，术语"包括"、"包含"或者其任何其他变体意在涵盖 非排他性的包含，从而使得包括一系列要素的过程、方法、物品或者终端设备不仅包括那些 要素，而且还包括没有明确列出的其他要素，或者是还包括为这种过程、方法、物品或者终 端设备所固有的要素。在没有更多限制的情况下，由语句"包括……"或"包含……"限定的 要素，并不排除在包括所述要素的过程、方法、物品或者终端设备中还存在另外的要素。此 外，在本文中，"大于"、"小于"、"超过"等理解为不包括本数；"以上"、"以下"、"以内"等理解 为包括本数。
[0090] 本领域内的技术人员应明白，上述各实施例可提供为方法、装置、或计算机程序产 品。这些实施例可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例 的形式。上述各实施例涉及的方法中的全部或部分步骤可以通过程序来指令相关的硬件来 完成，所述的程序可以存储于计算机设备可读取的存储介质中，用于执行上述各实施例方 法所述的全部或部分步骤。所述计算机设备，包括但不限于:个人计算机、服务器、通用计算 机、专用计算机、网络设备、嵌入式设备、可编程设备、智能移动终端、智能家居设备、穿戴式 智能设备、车载智能设备等;所述的存储介质，包括但不限于:RAM、R0M、磁碟、磁带、光盘、闪 存、U盘、移动硬盘、存储卡、记忆棒、网络服务器存储、网络云存储等。
[0091] 上述各实施例是参照根据实施例所述的方法、设备（系统）、和计算机程序产品的 流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每 一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机 程序指令到计算机设备的处理器以产生一个机器，使得通过计算机设备的处理器执行的指 令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的 功能的装置。
[0092] 这些计算机程序指令也可存储在能引导计算机设备以特定方式工作的计算机设 备可读存储器中，使得存储在该计算机设备可读存储器中的指令产生包括指令装置的制造 品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指 定的功能。
[0093] 这些计算机程序指令也可装载到计算机设备上，使得在计算机设备上执行一系列 操作步骤以产生计算机实现的处理，从而在计算机设备上执行的指令提供用于实现在流程 图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
[0094]尽管已经对上述各实施例进行了描述，但本领域内的技术人员一旦得知了基本创 造性概念，则可对这些实施例做出另外的变更和修改，所以以上所述仅为本发明的实施例， 并非因此限制本发明的专利保护范围，凡是利用本发明说明书及附图内容所作的等效结构 或等效流程变换，或直接或间接运用在其他相关的技术领域，均同理包括在本发明的专利 保护范围之内。
【主权项】
1. 一种车辆运动规划方法，其特征在于，包括步骤： S110、根据η个行走路径更新经验区域的概率分布； S120、在车辆运动过程中，根据更新后的经验区域的概率分布结合车辆状态转换的概 率计算车辆转移到相邻栅格的概率； S130、根据转移到相邻栅格的概率预扩展当前车辆行走路径对应的随机树，并对车辆 作碰撞检验，若通过碰撞检验，则用对应的栅格扩展随机树，车辆移动到对应栅格并更新当 前车辆的状态， S140、继续通过上述步骤S120至S130扩展当前车辆行走路径对应的随机树，直至尝试 车辆所处栅格的周围的所有栅格都无法通过碰撞检测或已到达目的栅格。2. 如权利要求1所述的一种车辆运动规划方法，其特征在于，所述根据η个行走路径更 新经验区域的概率分布，为： 根据η个实际行走路径，获得经验区域内各个栅格s = [S1，...，sk]以及对应的分布概率 μ=[μι, . . .，yk]，k为经验区域内的栅格个数，取值为[l，n]; 从经验区域的狄利克雷后验分布取样，然后进行归一化，得到更新后的经验区域的概 率分布，对于栅格k更新后的概率为：3. 如权利要求1所述的一种车辆运动规划方法，其特征在于，所述车辆状态转换的概 率，通过下述方法计算： 车辆位于栅格X，则车辆从状态S转移到状态Y的概率是：其中T(x，y)为从状态X到状态y进行状态转换的次数，为栅格X的每个相邻的状态，N (Xs)为Xs的所有相邻状态的集合，Xs为处于栅格X并且车辆状态为s。4. 如权利要求1所述的一种车辆运动规划方法，其特征在于，车辆状态转换的概率的计 算还包括评估相邻栅格之间的互信息MI，将互信息MI相对于其相邻栅格是低于设定阈值的 状态删除； 所述车辆状态从X转移为车辆状态y的互信息MI为：5. 如权利要求1所述的一种车辆运动规划方法，其特征在于，所述η个行走路线为从行 驶日志中获取样本;或人为手工在经验区域内设定生成的。6. -种无人车，其特征在于，包括运动规划模块和碰撞检验模块； 所述运动检测模块用于根据η个行走路径更新经验区域的概率分布，用于根据更新后 的经验区域的概率分布结合车辆状态转换的概率计算转移到相邻栅格的概率，用于根据转 移到相邻栅格的概率预扩展随机树;所述碰撞检验模块用于碰撞检验。
【专利摘要】发明人提供一种车辆运动规划方法和无人车；本发明涉及无人车领域，特别涉及一种无人车运动规划；其根据n个行走路径更新经验区域的概率分布，在车辆运动过程中，根据更新后的经验区域的概率分布结合车辆状态转换的概率计算转移到相邻栅格的概率；根据转移到相邻栅格的概率预扩展随机树，并作碰撞检验，若通过碰撞检测，则用对应的栅格扩展随机树，并更新当前状态；直至尝试所有的栅格都无法通过碰撞检测或已到达目的栅格。本方法将n各实际路径转换为概率表示，并应用于路径规划方法中，以及根据车辆的状态信息计算转换到对应栅格的概率，让运动规划模块充分利用这些经验知识提高搜索效率。
【IPC分类】G05D1/02
【公开号】CN105487537
【申请号】CN201510750059
【发明人】潘晨劲, 赵江宜
【申请人】福州华鹰重工机械有限公司
【公开日】2016年4月13日
【申请日】2015年11月6日
最新回复(0)