返回主站|会员中心|保存桌面|手机浏览

《科技资讯》杂志

杂志等级
    期刊级别:国家级期刊 收录期刊:知网收录(中) 维普收录(中) 万方收录(中) 国家图书馆馆藏 上海图书馆馆藏
本刊往期
站内搜索
 
友情链接
  • 暂无链接
首页 > 杂志论文 > 智能体路径规划算法研究综述
杂志文章正文
智能体路径规划算法研究综述
发布时间:2018-12-03        浏览次数:25        返回列表

光晓亮 杨丽圆

摘  要:Agent路径规划指的是智能体在运动的过程中构成路径的策略。从Agent的传感器获取到的障碍物信息为动静的角度来看,路径规划有两种规划方式,一是智能体处于静态环境下的路径规划,二是智能体处于动态环境下的路径规划。该文对近年来的路径规划算法进行相比较,指出未来路径规划的研究方向和趋势。

关键词:智能体  策略  路径规划

中图分类号:TP2   文献标识码:A            文章编号:1672-3791(2019)05(a)-0023-02

路径规划是Agent系统设计中研究的中心问题。它基于一定的性能指标,比如Agent在进行路径规划时所走的长度最短、利用路径规划算法进行路径搜索时所用的时间最少、路径规划完成之后Agent所消耗的能量最少等指标,在其任务区中搜寻出一条或多条从起始点到目标任务点的最优或近似最优路径。路径规划应用于各个方面,例如:国防军事、抢险救灾、物流管理、道路交通、路由问题等。

1  路径规划研究现状

经过这些年的研究,当前的路径规划算法有很多种类别和方案,每种算法各有所长,各有所短,并且其所适用的范围也大有不同。有的算法适用于二维空间,而有的算法适用于三维空间。有的算法灵活性好,但计算的路径并不太令人满意,而有的算法尽管灵活性差一些但所规划的路径却是使人满意的,有着较好的平滑度并且路径长度也较为合适。但是归根结底都可以划分为动静态两类路径规划算法,一个是静态路径规划算法,另一个是动态路径规划算法。

2  静态路径规划

Agent的传感器获取到的障碍物的信息是静态的,并且所处任务空间的信息状况是能够获得的,比如说温度的高低、形态特征等信息,这个时候叫作静态的路径规划。主要方法有:栅格法、可视图法、概率路径图法、拓扑法等。下面对这几种典型算法进行了相应的研究并分析其优缺点。

栅格法将Agent的任务空间按照二进制进行划分,Agent在路径规划的时候能够正常通过的区域通常情况下用数字0来表示,不能通过的区域也就是所谓的障碍物区域则用数字1来表示。在栅格法中,网格大小的设计尤为关键。一般情况下将网格的大小设计要根据所处环境或者是所需的性能指标来进行设计,如果要求的路径精度高且对时间没有要求的话可以将网格划分得小一点,如果对规划路径的时间要求较高且对于路径的长度要求不大,那么可以选择的网格可以大一点,虽然得到的所规划的路径并不是路径最短或者是平滑性特别好的路径但是依旧可以满足时间短的要求。当然,一般情况下尽量选择的网格大小较为适中是比较好的方案。

可视图法的基本思维是把智能体当作一个点,而后利用线段衔接Agent的起点、目标点和障碍物的所有顶点,此处所说的障碍物指的是多边形的障碍物,并非圆形障碍物,由衔接的线段所构成的图形叫作可视图。在这种情况下可视化的图形便将性能最优路径问题转换为了从start到destination的间隔最短问题。它还能够使用一些优化算法来删除一些多余的线段,进而提高Agent在进行路径规划时的搜索效率。但是这种方法没有考虑到Agent比如形状、大小等形态特征,招致Agent在经过障碍物时摩擦甚至碰撞障碍物,而且它欠缺灵活性,只适用于低维空间。

概率路径图法[1]在配置空间通过随机抽样构造路径图,然后通过查找法得到Agent的路径规划方案。这种算法一般情况下通过3步来进行路径规划:(1)任务空间样点采样;(2)对采样点进行碰撞检测;(3)判断、检查采样点间的连通性。概率路径图法具有其复杂性与规划空间的维度和规划空间的大小无关,而只与路径搜索的困难有关的独特优势,但是传统的概率路径图方法效率较低。

