欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2022104449974
申请人: 郑州大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种多模态多目标的路径规划方法,其特征在于,包括如下步骤:

步骤1,对原始栅格地图数据进行建模,将其转化为带权重的无向图;

步骤2,根据无向图求解邻接矩阵,将地图中目标值的信息存入邻接矩阵中;

步骤3,进行多模态多目标Dijkstra算法中变量的定义及初始化;具体步骤为:S为节点状态,节点的状态S为1则代表已找到起点到该节点的最小路,节点的状态S为0则代表还未找到起点到该节点的最小路;若一个节点的状态S被置为1,则代表已经找到了至少一条从起点到该点的最小路,则此时起点到该节点最小路对应的目标值的帕累托排序的第一前沿已经初步确定;

dist存放起点到其他各个节点的最小路对应的目标值,其中dist的第i列存放起点到节点i的最小路的目标值;由于dist的第i列可能不止一行,且可能存在多行相同的目标值,若存在多行相同的目标值则代表该目标值对应多条最小路,即它是节点i的一个多模态最优解;将dist的第i列称为节点i的dist;

prev为前节点,存放起点到其他各个节点的最小路对应的前一个节点,其中prev的第i列存放起点到节点i的最小路中节点i的前一个节点;由于prev的第i列可能不止一行,且可能存在多行相同的前节点,若存在多行相同的前节点则代表该前节点对应节点i的多条最小路,即节点i的最小路中有多条路需经过该前节点才能到达节点i,将prev的第i列称为节点i的前节点prev;

candidate为候选者,存放暂时的dist;

hx为候选,存放每次找到的dist的帕累托第一前沿中的目标值对应的节点序号;

u,节点u称作循环的起点,节点u是hx中第一个状态S为0的节点,第一次循环除外;

plus,存放起点经过节点u到节点i的最小路的目标值;在循环的过程中,plus会不断被更新,即节点i不同则plus也不相同;

n,地图中节点的个数;

对上述变量进行初始化,初始状态下,节点START的状态S为1,其余节点的状态S均为0;节点的dist均为无穷大;prev、candidate、hx、plus初始状态均为空;u初始状态为START;

步骤4:使用多模态多目标Dijkstra算法、邻接矩阵及初始化变量进行路径规划,具体步骤为:步骤4-1,输入邻接矩阵m及起点的节点序号,首先对dist、prev、S、u分别进行初始化,将起点与起点的目标值记为起点自身的目标值,即m(start,start);将节点的prev均置为0;将其余节点的目标值记为无穷大;令节点的状态S均置为0;

步骤4-2,将dist中的目标值放入candidate中,对candidate中的目标值进行帕累托排序,取出帕累托第一前沿将其对应的节点序号存入hx中;然后取出第一个状态S为0的节点,将该节点的序号赋给u,令S(u)等于1;由于循环之前会对dist进行初始化,所以第一次循环时节点u一定是起点start;

步骤4-3,根据邻接矩阵进行遍历,i从1开始,每次增加1,直到i等于n;计算起点到其他节点的目标值plus=dist(:,u)+m(u,i)+dist(i,i),然后对dist的第i列和plus中的目标值进行帕累托排序,找到帕累托第一前沿,对节点i的最小路的目标值dist(:,i)进行更新,将帕累托第一前沿所得到的目标值存入dist(:,i)中,并相应地将帕累托第一前沿中每一个目标值对应的最小路中的节点i的前一个节点存放在prev的第i列中;当i等于n时,dist更新完毕,第一次循环结束;

步骤4-4,将dist中的目标值放入candidate中,对candidate中的目标值进行帕累托排序,取出帕累托第一前沿将其对应的节点序号存入hx中;取出第一个状态S为0的节点,将该节点的序号赋给u,令S(u)等于1;根据邻接矩阵进行遍历,计算从起点经过节点u到节点i的最小路的目标值plus,plus=dist(:,u)+m(u,i)+m(i,i),然后对dist的第i列和plus中的目标值进行帕累托排序,找到帕累托第一前沿,对节点i的最小路的目标值dist(:,i)进行更新,将帕累托第一前沿所得到的目标值存入dist(:,i)中,并相应地将帕累托第一前沿中每一个目标值对应的最小路中的节点i的前一个节点存放在prev的第i列中;当i等于n时,dist更新完毕,第二次循环结束;

步骤4-5,重复步骤4-4的操作,直至所有节点的状态S均为1,算法结束;至此dist中存放了起点到其他各个节点的所有最小路的目标值,prev中相应地存放了目标值对应的最小路的前节点。

2.根据权利要求1所述的一种多模态多目标的路径规划方法,其特征在于,所述无向图的建模过程包括如下步骤:步骤1-1、找到原始栅格地图数据中的节点,生成节点集合A;

步骤1-2、对节点集合A所有节点进行编号,记作index

步骤1-3、初始化i=1,空集合D,两两节点间边的编号index

步骤1-4、找到对应地图数据中起点START,即index

步骤1-5、根据以下流程求解节点两两之间的路径目标值:

ifβ

计算节点i到其相邻可行节点j的路径目标值d

将d

else转到步骤1-4,直至S

End

其中,β为判断地图区域是否可行的指标;

步骤1-6、判断i是否大于等于n,若是:执行下一步,若否:i=i+1,并转到步骤1-4;

步骤1-7、对无向图中不是相邻可行节点的两两节点的路径进行权重赋值:各个目标值均为无穷大如[inf,inf,inf];

步骤1-8、当节点集合A中的节点编号index

3.根据权利要求1所述的一种多模态多目标的路径规划方法,其特征在于,步骤2中根据无向图建模过程中得出的相关数据来求解邻接矩阵的步骤为:根据D[边序号,边两端节点,边,边的目标值],来求出邻接矩阵m;邻接矩阵m是一个n阶对称矩阵,其中n代表地图中节点的个数,D_all_input[i,j]表示序号为i的节点与序号为j的节点之间边的权值;若i等于j,则D_all_input表示节点i的目标值;若节点i与节点j不属于各自可行方向上的相邻节点,则D_all_input[i,j]为无穷大;然后将D_all_input变为对称矩阵,即得到邻接矩阵m。