基于单链序贯回溯Q学的移动机器人路径规划算法

摘要

本发明提出了一种基于单链序贯回溯Q学的移动机器人路径规划算法，是使用栅格法表示二维环境，每块环境区域都对应一个离散的位置表示，移动机器人在某一时刻的状态就表示为机器人所在环境位置，移动机器人的每一步搜索，都以非确定性马尔科夫决策过程的Q-学迭代公式为基础，从单链的末端即当前状态的Q值开始逐步序贯回溯到单链的首端的Q值，直到到达目标状态，移动机器人循环往复地从初始状态开始寻找到达目标状态的路径，在搜索的每一步按照上述步骤，不断迭代和优化状态的Q值，直到收敛为止。本发明搜索最优路径需要的步数远少于经典Q-学算法和Q(λ)算法，学时间较短，学效率较高，特别是对于大环境，优势更加明显。

主权项

一种基于单链序贯回溯Q学习的移动机器人路径规划算法，其特征是：使用栅格法表示二维环境，每块环境区域都对应一个离散的位置表示，移动机器人在某一时刻的状态就表示为机器人所在环境位置，按照移动机器人顺序通过的环境位置依次排列，形成移动机器人的状态单链，移动机器人的每一步搜索，都以非确定性马尔科夫决策过程的Q‑学习迭代公式为基础，从单链的末端即当前状态的Q值开始逐步序贯回溯到单链的首端即初始位置的Q值，直到到达目标位置，移动机器人循环往复地从初始位置开始寻找到达目标位置的路径，在搜索的每一步按照上述步骤，不断迭代和优化状态的Q值，直到收敛为止；具体步骤如下：(1)建立状态单链：在每一t时刻，为移动机器人记忆矩阵M(t)增加一行M(t)←[s_t,a_t,r_t,λ_t]，其中s_t表示机器人的当前状态，当前状态就是机器人所在位置的坐标，s_t＝[x_t,y_t]，a_t表示在当前状态下执行的动作，包括向上、向下、向左、向右、静止五个动作，分别表示为[0,1]，[0,‑1]，[‑1,0]，[1,0]，[0,0]，动作集合表示为A，当前状态s_t与五个动作构成五个状态‑动作对，每一个状态‑动作对对应一个Q值Q(s,a)，所有的Q(s,a)初始化为零，并根据步骤(2)中的迭代更新公式进行更新，根据贪婪策略选择动作a_t，即选择满足也就是选择与当前状态s_t构成的五个状态‑动作对的Q值最大的动作作为a_t，s_t+1表示执行动作a_t后下一时刻状态值，r_t表示对动作a_t奖励值，如果执行a_t后的下一个坐标上有障碍物，则机器人下一时刻状态s_t+1仍为s_t的坐标值，奖励值r_t＝‑0.2；如果执行a_t后的下一个坐标上没有障碍物，则s_t+1为该坐标，奖励值r_t＝‑0.1；如果执行a_t后的下一个坐标是目标位置即终点，则奖励值r_t＝1；λ_t∈(0,1)表示学习率，只要λ_t∈(0,1)，经过有限次迭代，Q‑学习算法一定能够收敛于最优解；从初始时刻t＝0到当前时刻t＝n，所有的状态依序构成一个状态单链；(2)序贯回溯迭代：在t+1时刻，记忆矩阵M(t)增加一行新内容[s_t+1,a_t+1,r_t+1,λ_t+1]，并根据记忆矩阵中存储的状态链，用Q‑学习迭代公式进行序贯回溯迭代更新：对于k＝t,t‑1,t‑2,…,1,0，执行：$Q_{t+1}(s_k,a_k)\leftarrow (1-{\lambda }_k)Q_t(s_k,a_k)+{\lambda }_k[r_k+\gamma \underset{a_{k+1}\in A}{\max }{Q}_{t+1}(s_{k+1},a_{k+1})],$其中，γ是折扣因子，反映了后续状态‑动作对对应的Q值对状态单链中前面状态动作对Q值的影响，使得某一状态的动作决策能够直接受到其后续状态的影响，γ∈(0,1)，值越大，后续状态对状态单链中前面的状态动作选择影响越大；通过序贯回溯迭代，在t+1时刻不仅更新了状态s_t的Q值，也顺序地更新了状态单链中s_t前面的状态s_t‑1，s_t‑2，……，s₂，s₁，s₀的Q值，迭代过程如下：t＝1时刻s₀←s₁t＝2时刻s₀←s₁←s₂t＝3时刻s₀←s₁←s₂←s₃……t＝n时刻s₀←s₁←s₂←……s_n‑1←s_n，其中s₀表示机器人的初始状态，s₁表示t＝1时机器人状态，……，s_n表示t＝n时机器人状态，箭头表示数据传递方向，所传递的数据包括奖励值r_k和状态‑动作对的Q值；这样，t+n时刻的状态‑动作对(s_t+n,a_t+n)的Q值通过单链序贯回溯迭代更新t时刻机器人状态‑动作对的Q值，$\begin{array}{c}{Q}_{t+n}(s_{t+n-1},a_{t+n-1})\leftarrow (1-{\lambda }_{t+n-1})Q_{t+n-1}(s_{t+n-1},a_{t+n-1})+{\lambda }_{t+n-1}\{r_{t+n-1}+\gamma \underset{a_{t+n}\in A}{\max }{Q}_{t+n}(s_{t+n},a_{t+n})\},\\ Q_{t+n}(s_{t+n-2},a_{t+n-2})\leftarrow (1-{\lambda }_{t+n-2})Q_{t+n-1}(s_{t+n-2},a_{t+n-2})+{\lambda }_{t+n-2}\{r_{t+n-2}+\gamma \underset{a_{t+n-1}\in A}{\max }{Q}_{t+n}(s_{t+n-1},a_{t+n-1})\}...\\ ...,Q_{t+n}(s_{t+1},a_{t+1})\leftarrow (1-{\lambda }_{t+1})Q_{t+n-1}(s_{t+1},a_{t+1})+{\lambda }_{t+1}\{r_{t+1}+\gamma \underset{a_{t+2}\in A}{\max }{Q}_{t+n}(s_{t+2},a_{t+2})\},\\ Q_{t+n}(s_t,a_t)\leftarrow (1-{\lambda }_t)Q_{t+n-1}(s_t,a_t)+{\lambda }_t\{r_t+\gamma \underset{a_{t+1}\in A}{\max }{Q}_{t+n}(s_{t+1},a_{t+1})\};\end{array}$(3)寻找目标点：移动机器人在环境中每走一步，就会在记忆矩阵M(t)增加一行，并按照记忆矩阵，依次序贯迭代修正单链中前面所有状态‑动作对所对应的Q值，直到到达目标位置，并更新完单链中所有状态‑动作对对应的Q值，才会停止本次路径搜索；(4)机器人回到初始状态，在先前建立的Q值表基础上继续搜索，直到收敛，找到最优路径。