1. 研究目的与意义
| 近年来，机器人(Robot)一直是现代科学技术的研究热点之一。机器人的起源可以追溯回三千多年以前我国的西周王朝，能歌善舞的木偶“伶人”是有记载以来最早的机器人；古人用滴漏计时改成的水钟，其实就是一种机器自动化设备；中世纪，欧洲人发明了用发条控制的钟。19 世纪 20 年代，捷克斯洛伐克作家萨佩克首次提出“机器人”一词，并根据捷克文“Robota”将机器人命名为“Robot”。目前国际上一般定义机器人是一类依据自身智能感知和决策控制系统实现多种功能任务和作业的可编程多功能操作机。路径规划是移动机器人人工智能的研究热点之一，是机器人实现自主导航和执行各种特定任务的基础。路径规划是指移动机器人在给定的起始位置和目标位置，两点间障碍物和可通行区域已知或者未完全可知的环境下，自主规划一条满足从起始位置到目标位置路径距离最短或者移动代价最小的安全可通行无碰撞路径。路径规划是运动规划的主要研究内容之一。运动规划由路径规划和轨迹规划组成，连接起点位置和终点位置的序列点或曲线称之为路径，构成路径的策略称之为路径规划。 启发式搜索算法A*算法因其简单高效、可操作性强和准确性高的优点而被广泛应用于解决路径规划问题。A*算法是一种典型的启发式搜索算法，建立在Dijkstra算法的基础之上，广泛应用于游戏地图、现实世界中，用来寻找两点之间的最短路径。它是一种静态路网中求解最短路径最有效的直接搜索方法，也是许多其他问题的常用启发式算法。A*算法是经典的启发式搜索算法，其借鉴吸收了图的遍历搜索思想和Dijkstra 算法的优点，引入了启发信息引导算法选择下一步访问扩展的节点，并充分利用已知路网环境信息，具有简单高效、可操作性强、搜索速度快、准确性高和适用性高的特点，故在路径规划问题中被广泛运用。因此本文选择 A*算法作为研究路径规划问题的基础算法，并针对 A*算法存在的不足提出相应的改进方法。 |
2. 研究内容和预期目标
为了解决盲目式搜索算法和 Dijkstra 算法中各自的缺陷和不足，美国人P.E.Hart、N.J.Nilsson 和 B.Rapheal 于 1968 年在上述算法思想基础上提出了新的启发式算法 A*算法。A*算法自提出以来被广泛应用于解决图搜索及机器人的路径规划。A*算法自1968年被E.Hart等人提出以来，因其优良的性能和可操作性而在路径规划问题中大量运用。此后数十年诸多国内外学者在对A*算法的研究中不断改进发展A*算法，取得了大量成果。 Korf等提出了基于A*算法和迭代加深算法相结合的IDA* (LiterativeDeepening A*)算法，其核心思想是设置算法在每次路径规划搜索中可到达的深度阂值最大值，解决标准A*在广度空间中易陷入盲目搜索的不足，若没有达到目标则加深最大深度阂值直到算法找到路径最优解;Stentz X21]提出了基于A*算法的动态A*算法，简称D*(Dynamic A*)算法，该算法向目标点移动中只检查最短路径上下节点或者临近节点的变化情况，提高了A*算法对于环境如权重等不断变化的动态环境的适应性;Koening等提出的LPA*(Longlife Planning A*)算法在A*算法的基础上融入了人工智能领“增量搜索”(Ineremental Search)思想，LPA*相对于标准A*算法采用递进式的搜索策略，通过利用算法先前搜索最优路径时存储的有效数据信息高效规划出二次最优路径，LPA*算法对于起始节点和目标节点状态信息己经确定的路径规划有良好的适用性;Koening等利用LPA*算法先前搜索最优路径时存储的有效数据信息高效规划出二次最优路径，提出了D *Lite算法，该算法改善了LPA*算法对于解决起始节点和目标节点状态信息不断改变的动态实时路径规划的不足和缺陷，提高了A*算法在动态环境中的适用性;Szczerba等提出了稀疏A*算法(Sparse A* Search,SAS)，稀疏A*算法在基本A*算法中添加了搜索约束条件，SAS算法可以根据约束条件的不同改变标准A*算法的节点搜索空间，在保证规划路径准确性的基础上有效地减少了待搜索范围内的无效节点，提高了算法的收敛效率。
3. 研究的方法与步骤
前期准备：收集相关资料，查阅中外文献、请教老师。学习、掌握路径规划算法所需软件Matlab，了解a*算法一般编写过程与原理。了解其他路径规划算法一般编写过程与原理。
本课题的主要研究工作就是研究A*算法，在理解上述理论和算法实现的基础上要熟悉Matlab语言的基础，了解利用Matlab。所有路径算法及其改进方法都通过 Matlab 软件编写。
4. 参考文献
| [l]王田苗，陶永.我国工业机器人技术现状与产业化发展战略 [月.机械工 程学报，2014, 50(9):1-13. [2]谭民，王硕.机器人技术研究进展[J].自动化学报，2013, 39(7):963-972. [3] Nilsson N J.A mobileautomation: an application of artificial intelligencetechniques[C]// International Joint Conferenceon Artificial Intelligence.Morgan Kaufmann Publishers Inc. 1969:509一520. [4]熊有伦.机器人技术基础[M].武汉:华中理工大学出版社，1999. [5]马靖雯.移动机器人路径规划方法研究[[D].哈尔滨:哈尔滨工程大学，2016. [6]宋丹一改进A*算法在钢铁企业安全巡检机器人路径规划的研究[[D].鞍山:辽宁科技大学，2017. [7]于振中，郑为凑，刘鑫，等.基于Kinect的移动机器人实时局部路径规划.[J].计算机工程，2013, 39(4):243-247. [8]王学梅.基于自适应蚁群算法的移动机器人路径规划研究[[D].芜湖:安徽工程大学，2016. [9]Dijkstra,E.W.A note on two problems in connexion with graphs[J].Numerische Mathematik, 1959,1(1):269-271. [10] Hart P E, Nilsson N J,Raphael B. A formal basis for heuristic determination of minimum path cost[C] //Sequences Subsequences,Consequences.1968. [11」Holland J H. Adaptation in natural and artificialsystems[J].Ann Arbor, 19756(2):126-137. [12] Lozano-P, Rez T, Wesley MA. An algorithm for planning collision-freepaths among polyhedralobstacles[J].Communications of the Acm, 1979,22(10):560一570. [13] Kirkpatrick S,JrGC,Vecchi M P. Optimization by simulated annealing.[J].Science,1983,220(4598):671一680. [14] Khatib O.Real一Time Obstacle Avoidance forManipulators and MobileRobots [J].International Journal of Robotics Research, 1986, 5(1):90一98. [15] Dorigo M.Optimization,Learning and NaturalAlgorithms[J].Thesis Politecnico Di Milano Italy, 1992.
|
5. 计划与进度安排
2022-3-5～2022-3-11 查阅资料，分析实施方案；
2022-3-12～2022-3-31 完成a*算法的研究；
2022-4-1～2022-4-30 改进a*算法；
课题毕业论文、开题报告、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