拓扑法的基本思维是将任务空间进行相应的分类,通常情况下将任务空间分为三部分,分别是可行走空间、障碍物空间和介于可行走空间与障碍物空间的中间空间,而后搜寻每个子空间及其连接的子空间,接下来计算它们之间的连通性。从而建立了拓扑网络。利用拓扑法进行路径规划,不仅降低了三维空间路径规划和上层空间路径规划的难度,并且能够很好地接受Agent的移动所产生的位置误差。因为一般来说,这种方法在运动过程中并不需要Agent的确切位置,然而当任务空间中的障碍物分布情况发生变化时,拓扑网络的重建将是一个棘手的问题。

3  动态路径规划

任务空间中障碍物信息只知道一部分或者完全都不知道,传感器从任务空间中获取到的障碍物信息是动态的,称为动态路径规划。主要方法有:人工势场法、模糊逻辑法、蚁群算法等。接下来对这几个路径规划算法分别进行介绍。

人工势场法[2]的基本思想是人为地将移动智能体所处的空间虚拟成一个空间场,并且把目标点对智能体产生的场力称为引力并且引力随着距离的减小而增大,把障碍物对智能体产生的场力称为斥力并且智能体与障碍物的距离越大斥力越小,任务空间中的势场是目标点对Agent的引力和障碍物对Agent的斥力的合力,Agent通过合力从起始点到达目标点。与其他算法相比,人工势场法通俗易懂,没有繁琐的计算量,并且生成的路径较为光滑,但也存在着好多缺陷:当智能体经过狭小的通道时会有摆动现象从而导致路径规划失败;动态环境适应性差;当智能体、目标点和障碍物处于同一条直线上时容易出现目标不可达问题或者陷入局部极小值问题等。由于该法存在上述的种种问题,一些学者便提出了相应的解决方案,如构造一个新的势场函数,从而减少或使其不带局部极小值点;引入了其他的场力,以引导Agent离开局部最小点;它还可以与模拟退火算法等其他搜索算法相结合,使用它们没有局部极值的特点。

模糊逻辑算法基于经验,通过查找表获取规划信息,模糊控制逻辑算法实时性好,不存在局部极小值问题。由于目前还没有较为系统的理论方法来设计模糊隶属函数及控制规则,所以如何设计隶属函数和控制规则是研究者在利用此法时需要攻克的问题。

蚁群算法的原理是蚂蚁在寻找食物的时候会遗留下激素。蚂蚁之间通过激素留下的特殊气味来进行彼此间的交流,蚂蚁群在某一条路径上所遗留下的激素越多气味越大,团体内的其他蚂蚁便根据激素所散发出的气味的强度来选择路径。蚁群算法是一种新型的启发式搜索算法,利用蚁群算法来解决比较复杂的优化问题时,有它的独到之处,具有很强的寻路能力。但是它在进行路径规划的时候耗时且实时性差。它是一种基于群体的并行分布式进化算法,易于和其他的启发式算法相结合。蚁群算法没有统一系统的分析方法,还需要坚实的数学基础,并且需要大量的实验和长期实验积累的经验来进行参数的设定,不太适合用于路径规划。

4  结语

路径规划算法有很多,一些研究学者对那些传统的、经典的算法所提出的改进算法亦有很多,但是依旧有很大的改进空间,在探究路径规划算法的过程中,可以综合考虑各种因素,比如能量消耗、Agent自身特性等。在实际的环境中进行路径规划的时候,将上述两种类型的算法有效的结合在一起,利用各自的优点来弥补各自的缺点,同时再结合良好的建模方案,从而得到最优或次优方案。目前虽然已有相应的算法应用于实体上,但依旧不太成熟,要是真正地将路径规划方法应用于生活当中,大量问题尚待发现和解决。

參考文献

[1] 陈家照,张中位,徐福后.改进的概率路径图法[J].计算机工程与应用,2009,45(10):54-55,58.

[2] 安林芳,陈涛,成艾国,等.基于人工势场算法的智能车辆路径规划仿真[J].汽车工程,2017,39(12):1451-1456.