一种移动机器人路径规划新方法

2016-09-13山西中北大学机电工程学院闫鹏杰张亚

河北农机 2016年2期

山西中北大学机电工程学院　闫鹏杰　张亚

一种移动机器人路径规划新方法

山西中北大学机电工程学院闫鹏杰张亚

路径规划是自主移动机器人导航的基本任务，其精度取决于地图构建和定位。一些路径规划算法已经应用于精确的路劲规划过程，比如Dijkstra算法，A*算法等。如果机器人的体积大于栅格地图的栅格单元，传统A*算法路径规划就会不精确，在这种情况下移动机器人很难安全通过门和狭窄的通道。本文提出的新的路径规划方法在障碍物周围虚拟增加障碍栅格单元，有效降低了发生碰撞的可能性。

路径规划；A*算法；自主移动机器人

1　引言

路径规划是自主导航移动机器人的关键技术之一。准确、最优的路径规划一方面需要机器人通过传感器获取准确的环境信息和里程计信息；另一方面移动机器人必须避开障碍物安全到达目标点，并且路径必须是最短的。最短路径是节省时间方面的约束，最安全路径是移动机器人安全方面的约束［1-2］。

Dijkstra算法是一种移动机器人最短路径规划算法。Peter E. Har等人在dijkstra算法基础上提出了A*算法［3］，加快了搜索效率。但是A*一直存在一个问题：当机器人的外形尺寸大于栅格地图中栅格的尺寸时，当机器人沿着规划的最短路径行走时存在撞到障碍物的可能性，这对机器人是不安全的。本文就是在传统A*算法的基础上，将机器人的外形尺寸因素引入到路径搜索的过程中，从而寻找到最短路径。

2　路径规划

2.1A*路径规划算法

A*算法应用在栅格环境地图中，是一种启发式搜索算法，启发函数h（n）是算法的核心，也是区别于Dijkstra算法的关键。启发函数的作用是给出当前节点到目标节点的估计距离，这个距离不考虑路径中的障碍物。启发函数使算法可有效得到更多关于环境地图的信息。A*算法从起始节点开始搜索，并把起始节点周围的节点加入到一个列表中，我们称之为Open列表。Open列表中的节点按f（n）值由小到大排列，启发函数h（n）是f （n）的组成部分。Open列表中f（n）值最小的节点就是下一次的扩展节点，这个过程一直循环直到扩展到目标节点，这样最终路径就被搜索出来了。每个栅格节点的代价函数如下式：

f（n）=g（n）+h（n）（1）

上式中，假设当前的搜索节点为n（xn，yn），f（n）是从起始节点S经过当前节点n到达目标节点G的最小代价估计值，g （n）是从起始节点S到达当前节点n的实际最小代价值，h（n）是从当前节点n到达目标点G的最小估计代价值。g（n）的值表示如式（2）：

当prev（n）=Sk时，即当前节点为Sk时：

式（4）中的h（n）值是从当前节点n到目标节点G的欧式距离。启发函数h（n）的值也可以按Manhattan距离计算或是其他相对应的距离计算方法。

通过以上计算方法和搜索策略就可以找到最短路径。从目标点依次向前追踪到起始点S就是所求最短路径。传统A*算法的路径规划仿真结果如图1所示。

2.2缺陷

仿真实验模拟的是室内的环境，包括一些虚拟的障碍物如门、墙、桌子等。占有栅格地图是虚拟室内环境的映射，障碍物栅格用‘1’表示，可行区域用‘0’表示。仿真实验中起始节点和目标节点在栅格地图中的位置是事先给定的。起始位置设置为‘-1’目标位置设置为‘-2’。按照公式（1）-（4）的计算方法，从起始点到目标点用传统A*算法进行路径搜索就会找到路径。为了获得更精确的最短路径，必须增大栅格地图的分辨率，即机器人的外形尺寸会大于栅格大小，这就会使传统A*算法规划出的路径存在安全问题，如图1所示，机器人行走路径会很接近障碍物，这就会导致实际移动机器人在行走中会撞上墙等障碍物。另一方面，如果门等通道是很狭窄的，机器人可能被夹住。

同理，式（1）中的h（n）估计值如式（4）：

图1　传统A*算法

2.3改进方法

为了解决上述问题，本文对A*算法进行了改进。在新方法中，我们按照公式（5），在障碍物的周围增加了虚拟的障碍栅格所有的障碍物栅格被定义为‘1’。虚拟障碍物的设置规则如下：

代价值被标记为‘1’和‘2’的所有栅格都放在关闭列表中。关闭列表是机器人下一次搜索不能选的单元列表。代价值为‘2’的栅格单元就被认定为虚拟障碍物。现在传统的A*算法按式（5）进行了改进。改进后的A*算法更适应于机器人外型等于栅格大小的情况。

A*算法的过程：

A.生成可行节点和不可行节点的地图。

B.创建“Open”和“Closed”列表，初始状态都为空。

C.将所有的不可行节点放入“关闭”列表。

D.创建起始节点和目标节点。将起始节点放在开启列表中

E.如果开启列表不是空的并且没有找到路径，按如下步骤：

a）将开启列表中f（n）值最小的节点移出，这个节点就作为当前节点。

b）将当前节点的状态设置为关闭状态。

c）对于当前节点周围相邻的8个节点做如下处理：

·如果该节点是地图范围内可以行走的，并且不在关闭列表中，做如下处理：

·如果该节点不在Open列表中，把它放入Open列表中，并存储其f、g、h值，同时将它的状态设置为开启状态。

·如果该节点已经在Open列表中（也就是说它的状态为开启状态），重新计算它的g值，如果新的g值小于之前的g值，则将它的父辈节点改为当前节点，并且在Open列表中存储新的f 和g值。

d）当目标节点的状态被放到开启列表中时，意味着找到了路径。

F.当开启列表为空时，意味着路径搜索失败。

以此类比，当机器人的外形尺寸是栅格尺寸的2～3倍时，从安全角度考虑，我们将虚拟障碍物再向外扩展一层，如图3所示。

3　仿真实验

本实验假设环境地图为已知的栅格地图，地图大小分为100×100格。栅格地图的表示方法为：‘1’表示为障碍物（不可行节点），‘0’表示可通行区域（可行节点），起始位置都预先在地图中设置。本文提出的改进策略也在算法中实现。

传统A*算法的搜索结果见图1，机器人在移动过程中会离障碍物很近。经过公式（5）改进，从图2中可以很明显的看到，改进后的A*算法搜索出的路径对机器人更安全。如果机器人外形尺寸变为栅格尺寸的2～3倍时，继续扩大虚拟障碍物范围，此时的搜索结果如图3所示。对比图1与图3可以发现，改进后的A*算法可以解决机器人在移动过程中碰到障碍物的问题。