移动机器人的智能路径规划算法综述*

王春颖, 刘 平, 秦洪政

(山东农业大学 机械与电子工程学院 山东省园艺机械与装备重点实验室,山东 泰安 271000)

0 引 言

移动机器人的路径规划是指在具有障碍物的环境中寻找一条从起始状态到目标状态的无碰撞路径[1]。目前对于已知环境的路径规划已存在很多成熟算法,实现了无碰撞到达目标地点,但在未知环境下如何能够根据移动机器人的传感器实时探测到的局部环境信息,进行路径规划,仍处于试验研究阶段。近年来,我国农业装备产业快速发展,路径规划作为自主导航的关键技术之一,是智能农业装备的研究重点。

本文针对路径规划技术进行分析与归纳,重点分析了基于强化学习算法的路径规划技术,并提出类脑智能在路径规划上的应用展望和农业装备路径规划的新思路。

1 移动机器人的路径规划

移动机器人种类繁多,根据路径应用目的的不同,如时间最优、路径最优、路径全遍历,将路径分为点对点路径和完全遍历路径2种[2]。

1.1 点对点路径规划

根据移动机器人所处外部环境信息的获取情况将点对点路径规划[3]分为全局路径规划和局部路径规划。全局路径规划[3]是在已知的环境信息下,在事先建好的环境模型中,获得从初始地到目标地的最优路径,其优点是保证了规划路径的最优性和可达性。局部路径规划[3]是在未知环境中,基于传感器获取周围环境信息,并使机器人自主获得一条无碰撞的最优路径,其优点是更具有对于未知环境的适应性和规划的实时性。

1.1.1 全局路径规划

1)根据对环境构建的描述分为构型空间法、栅格法、拓扑法[4]等,在构型空间法中,较为成熟的有可视图法[5]、Voronoi图法[4,6]。栅格法[7,8]应用较多,具有直观简洁、分辨率可变、容易创建和存储等优点,适用于室内环境路径规划地图模型的建立,鲁棒性强。环境构建法常与其他路径规划算法结合实现路径规划,如陈晓蛾在环境栅格地图的基础上实现多机器人路径规划。

2)在搜寻最优路径的算法上,全局路径规划依据搜索算法分类,主要包括图搜索类算法、随机采样类算法、智能算法等。图搜索类算法[9]主要有Dijkstra算法、A*算法、D*算法等,与Dijkstra算法相比,A*增加了启发式估计,减少搜索量,提高效率,同时保证路径的最优性,但环境复杂、规模较大时,效率仍较低；随机采样类算法主要有概率路标算法[10]、快速随机数算法[11],广泛应用在动态障碍物、高维状态空间和存在运动学、动力学等微分约束的复杂环境中,但存在耗费代价大、应用实时性较差、规划所得路径有可能不是最优路径的问题[12]；智能仿生算法是一种模拟生物进化和仿生自然界动物昆虫觅食筑巢行为的智能化算法,主要有遗传算法[13]、蚁群算法[14]、粒子群算法[15,16]等,遗传算法、蚁群算法适用于复杂问题求解和优化,具有潜在的并行性,但存在运算速度慢,解早熟现象；与这两种算法相比粒子群算法优点在于收敛速度快。朱铁欣[17]提出将蚁群算法和人工势场法、Memetic结合应用于农业机器人。王春华等人[18]提出一种改进蚁群算法用于机器人焊接路径规划,王友钊等人[19]将贪心算法和遗传算法结合用于实现仓储车辆调度。

1.1.2 局部路径规划

局部路径规划[20,21]是在未知环境中,基于传感器获取周围环境信息,并使机器人自主获得一条无碰撞的最优路径。用于局部路径规划的经典算法有人工势场法[22]、模拟退火法[23]、模糊逻辑法[24]、神经网络法[25]、动态窗口法[26]、强化学习法[27]以及基于行为的路径规划方法。人工势场法结构简单、计算量较小,但存在容易产生局部最小值的问题,在实际应用中发现,当目标点附近存在障碍物时,移动机器人无法顺利到达,于振中[28]在障碍物的斥力势场中添加系数项,解决了这一问题。模拟退火法,将热力学的理论套用到统计学上,利用概率的突跳性,实现随机优化问题的求解,避免出现局部极值问题,弥补人工势场法的缺陷。刘爱军[29]提出模拟退火算法与粒子群算法相结合,解决了粒子群算法容易陷入局部最优的问题,并引入自适应温度衰变系数,使模拟退火算法能够根据当前环境自动调整搜索条件,从而提高算法的搜索效率。模糊逻辑法是根据模糊的环境信息,依照对应表格规划出的信息,实现局部路径规划,优点在于容易计算,能够实时跟踪规划。杨小菊等人[30]提出一种基于模糊控制的移动机器人避障方法,但模糊规则根据经验设定,存在经验不完备等问题,因此该算法灵活性差,存在未知短板。

目前多采用两种算法结合的方法弥补各自存在的问题。对于容易陷入局部最优的缺陷如遗传算法、蚁群算法、粒子群算法、人工势场法等,可以采用混沌或者神经网络等算法进行优化。2013年,胡喜玲[31]将混沌优化算法的遍历特性引入遗传算法,以防止和克服进化过程中的“早熟”现象。2012年,肖乐[32]对蚁群算法的信息素添加混沌扰动,提高最优解的精度,多用于仓储和物流配送。2013年,刘爱军[29]提出混沌模拟退火粒子群优化算法,解决了粒子群算法容易陷入局部极值点、进化后期收敛速度慢、精度较差等缺点。2007年,刘玲[33]将神经网络和遗传算法相结合,环境采用神经网络进行描述后,遗传算法经路径搜索,实现无碰撞路径规划。

