基于D*算法的动态环境路径规划算法研究
基于D*算法的动态环境路径规划算法研究(任务书,开题报告,外文翻译,论文12000字)
摘要
移动机器人自主导航是机器人智能化和人工智能（AI）的关键技术。其核心是精准的定位和实时路径规划，即依据某些最优准则，在变化的环境中规划出从起始状态到目标状态，并且能够避开障碍物的最优路径。移动机器人自主导航的运用极其广泛，小到高德地图的导航，游戏中角色的移动，以及无人机等，大到炙手可热的无人驾驶汽车，火星探测中的智能探测机器人等。目前的机器人路径规划方案中还存在着一些不足之处：全局规划中效率不高，局部规划中动态规避障碍的实时性较差。
D*算法，即动态A*算法（D-Star，Dynamic A Star），是一种启发式的路径规划算法，由卡内基梅隆机器人中心的Stentz于1994年和1995年在两篇发表的文章中提出[1]。本文研究基于D*算法的动态环境路径规划算法。
本文对比了国内外移动机器人路径规划的研究现状，然后研究了A*算法和D*算法的基本原理和路径搜索过程。并且以Python语言作为仿真语言，利用栅格法建立环境模型，分别对A*算法和D*算法做了仿真。接着根据仿真结果，比较D*算法和A*算法的差异，分析基于D*算法的动态环境路径规划特点。最后总结和展望了移动机器人路径规划的发展。
关键词：移动机器人D*算法自主导航路径规划
Abstract
Mobile robot autonomous navigation is the key technology of robot intelligence and artificial intelligence (AI). The core is accurate positioning and real-time path planning, which is to plan the optimal path from the initial state to the target state in a changing environment according to certain optimal criteria, and to avoid obstacles. Autonomous navigation of mobile robots is widely used, ranging from the navigation of Golden Map, the movement of characters in the game, and UAVs,to driverless cars, intelligent robots for Mars exploration , etc.
D* algorithm is dynamic A* algorithm (D-Star, Dynamic A Star), proposed by Stentz of Carnegie Mellon Robot Center in 1994 and 1995 in two articles. This paper studies the dynamic environment path planning algorithm based on D* algorithm.
This paper compares the research status of mobile robot path planning at home and abroad, and then studies the basic principles and path search process of A* algorithm and D* algorithm.And using Python language as the simulation language, the grid model is used to build the environment model, and the A* algorithm and D* algorithm are simulated respectively.Then, according to the simulation results, the differences between D* algorithm and A* algorithm are compared, and the characteristics of dynamic environmental path planning based on D* algorithm are analyzed.Finally, the development of mobile robot path planning is summarized and forecasted.
Key words：Mobile robot D* algorithm Autonomous navigation Path planning
目录
摘要 I
Abstract II
第一章绪论 1
1.1 相关背景 1
1.2 国外研究现状 2
1.3 国内研究现状 4
第二章路径规划D*算法 5
2.1 A*算法 6
2.1.1 A*算法简介 6
2.1.2 A*算法代价函数 6
2.1.3 A*算法基本原理 7
2.2 D*算法 7
2.2.1 D*算法简介 7
2.2.2 节点状态 7
2.2.3 D*算法基本原理 8
2.3 A*算法和D*算法的比较 9
2.3.1 相同点 9
2.3.2 不同点 9
第三章路径规划仿真 9
[资料来源：http://Doc163.com]
3.1 仿真语言Python 9
3.2 环境建模方法 10
3.3 仿真结果 11
3.3.1 A*算法仿真结果 11
3.3.2 D*算法仿真结果 15
3.4 仿真结果分析 19
第四章总结和展望 20
参考文献 22
致谢 24