聚类引导搜索的移动机器人路径规划方法

本文提出一种聚类引导搜索（cluster guide searching，CGS）的路径规划方法。采用基于最大最小距离的K均值聚类方法对样本进行离线聚类学习，学习结果以相似环境相似决策的知识形式进行存储。路径规划过程中，机器人在线整理环境信息，获得输入空间样本，通过与知识库匹配，检索到最近的类别，然后在该类别内部采用速度优先策略和方向优先策略交替的方式搜索输出空间。若知识不完备导致检索失败，可重启线性规划算法（linear programming，LP）进行在线路径规划，并更新聚类知识库。仿真结果表明该方法是一种有效的路径规划学习方法。

This paper proposes a cluster guide searching (CGS) based path planning method, which min-max-K means clustering method is taken for clustering offline. The result of the clustering, namely the knowledge, is stored in the database with a style of similar-environment with similar-decision. When planning online, the robot acquires the input sample from the real environment and then fetches the matched cluster from the database, which is nearest to the current environment. Velocity-first or direction-first strategies are alternatives when searching the decision inside the cluster. If the searching process is fault due to the incomplete database, the Linear Programming algorithm will be called to plan online, and the database then updates based on the planned result. The effectiveness of this method is demonstrated through a simulation.

国家自然科学基金资助项目（60705028）