路径规划范文

路径规划篇1

【关键词】移动机器人；动态环境；遗传算法；路径规划

移动机器人路径规划就是移动机器人从初始出发点，在一个有障碍物的环境中，找到一条从初始点到目标点的无碰撞最优路径。本文在分析了目前各种路径规划方法优缺点的基础上，采用遗传算法来解决动态环境下移动机器人的路径规划问题。首先针对路径规划问题的特点，对遗传算法的各个环节进行了细致的分析，包括地图环境的建立，染色体的表示和编码、适应度函数的设计，遗传操作算子的设计，算法参数的分析和选取等。然后基于MATLAB和VC++可视化编程语言，开发了基于遗传算法的机器人的路径规划仿真系统。并在动态环境下开展了移动机器人的仿真实验，分析了实验结果。

一、遗传算法

遗传算法是基于自然选择和遗传学原理的搜索算法。它将“适者生存”这一基本的达尔文进化理论引入串结构，并且在串之间进行有组织但又随机的信息交换。伴随着信息交换的进行，优良的品质被逐渐保留并加以组合，从而不断产生出更佳的个体。遗传算法的基本思想是：在问题的求解过程中，把搜索空间视为遗传空间，把问题的每一个可能解看作一个个体，个体里面有基因，所有的个体组成群体。依据某种评价标准对每一个个体进行评价，计算其适应度，并根据适应度对每一个个体进行选择、变异和交叉操作，淘汰适应度小的个体，留下适应度大的染色体，从而得到新的群体，新的群体优于旧的群体。对新的群体再施加自然选择法则，结果一代胜过一代，直到达到预定的优化标准。以上就是遗传算法的基本原理。

二、移动机器人路径规划建模

本文在对移动机器人路径规划时采用栅格法来表示，即用大小相同的栅格来划分机器人的工作空间。首先，移动机器人通过势场生成一个障碍物地图，然后机器人利用障碍物地图来规划一条安全的路径，该路径是使机器人由起点运动到终点的一条无碰路径。障碍物的位置一旦被传感系统如视觉传感器探测到，则赋给与那些位置相对应的栅格一定的初始值，并根据规定的减函数向相邻栅格传播，这样就得到一张障碍物地图。在地图中，用“0”来代表开放的空间，“1”代表障碍物或墙壁，“8”为起始点，“5”为出口。整数表示的地图数组如图1所示：将环境空间划分为独立的栅格空间；首先将环境空间的每个栅格初始化为0；探测障碍物所占据的部分栅格；把1赋给障碍物所占据的栅格；在障碍物地图中，被占栅格上、下、左、右的四个相邻栅格的值neighbor通过规定的减函数decrease来计算，直到计算值小于或等于0，即neighbor [Edirection]=decrease（s，dtreclion），其中direction为0，1，2，3，表示赋值为0的左右四个相邻栅格，s为当前栅格的值，在屏幕上显示的仿真效果图如图1～2所示：

三、基于遗传算法的路径规划实现

（1）问题定义。本文研究的移动机器人运动环境为二维平面空间，环境中的静态障碍物已知，动态障碍物可以探测。这样使得问题便于着手，有利于把重点放在探索遗传算法在这类问题的实际应用上来，为今后研究三维空间内机器人的运动路径规划打下基础。本文将移动机器人视作一个质点，即不考虑机器人的尺寸。本文的目标是要在静态环境和具有少量动态障碍物出现或运动的环境里，为机器人找到一条从当前位置到目标位置的行动路线，要求这条路径满足以下条件：该路径不与任何障碍物发生冲突；该路径应尽可能短；该路径应与障碍物保持一定的安全距离；该路径应尽可能平滑。（2）遗传算子设计。优胜劣汰是设计遗传算法的基本思想，它应在选择、交叉和变异等遗传算子中得以体现，并考虑到对算法效率与性能的影响。一是赌法选择。赌法是把种群中所有个体适应度的总和比作一个轮子的圆周，每一个个体按其适应度的大小占轮子不同大小的扇区。轮子随即旋转后停在哪个扇区，对应的个体就被选中。具体步骤如下：计算每一个个体的适应度值f（xi）；累加所有个体的适应度值SUM=∑f（xi），并记录每一个个体的中间累加值S_mid；产生一个随机数N，0

三是变异算子。变异运算模拟生物在自然界中因各种偶然因素而引起的基因突变。它提供了种群中遗传基因类型的多样性，当交叉操作产生的适应度值不再进化且没有达到最优时，就意味着算法的早熟收敛。这种现象的根源在于有效基因的缺损，变异操作在一定程度上克服了这种情况，有利于增加种群的多样性。