1.2 遍历路径规划

与常规的点对点的规划不同,遍历路径规划[2]找到一条能够遍历区域内的所有点,同时避开障碍物的路径。该方法要求遍历性强、重复率低,相关算法可以分为3类[34]：

1)随机遍历策略。采用迂回往复式、内外螺旋式[35]、随机转向式进行路径规划,不采用目前通用的效益函数,规划算法简单,遍历性强、重复率低,但不能有效避开障碍物,需与局部路径规划算法结合。

2)沿边规划策略。首先沿边移动建立环境轮廓模型,然后采用全局视角与局部路径规划相结合的算法实现路径规划。环境建模的方法有栅格法、可视图法、Voronoi图法、拓扑法等,局部路径规划方法有人工势场法、模拟退火法、模糊逻辑法、神经网络法等。窦文豪[36]针对大棚环境,提出基于拓扑地图的路径规划方法,以最短的路径遍历必走路线。王仲民[37]将神经元激励与栅格地图结合实现全遍历的路径规划。

3)漫步式探测路径规划。主要有动态窗口法、强化学习法、随机采样类搜索算法,能够有效地避开障碍物,实现全遍历路径规划,但存在着遍历重复率高、时间开销大、资源浪费严重等缺点。

遍历路径规划不同于常规的点对点的规划,要求规划的路径具有覆盖率高、重复率低等特点,但采用的算法是相通的,如神经网络、强化学习、动态窗口等智能算法。通过将智能算法融入沿边策略、漫步策略,实现在未知地图下的全遍历路径规划。

2 强化学习算法在路径规划上的应用

随着移动机器人智能化的应用需求逐渐上升,基于强化学习的路径规划方法[27]成为当前研究的热点,该方法将传感器感知的环境状态映射到执行器动作,对外界环境变化快速响应,实现自主路径规划,具有实时、快速的优点。强化学习利用类似于人类思维中的试错的方法来发现最优行为策略,目前已经在机器人行为学习方面展现出了良好的学习性能。针对基于强化学习的路径规划方法主要从两大方面内容进行分析：从状态到动作映射的正确策略和移动机器人所在环境状态的内部表示即状态泛化问题。

2.1 从状态到动作映射的正确策略

强化学习的算法有时间差分法(temporal difference,TD)[38]、Q-Learning算法[39]、Sarsa算法[40]、Dyna算法[39]、Actor-Critic[41]算法等。其中TD算法是较早出现的强化学习算法,Q-Learning算法、Sarsa算法都是在TD算法的基础上改进的,区别在于迭代的是动作值函数Q(s,a)或状态值函数V(s),如表1。前3种算法多用于已知环境状态下,Dyna 算法是建立环境模型代替真实环境,迭代虚拟样本函数值,实现实时学习规划。Actor-Critic算法[42]是一种同时估计值函数和策略的学习方法,是一种具有独特记忆功能的TD算法,提高收敛速度,保证处处收敛。强化学习算法仍处于不断发展的过程中,收敛速度和状态泛化是研究的主要问题,其中在收敛速度问题上,Q-Learning算法表现出良好的收敛性,目前多采用该方法。马朋委、潘地林[40]采用策略择优和优化回报函数的启发函数对Sarsa(λ)算法进行优化,提高起收敛速度；Wen S,Chen X[43]将Q-Learning与SLAM结合,实现移动机器人自主行走。

表1 三种函数区别对比

2.2 状态泛化问题

状态泛化问题[44～46]即环境状态的内部表示,作为强化学习的主要研究内容之一,目的在于为强化学习方法提供较好的学习基础,提高机器人的学习效率。主要有离散化方法、值函数逼近方法,其中值函数逼近的方法主要有神经网络法、模糊逻辑法、人工势场法等。

离散化方法容易出现信息丢失和“维数灾难”的问题,多采用值函数逼近的方法进行优化。值函数逼近的方法多应用于连续环境状态中,能够降低存储量,提高收敛速度。童亮[27]采用Kohonen状态泛化,提高了Q-Learning的收敛速度；宋勇、李贻斌[46]提出基于人工势能场的移动机器人强化学习初始化方法；Cruz D L,Yu W[38]将神经网络和内核平滑技术用于强化学习的状态泛化；黄铝文[41]将强化学习、神经网络应用到苹果采摘机器人路径规划,得到最优安全路径。

3 结束语

基于以上分析,移动机器人智能路径规划方法[47，48]研究虽然取得了重要成果,但仍存在局限性,如遗传算法、蚁群算法容易陷入局部最优,神经网络算法需要大量样本。目前的改进算法以多种算法相结合、分层优化等方式为主,虽弥补了缺点,但存在诸多发展瓶颈,如算法复杂度增加,收敛速度慢。

较于其他算法，强化学习,学习能力强,适应复杂未知环境,但目前强化学习的试错学习、状态泛化,需要耗费大量资源。近年来脑科学与类脑智能已成为世界各国研究和角逐的热点,类脑智能能够智能化获取信息、智能信息处理与通信、智能人机交互,能够适应路径规划的智能化需求。类脑智能通过模仿及与环境的交互进行动作和规划,具有自主发育能力,少量样本学习,解决了强化学习的资源浪费的缺陷,使机器人具有发育能力,不断提升路径规划的智能化水平。

类脑智能是实现通用人工智能的重要途径,因此类脑智能应用于农业装备的路径规划能够解决目前农业装备的路径规划在复杂环境中鲁棒性差,适应性差的问题,可实现农田全区域路径规划、地头转向最优路径规划以及作物行跟踪等智能规划,提高农业装备自动化、智能化水平。