利索能及
我要发布
收藏
专利号: 2021114777858
申请人: 重庆邮电大学
专利类型:发明专利
专利状态:已下证
更新日期:2026-06-16
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.基于Angle‑Propagation Theta*算法改进的JPS路径优化方法,其特征在于,包括以下步骤:S1,对JPS算法进行栅格顶点地图适配,改进JPS算法的剪枝邻居法则和强迫邻居的判断标准,修改JPS算法的寻路过程,针对栅格顶点地图中障碍物的位置和数量,改进机器人移动路径规则;

S2,通过引入视野三角形与离散函数Route,对传统JPS路径优化策略进行改进;

S3,利用Angle‑Propagation Theta*算法,计算需优化路段的可视角范围,并通过此可视角范围来直接判断新的节点与父节点之间是否存在可达路径,具体包括:S31,当前节点s为障碍物栅格的顶点,且当前栅格的其他邻居顶点z都满足以下条件之一,则当前节点的lb(s)=0;

parent(s)=z                     (1)θ(s,parent(s),z)<0                    (2)θ(s,parent(s),z)=0 AND c(parent(s),z)≤c(parent(s),s)         (3)S32,若当前节点s为障碍物栅格的顶点,且当前栅格的其他邻居顶点z都满足以下条件之一,则当前节点的ub(s)=0;

