基于距离变换的PRM路径规划算法  

Distance transform based PRM path planning algorithm

作　　者：李敏 周远远[2] 黄鲁[2] Li Min;Zhou Yuanyuan;Huang Lu(Department of Electronic Science and Technology, University of Science and Technology of China, Hefei 230027,China;Information Science Center, University of Science and Technology of China, Hefei 230027, China)

机构地区：[1]中国科学技术大学电子科学与技术系,安徽合肥230027 [2]中国科学技术大学信息科学实验中心,安徽合肥230027

出　　处：《信息技术与网络安全》2018年第3期74-79,共6页Information Technology and Network Security

摘　　要：当环境中存在窄通道时,传统的概率路图(PRM)路径规划算法很难高效地建立能通过窄通道的无向图。针对该问题,利用图像处理中的距离变换技术,提出一种基于距离变换的PRM路径规划算法(DTPRM)。首先基于距离变换地图,设计一种定量计算工作空间中障碍物稠密度的方法,利用该方法自适应地计算总采样点数目;然后利用距离变换地图识别不同区域,并采用不同密度的采样策略,使采样点在窄通道内密集分布,构建能通过窄通道的无向图。仿真结果表明,DTPRM算法能够根据不同障碍物环境自适应地计算总采样点数,得到合理的采样点分布,有效解决了窄通道问题。It is difficult to generate an efficient undirected-graph which can pass through the narrow passages by using the classical Probabilistic Road Map（PRM） path planning algorithm when there are narrow passages within the robot workspace. To solve this problem,a new roadmap sampling method,named Distance Transform based PRM（DTPRM） was proposed by using the distance transform technology in image processing. A new method was designed to evaluate the obstacle density of the workspace by using the distance transform map,then it was used to adaptively calculate the number of total sampling nodes. Different density sampling strategies were used in different areas which were recognized by using the distance transform map,thus ensuring most of the sampling nodes gather in the narrow passages and constructing undirected-graph which can pass through the narrow passages. Simulation results show that the proposed algorithm can adaptively calculate the number of sampling nodes and get favorable sampling nodes distribution which can construct efficient graph in the narrow passages.

关 键 词：路径规划 概率路图 窄通道 距离变换 机器人 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]