基于改进 A* 算法的机器人路径规划外文翻译资料

英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料

保加利亚科学院

CYBERNETICS AND INFORMATION TECHNOLOGIES bull; 第15卷, 第 2 期

索菲亚 bull; 2015 打印 ISSN: 1311-9702; 在线 ISSN: 1314-4081

DOI: 10.1515/cait-2015-0036

基于改进 A* 算法的机器人路径规划

彭建生, 黄益勇, 关罗

中国UEST通信国家重点实验室, 成都 610054

河池学院物理与机电工程系, 宜州 546300

电子邮件: sheng120410@163.com

摘要:由于A*算法在遍历OPEN表和CLOSED表时需要很长的时间，因此提出了一种改进的方法，该方法是一种在OPEN表和CLOSED表中存储数组的新方法。与原来的A*算法相比，数组存储的方式通过每次访问指定元素时查找数量排序来访问数组元素，这可以通过一次操作完成。原始的A*算法需要遍历很多个节点才能找到指定的元素。试验结果表明，改进的A*算法与原始A*算法的比较表明，运行效率提高了40％以上。基于改进的A*算法，该方法保留了原始A*算法的优点，提高了A*算法的运行效率。

关键词: A* 算法, 路径规划, 网格, 机器人.

1. 介绍

A* 算法由 P. E. H a r t, N. J. N i l s s o n and B. R a p h a e l 1968 [1]共同提出. A* 算法是一种紧凑且高效的算法.A* 算法是启发式搜索的典型人工智能算法.与其他人工智能算法 [2, 3] 相比,他具有运行时间段,效率高,易于实现等诸多优点.因此,A*算法已被广泛应用于各个领域 [4]. A*算法应用[5]的路径规划方面已经有了很多研究成果.

171

Brought to you by | Nanjing University of Information Scienc

Authenticated

Download Date | 4/7/18 5:05 PM

A* 算法经过几十年的发展已经成熟.目前,改进A*算法的方法有两种 minus; 降低算法运行时间并减少存储空间.通过改进遍历方式,减少算法运行时间,通过改变数据存储方式,减少存储空间.A*算法是渐进式全局搜索算法,从本地开始搜索到本地推测全局搜索的算法.虽然A*算法是一种全局搜索算法,但他不会遍历整个全局搜索算法.

2. A* 算法相关介绍

2.1. 定义一个子节点和一个父节点

定义 1. 子节点是父节点的扩展,子节点总是指向父节点,子节点只有一个父节点.

定义 2. 父节点是一个可扩展的节点,父节点可以将子节点扩展到8个.

如图1所示,红色网格是父节点,八个绿色网格是子节点.

图1. 一个子节点和一个父节点的定义图

2.2. 评估功能

A*算法的核心是评估函数.A*算法通过评估函数选择下一个展开的子节点.评估函数用于获得高效且轻量的A*算法.评价函数的表达式为

⁽¹⁾ F (n) = G (n) H (n) ,

其中: F(n) 是A*算法的评估函数; G(n) 是从起始节点到当前节点n (即从起始点到节点n的最佳路径总距离); H(n) 是从当前节点n到目的节点的估计考虑因素 (即从节点n到目标节点的估计距离).

F (n) 的函数G(n)实际可以计算,但H(n ) (评估函数) 不能计算实际值,只能估算近似值.选择不同的评估函数H(n), 从 F(n) 值的不同结果中获得,最短路径搜索和运行程序所需的时间也不相同.

172

Brought to you by | Nanjing University of Information Scienc

Authenticated

Download Date | 4/7/18 5:05 PM

2.3. 使用曼哈顿距离作为评估函数

曼哈顿距离由 Hermann Minkowski 在十九世纪提出,他在空间几何中的表示是:x方向两点之间的距离加上y方向.

假定点P1是节点n, 点P2是末端节点m,点P1的坐标是 ( x₁ , y₁) ,点P2 是 (x₂, y₂). 从节点n到节点m的曼哈顿距离是

(2) H _m (n) =| x₁ minus; x₂ | | y₁ minus; y₂ | .

2.4. A* 算法过程

一个A* 算法需要设置两个表:一个OPEN表和一个CLOSED表.OPEN表保存所有生成的节点,但尚未检查.CLOSED表记录已访问的节点.A*算法流程图如图2所示.

k

判断是否n个新包含目标节点子节点

图2. A* 算法流程图

173

Brought to you by | Nanjing University of Information Scienc

Authenticated

Download Date | 4/7/18 5:05 PM

3. 改进的 A* 算法

A*算法的OPEN表和CLOSED表以二进制树或列表的形式存储数据.尽管二叉树和列表具有易于插入和删除操作的优点,但为了找到节点需要遍历几次以确定数据是在列表中还是在二叉树位置中.每次访问一个OPEN表和一个CLOSED表需要遍历多个节点才能找到指定的节点.改阵列能够实现定位节点的一项操作.根据数组的优点,提出了一个数据结构query_table(i, j), 这是OPEN表和CLOSED表查找函数中改进方法的替代方案.通过访问结构化数据,可以找到节点,并确定节点的状态.节点的状态有:空闲状态,OPEN表状态和CLOSED表.改进的A*算法仍然保留一个OPEN表,CLOSED表不存在,并且使用结构化数据query_table(i, j) 代替OPEN表和CLOSED表的查询函数.

3.1. 结构化数据 query_table(i, j)

数据结构在 MATLAB 语言结构体数据类型中.数据结构query_table(i, j) 成员的结构如表1所示.

表1. 数据组成员的表述结构

query_table( i, j).Pointer的变量用于记录(i, j)节点的父节点的坐标,例如query_table(2, 3).Pointer = (2, 2) 表示父节点2行和3列节点,等于2行和2列节点.

初始化数据结构成员 query_table(i, j).函数的状态和说明:

1. 初始化query_table(i, j).State的数据结构成员

query_table(i, j). State=0,

1. 0lt;i≦line

0lt;j≦line

1. 更新数据结构成员 query_table(i, j)状态的指令:

假设 (3, 4) 节点为扩展父节点,则(4, 5)节点为扩展节点的最优扩展子节点, query_table(4, 5)的状态

174

Brought to you by | Nanjing University of Information Scienc

Authenticated

Download Date | 4/7/18 5:05 PM

等于 0, 则扩展子节点加入OPEN表,并设置query _table(4, 5)的状态为 1. 从OPEN表中删除 (3, 4) 节点,重新设置query_table(3, 4)的状态 为 2.

3.2. 改进 A* 算法的步骤

步骤 1. 初始化数据结构query_table(i, j)的每个成员的状态：

query_table(i, j).F = infin; ,

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[22958]，资料为PDF文档或Word文档，PDF文档可免费转换为Word