一种考虑目标节点时效性的多目标路径规划方法

摘要

一种考虑搜索机器人目标节点时效性的多目标路径规划装置和方法，通过包含路线规划和路径生成在内的两阶段解耦，使用多目标遗传算法来实现考虑路径消耗和节点时效性两个优化目标的路线规划，从而有助于提高有操作者监督的移动机器人的搜索性能，特别是在路径搜索需要考虑节点时效性问题时可以获得更好的搜索表现。

主权项

一种考虑搜索机器人目标节点时效性的多目标路径规划方法，包括以下步骤：加载机器人需要搜索的空间的简易地图；选择目标节点的位置和权重；进行考虑路径消耗和节点时效性两个优化目标的路线规划；如果生成可执行的路线规划序列，进行生成的路线序列中相邻节点间的路径生成；如果所生成的路径存在，返回最优解；其中所述进行考虑路径消耗和节点时效性两个优化目标的路线规划进一步包括：(a)读取目标节点位置和权重；(b)判断步骤(a)中的权重是否为默认值，若是，转入步骤(i)，若不是，转入步骤(c)；(c)读取节点的时效值和衰减系数；(d)在读取的目标节点中，随机选取目标点对(i，j)；(e)计算时间消耗估计函数的值；(f)基于改进的多目标遗传算法进行路线规划；(g)判断是否存在路线规划的解，若存在，转入步骤(h)，若不存在，转入步骤(k)；(h)返回路线规划的最优解；(i)采用传统的旅行商问题(TSP)算法生成路线；(j)判断该路线规划是否存在解，若是，转入步骤(h)，若不存在，转入步骤(k)；(k)返回不存在解时的错误代码；所述基于改进的多目标遗传算法进行路线规划进一步包括：(f.1)染色体编码，将步骤(a)中读取的目标节点进行编码，每条染色体代表一个经过这些目标点并满足传统的旅行商问题(TSP)约束的路线序列的解，其中染色体编码格式为：x＝Rand{1,2,...,n}其中x代表染色体，由(a)中读取的n个目标点的序号产生的随机序列组成；(f.2)产生种群个数为N的随机初始化的初始种群，其中种群中的N个染色体均由(f.1)随机初始化得到；(f.3)初始化遗传代数，将i置为1；(f.4)使用适应度函数计算每个个体的适应度f_fit；(f.5)进行个体的选择，根据步骤(f.4)中得到的每个个体的适应度，从种群中筛选符合要求的个体；(f.6)进行个体间的杂交，其中杂交表示通过改变染色体中部分节点序号的排序，进而获得新的个体；(f.7)进行变异操作，即在本过程中通过随机选取染色体中的两个节点编号进行交换来实现染色体的变异；(f.8)判断遗传代数是否大于给定的最大允许代数I，若是，则转入步骤(f.9)，若不是，则转入步骤(f.10)；(f.9)输出最优个体，即输出规划出的最优的路线序列的解；(f.10)遗传代数增加1，同时转入步骤(f.4)；其中(f.4)中用到的适应度函数具体表示为：$f_{fit}=(1-\gamma ){(1-\frac{{\pi }_i-{\pi }_{\min }}{{\pi }_{\max }-{\pi }_{\min }})}^m+\gamma \left(\frac{\underset{j=1}{\overset{n}{\Sigma }}{(1-\frac{s_{ij}-s_{j_{\min }}}{s_{j_{\max }}-s_{j_{\min }}})}^m\times {ϵ}_j}{\underset{j=1}{\overset{n}{\Sigma }}{ϵ}_j}\right)$其中，π_i为个体x_i的总的路径消耗，π_max和π_min分别表示当前种群中个体所代表的路线序列路径消耗的最大值和最小值，s_ij为个体x_i中从起始节点，节点序号为0，到第j个节点，的时间消耗，其中s_jmax为整个种群中的最大值，s_jmin为整个种群中的最小值，ε＝{ε₁,ε₂,…,ε_n}为目标节点的优先级因子，即权重值，r为分布系数用来平衡总路径距离和时间消耗各自所占的权重；ε的值由以下时效性方程确定：C(t)＝C₀‑v₀βt其中C₀是初始的节点时效值，v₀是默认的衰减速率，β是衰减速率影响因子，代表时效性衰减速率的变化情况，令β＝ε将目标节点的时效性和节点的权重联系起来。