一种机房机器人巡视路径生成算法的研究

方案。本文介绍了机房机器人在机房巡视中快速生成最佳巡视路径的一种算法，提高了机房巡视机器人的稳定性和高效性。

关键词：机器人；机房巡视；路径算法

0引言

机房环境和设备巡视是保证机房安全稳定运行，提供信息通信可靠性的一项基础工作，随着现代科学技术的不断进步以及信息通信技术的发展，机房运行可靠性面临着严峻的考验，机房巡视工作也受到了极大的重视。机房巡视机器人凭借其高效性、稳定性等特点，在机房巡视中发挥着越来越重要的作用。对于机房巡视机器人如何在复杂的机房环境中快速找到最佳的巡视路径，本文提出了相应巡视路径生产算法的研究。

1 研究目的

机房巡视机器人系统的整个软件流程如图1-1所示。机房巡视机器人的路径生成算法分为搜索算法和最优路径算法。搜索算法的目的是在未知机房路径的情况下从机房起点搜索到整个机房的巡视路径。最优路径算法要求根据已知的机房信息，在尽可能短的时间内找出一条最优路径，最优路径不仅要短，而且要求弯道尽量少。

2 搜索方法

机器人的搜索方法应满足：一、尽快到达目的地；二、搜索完整个机房。综合考虑，采用了尽快完成路径搜索的方法，这类方法有三种：右手法则、左手法则、向心法则。

2.1右手法则原理

机器人在前进方向上存在两条或两条以上的支路时，优先考虑右转，其次向前，最后才考虑左转。右手法则流程图如图2-1所示。

左手法则与右手法则相似，只不过优先考虑左转，其次是向前，最后才考虑右转。

2.2求心法则原理

求心法则就是当机器人有至少两个方向可以选择时，优先选择向离中心最近的方向前进。确定指向中心的方向時，需要把机房分为四个对等的区域，这里分为1、2、3、4四个部分。通过图2-2可以看出，在区域1中机器人向右和向上能更接近中心。同理，在区域2中机器人向左和向上能更接近中心，在区域3中向下和向右能更接近中心，在区域4中向左和向下能更接近中心。

当机器人可前进方向都是距离机房中心最近的方向时，优先可以选择直线前进方向，其次选择只转90°的方向前进。

如果机器人可前进方向都是远离中心的方向时，优先选择直线运行方向，其次选择转弯90°的方向。

3机房最优路径算法

在对机房搜索完成以后，可能得出了若干条巡视机房巡视的路径，为了寻找出其中最短路径，需要使用最优路径算法。对于机器人走机房来说，经典的最优路径算法有：

1.深度优先搜索（DFS）：从入口出发，顺着某一方向向前探索，若能走通，则继续往前走；否则沿原路退回（回溯），换一个方向再继续探索。直至所有可能的通路都探索到为止。为求出最短路径，必须用DFS算法搜索出所有到达出口的路径，通过比较得到最短距离的路径，这样需要更多数据空间保存搜索的路径，增加了空间复杂度。

2.广度优先搜索（BFS）：从入口出发，离开入口后依次访问与当前位置邻接的单元格（上下左右方向），然后分别从这些相邻单元格出发依次访问它们的邻接格，并使“先被访问的单元格的邻接格‘先于’后被访问的单元格的邻接格”被访问，直至访问到机房出口，则找到了机房问题的最优解，即最短路径。该算法的显著特点是“层层推进”，探索点会随着探索的深入急剧增加，相应地需要大量的空间用来保存探索过程的记录，空间复杂度大。

3.等高图法：通过计算出已经搜索过的各个坐标位置距离起点坐标的步数，每一个单元格坐标记为一步，该步数即为该坐标的“高度”，起点坐标的步数设置为0，将所有坐标的高度值存放在一张二维表中，该表即为等高图。举例来说，从起点可以直接到达的相邻坐标位置的高度均为1，再远的可以到达的坐标的高度值依次递增，距离起点坐标越远的地方，其高度值越大。等高图建立完成后，从起点出发，对所有可行的路径进行查找，在允许前进的方向上，按照比当前坐标的高度值高1的方向前进，直到终点。将所有的可行路径的步数计算出来后，选择其中步数最短的为最优路径。

等高图算法利用高度值对深度优先遍历时的分支进行评估，选择出最佳的分支进行搜索。这种算法相对于单纯的深度优先搜索，减小了算法的空间复杂度和时间复杂度，因此该算法适用计算最优路径。

4 结语

实验分析表明，本文方案具有智能、高效、稳定的特点。能使机房巡视机器人在复杂的机房环境下完成巡视工作，提高了机房巡视效率，保障了机房安全稳定运行，具有较大的使用价值。

参考文献

[1] 林闯，单志广，盛立杰等. Internet区分服务及其几个热点问题的研究[J]. 计算机学报，2000，23（4）：419-433.

[2] 杨帆. 基于负载平衡的新一代核心网络技术研究[D]. 北京邮电大学，2010.

[3] 王晓东.关于计算机网络的发展和应用[J].信息科学，2009（10）：42.

推荐访问： 巡视 机器人 算法 机房 路径

---