基于近似最近邻搜索的改进PRM算法

作     者：薛阳 孙越 叶晓康 李蕊 华茜 XUE Yang;SUN Yue;YE Xiao-kang;LI Rui;HUA Xi

作者机构：上海电力大学自动化工程学院上海200090 

基　　金：国网浙江省电力有限公司科技基金项目(5211HZ17000F) 上海市电站自动化技术重点实验室基金项目(13DZ2273800) 

出 版 物：《计算机工程与设计》 (Computer Engineering and Design)

年 卷 期：2021年第42卷第11期

页      码：3211-3217页

摘      要：针对移动机器人工作环境范围复杂时,使用传统概率路线图(PRM)算法非常耗时的问题,提出一种改进的PRM算法。PRM算法最耗时的部分是构建无向路径图,构建无向路径图的关键是近邻搜索。通过使用近似最近邻搜索中的局部敏感哈希算法代替原先最近邻搜索算法,在不降低生成路线图质量的前提下,加快无向路线图的构建速度,减少PRM算法的运行时间。仿真结果表明,改进的PRM算法相较于传统的PRM算法在无向路径图建立时间上减少27.36%~33.27%,使PRM算法效率大大提高。

主 题 词：概率路线图(PRM)算法 无向路径图 最近邻搜索 近似最近邻搜索 局部敏感哈希 

学科分类：08[工学] 081202[081202] 0812[工学-测绘类] 

D　O　I：10.16208/j.issn1000-7024.2021.11.028

馆 藏 号：203106028...