Dijkstra改进算法在地震救援中的应用

讨论关于地震救援机器人行走避障的最短路径问题.首先用了Dijkstra最短路径的改进算法,得出其最短路径.但由于这样得出的路径往往会有很多迂回,所以又对其进行一定的优化,最终得到一条较为合理的路径,达到省时和运算代价少的目的.

嚣霎弘渊裂-簟

Dijkstra改

进算法在地震救援中的应用

邓博斌

(南京邮电大学计算机学院江苏南京210046)

[摘要n}论关于地震救援机器人行走避障的最短路径问题。首先用TDijkstra最短路径的改进算法。得出其最短路径。但由于这样得出的路径往往会有很多迂回，所以义对其进行一定的优化，最终得到。条较为合理的路径，达到省时和运算代价少的H的。

[关键词]Dijkstra改进箅法地震救援最婧路径最幻路杼优化机器人避障算法中图分类号：TB9

文献标识码：A文章编号：1671--7597(2008)”20138一01

一、引■

2008年的四川汶川火地震给我国特别是四川人民造成了巨大的损失。并且日后救援工作也面临重重困难。救援队员们j{能靠人上的方式来抢救，面对这种刻不容缓的时刻，效率却硅得比较不尽人意，而且还Il，能会给救援人员带来种种乍命危险。这里我们叮以设想一下，我们能否把机器人应用到救援r作巾?对j：在地震救援中使用机器人，可以总结出以卜．优点：

(1)机

器人通过传感技术可以具有独立的枪测牛命气息能力，可以较准确地定位伤者的位置。(2)机器人具有比人更大的气力，且小会劳累，可以日以继夜地工作。(3)

‘定程度上减少了救援人员的危险，包括房屋倒塌，瘟疫

等。本文利用了经典的最短路径算法Dijkstra，对地震救援机器人的行走路径作出了研究和优化，使其剑目的地的距离尽可能短，为该类机器人的实现做一定的铺挚。

=、地形分析和数据结构的建立

假设地表乌瞰状况如图2．1所示，该图可以由卫星拍摄，再传送给机器人。机器人必须有一定的模式识别能力，对于发送过来的图片，可以识别出障碍物和空地。

◆图2．1中，黑色多边形指的是障

■

四

碍物，星号表示目的地。机器人表示起点。现在的『nJ题是，机器人如

▲舞譬竺曹寓譬篓≯釜燃墨警曩

◆

调路径的短。因为在机器人移动速率相等的情况F，路径越短就越能I_

▲¨▲会

节省时间，特别是在地震救援这种

分秒必争的时刻硅得m为重要。

这里，我们引入Dijkstra最短路径算法。在计算最短路径之前．我们首先定义节点。我们可以用以下方法确定：

障碍物的每个角都对应于一个节点。该节点在这个角的角平分线卜，并且位于距离角顶点略大j：R的非障碍物吒域。其中，R为机器人的半径，设置距离略大fR是为了避免机器人和障碍物发生摩擦或碰撞。

给图中每个节点一个标识符(这里用数字表示)，把任意两个节点的连线不经过障碍物的两个节点连结起来。这里錾讨论一个细竹『u】题：如果连接时和已经连好的路径相交，理论上也町以把该路径加入图中，但这样傲并不口，取。因为

来这样会加人数据最，

图2．2

给计算处理造成很大的负担，

另外。计算处理后期还可以对路径距离进行优化。在连接好箝点的基础上．计算出每条路径的代价，这里代价主要指路径的长度，就町以得到图2．2(省略了代价数值)。

三、Dijl馆tra量短路境算法的改进与■短路径的实现

如何寻找从机器人的起始位置到H的地在图中的撮烯路径昵?我们可以运用经典的Dijkstra最短路径算法，但这里我们有必要对它作出一定的改

圊

进，其原因是：在地震救灾过程中，时间足很’矗贵的。经典的Dijkstra最短路径算法足计算对某一确定起点到其它任何‘节点的最短路径。这明显足做了很多无用功，我们只关心从一确定起点到另一确定终点的最短路径，我们没必要计算所有节点。

我们知道，经典I)ijkstra算泫计算时是按从起始节点到其余节点的最短路径长度m小到大的逐个加入最短路树中的，而且加入r最短路树中的每一个节点的最短路径都已经求出。所以Dijkstra改进算法的基本思想可以如下：以始发点(假设为UO)为树根，按照跑u0的最短距离以及竹点的相邻关系，逐次放入树中，I{{近至远，直到目标点放入树中，形成最短路树，树上每一个节点与u0的路径都足最短路径。其悟点标记与Dijkstra算法完全相同。算法步骤的方法、原理也丰H同，只是算法的停止条件足H标点是甭进入最短路树，而／fi足把所有住点是古都标记作为运算停止的判断条件，囡此计算量则大大减少。

另外，为r进一步提高运算速度，我们可以筛选出部分节点小参加Dijkstra算法的求解。这样可以避免

由于l乜了地图巨人的道路扮点数而带来的超额运算量，从而大大降低算法的运算强度，提高运行效率。

经过以上改进Dijkstra算法的初步处理，可以得出一条最短路径，如图3．1

同3．1所示。

观察图3．1我们会发现该路径存在很多转弯迂回的地方，如果按此路径走消耗的时问也／fi少，我们可以对该路境进行进‘步的优化。虽然优化路径会消耗。定的时问，但处理优化的耗时和机器人进行多余的迂回机械运动消耗的时问比起来是微不足道的。在机器人行走速度一定的情况卜．，H『以大大减少到达H的的时问。

优化办法以图3．1为例说明：(1)初始化，令i=l，n=8，k=n。

(2)从{号节点开始，给k符点作连线，检查该连线是否通过障碍物(不能忽略机器人的半径R，否则会发生磨擦或碰撞)。小通过则转(4)；通过障碍物时．如果k==i+2时，转(3)，否贝ljk：k—l。转(2)。

(3)若i—n，转(5)：否则i=i+l，k=n，n=n一((k一1)一(i+1)+1]，

k=n，并对剩余的且大于i的节点进行重新顺序编号，i=i+l，转(2)转(

2)。

(4)把该直线作为路径加入图中，删除编号为i+l到k-1的节点和相关

边。

(5)算法结束。

注意：上面的“一”表示等于关系，“=”表示赋值符，n表示要优化的图中的节点数。该算法得出的路径并不是最优路境，但其实现起来相对简单。最终可得到如下的路径。见}冬13．2．

四、结语

图3．2

(下转第179页)

本文来源：https://www.bwwdw.com/article/veh4.html