其程序如下所示：Mutate（vector &vecBits）；{for（int curBit=0；curBit

四、路径规划仿真研究

移动机器人的动态环境路径规划是个相当困难的问题。本文所研究的动态环境限于机器人运动空间里一直存在一个或多个不断移动的障碍物。与A*算法进行比较图4（a）为A*算法的仿真结果。图4（b）为本文所用的遗传路径规划方法的仿真结果。由图4和表1数据可得，本文所研究的路径规划方法具有时间短，路程优，可视性强的特点，并能有效的实现路径规划。

本文在分析比较目前各种移动机器人路径规划算法的优缺点的基础上，对采用遗传算法解决静态和动态环境里路径规划问题的方法作了进一步的分析研究。通过在多个复杂程度不同的环境下，分别进行静态和动态情况下的仿真，仿真结果表明，该算法能够成功地规划出近似最优的路径。

参 考 文 献

[1]徐国华，谭民．移动机器人的发展现状及其趋势[J]．机器人技术与应用．2001，20（2）：45～51

[2]龚进峰．数字势场和遗传算法的机器人路径规划的方法[J]．天津大学学报．2002，10（2）：75～78

[3][美]Mat Buckland.Ai Techniques for Game Programming[J]．北京：清华大学出版社，2006

[4]赵翊捷，陈卫东．基于地图的移动机器人定位技术研究[D]．上海：上海交通大学．2002

[5]王仲民，岳宏．一种移动机器人全局路径规划新型算法[J]．机器人．2003（2）：152～155

[6]王醒策，张汝波，顾国昌．基于势场栅格法的机器人全局路径规划[J]．哈尔滨工程大学学报．2003，24（4）：170～172

[7]李智军，吕恬生．遗传算法在自主移动机器人局部路径规划中的应用[J]．机械设计．2000，12（7）： 27～28

[8]杨正华，张秋生．Visual C++游戏编程导学[J]．北京：清华大学出版社，2004

路径规划篇2

【关键词】路径规划；自适应；智能搬运

【Abstract】Intelligent transportation has a very wide range of applications in modern industry. Inproving route planning algorithm is one of the important ways to increase the efficiency of intelligent transportation. Based on Intelligent Transportation Project in China Robocup competition，an adaptive route planning algorithm is designed. The proposed algorithm can be applied to the intelligent classification of garbage and the automation of logistics. Compare with the exist algorithms， it can change the route and destination before the start of transportation.

【Key words】Route Planning； Adaptive； Intelligent Transportation

0 引言

智能搬运机器人主要指按设定的路线，或者使用视觉、磁线、激光导航的自动行驶的机器人。智能搬运机器人是一种自动导向车（Automated Guided Vehicle，简称AGV）[1]， 也称自动导向搬运车、自动引导搬运车。随着AGV的性能逐渐提高，智能搬运机器人被广泛用于工业、农业、医学、国防等领域[2]。路径规划是提高智能搬运机器人性能的一个重要方向[3]。

路径规划指的是根据既定的标准，如何规划一条从起始点到终点的最优路径[4]。根据环境信息的知情情况，路线规划又分为局部路径规划和全局路径规划[5-6]。本文讨论的路线规划以中国机器人大赛中的智能搬运项目为蓝本，利用颜色识别技术设计了一个自适应的路径规划算法，它可以应用于工业自动化过程中自动化物流、垃圾智能分类等领域。

1 可适应的路径规划算法

在描述本文提出的可适应的路径规划算法之前，首先介绍机器人大赛智能搬运项目的比赛规则，在1.2节将介绍根据算法设计的机器人。

1.1 路径规划规则

图1所示为中国机器人大赛智能搬运项目中的使用的场地图。图中黑字A、B、C、D、E、F、G为待搬运的色块所在地，其中A、B、C、D、E可随机放置3-5个色块，F和G点每点可随机放置不超过5个色块。O点所在为起点及终点，图中a、b、c、d、e为目标所在地，机器人要识别待搬运色块的颜色，并搬运到相应的颜色目标所在地，机器人的路径除点a、b、c、d、e外只能为图中黑色的线条。根据要求，设计的机器人必须有颜色识别、路径识别存储等功能。色块共用5种颜色：绿色、白色、红色、黑色、蓝色。本文假设图中目标点a、b、c、d、e 的颜色在搬运前是可以随机调整的，但搬运过程中是固定的，这种假设与生活中的情形比较相符。现有比赛中用到的算法都是固定了目标点的颜色、每个夹角的度数和每段路径的长度，应用性低，因此本文提出自适应的路径规划算法。

1.2 智能搬运机器人设计

本文设计的智能搬运机器人包括如下几个模块：（1）路径检测；（2）转向控制；（3）电机驱动；（4）车速检测；（5）电源管理；（6）物体检测（7）物体抓取；（8）路径规划。主控制器是51单片机，它负责接收赛道数据、赛车速度等反馈信息，并对这些信息进行恰当的处理，形成合适的控制量来对舵机与驱动电机进行控制，采用红外传感器控制小车沿着预设的轨道黑线及时调整车身姿态，使之准确、快速地跑完全程，采用四驱差速来进行原地转向与前进，使用稳压芯片7805稳定电压，用颜色传感器准确识别要抓取物块的颜色，超声波传感器定位需抓取物块，测算出距离出来以便接下来准确的搬运至目的地。实现这些功能共包含电机模块，超声波模块，颜色传感器模块，红外模块，伺服电机抓手模块，电源稳压模块。智能车的设计主要体现在电路板和机械结构上面，车的前部携带着超声波探头，与颜色传感器，用于识别物体，在颜色传感器与超声波探头下面是红外模块用来循迹，来到车身是双层的结构，在上层前端固定着有三个伺服电机控制的抓手，上层的中间是红外驱动模块，车的尾部则是放置电池及电源模块，由一根铜柱支撑着51的最小系统外加电机驱动的模块。而车的下层则是装载着四个电机驱动四个轮子。

本文设计的智能搬运机器人在行驶过程中通过不断地向地面发射红外光来进行路径检测，当红外光可遇到白色地面时发生漫发射，反射光被装在小车上的接收管接收；如果遇到黑线则红外光被吸收，则小车上的接收管接收不到信号，再通过比较器来采集高低电平，从而实现信号的检测，最终形成路径。

1.3 自适应的路径规划算法

所谓的自适应指的是没有完全掌握整个搬运路径，包括目标点a、b、c、d、e的颜色、两点间距离，弧线间角度等，这样，机器人在搬运前必须遍历路径并记录下来。a、b、c、d、e的颜色可在搬运前任意更改，在搬运当中目标颜色不变，每次搬运前机器人都需要自己检测目标点的眼神。为方便描述，假设E和F并无任何块。算法令1代表绿色，2代表白色，3代表红色，4代表黑色，5代表蓝色，用数字来记录颜色，这样如果算法涉及加权，例如aA是一段斜坡，则预算aA可能更花费时间。算法首先要判断障碍色块及目标点a、b、c、d、e的颜色。

该算法如下：

如果点E、F也存在色块，算法类似。算法可以加入权值。

2 结论

本文针对中国机器人大赛智能搬运项目的路径规划算法进行改进，提出自适应的智能路径规划算法，同时开发上位机软件和搬运部件接口。经实验证明，该算法有效可靠，有较高的效率。

【参考文献】

[1]陈书光.机器人路径规划算法探讨[J].商，2012（15）.

[2]宁志刚.一种高效的机器人路径规划算法[J].科技致富向导，2011（18）.

[3]周嵘，张志翔，翟晓晖，闵慧芹，孔庆杰.机器人室内路径规划算法的实用性研究[J].机械与电子，2016（8）.

[4]户硕.搬运机器人的设计与制作[J].煤矿机械，2015（08）.

[5]开思聪.基于STM32控制的仓储搬运机器人.计算机系统应用，2016（7）.

路径规划篇3

关键词：PDDL；VRP；智能规划；物流

中图分类号：U116.2文献标识码：A

Abstract: In order to solve the vehicle routing problem and other extended problems, a modeling and solution method that is based on artificial intelligence planning of PDDL are put forward. Multifarious PDDL models of vehicle routing problem are designed and solved by using SGPlan6 and DaeYa planner. The experiment results indicate the algorithm can provide high quality scheduling scheme of vehicle routing in short time and has better extended capability.

Key words: PDDL; VRP; artificial intelligence planning; logistics

0引言

车辆路径问题（Vehicle Routing Problem，VRP）最早是由Dantzig和Ramser在1959年提出的，通过对车辆运输路线进行优化，在满足客户需求的前提下，达到诸如路程最短、成本最低、耗时最少等目的[1]。VRP自提出以来就一直是运筹学领域国内外学者研究的热点，围绕着问题建模和求解算法研究有大量的研究成果，在物流配送、交通运输等领域也获得了广泛的应用。

VRP存在多种扩展问题，而每种VRP都具有多种优化目标，国内外学者针对这些类型的VRP特点提出了一些特定的建模方法和求解算法。本文基于智能规划的PDDL（Planning Domain Definition Language）语言对VRP和扩展问题进行统一建模，再借助通用的PDDL规划器对VRP进行求解，最后给出一些改进方法以提升利用PDDL求解VRP的效率。

1VRP和扩展问题定义

基本的VRP可描述为：对一系列给定的客户（送货点或取货点），确定适当的配送车辆行驶路线，使其从车场（配送中心）出发，依次访问各客户点，最后访问车场，并在满足一定约束条件下（如车辆载货量、客户需求量）使用数目最少、车辆行驶路程或时间最短等。从定义上看，VRP是考虑多车辆的旅行商问题（TSP）。由于VRP过于简化模型，为了更贴近实际问题，在VRP基础上增加更多的特征形成了多种VRP扩展问题。

带时间窗车辆路径问题（VRPTW）在基本VRP基础上，对各客户点设置了服务时间窗，其中硬时间窗是指车辆对客户的服务必须在该窗口内完成，软时间窗是指当车辆服务超出窗口时，对目标函数给予一定惩罚。

带分割车辆路径问题（VRPSD）是指客户点的需求可以同时被几个车辆分割来服务，可以节约所需车辆数和总的行驶路程。

多车场车辆路径问题（MDVRP）扩展了基本VRP中只有一个车场的约束，多个车场分布在不同区域，但通常限制车辆必须返回出发时的车场。

开放式车辆路径问题（OVRP）中车辆在完成服务后不需要回到出发的车场，即车辆的行驶路线是开发式的，而不是闭合的。

带回程车辆路径问题（VRPB）是指车辆除了向某些客户提供配送服务外，可同时向另外一些客户提供收取货物的服务，这种VRP问题需要充分考虑到车辆载重量的限制。

带取送货车辆路径问题（VRPPD）是指车辆可同时向客户提供配送和收取货物的服务。

多车型车辆路径问题（HVRP）中所用车辆可为多种类型，每种车型的费用和载重量不同，允许限定各车型的数量。

此外，还包括多车程车辆路径问题（VRPMT）、带拖车车辆路径问题（VRPTT）、随机车辆路径问题（SVRP）、模糊车辆路径问题（FVRP）、非对称网络车辆路径问题（AVRP）等多种类型。通过对VRP增加新的属性和特征，这些新的VRP扩展问题更加符合实际需要，也逐步拓宽了VRP的研究广度和深度，但这同时也给VRP进行准确的建模和求解带来了新的挑战。基于智能规划的方法能够实现统一的VRP建模，而这种通用规划语言描述的VRP模型也为下一步统一的VRP求解奠定了基础。

2PDDL智能规划语言

智能规划是人工智能领域中应用性很强的一个研究领域，主要研究关于动作的推理，通过对预期动作的期望效果，选择和组织一组动作，其目的是尽可能好地实现一些预先给定的目标。对于一个智能规划求解系统来说，通常由三部分组成，知识表示、知识存储和知识推理，知识表示是知识推理的前提。PDDL是作为目前智能规划领域应用较多的规划语言，是完成知识表示的主要工具之一。

1998年，McDermott提出了规划领域定义语言PDDL[2]，并逐渐成为国际智能规划比赛IPC公认的标准，PDDL不仅给出了规划问题定义的语法，还从语义的角度给出了规划的定义。2002年，Fox和Long在第三届规划器比赛中提出了PDDL2.1[3]，增加了数值表达、规划尺度和持续动作等新的表达能力。PDDL2.2[4]新增了导出谓词和时间化初始文字这两种表达能力。PDDL3.0[5]在PDDL2.2的基础上进行了扩展，新增了软目标和状态路径约束，增强了对规划质量的表达。

可以将PDDL看作是一种表达动作的语法标准，每个动作的可用性和效果通过动作的前件和后件来描述，前件和后件又是利用由谓词、项和逻辑连接词组成的逻辑命题来表示。一个规划问题由一个域描述和问题描述组成，一个域描述可以对应多个问题描述，其中每个问题描述都表示不同的规划问题。

基本的VRP并不像一个通常意义上的规划问题，因为映射VRP车辆移动的PDDL动作之间只有很有效的因果关系，同时规划的多个目标之间也是一种松散关系。但随着VRP扩展问题不断引入新的属性和特征，如车辆载重能力限制、客户点上不同的需求、时间窗口的约束等，都使得车辆移动路线的选择更为复杂，在这种情况下，利用智能规划能够给求解VRP带来一定的帮助。

3PDDL建模

3.1基本VRP的PDDL建模

对基本的VRP进行PDDL建模，域描述内容参见图1。PDDL域描述中包含2个动作：visit和back，分别描述车辆去客户点提供服务和回程两种移动。车辆的载货量通过loadage函数来定义，当该车访问某个客户点时，loadage函数值的减少量为该客户的需求量。

路径规划篇4

[关键词]：动态环境 虚拟传感器 可回溯势场法 避障策略

1 引言

虚拟人导航的难题涉及到为达到它目标位置，执行动作（或规划）的方针。在执行期间，虚拟人必须对一些不可预见的事件（如障碍）以某种方式做出反应，使之仍然能够达到目标。虚拟人在进行导航的过程中，除了要保持运动的平稳性，还要能避免与静态或动态障碍物发生碰撞。

目前，对于虚拟人路径导航问题，业界已经研究出很多算法，由最开始的无障碍无检测的可回溯瞎子爬山法，到静态环境下进行障碍物检测的全局路径规划方法，这一领域正在逐步的走向成熟。但是，在动态复杂环境下避障路径规划还是一个研究的看点，因为我们的现实生活中所面对的往往都是动态环境。针对这一问题，本文采用了机器人领域中比较成熟人工势场法来对虚拟人进行实时的路径规划，并加入了虚拟传感器对虚拟场景的障碍物进行实时探测。

2 人工势场法

2.1传统的势场函数表示

人工势场法是将虚拟人运行空间模拟成一个有力存在的场地，把力分为引力和斥力。首先在虚拟人的运动空间中创建一个势场U，该势场由两部分组成：一个是引力场Ua，方向指向目标点；一个是斥力场Ur，方向指向障碍物。整个势场U是其引力部分和斥力部分的矢量叠加。势场函数的表示如下：

2.2.1建立势场模型。确定引力场和斥力场的正比例位置增益系数k和 瘙 ，斥力的影响距离ρ0，以及移动的步长，假设虚拟人是匀速运动的，确定虚拟人的起始位置X，按照具体的环境信息建立势场模型；

2.2.2根据建立的势场模型计算虚拟人的受力，利用公式（5）计算虚拟人的合力；

2.2.3虚拟人按合力的方向运动到下一点；

2.2.4判断虚拟人是否到达目标，如果到达则规划结束；如果没有到达则转（2）继续执行。

3可回溯的人工势场法

人工势场法的以其在数学描述上简洁、美观，便于低层的实时控制的优势，在实时避障中，得到了广泛应用。但是该方法同时存在容易陷入局部极小值造成死锁的缺点，即：在相近障碍物间不能发现路径；在狭窄通道中摆动；在障碍物前振荡；存在陷阱区域；当目标附近有障碍物时无法达到目标点。为了避免算法陷入局部极小值，实现了可回溯人工势场法。

可回溯的人工势场法思想是在传统势场法基础上添加了回溯条件，由于在进行路径规划时采用的是八叉树的存储结构，虚拟人的行走路径都被保存Close表的队列中，而Open表保存的是八叉树的第N层和第N-1层节点，所以在虚拟环境中出现上述的极值点时，虚拟人根据Close表中保存的节点来回溯到上一节点，再从Open表的优先队列中查找该节点的兄弟节点下一节点。

可回溯势场法的关键在于回溯条件，这里，我们设置回溯条件为：如果当前节点是初始节点，其斥力大于或等于引力，则转移路径；如果当前节点不是初始节点，其斥力大于或等于引力且无兄弟节点，则进行回溯。

4 结束语

根据人工势场法结构简单以及便于底层实时控制的优点，将其引入到虚拟场景中进行实时避障。通过对虚拟传感器的设计，实现了对障碍物的实时探测，协助虚拟人躲避障碍物。

参考文献：

路径规划篇5

Abstract： Aiming at the problem of GNRON in the application of artificial potential field in robot fish path planning， a fuzzy controller is proposed by combining the artificial potential field and fuzzy logic. When the robot fish falls into the trap area， switch to the matching fuzzy control algorithm， so that the robot fish can quickly get rid of the trap area and move to the target point. Through the experiment， the obstacle avoidance of the robot fish in the global environment is realized， which proves the effectiveness of the method.

关键词：人工势场法；模糊逻辑；仿生机器鱼；避障

Key words： artificial potential field method；fuzzy logic；robot fish；obstacle avoidance

中图分类号：TP242 文献标识码：A 文章号：1006-4311（2017）10-0087-02

0 引言

当前，随着各类机器人技术的不断发展和广泛应用，机器人技术引起了越来越多的高校与研究机构的重视。水下仿生机器鱼由于兼具灵活性和使用性，引起了国内外多数学者的重视。但是由于水下运动环境的复杂性以及水流条件的不可预知性导致出现机器鱼研究的瓶颈。

由于人工市场法具有实时性强、算法简洁且便于数学描述等优点，因此在陆地机器人路径规划中占据主导地位。但传统的人工势场法仍然存在有局部最小值、遇障碍物易导致系统不稳定、动态环境下易产生震荡等各类缺陷。不少学者针对人工势场法存在的缺陷，进行了大量的研究工作，主要从三个方面着手[1]：一是在原有势场函数中补充一些其它新的影响因素，如速度、角度等[2]；二是通过构造其它形式的场，设计新的势场函数[3，4]；三是通过将多种智能算法与搜索算法相结合[5，6]。综合来说，实际当中障碍分布存在有不确定性，与其为了避免局部极小值发生做大量的计算，不如在发生局部极小值时，做出适当处理。

本文首先以人工势场法作为机器鱼路径规划的基础，然后根据机器鱼、目标点及障碍物三者之间的实时位置关系设计了一个模糊控制器，及时引导机器鱼避开障碍物到达目标区域。最后通过实验表明，仿生机器鱼能够成功避开障碍物，以迅速、快捷、平滑的路径到达目标区域。

1 人工势场法的基本原理

人工势场法的本质思想是将现场环境假象成一个势力场U，U由两部分组成：一个是斥力场Urep，驱动机器人远离障碍物；另一个是引力场Uatt， 驱动机器人靠近目标点，机器人在其中运动受到斥力场Urep， 与引力场Uatt，的合力控制。

机器鱼从起点开始在合力作用下沿着既定路径朝目标点进发，此合力在全局范围内为机器鱼导航。

2 人工势场法的缺陷及改进

传统的人工势场法虽然算法简洁，物理意义明确，但是实际应用的时候有其局限性。主要表现为当移动机器人向目标点逼近时，随着引力减小而斥力增大，此时可能会出现合成势场最小值不趋向目标点或者在目标点和障碍物前抖动甚至无法前行等情况。

基于模糊逻辑的路径规划算法的主要优点在于能够在难以建立障碍物位置信息精确数学模型来描述的情况下进行局部路径规划。但如果完全采用模糊逻辑进行路径规划，不仅所需计算量较大，在路径出现突变时，会妨碍对智能体的控制。因此将模糊逻辑和人工势场两种规划算法进行组合，充分发挥人工势场算法简单、控制精确以及模糊逻辑法适应环境能力强的特点。

3 模糊控制器的设计

将机器鱼与障碍物之间的距离d及障碍物相对于机器鱼与目标方向之间的夹角θ作为模糊控制器的二维输入。首先，将输入变量d以VS，S，M，B，VB五种语言变量进行模糊化，θ（φ）的语言变量定义为NVB，NRB，NB，NM，NS，NRS，NVS，Z，PVS，PRS，PS，PM，PB，PRB，PVB。以全局为坐标，当目标点位于障碍物右 （左）侧时，夹角θ为正 （负），机器鱼则右 （左）转为正（负）。输入变量d的模糊分割图形如图1所示。

研究对象机器鱼的运动形式主要以直行，左转弯和右转弯为主。因此，定义左转和右转为七种模糊语言变量。同时，θ、φ选取相同的梯形隶属函数。其隶属度函数分布见图2。

为了保证机器鱼能够有效避障可以设定：当目标点位于障碍物的右 （左）侧时，则机器鱼向右 （左）转，转角大小由障碍物大小及障碍物与机器鱼的间距决定。若障碍物位于机器鱼正前方时，默认机器鱼右转。

根据实验经验，归纳模糊控制规则[8]得表1。

4 实验及分析

在微小型机器鱼实验台上对所述算法进行验证，假想将机器鱼理想化为一条直线，忽略在实际避障过程中的一些误差，总体效果令人满意，能顺利避开障碍物，到达指定位置。

如图3（a），（b）所示，实验环境为一水池长2000mm， 宽1200mm。图中黑色球型为目标点区域，灰色圆柱为障碍物。通过两次实验取得了相同的结果。序列图（a）中从上至下，机器鱼所受合力指引它越过中间障碍物的上方，最终到达目标区域。序列图（b）中，机器鱼从中间障碍物的下方绕过障碍物到达目标区域。实验结果表明，基于混合算法的仿生机器鱼控制效果良好，机器鱼能够以最佳途径到达目标区域。

5 结束语

本设计首先采用传统人工势场法，对一类仿生机器鱼的行进路径进行初步规划，针对人工势场法的局限性，即障碍物目标附近不可达问题（GNRON），设计了二维模糊控制器，在机器鱼陷入陷阱区域时，使用模糊控制算法为机器鱼导航。最后设置一个避障实验，验证了该算法的有效性，且路径平滑。

参考文献：

[1]张捍东，王丽华，岑豫皖.基于势场的移动机器人自主导航研究综述[J].自动化与仪表，2007（4）：8-12.

[2]覃柯，孙茂相，孙昌志.动B环境下基于改进人工势场法的机器人运动规划[J].沈阳工业大学学报，2004，26（5）：568-571.

[3]Ge S S， Cui Y J. New potential functions for mobile robot path planning[J]. IEEE Transactions on Robotics and Automation， 2010， 16（5）： 615-620.

[4]Prahlad Vadakkepat， Kay Chen Tan， Wang Ming-Liang. Evolutionary artificial potential fields and their application in real time robot path[C]//Proceedings of the 2000 Congress on Evolutionary Computation. 2010： 256-263.

[5]A.K. Kulatunga， D.K. Liu， G. Dissanayake， and S.B. Siyambalapitiya. Ant colony optimization based simultaneous task allocation and path planning of autonomous vehicles[C]. IEEE Conference on Cybernetics and Intelligent System， volume 1， pages 1-6， 2015.

[6]Jean Bosco，Xinhan and Min.Fuzzy motion planning among dynamic obstacles using artificial potential fields for robot manipulators[J]. Robotics and Autonomous Systems.July 2013， （32）： 6l-72.

路径规划篇6

关键词 自动泊车；最佳泊车路径

中图分类号：TP182 文献标识码：A 文章编号：1671—7597（2013）041-184-01

经过一百二十多年的发展，汽车逐渐向小型化、智能化和安全化的方向发展。而随着我国经济的发展，汽车的需求量逐年递增。于此同时带来的问题是停车位需求量越来越大。而在国内，城市占道停车不但能有效的满足停车位的需求，而且能有效缓解交通堵塞。但是，对于许多驾驶员而言，顺式驻车通常是驾驶员考试中最令人担心的一项，而且几乎每个人都会在某些地点碰到这样的事情。大城市停车空间有限，将汽车驶入狭小的空间已成为一项必备技能。 很少有不费一番周折就停好车的情况，特别是城市占道停车可能导致交通阻塞、神经疲惫和保险杠被撞弯，占道停车成为了一种痛苦的经历。

在实际泊车中驾驶员的视野狭隘，仅通过后视镜来观察车身后面和车周围的情况，即使如此，也很难准确的把握车尾的情况。不仅如此，驾驶员还要兼顾控制方向盘、油门、刹车和换挡等，易造成操作失误。如果停车时间过长，又容易造成交通堵塞，特别是驾车新手，在缺乏经验的情况下，很难准确停入车位。

基于以上问题，寻找到了最佳泊车路径，以解决广大驾驶员泊车难的问题。

1 自动泊车最佳路径规划

最佳路径虽然可以通过数学建模和泊车经验等方法得出，但可靠性低，运算复杂，而且变量较多，如果通过CAD与Pro/e等绘图软件模拟其几何路径，则可节省多处计算而且能简洁直观的表达。使用CAD绘图软件寻找最佳路径，主要是通过一些相关约束条件和泊车要求绘制最佳几何路径。

1.1 泊车危险点与安全圆

倒车最难在于兼顾控制车辆的时候，难以观察自己车辆是否与其它车辆相撞，经过分析可知，倒车时，最容易触碰的地方是尾部的后对角点和前部的前对角点。根据避免碰撞要求，可以在停车前方的最佳停车位上的对角点绘制一个以汽车前轮轴中点与对角的距离为半径的圆R1，圆R1称为安全圆。

汽车行驶的轨迹为一个个圆弧构成的圆，由此可知，只需要其自动泊车轨迹与安全圆相离或者相切就不会与前方车辆相撞，而后对角点只需控制其倒车行程即可避免碰撞。

1.2 泊车关键圆的确定

自动泊车进入车位是关键阶段，把倒入车位的大圆称为关键圆。首先可以认为轴距是其轨迹圆的一根弦，经分析可知，此圆越大，倒入车位后此弦与水平线所成的夹角a也就越小，泊车就越准确，泊车后需要调整的角度就越小，因此假设关键圆R2与R1相切，且与车位中线相切时可取最大圆，由于与R1安全圆相切，所以能保证两个对角点不与其他车辆发生碰撞，并且有足够的空间可以进行泊车后的角度调整。

由CAD模拟可以直接测量得出R2=5702 mm，又由汽车参数可知模拟车辆最小转弯半径为r=5500 mm，有R2>r，所以其关键圆R2符合汽车的行驶要求。

1.3 泊车辅助圆的确定

辅助圆是为了帮助车辆倒入关键圆的一段圆弧，使得车辆最终在倒车时能够按照R1的轨迹进入车位。经过分析可知，辅助圆R3越大，越是难以矫正车辆进入关键圆R2，故以最小转向半径5500 mm计算，经过测试调查可知，驾驶员使车辆行驶在车道中间较容易控制，所以把初始位置定在车道中线上，故辅助圆需与行驶车道中线和关键圆R2相切，这样便可以确定辅助圆R3。

另外，考虑到变换轨迹时，车辆是以车身前后轴中心的连线即轴距所构成的弦进入R2轨道，所以，需使R3向左平移，使得R3与R2相割所构成的弦与车身前后轴中心的连线即轴距长度相等。经过CAD模拟和测量可知需使R3向左平移452.3 mm，即可获得R3的最终位置。

1.4 泊车路径总结

如上分析和建模可知，找到了安全圆、关键圆和辅助圆，将其合并在一起，即可得到最佳泊车路径如图1所示。

如上所示，驾驶员需要先将车辆行驶至道路中间，当找到停车位时，驾驶员需要寻找一定的参照，使得车量后轮与车位前方车辆的前轮稍后的地方确定初始位置。首先把方向盘右转至打死，开始倒车，车辆进入辅助圆，当车辆与水平方向夹角大致成50度时，再把方向盘左转打死，直到车辆进入车位，再调整车辆与水平线所成的角度，即可进入最佳车位。

如上所述可得到泊车的完整路径，不容易与其他车辆发生碰撞，并且容易确定泊车的初始位置，所以安全可靠，具有较高的可行性。但是，即使最佳路径也不可能一次性倒入车位。第一次倒入车位后需要细微的调整，由于调整路径比较复杂，其规律性需要从汽车试验中寻找规律，所以调整路径暂不使用模拟CAD得出。

2 泊车最佳路径的验证

选择模拟小车对最佳路径进行验证，模拟小车的实际尺寸与研究对象车辆的实际尺寸比为1：10.47，由最佳路径分析中的CAD模拟路径可知，辅助圆半径为5500 mm，而关键圆半径为：5702 mm。验证过程选择PWM波来控制模拟小车转向，查阅资料可得以上辅助圆应当采用PWM波比值约为900/200，而关键圆应当采用PWM波值为：1100/200，再使用单片机控制PWM波的输出进行实验。最终，顺利验证了最佳泊车路径的可行性和实用性。

参考文献

[1]王芳成.自动平行泊车系统的研究[J].中国科技大学，2010.

[2]周健.嵌入式模糊自动泊车系统的研究[J].广东工业大学，2011.

[3]何峰.自动泊车系统的研究及实现[J].广东工业大学，2009.

路径规划篇7

关键词：路径规划；卷烟配送；启发式算法；多目标

中图分类号：F252.14 文献标识码：A

Abstract： The cigarette distribute route problem is a LS-VRP problem with includes the consideration of distance saving and the work balance between each car. This paper found the module with the object of work balance， car saving and distance saving. Then design the route cut based heuristic algorithm to solve the module and get a good effect in the example problem solving.

Key words： route planning； cigarette distribute； heuristic algorithm； multiple objects

在我国，一般以市级烟草配送中心为中心，直接配送到全市各地的上万个配送点。负责卷烟配送的车辆由烟草配送中心出发，依次到其负责的收货点进行配送，最终配送完成后车辆返回配送中心[1]。现有的卷烟配送车辆型号众多，载货量也有区别。卷烟配送路线的规划是一个LS-VRP（大规模车辆路径）问题，是一个NP问题。对于一般的LS-VRP问题有精确算法、亚启发式算法和启发式算法等。

众所周知，我国卷烟配送工作由来已久，因此各地烟草商业企业在发展中已经形成了自己的配货顺序，并根据配货顺序安排配送车辆。这种配货顺序有其存在的合理性，并且已经在运行之中，进行较大的改动有一定的风险。但是传统的车辆配送任务分配主要采取人工的方式进行，工作量大且优化程度较低。另外，在解决大规模VRP问题的方法中，一种思想先按照TSP问题利用算法生成一个全局的配送路线，之后对这个总的配送路线进行截断，来确定分配给每辆车的配送路线，从而生成卷烟配送VRP问题的配送方案。这种方法优化程度较高，而且可以保证较快的计算速度。因此基于大线路截断成小线路进行配送的方法有一定的实际价值。

而且除了总配送路程最短、费用最小、时间最短等一般VRP问题的约束之外，处于管理上的考虑，卷烟配送过程有其特有的特点，例如要求不同车辆工作时间比较均衡且小于上限、车辆之间的配送量均衡等。因此引入了一些原则进行配送任务划分来保证车辆工作强度的均衡。

本文研究的基于配送任务均衡的线路截断方法，属于一种亚启发式算法，主要实现的功能是在收货点配送排序确定的情况下，把这些收货点的配送任务分配给各配送货车。货车从配送中心出发，按照指定的顺序配送其负责的收货点，之后返回配送中心。在这个过程中要考虑配送路径最短、所用车辆最少、配送工作量均衡的要求。

1 模型建立

收货点配送任务序列为：

S=s，s，…，s，…，s

其中s，s，…，s表示n个收货点的收货量。而其角标表示该收货点配送的次序。s为第一个配送，s为第二个配送，依次类推，s为最后一个。每个收货点只能由一个车辆配送。

每个车辆包含标准载货量和标准服务客户数两个指标，这两个指标由车辆的型号和配送人员的工作时间确定。

配送车辆标准载货量为：

V=v，v，…，v，…，v

配送车辆标准服务客户数为：

C=c，c，…，c，…，c

目标函数为：

MinDis=∑d

MinN

MinPv=∑ρv-

MinPc=∑ρc-

式中Dis表示每个配送车辆的配送距离d之和，即总配送距离。N为使用的车辆总数。ρv、ρc分别表示第j辆车的装载量与标准载货量、服务客户数与标准服务客户数的比值，即装载率和服务率，用来衡量车辆的工作负荷程度。、表示了所有车辆的装载率和服务率。Pv与Pc计算了车辆实际装载率、服务率与平均值的差值之和，其值越大表示车辆的任务分配越不均衡。目标函数反映了实际卷烟配送中的实际要求。

2 模型求解

在实际的配送过程中，首先需要设定每辆车的装载率和服务率的上下限值ρv， ρv、ρc， ρc。即车辆的装载率不得高于其上限值，也不能低于其下限值，服务率亦然。这样可以保证车辆的使用率。如果车辆运力紧张的情况下可以将下限值提高，但会降低在配送距离优化中的调整余地。如果需主要考虑配送里程的节约可以适当扩大区间，从而可以在更宽的范围内进行配送任务的划分。

为了保证任务量的均衡和较短的配送距离，本文设计了基于线路截断的亚启发式算法进行配送任务划分。算法的流程如下：

Step1 对每辆车进行模拟装车，以车辆j为例，将待分配任务序列（第一次循环时即为初始S序列）中的收货点从前到后依次装入车辆j中，当车辆j的装载量与服务率之一达到其下限值时，当前最后一个装入的点即为其装载任务的下限点，假设该点为sl，之后继续装载，当车辆j的装载量与服务率之一达到上限值时，最后一个装入的点即为其装载任务的上限点，假设该点为s，则车辆j的可截断区间为s，s。即该车辆的当前配送任务可以是从配送序列的第一个点s开始到s，s中任何一点结束。计算所有车辆的可截断区间。

Step2 找到每个车辆可截断区间内相隔距离最长的一组相邻点s，s，两点之间距离记录为Sav，则车辆的模拟配送任务为s…s，

s是剩余配送任务序列的起始点，即新的s。之后比较所有车辆当前模拟装车的使用效率ρ=ρv+ρc，选择使用效率最高的车型作为当前循环的所选车型，其配送任务为其对应的s…s，将已配送的点以及该车辆从任务序列和备选车型中删除。

Step3 如果最后一个车的使用效率低于平均使用效率的20%，则可以通过调高每辆车的装载率和服务率下限值之后返回Step1，直到将最后一辆车的配送任务分配至其他车辆为止。如果使用效率高于平均使用效率的20%低于85%，则通过调低每辆车的装载率和服务效率下限值返回Step1，可以减少前面车辆的任务量，提升最后一辆车使用效率。如果最后一辆车的使用效率高于平均使用效率的85%则任务分配结束。

若循环20次之后仍无法跳出循环，则输出当前解。

3 仿真实验与数据分析

下面通过Matlab软件编程进行仿真实验。

配送任务序列为某地市实际卷烟配送任务，共712个点。

输入数据：

配送中心与收货点、各收货点之间的距离矩阵，各收货点的收货量，车辆矩阵：

首次循环的装车方案为：

当前总配送里程为1 201km。最后一辆车的使用效率1.96为平均使用效率1.93的1.014%，达到终止条件，配送任务分配完毕。整个算法运行时间为1.87s。

可以看出，该算法可以在很短的时间内完成大规模配送任务的划分，并且较好地实现了配送任务的均衡与配送里程的节约，从而可以针对不同的卷烟需求做出相应的配送方案，从而实现动态任务规划和卷烟敏捷供应的目的。

参考文献：

路径规划篇8

【关键词】人工神经网络 路径规划 移动机器人

1 引言

在移动机器人导航技术应用过程中，路径规划是一种必不可少的算法，路径规划要求机器人可以自己判定障碍物，以便自主决定路径，能够避开障碍物，自主路径规划可以自动的要求移动机器人能够安全实现智能化移动的标志，通常而言，机器人选择的路径包括很多个，因此，在路径最短、使用时间最短、消耗的能量最少等预定的准则下，能够选择一条最优化的路径，成为许多计算机学者研究的热点和难点。

2 背景知识

神经网络模拟生物进化思维，具有独特的结构神经元反馈机制，其具有分布式信息存储、自适应学习、并行计算和容错能力较强的特点，以其独特的结构和信息处理方法，在自动化控制、组合优化领域得到了广泛的应用，尤其是大规模网络数据分析和态势预测中，神经网络能够建立一个良好的分类学习模型，并且在学习过程中优化每一层的神经元和神经元连接的每一个节点。1993年，Banta等将神经网络应用于移动机器人路径规划过程中，近年来，得到了广泛的研究和发展，morcaso等人构建利用一个能够实现自组织的神经网络实现机器人导航的功能，并且可以通过传感器训练网络，取得更好的发展，确定系统的最佳路径。神经网络拓扑结构模型可以分为：

2.1 前向网络

网络中各个神经元接受前一级的输入，并输出到下一级，网络中没有反馈，可以用一个有向无环路图表示。这种网络实现信号从输入空间到输出空间的变换，它的信息处理能力来自于简单非线性函数的多次复合。网络结构简单，易于实现。反传网络是一种典型的前向网络。

2.2 反馈网络

网络内神经元间有反馈，可以用一个无向的完备图表示。这种神经网络的信息处理是状态的变换，可以用动力学系统理论处理。系统的稳定性与联想记忆功能有密切关系。Hopfield网络、波耳兹曼机均属于这种类型。

3 基于人工神经网络的移动机器人路径规划算法

神经网络解决移动机器人路径规划的思路是：使用神经网络算法能够描述机器人移动环境的各种约束，计算碰撞函数，该算法能够将迭代路径点集作为碰撞能量函数和距离函数的和当做算法需要优化的目标函数，通过求解优化函数，能够确定点集，实现路径最优规划。神经网络算法在移动机器人路径规划过程中的算法如下：

（1）神将网络算法能够初始化神经网络中的所有神经元为零，确定目标点位置的神经元活性值，并且能够神经网络每层的神经元连接将神经元的值传播到出发点；

（2）动态优化神经网络，根据神经网络的目标节点和障碍物的具置信息，在神经网络拓扑结构中的映射中产生神经元的外部输入；

（3）确定目标值附件的神经元活性值，并且使用局部侧的各个神经元之间，连接整个神经网络，并且在各个神经元中进行传播。

（4）利用爬山法搜索当前邻域内活性值最大的神经元，如果邻域内的神经元活性值都不大于当前神经元的活性值，则机器人保持在原处不动；否则下一个位置的神经元为邻域内具有最大活性值的神经元。

（5）如果机器人到达目标点则路径规划过程结束，否则转步骤（2）。

4 基于人工神经网络的移动机器人路径规划技术展望

未来时间内，人工神经在机器人路径规划过程中的应用主要发展方向包括以下几个方面：

4.1 与信息论相融合，确定神经网络的最优化化目标解

在神经网络应用过程中，由于经验值较为难以确定，因此在神经网络的应用过程中，将神经网络看做是一个贝叶斯网络，根据贝叶斯网络含有的信息熵，确定神经网络的目标函数的最优解，以便更好的判断机器人移动的最佳路径。

4.2 与遗传算法想结合，确定全局最优解

将神经网络和遗传算法结合起来，其可以将机器人的移动环境设置为一个二维的环境，障碍物的数目、位置和形状是任意的，路径规划可以由二维工作空间一系列的基本点构成，神经网络决定机器人的运动控制规则，利用相关的神经元的传感器作用获未知环境的情况，将障碍信息和目标点之间的距离作为神经网络的输入信息，使用遗传算法完成神经网络的权值训练，神经网络的输出作为移动机器人的运动作用力，实现一个可以在未知环境中进行的机器人运动路径规划。

4.3 与蚁群算法相结合，降低搜索空间，提高路径规划准确性

为了提高神经网络的搜索准确性和提高效率，可以将蚁群算法与神经网络相互结合，蚁群算法的路径规划方法首先采用栅格法对机器人工作环境进行建模，然后将机器人出发点作为蚁巢位置，路径规划最终目标点作为蚁群食物源，通过蚂蚁间相互协作找到一条避开障碍物的最优机器人移动路径。

5 结语

随着移动机器人技术的发展，路径规划作为最重要的一个组成部分，其得到了许多的应用和发展，其在导航过程中，也引入了许多先进的算法，比如神经网络，更加优化了移动的路径。未来时间内，随着神经网络技术的改进，可以引入遗传算法、信息论、蚁群算法等，将这些算法优势结合，将会是路径规划更加准确和精确。

参考文献

[1]朱大奇,颜明重,滕蓉. 移动机器人路径规划技术综述[J].控制与决策,2010,25(7): 961-967.

[2]刘毅.移动机器人路径规划中的仿真研究[J].计算机仿真,2011,28(6): 227-230.

[3]熊开封,张华.基于改进型 FNN 的移动机器人未知环境路径规划[J].制造业自动化,2013,35(22): 1-4.

[4]柳长安,鄢小虎,刘春阳.基于改进蚁群算法的移动机器人动态路径规划方法[J].电子学报,2011,39(5).

[5]范浩锋,刘俊.基于 BP 神经网络的红外目标识别技术[J].计算机与数字工程,2013,41(4): 559-560.

作者单位