parent(s)=z                      (4)θ(s,parent(s),z)>0                    (5)θ(s,parent(s),z)=0 AND c(parent(s),z)≤c(parent(s),s)         (6)S33,对于当前节点s的邻节点s',若s'满足以下所有条件:s'∈closedlist                     (7)parent(s)=parent(s')                    (8)s'≠Sstart                       (9)若s节点与s'节点之间满足lb(s')+θ(s,parent(s),s')≤0则lb(s)=max(lb(s),lb(s')+θ(s,parent(s),s'))              (10)若s节点与s'节点之间满足ub(s')+θ(s,parent(s),s')≥0则ub(s)=min(ub(s),ub(s')+θ(s,parent(s),s'))            (11)S34,对于当前节点s的邻节点s',若s'满足以下所有条件:

c(parent(s),s')<c(parent(s),s)                (12)parent(s)≠s'                     (13)若可视角满足θ(s,paret(s),s)<0则

lb(s)=max(lb(s),θ(s,parent(s),s'))               (15)若可视角满足θ(s,paret(s),s)>0则

ub(s)=min(ub(s),θ(s,parent(s),s'))               (16)其中,θ(s,parent(s),s')为当前节点s的父节点parent(s)与当前节点所组成的直线与parent(s)和当前节点的邻居节点s'所组成的直线的夹角,θ(s,parent(s),z)为当前节点s的父节点parent(s)与当前节点所组成的直线与parent(s)和当前节点的同栅格邻居顶点z所组成的直线的夹角,c(parent(s),s)为当前节点s与其父节点parent(s)之间的代价值,c(parent(s),s')为当前节点的邻居节点s'与当前节点的父节点parent(s)之间的代价值,c(parent(s),z)为当前节点的同栅格邻居顶点z与当前节点的父节点parent(s)之间的代价值,closedlist为JPS算法当中的close节点列表,Sstart为路径初始节点;

S4,采用双向优化算法从路径的起始点和目标点同时进行基于Angle‑Propagation Theta*的可视角检索,根据继任搜索点的位置信息,不断更新双方的Route离散函数。

2.根据权利要求1所述基于Angle‑Propagation Theta*算法改进的JPS路径优化方法,其特征在于:所述栅格顶点地图适配包括:S11,路径起始点与目标点位置由栅格中心变更为栅格顶点;

S12,在算法寻路的过程中将邻居栅格变更为邻居节点,节点邻居域由8栅格变为4栅格与8顶点;

S13,JPS算法的强迫邻居和邻居剪枝法则由栅格化变更为节点化,其中剪枝路径由连续栅格变更为连续节点。

3.根据权利要求2所述基于Angle‑Propagation Theta*算法改进的JPS路径优化方法,其特征在于:所述机器人移动路径规则为:(1)若存在单一栅格障碍物情况,允许移动机器人沿障碍物边界行走,但不允许斜向跨越障碍物;

(2)若存在多联合栅格障碍物情况,允许移动机器人沿障碍物整体边界行走,但不允许跨越单栅格障碍物之间的交界边和斜向跨越障碍物;

(3)若存在障碍物与地图边界相接的情况,则不允许出现跨越障碍物与地图边界的交互边。

4.根据权利要求1所述基于Angle‑Propagation Theta*算法改进的JPS路径优化方法,其特征在于:所述剪枝邻居法则为:(1)若当前节点x为起始点,x节点不存在父节点,则不存在邻居剪枝规则,搜索方向为相邻节点的八个方向;

(2)当前节点x为非起始节点,且x节点的父节点parent(x)到x为直线搜索方向,n为x节点的邻居节点,若存在parent(x)到n不经过x的路径,且此路径小于或等于parent(x)经过x到达n的路径,则n节点被剪枝;

(3)当前节点x为非起始节点,且x节点的父节点parent(x)到x为对角线搜索方向,n为x节点的邻居节点,若存在parent(x)到n不经过x的路径,且此路径小于parent(x)经过x到达n的路径,则n节点被剪枝;

所述强迫邻居为:当前节点x的8个邻居中存在障碍物,n为当前节点的非障碍物、非搜索方向上的邻居节点,则x的父节点parent(x)经过x到达n的距离代价比不经过x到达n的任意路径的距离代价要小,则称n为x的强迫邻居。

5.根据权利要求1所述基于Angle‑Propagation Theta*算法改进的JPS路径优化方法,其特征在于:所述步骤S2具体包括,引入视野三角形判断是否存在转折节点位于此视野三角形所覆盖范围之内,并计算转折点与当前节点的父节点之间的代价值G(x),进行比较,选择最小代价值对应的转折点作为最优转折点。

6.根据权利要求5所述基于Angle‑Propagation Theta*算法改进的JPS路径优化方法,其特征在于:所述视野三角形由按照离散路径顺序进行视野线检测的第一条不可达路径与前一条可达路径和原路径组成。

7.根据权利要求6所述基于Angle‑Propagation Theta*算法改进的JPS路径优化方法,其特征在于:所述视野三角形具体通过以下方法确定:S21,设当前跳点为s点,s的父节点为p(s)点,s的路径子跳点为e点;

S22,检测p(s)点与e点之间的可达性,若可达,则丢弃s节点,将e节点的父节点由s变为p(s),路径由原来的p(s)‑>s‑>e改变为p(s)‑>e完成优化;若不可达,则将s节点与e节点之间的路径按照栅格顶点离散化为Route(<s,1,2,3,...,e>),从s节点算起,分别按照顺序计算p(s)与Route(<s,1,2,3,...,e>)内节点的可达性,若遇到第一条不可达路径将其设置为Lm,对应的Route(<s,1,2,3,...,e>)中的节点Rm,Lm‑1为前一离散点可达路径,对应Route(<s,1,2,3,...,e>)中节点Rm‑1,S23,将Lm‑1、Lm与s节点到e节点的原路径所生成的三角形区域设置为视野三角形。

8.根据权利要求1所述基于Angle‑Propagation Theta*算法改进的JPS路径优化方法,其特征在于:所述步骤S4具体包括,S41,选取起始点与目标点作为双方的初始搜索点位;

S42,对于双方搜索点之间进行LOS可达性检测;

S43,若可达,结束算法,若不可达,则继续进行第S44步;

S44,更新双方Route函数,并按照Route函数中所包含的栅格信息,将双方搜点之间的路径离散化;

S45,从双方搜索点开始,按照离散顺序依次计算各节点与搜索点之间的可视角角度范围,并寻找在双方搜索过程中产生的第一条不可达路径Lm,以及不可达路径点Rm;

S46,双方需要在由Lm,Lm‑1以及原路径段组合形成的视野三角形区域内选择最优转向点,并使之继承下一任搜索点;

S47,步骤跳转至S42执行下一轮检索。

9.一种计算机可读存储介质,其存储有计算机程序,其特征在于:所述计算机程序被执行时,可实现权利要求1‑8任一项所述的路径优化方法。