模板智能移动小车AGV简介.ppt

算法A*(A)的程序流程说明： ①???? 把起始节点ns代入OPEN。 ②???? 如果OPEN是空表，由于路径不存在，所以算法终止。 ③???? 从OPEN取出先头(费用f最小)的节点n，并把它移到CLOSED。 ④???? 如果节点n是目标节点ng，则顺次返回到来自的节点上(程序上是追寻(返回)指针)。然后，若是到达起始节点ns，则终止算法，得到一个路径。 ⑤???? 如果不是这样，扩展节点n，把指针从其子孙节点n’返回到节点n(记住从哪来的)。然后，对所有的子孙节点n’做以下工作: 节点n’如果不在OPEN或CLOSED表中，则它就是新的搜索节点。因此，首先计算估计值h(n’)(从节点n’到节点ng的最短距离的估计值).其次,计算评价值 f(n’)=g(n’)+h(n’) (这里g(n’)=g(n)+c(n、n’),g(ns)=0,c(n、n’)是连接节点n和n’弧的费用)。然后，把节点n’同估计值f（n’）都代入OPEN。 · 若节点n’存在于OPEN或CLOSED表中，则它就是已被搜索的节点。于是，把指针换到带来最小值g(n’)的路径上(变更来自的地方)。然后，在这个指针发生替换时，若节点n’存在于CLOSED中，则把它返回到OPEN后，再计算值f(n’)=g(n’)+h(n’)。 ⑥ 返回到② 最新. * 算法A*(A)的程序流程 最新. * 估计值h比真值h*小或相等时，上述的算法变为A*，可选出从起始节点ns到目标节点ng的最佳路径(总计费用最小的路径)。 若估计值h比真值大， h*算法则变为A，可选出从起始节点ns到目标节点ng的满足要求的路径(总计费用不是最小的路径)。 因此，机器人的路径规划多用从当前地点( , , )到目的地( , )的平方范数 定义估计值。这个估计值h常常比h*小，成为算法A*，用它可选择最佳路径。 图7-20的搜索图G存在估计值h(在节点上用括号给出)比真值h*大的节点。例如，节点A和H的估计值h是8和4，但到达目的地的最小真值是7和2。由于这个费用评价过大，存在于最短路径上的节点H等可以忽略，算法错过了费用8的最佳路径，最终得到费用9的满足要求的路径。 最新. * E D F G H I B C A S (7) 3 2 (5) (5) (5) (3) (8) (1) (4) (3) 2 2 1 3 3 2 3 2 2 4 4 1 图7-20 搜索图G(有的地方估计值比真值大) E D F G H I B C A S (7) 3 2 (5) (5) (5) (3) (8) (1) (4) (3) 2 2 1 3 3 2 3 2 2 4 4 1 图7-20 搜索图G(有的地方估计值比真值大) 最新. * B（8） 最新. * 起始节点S被代入OPEN[图7-21(a)]，子节点A和B被代人OPEN[图7-21(b)]。起始节点S扩展后移到CLOSED， 由于节点A、B的评价值分别为10、8，所以选中扩展节点B 。B的子节点D、E、F，评价值分别为9、8、10，全都代人OPEN，扩展后节点B被移到CLOSED[图7-21(c)]。 节点E评价值最小，选中扩展节点E。E的子节点H同评价值10都代入OPEN，扩展后节点E被移到CLOSED。 OPEN中当前评价值最小的子节点是D，所以选中节点D。 D的子节点H被再次搜索 ，节点D被移到CLOSED。注意到节点H的值g，由于过去的费用6(经由节点E、B返回到节点S)比新的费用7(经由节点D、B返回到S)小，所以不更换指针[图7-21(d)]。指针仍在E。由于当前OPEN上存在评价值f都为10的三个节点A、H、F，此时须对这三个节点A、H、F都分别向下扩展。 最新. * 第七章 自动导引车 7.1 概述 自动导引小车是一种以电池为动力，装有非接触式导向装置的无人驾驶自动运输车(见图7-1、7-2)。其主要功能是，在计算机控制下，通过复杂的路径将物料按一定的停位精度输送到指定的位置上。 最新. * 7.1.1 AGV的发展现状 20世纪50年代中期，Barret公司设计出无人驾驶卡车，也就是AGV的最早雏形。后来，美国物料搬运研究所将其定义为AGV，它是可充电的无人驾驶小车，可根据路径和定位情况编程，而且行走的路线可以改变和扩展。据报导，到1960年时，欧洲就安装了各种型号不同水平的自动搬运车系统，使用了13,000多台AGV。1959年AGV开始用于仓库自动化和工厂作业中。日本也从这时开始引进AGV技术。日本是使用这种车辆最多的国家，在20世纪80年代末，拥有各种类型的自动搬运车超过一万台，其生产厂家达47家，广泛应用于汽车制造、机械、电子