一种室内清扫机器人路径规划算法

摘要

清扫机器人作为服务机器人领域中的一个新产品已成为人们家庭当中的重要一员,全覆盖路径规划问题是其重要技术之一。提出一种新的路径规划算法,该算法对室内环境进行栅格模型建模,生成一个无向完全图G,对图 G 采用深度优先搜索和广度优先搜索,并应用拓扑排序动态更新图 G,生成最短全覆盖规划路径,最后用生成树来验证该算法的有效性和可行性。%Cleaning robots has become an important one among the family as service robots; full coverage path planning is one of the important technologies. This paper presents a new path planning algorithm, which uses a grid model for modeling for the indoor environment, and generates an undirected complete graph G. It uses depth-first search and breadth-first search combined in figure G, while applying topological sorting constantly updated graph G to generate the full coverage of the shortest path planning. Finally, it uses the spanning tree to prove the effectiveness and feasibility of this algorithm.