文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 能源/化工 > 基于图论的电力巡检机器人智能寻迹方案
侵权投诉

基于图论的电力巡检机器人智能寻迹方案

基于图论的电力巡检机器人智能寻迹方案

研制与开发 王建元,等基于图论的电力巡检机器人智能寻迹方案

79

确、高效、自主地进行路径选择和定位。

如图1所示的“图”(graph)有若干个不同的点u。,u。,…,u。,在其中一些点之间用直线或曲线连接。图中的这些点被称为顶点(vertex)或结点,连接顶点的曲线或直线称为边(edge)。通常将这种由若干个顶点以及连接某些顶点的边所组成的图形称为“图”,顶点通常被称为“图”中的数据元素。

图1“图”的结构

Fig.1

Structureofgraph

对于“图”的转化和存储,可以通过考察实际关联节点的方式来表示顶点间的关系。“图”作为一种数据结构,通常可被定义为:graph=(V,E),即一个“图”是由顶点的集合V和边的集合E组成。

常见的“图”的存储方式主要有邻接矩阵和邻接表。邻接矩阵是表示顶点间邻接关系的矩阵;邻接表采用的是“图”的一种链式存储方式。这里采用邻接矩阵来实现矩阵的存储。本文设计了一个矩阵类动态定义数组大小,这种数组存储方式可以很方便地实现邻接矩阵的定义、存储,矩阵大小的改变可以通过改变存储矩阵中的行列参数实现。用邻接矩阵表示系统的内部节点关系并进行存储,通过分析考察研究对象“图”中顶点问路径的关联情况,从而查找出全部有效路径。

2,路径搜索的图论算法及实现

本文利用图论算法来实现对巡检路径关联信息的分析处理。对于计划监测节点,通常希望获取其他节点与其关联的信息。统计所有关联节点,进行分析。鉴于实际变电站构建情况,应做适当的简化假设:首先,所研究的“图”无自环流的节点,任意2个节点之间存在通路;其次,变电站内布局较为规范,以此生成的“图”亦相对有序,也为地图信息编译工作降低了难度。

2.1

实时巡检路径搜索

路径搜索的经典算法是求单源最短路径的迪杰

斯特拉(Dijkstra)算法[81和求顶点最短路径的弗洛伊德(Floyd)算法[9。0|。两者都可实现顶点间是否存在路径的判断,但是由于这2种算法主要针对路径长短的最优性,所以需要对考察路径进行存储和比较判断,因此占用微机资源,延长了计算时间,在

万 

方数据单一的查询路径环节并不能发挥其算法优势。本文

结合了一种新的算法——Warshall算法。此算法

基于传递闭包(transitiveclosure)算法,不但可以处理“图”中任意2个顶点是否可以相互到达的问题,而且还能找出2点之间的所有路径。

所谓传递闭包是指可达性矩阵A一(a。),其中:

f1

从顶点i到顶点J存在通路“”

l

0

从顶点i到顶点J不存在通路

从而可以找到对于任意一个顶点存在有效路径的其他顶点的集合。

2.2基于传递闭包的路径搜索

传统的迪杰斯特拉算法与弗洛伊德算法都可以实现存在路径的2个节点之间最优路径的选择,然

而在实际应用中,并非都以最优路径进行搜索。对于现场的任意一个检测点与起始点,应找出所有关联路径,根据具体需要,进行有目的的路径选择。

假设巡检地图如图2所示。

图2巡检地图信息

Fig.2

Informationofthepatrollingmap

为了寻取节点1到节点4通路的所有路径,可将图2展开成图3所示的层次图。展开原则为:从要查找路径的源点出发,找出源点能够直接到达的顶点的集合作为第1层,分别找出第1层中各顶点能够直接到达的顶点的集合作为第2层。这里提出了避免死区的搜索方案,令第2层中不能与其相关的前几层中的数据有重复,即后层顶点不可以沿已寻路径再返回上层顶点,如第1层中的顶点2的后续层中不能再出现顶点1,否则将会出现搜索死循环(1—2—1一…)。以此类推,直至找到目的顶点或者再也找不到满足条件的层为止。

第1层第2层第3层

图3路径分层搜索

Fig.3

Pathssearchinglevels

上一页第2页

你可能喜欢

  • 变电站巡检机器人
  • 机器人系统
  • 机器人设计
  • 孕妇饮食大全
  • 怀孕十月
  • 准爸爸注意事项
  • 智能变电站介绍
  • 智能系统

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email