基于改进分层D*搜索算法的室内路径规划问题研究

摘要

近年来，随着科技的进步和机器人相关学科的快速发展，移动机器人技术逐渐成为研究热点，而室内服务机器人作为移动机器人研究领域的热点之一，相应的路径规划问题也随之成为研究者们的研究对象。
　　本文在现有移动机器人路径规划算法的基础上，对室内环境下移动机器人路径规划做出了以下几个方面的研究:
　　首先，分析了启发式路径规划算法D*算法的基本原理。针对D*算法搜索空间大的缺陷，引入抽象分层的思想，将机器人的工作环境结构化为多个层次，并为各层次中的子地图设置关键节点，缩小D*算法的搜索空间;利用Voronoi图理论离线生成各关键节点之间的先验安全路径，提高关键节点间路径规划的效率。
　　其次，考虑到D*算法是一种长度优先算法，算法搜索到的优化路径存在小范围内多次转角的问题，降低了优化路径的平滑度;而优化路径性能的高低又直接取决于算法的代价估计函数。因此，本文利用对角线函数对代价估计函数中的启发函数进行改进，并在基本项中增加方向偏移代价。仿真实验证明，利用改进后D*算法规划出优化路径的平滑度得到明显提高。
　　最后，对动态环境下的路径规划问题进行分析，利用二次路径规划的方法避免与动态障碍物发生碰撞，其路径规划的效率较低，对此，本文提出了一种动态环境下的局部路径规划算法。算法借鉴滚动窗口的原理，对位于当前滚动窗口内的动态障碍物的运动轨迹进行预测，并判断其是否会与移动机器人发生碰撞。对于运动轨迹不确定的动态障碍物，利用卡尔曼滤波算法对其进行较为准确的预测，并根据不同的碰撞情况，采取不同的碰撞避免措施指导移动机器人前进。仿真实验证明，本文提出的局部路径规划方法能够较好地适应动态环境下移动机器人的路径规划，有效地避免移动机器人与动态障碍物发生碰撞。

目录

声明

致谢

摘要

第一章 绪论

1．1 课题研究背景及意义

1．2 移动机器人路径规划算法的研究现状

1．2．1 传统路径规划方法

1．2．2 智能仿生路径规划方法

1．3 移动机器人路径规划主要研究内容

1．4 本文的主要研究内容和结构安排

第二章 基于D*算法的路径规划方法

2．1 引言

2．2 环境建模及层次图定义

2．2．1 栅格地图建模

2．2．2 层次图的定义

2．3 D*算法

2．3．1 D*算法简介

2．3．2 D*算法实现

2．3．3 D*算法流程

2．4 D*算法存在的问题

2．5 本章小结

第三章 改进分层D*算法

3．1 引言

3．2 分层D*算法及离线先验路径

3．2．1 分层D*算法

3．2．2 离线先验路径

3．3 D*算法的改进

3．3．1 改进的启发函数

3．3．2 方向性

3．4 改进分层D*算法的流程

3．5 实验结果和分析

3．6 本章小结

第四章 动态环境下的移动机器人避障算法

4．1 引言

4．2 自主感知

4．3 局部碰撞预测

4．3．1 运动轨迹为直线的碰撞预测

4．3．2 运动轨迹不确定的碰撞预测

4．4 局部碰撞避免

4．4．1 运动轨迹近似直线动态障碍物

4．4．2 运动轨迹不确定动态障碍物

4．5 局部路径规划算法流程图

4．6 仿真实验及结果分析

4．6．1 卡尔曼滤波算法预测动态障碍物位置仿真实验

4．6．2 局部路径规划仿真实验

4．7 本章小结

第五章 总结与展望

参考文献

硕士期间发表论文和参与的科研工作