移动机器人全局路径规划算法的研究.pdf

《移动机器人全局路径规划算法的研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2014钲仪表技术与2Ol4第12期InstrumentTechniqueNo．12移动机器人全局路径规划算法的研究黄静，陈汉伟(浙江理工大学信息学院，浙江杭州310018)摘要：全局路径规划是移动机器人要解决的重要问题，较好的路径搜索算法可以迅速搜索有效路径，提升移动机器人的智能性，提升用户体验。针对目前移动机器人行为决策能力较弱的问题，着重研究移动机器人的全局路径规划问题，通过研究盲目式搜索算法、A算法和遗传算法，分析了3种算法在解决路径规划问题中的优劣，使用A算法在Unity平台上虚拟移动机器人的全局路径规划模块，并且使用贪婪平滑算法优化A算法产生的多余路径，

2、路径搜索的效率较高，移动机器人的智能性和真实感较好。关键词：移动机器人；人工智能；路径规划；遗传算法；A算法中图分类号：TP212文献标识码：A文章编号：1002—1841(2014)12—0080—04ResearchonGlobalPathPlanningAlgorithmofMobileRobotHUANGJing，CHENHan—wei(CollegeofInformation，ZhOiangSci-TechUniversity，Hangzhou310018，China)Abstract：Pathplanningisanimportantproblemofm

3、obilerobots，andabetterpathplanningalgorithmcansearchtheeffec—tivepathsquickly，enhancetheintelligenceofmobilerobotandenhanceinteractionexperienceofusers．ThispaperstudiedtheAalgorithmandgeneticalgorithmandappliedthesealgorithmsinpathplanningofmobilerobotbasedonUnityengine．Pathplan—ningmo

4、duleforvirtualmobilerobotwasimplementedusingtheAalgorithm．Thepathsearchefficiencyisincreasedandtheno—bilerobotsaremoreintelligentandauthentic．Keywords：mobilerobot；artificialintelligence；pathplanning；genericalgorithm；Astaralgorithm0引言文中针对移动机器人智能化中的路径规划问题，着重研究目前，移移动机器人普遍存在行动机械、决策迟钝的问题，无了

5、盲目式搜索算法、A算法和遗传算法，使用A算法在Unity法真正实现模拟自然环境中生物体的行为模式。因此，如何使这平台上实现移动机器人的路径规划模块，旨在提高路径搜索的些移动机器人拥有较为真实的行为能力成为一个研究热点。全局效率，提升移动机器人的真实感。路径规划是移动机器人要解决的重要问题之一，作用是移动机1路径规划算法的研究与分析器人在已知错综复杂的地形的状况下，找到一条到目标位置较优1．1盲目式搜索算法的路径，不仅能够有效避开障碍，而且时间开销较短。由于特殊地深度优先搜索算法(DeepFirstSearch，DFS)和广度优先搜形、障碍、多角色实时移动等因素，使路

6、径规划变得十分复杂。优索算法(BreadthFirstSearch，BFS)是两种常见的搜索算法秀的路径规划方法不仅可以让移动机器人的行为让用户看起来更DFS沿着树的深度遍历地图中的节点，尽可能深地搜索分加智能，而且能够节约大量的运算时间。支节点。当一个节点i的所有子节点都已被探寻过，搜索将回如图1所示，尽管两条路径的长度相同，图1(b)模型显然溯到发现节点i的那条边的起始节点。如果并没有搜索到目标更符合现实中智能体的移动规律。节点，则选择其中一个作为源节点并重复以上过程，整个进程——反复进行直到发现目标节点为止。深度优先算法找到的路径●广●广J通常不是最短或最有效

7、的路径，在场景地形复杂、障碍物繁多厂_J的情况下，搜索到的路线常常偏离目标方向，具有一定的盲目厂_J性，搜索的过程也缺乏移动机器人应有的智能性。图2为深度厂JJ优先搜索的示意图。厂BFS则是从起始节点开始，先访问起始节点的所有子节●I●点，再访问子节点的所有子节点，直到搜索到目标节点为止。这种搜索方式可以搜索到最短的路径，但是算法本身消耗的时(a)路径一(b)路径二间根本无法满足移动机器人决策模块对实时性的要求。图3图1无障碍普通路径规划示意图为广度优先搜索的示意图。使用C／C++实现DFS和BFS搜索算法，解决一个20×20的收稿日期：20131104收修改稿