移动机器人混合式全遍历覆盖路径规划算法VIP专享VIP免费

第２７卷第５期２０１３年９月山东理工大学学报（自然科学版）JournalofShandongUniversityofTechnology（NaturalScienceEdition）Vol．２７No．５Sep．２０１３收稿日期：２０１３０８０４基金项目：山东省高等学校科技计划项目（J１３LN２７）作者简介：陈鹏，男，herochenpeng＠１６３．com；通信作者：李彩虹，女，lich＠sdut．edu．cn文章编号：１６７２－６１９７（２０１３）０５－００２２－０６移动机器人混合式全遍历覆盖路径规划算法陈鹏，李彩虹（山东理工大学计算机科学与技术学院，山东淄博２５５０９１）摘要：针对移动机器人在未知环境下的全遍历覆盖任务，将滚动规划与已知环境下的搜索策略相结合，设计了一种混合式的全遍历覆盖路径规划算法．对声纳传感器探测到的环境信息进行滚动规划，把未知区域转化为已知区域．在已知区域，采用有限状态机方式来组织全遍历覆盖路径规划算法，状态之间的转换通过二叉树搜索策略、目标栅格选取策略和两点法搜索策略来实现，并对算法进行仿真．结果表明，移动机器人能全遍历覆盖整个工作区域，重复率低，能有效提高工作效率．关键词：移动机器人；全遍历覆盖路径规划；滚动规划；有限状态机中图分类号：TP２４２文献标志码：AAhybridalgorithmofcompletecoveragepathplanningformobilerobotCHENPeng，LICai‐hong（SchoolofComputerScienceandTechnology，ShandongUniversityofTechnology，Zibo２５５０９１，China）Abstract：Thispaperpresentsahybriddesignalgorithmofcompletecoveragepathplanningformobilerobotunderunknownenvironmentbasedontherollingplanningandknownenvironmentsearchstrategy．Theunknownenvironmenthasbeenconvertedtotheknownareausingtheenvi‐ronmentalinformationdetectedbysonarsensors．Thealgorithmofcompletecoveragepathplan‐ningisorganizedbyfinitestatemachine（FSM）approachundertheknownenvironment．Thestateswitchhasbeenrealizedbythebinarysearchstrategy，targetgridselectionstrategyandtwo‐pointsearchstrategy．Atlastthealgorithmhasbeentestedundersimulatedenvironment．Simulationresultsshowthatmobilerobotcancovertheentireworkareawithlowrepetitionrateandhighworkefficiency．Keywords：mobilerobot；completecoveragepathplanning；rollingplanning；finitestatemachine（FSM）全遍历覆盖路径规划［１］是指在满足某种性能评价指标最优或准优的前提下，寻找一条从起始点开始，且经过工作区域内所有可达点的路径规划．全遍历覆盖路径规划是一类特殊的路径规划，在许多领域都有着广阔的应用前景，特别是很多家用场合，都要求移动机器人具备全区域覆盖的能力．按照对环境知识的了解，全遍历覆盖路径规划可分为环境已知和环境未知的路径规划．已知环境下的路径规划，多采用单元分解法［２‐３］和模板模型法［４］．单元分解法是将环境分解为梯形单元，机器人在梯形单元中做往返运动，并通过邻接图来表示从一个单元到另一个单元的转移．缺点是单元分解过多致使重复率较高．模板模型法是根据覆盖区域获取的环境信息，与各个模板进行匹配来完成遍历．缺点是对环境缺乏整体规划，要求事先定义环境模型和模板记忆，对变化的环境很难处理．对于环境未知情形下的路径规划，郝宗波［５］等提出了基于传感器和栅格地图的路径规划方法，适合简单环境．Hsu［６］等采用离线规划和在线避障方式来完成全遍历，实现过程较为复杂．邱雪娜［７］等提出了基于生物激励与滚动启发式规则的路径规划，适合简单环境，在复杂环境下出现了较多转弯和重复．郭小勤［８］提出了可动态调节启发式规则的滚动路径规划算法，有效减少转弯次数，并解决了U型障碍物区域的连续遍历问题．禹建丽［９］等在犁田式路径规划的基础上，运用回溯法来解决遍历过程中的盲区问题．环境已知的路径规划方法不适用于环境未知的情形，而未知环境下的路径规划方法存在着重复率较高、系统开销大等缺点．为提高工作效率，采用混合式的全遍历覆盖路径规划算法．利用滚动规划把未知区域转化为已知区域．于是，未知...