适用于动态环境的LTL‑A*‑A*最优路径规划方法

摘要

本发明公开了一种可应用于动态环境的LTL‑A*‑A*最优路径规划方法，该发明将线性时序逻辑(LTL)能够满足实际应用中复杂的任务需求的优点和A*算法搜索效率高的优点相结合，其主要包括LTL‑A*全局路径寻优和基于A*算法的局部路径寻优两部分。首先，通过LTL‑A*全局路径寻优部分搜索出环境中满足任务需求的最优路径；然后，机器人对搜索得到的全局最优路径进行跟踪，并检测环境信息；最后，当局部环境发生变化，使得全局最优路径中部分路段无法继续通行时，则采用A*算法搜索局部最优路径，绕过无法通行路段后继续沿着全局最优路径运行，完成指定任务。

主权项

一种适用于动态环境的LTL‑A*‑A*最优路径规划方法，具体步骤如下：步骤1：将机器人所在的环境建模为一个加权切换系统模型，加权切换系统是一个元组T:＝(Q,q₀,δ_T,∏,ζ,ω_T)，其中Q为一个有限状态集，即环境中选取的路径节点集；q₀∈Q代表初始状态，即机器人运行的起点；δ_T→2^Q代表切换关系，即环境中各个路径节点之间的连通状况；∏代表原子命题集；ζ:Q→2^∏代表标识函数集；ω代表切换权重且ω＞0，即机器人在环境中任意两路径节点之间运行的成本；在加权切换系统中原子命题代表加权切换系统中各个状态的属性，当且仅当状态q处原子命题π为真时，π∈ζ(q)才成立，若q₂∈δ(q₁)，则q₂为q₁的后续状态；加权切换系统中的一条轨迹(路径)r_T是由T中的有限个状态组成，即r_T＝q₀q₁q₂...，其中对于任意的i≥0都有q_i+1∈δ(q_i)成立，轨迹r_T包含了有限个标识函数o＝o₀o₁o₂...，其中o_i∈ζ(q_i)；步骤2：根据线性时序逻辑理论，利用线性时序逻辑(LTL)公式φ描述移动机器人的复杂任务；遍历任务公式φ＝Fp₁∧Fp₂∧Fp₃，其中，p₁、p₂和p₃代表环境中的节点，∧为布尔算子与操作，则φ表示机器人最终到达p₁、最终到达p₂和最终到达p₃，也就是机器人必须遍历所有我们感兴趣的节点(任务节点)；避障任务公式其中o₁、o₂和o₃表示环境中的障碍物，p₁为任务节点，为布尔算子非操作，则φ表示机器人到达p₁节点之前要避开o₁、o₂和o₃三个障碍物；步骤3：为了将环境信息与任务信息相融合，通过LTL2BA工具包将线性时序任务公式φ转换为任务可行性图表的形式，即Büchi自动机，Büchi自动机是一个元组B:＝(S_B,S_B0,∑_B,δ_B,F_B)；其中，S_B代表一个有限的状态集；S_B0∈S_B代表初始状态；∑_B代表输入的字符表；代表切换函数；代表最终状态集；步骤4：将机器人运行环境对应的加权切换系统T:＝(Q,q₀,δ_T,Π,ζ,ω_T)和任务公式对应的Büchi自动机B:＝(S_B,S_B0,∑_B,δ_B,F_B)做笛卡尔乘积，构建即任务可行网络拓扑P，即P为一个元组(S_P,S_P0,δ_P,w_P,F_P)，其中S_P＝Q×S_B代表状态集；S_P0＝{q₀}×S_B0代表初始状态集；代表切换函数，其定义为当且仅当q_j∈δ_T(q_i)并且s_l∈δ_B(s_k,ζ(q_i))时，(q_j,s_l)∈δ_P((q_i,s_k))成立；ω_P为继承自T的权重，即当(q_j,s_l)∈δ_P((q_j,s_l))时，则ω_P((q_i,s_k),(q_j,s_l))＝ω_T(q_i,q_j)；F_P＝Q×F_B代表一个最终的接收状态集。任务可行网络拓扑通过笛卡尔乘积将环境信息与任务需求相融合，确保了最终寻优所得路径既能够符合环境信息，又能够满足任务需求；步骤5：在步骤4得到的任务可行性网络拓扑上，第一次利用A*算法搜索出全局最优路径，由于任务可行性网络拓扑包含了环境信息和任务信息，所以搜索出来的路径可以保证为全局最优路径，A*算法是一种启发式搜索算法，在搜索过程中通过建立估价函数来判断优先搜索方向，可以很大提高搜索效率；然后把在P图上搜索出来的路径映射回实际环境中得到移动机器人实际的运动路径，即r_P为P图中对应路径，r_T为时间环境T图对应路径，机器人按照r_T进行执行任务；步骤6：根据机器人执行任务过程中的环境变化信息，更新加权切换系统模型，并产生局部任务公式，再次利用A*算法进行局部搜索，获得局部最优路径；规划所得路径为：r_T＝p₁→p₈→p₁₅→p₁₆→p₁₇时，p₁,p₈,p₁₅,p₁₆,p₁₇为环境中的节点，当机器人运行达到节点p₁₅时发现节点p₁₆遇堵，无法通过节点p₁₆到达节点p₁₇，此时，将环境所对应的加权切换系统中节点p₁₆标识为障碍物，得到局部起点为p₁₅到达局部终点p₁₇，途中避开p₁₆的局部任务，然后采用A*算法进行局部搜索，机器人按照所的路径到达p₁₇后，继续按照全局路径执行任务，以此类推，当机器人在运行过程中环境路况发生变化时，则重复采用A*算法进行局部搜索最优路径，直至移动机器人完成指定任务。