第３１卷第５期南京理工大学学报
Ｖ０１．３１Ｎｏ．５
１塑！篁！！旦墅！！型堡望！翼！竖望堕！！塑墅堕！！丝！些竺！！墼！型！墅垒丝；！坚坚
复杂环境中基于圆弧区域分解的局部路径规划
成伟明，唐振民，赵春霞，陆建峰，刘华军
（南京理工大学计算机科学与技术学院，江苏南京２１００９４）
摘要：该文根据轮式车的运动学特点，针对机器人导航中安全性问题以及算法实时性要求，提出了基于圆弧的区域分解方法。在此基础上引入了对区域安全性的模糊子集描述，建立了代价函数，得到了符合轮式车运动学特点的局部路径。在实际系统中的运行结果表明，该算法能很好地满足复杂环境下机器人自主导航的局部路径规划要求。关键词：自主导航；局部路径规划；避障；区域分解中图分类号：ＴＰ
２４
文章编号：１００５—９８３０（２００７）０５—０５９５一０５
ＡｒｃＲｅｇｉｏｎＤｅｃｏｍｐｏｓｉｔｉｏｎＢａｓｅｄＬｏｃａｌＰａｔｈＰｌａｎ
ｉｎＣｏｍｐｌｅｘＥｎｖｉｒｏｎｍｅｎｔ
ＣＨＥＮＧ
Ｗｅｉ—ｍｉｎｇ，ＴＡＮＧ
（Ｓｃｈｏｏｌ
Ｚｈｅｎ－ｍｉｎ，ＺＨＡＯＣｈｕｎ・ｘｉａ，ＬＵＪｉａｎ－ｆｅｎｇ，ＬＩＵ
Ｔｅｃｈｎｏｌｏｇｙ，ＮＵＳＴ，Ｎａｎｊｉｎｇ２１００９４，Ｃｈｉｎａ）
ａｒｃ
Ｈｕａ－ｊｕｎ
ｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄ
Ａｂｓｔｒａｃｔ：Ｂａｓｅｄ
ｏｎ
ｔｈｅｋｉｎｅｍａｔｉｃｓｏｆｃａｒ・ｌｉｋｅｖｅｈｉｃｌｅ．ａｌｌｒｅｇｉｏｎｄｅｃｏｍｐｏｓｉｔｉｏｎｂａｓｅｄｍｏｔｉｏｎ
ｐｌａｎｓｔｒａｔｅｇｙｉｓａｄｏｐｔｅｄｔｏｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍｓｌｉｋｅｓａｆｅｔｙａｎｄｒｅａｌ・ｔｉｍｅｒｅｑｕｉｒｅｍｅｎｔｓ．Ｆｕｚｚｙｓｅｔｓｄｅ－ｓｃｒｉｂｉｎｇｔｈｅｓａｆｅｔｙｏｆｔｈｅ
ａｒｅ
ｒｅｇｉｏｎ
８ｔ－ｅ
ｃｏｎｓｔｒｕｃｔｅｄｗｉｔｈ
ａｃｏｓｔ
ｆｕｎｔｉｏｎｔｏｇｅｎｅｎｒａｔｅ
ａ
ｌｏｃａｌｐａｔｈｓｔａｆｆ一
ａＤｇ
印ｎｇ
ｃａｎ
ｋｉｎｅｍａｔｉｃｃｏｎｓｔｒａｉｎｔｏｆｔｈｅｍｏｂｉｌｅｒｏｂｏｔ．Ａｃｔｕａｌｅｘｐｅｒｉｍｅｎｔｓｈｏｗｓｔｈａｔｔｈｅｒｅｓｕｌｔｓｆｕｌｌｆｄｔｈｅｐａｔｈｐｌａｎｉｎｇｑｕｅｓｔｏｆａｕｔｏｎｏｍｏｕｓｎａｖｉｇａｔｉｏｎｉｎｃｏｍｐｌｅｘｅｎｖｉｒｏｍｅｎｔ．
ｎｉｃｅａｎｄ
Ｋｅｙｗｏｒｄｓ：ａｕｔｏｎｏｍｏｕｓｎａｖｉｇａｔｉｏｎ；ｌｏｃａｌｐａｔｈｐｌａｎ；ｏｂｓｔａｃｌｅａｖｏｉｄａｎｃｅ；ｒｅｇｉｏｎｄｅｃｏｍｐｏｓｉｔｉｏｎ
未知复杂环境下的移动机器人自主导航，作为机器人自主能力的一种重要体现，一直以来都是国内外自主导航研究的重点和热点。近年由
Ｍｅｌｌｏｎ
Ｕｎｉｖｅｒｓｉｔｙ，卡耐基梅隆大学）、Ｓｔａｎｆｏｒｄ
Ｕｎｉ－
ｖｅｒｓｉｔｙ等一批著名高校和研究机构的参与和关注。环境的复杂性要求使用更多更精确的传感器，以提供足够的环境地形信息；同时，进行环境理解与路径规划时。要求能够充分利用已有信息，及时弥补传感器缺陷，实时处理任何突发事件，以
ｎ删（Ｄｅｆｅｎｓｅ
ＡｄｖａｎｃｅｄＲｅｓｅａｒｃｈ
Ｐｒｏｊｅｃｔ
Ａｇｅｎｃｙ。
美国国防部高级研究计划局）举行的两届ＧｒａｎｄＣｈａｌｌｅｎｇｅ越野大赛吸引了来自ＣＭＵ（Ｃａｒｎｅｇｉｅ
收稿１３期：２００６—０３—２７
修回日期：２００７—０６—２２
作者简介：成伟明（１９８１一），男．江苏兴化人，博士生，主要研究方向：人工智能，路径规划．智能导航，Ｅ・ｍａｉｈ
Ｗｅ・
ｉｍｉｎ９１９８１＠１２６．哪；通讯作者：唐振民（１９６１一），男，教授，博士生导师，主要研究方向：人工智能，图
像处理，智能导航．Ｅ－ｍａｉｌ：ｔａｎｇ．拗＠ｍａｉｌ．ｎｊｕ毗，ｅｄｕ．ｃｎ。
南京理工大学学报第３ｌ卷第５期
对机器人提供最好的决策支持。
复杂环境下机器人的路径规划要综合考虑路程、时间、安全性、隐蔽性和机动性等指标，选择最佳路径，而不是简单地选择从起始点到目标点的最短无碰路径规划”］。早期的近似栅格法”１是目前应用较广的一种路径规划算法，但其计算量大．不适于实时动态环境。１９９１年，Ｂｏｒｅｎｓｔｅｉｎ等针对虚拟力场法（ｖｅｃｔｏｒ
ｆｉｅｌｄ
ｈｉｓｔｏｇｒａｍ，ＶＦＨ）的
缺点提出了向量场直方图法”ｏ，是目前多障碍物环境中局部路径规划广泛采用的一种方法。但ＶＨＦ未考虑机器人自身宽度和运动学特性，给出的路径实际上很难完成。针对ＶＦＨ的缺点，１ｗａｎ等又先后提出了ＶＦＨ＋”１和ＶＦＨ｝［５３算法。其目的都是希望通过简单的几何线条分解当前的局部环境，进行快速规划。
本文提出一种适于复杂环境下轮式车自主导航的局部路径规划算法。在全局规划的指导下，该算法通过基于圆弧的区域分割迅速将局部环境分解成可通行区域和不可通行区域。在此基础上，利用模糊子集对可通行区域的安全性进行描述，并建立了可通行区域的通过代价函数。算法的设计考虑了轮式车辆的非完整性约束对规划路径的要求，以及机器人自身的宽度对避障安全性
的影响。在实际试验中，该算法取得了令人满意
的效果。１
基于圆弧区域分解的局部路径规划
算法
图１为算法的试验环境。由于试验环境地形
相对复杂，没有道路环境中的白线或者路标等标识，在二维图像上很难找到明显的路边信息，可靠的环境信息一般来自于三维视觉。
图１算法试验环境
在本文的局部环境中，局部路径规划算法充分考虑并且满足以下４个要求：（１）算法实时性，
每次运行时间要尽可能短；（２）考虑机器人避障过程中的安全性；（３）路径对于控制模块可执行，是否违反了机器人自身的运动学约束；（４）满足以上条件的最短路径。
１．１基于圆弧的可通行区域生成
由于视觉传感器的视野范围有限，因此，试验中，比较准确的环境数据范围是机器人前方一块固定大小的矩形区域”’“。本文分解算法即针对当前这块可视区域，以车体中心为原点，当前航向为Ｙ轴正向，垂直于Ｙ轴向右为ｘ轴正向，分解算法描述如下：（１）先对每个障碍作包络圆弧，圆弧通过车体中心，并且与当前航向相切。圆弧所属圆方程为（』一Ｒ）２＋ｙ２＝Ｒ２（１）
式中月的计算方法如下
“一１０
。ｆ（《＋ｄ；）／（２ｄ，）ｄ。≠ｕ
…¨’
ｄ：：０
式中ｄ…ｄ为圆弧所经过的障碍顶点的坐标。这
里，Ｒ不是非负的，当顶点位于车体坐标左半边时Ｒ＜０，否则Ｒ＞０，圆弧半径大小为Ｉ冠ｌ。对于每个障碍物０６ｓ。，得２两条圆弧线段ｏＬ，和ＯＲ，构成该障碍物的不可通行区域，０为车体中心，Ｌ。（Ｌ。．ｘ，Ｌ，．Ｙ），Ｒ。（Ｒ。．ｘ，Ｒ．．Ｙ）分别是障碍物相应左右顶点，ＯＬ。，ＯＲ。方程如下
现。：Ｚｊ础＝（Ⅳ一Ｒｕ。ｈ）２＋Ｙ２一Ｒ２Ｊ曲＝ｏ
Ｙ＞０，Ｉｘｌ＜ＩＬ。．引
（３）ＯＲ。：Ｚ，ｇｈｔ＝（ｘ—Ｒｉ＿ｔｉｇｈｔ）２＋ｙ２一尺０ｍ＝ｏ
Ｙ＞０，Ｉｘｌ＜ＩＲ。．引
（４）
（２）将车辆由于自身约束无法达到的区域也增加到不可通行区域中。对于轮式车而言，存在最小转弯半径的问题，小于最小转弯半径的圆弧同样无法执行，应该也划为不可通行区域。对每次规划这是两个固定区域。（３）合并相互重叠的不可通行区域，对所得到的不可通行区域，用其左右圆弧的方程描述为：ｏｂｓ—ｚｏｎｅ。＝ｆ，ｊｍ（＊，Ｙ）＞０ｎ
几种（＊，Ｙ）＜０∥ｍ（ｘ，Ｙ）＝０，允ｍ（ｘ，Ｙ）＝０为
根据式（３）和式（４）获得的左右圆弧曲线。将所有不可通行区域从左到右排列，进行遍历。如果有相邻的区域方程相交则合并并且进行更新。重复这一过程直到不再有新的更新。
不可通行区域之间的区域即为可通行区域，
图２为传感器视场分解示意图。由图２可见，以机器人中心为切点，航向方向为切线方向，在局部
地图上获得若干弧形可通行区域。
总第１５６期成伟明唐振民赵春霞陆建峰刘华军复杂环境中基于圆弧区域分解的局部路径规划５９７
圉２传感器视场分解示意图
本文的分解方法有如下特点：（１）算法简单、快速，实时性好。复杂环境机器人自主导航试验实时性要求较高，算法必须满足其基本条件。（２）符合机器人平台的运动学规律，并且考虑了平台的约束，能够更好地与控制模块耦合。１．２可通行区选择与局部路径生成
可通行域的选择应该综合考虑以下因素：（１）可通行区域安全性；（２）可通性区域方向尽量接近目标点方向；（３）尽量保持车体的当前航向。设计如下的代价函数，对每个可通行区域计算其代价函数，进行可通行区域的选择，第ｉ个可通行区代价函数为
Ｃ。＝ｋ，Ｓ。＋ｋｑＱ。＋Ｉ疋
（５）
式中：ｓ。代表可通行区域安全性；Ｑ。代表可通行区域的方向与目标点方向的差异；正为可通行区
域方向与机器人当前航向差异；ｋ。…ｋ
ｔ。都是权
值系数且ｋ。…ｋ
ｋ。都非负，可根据３条原则的重
要性给出大小，本文试验认为原则（１）比原则
（２），（３）重要。
下面先给出Ｑ，和ｔ的计算方法，最后讨论如何计算可通行区域安全性Ｓ。。设该可通行区域
左右圆弧半径为尺ｕｍ与矗㈣。。首先利用式（２）
计算目标点所处圆弧半径Ｒ。，则Ｑ
＝
．星
Ｌ呻
（６）
丁
＝
咖
佳上‰百¨川引去ｋ，
（７）
对可通行区域的安全性描述采用模糊子集。影响可通行区域安全性的有２个主要因素：可通行区域宽度和可通行区域两边障碍物的位置，而且障碍物越近影响越大。
如图３所示，以车体中心为圆心、固定半径作圆弧．与可通行区域ｉ交于曰，ｃ两点，并与左右最小半径圆弧交于Ａ，Ｄ两点，设ＬＢｃ表示ＢＣ间的弧
长，Ｌ。Ｄ表示ＡＤ间的弧长。则定义陵可通行区域ｉ的宽度系数Ｅ＝￡。儿。。Ｅ的定义为可通行区的宽度提供了一个统一度量。
两边障碍物的影响定义如下：首先通过比较获得的较近的障碍物点，不妨设为Ｅ点，则障碍
系数Ｄ。＝（厶”×工础）／￡ｗ×ｋｏ—ｍ，五刚ｄｈ是车宽
系数，该式表示障碍附近的可通行区域宽度相对于车宽的倍数。
圉３可通行区域宽度计算示意
形与Ｄ。的模糊子集都定义为ｉＮＢ，ＮＳ，ＰＳ，ＰＢ｝，表示｛很窄，较窄，较宽，很宽｝。输出Ｓ的模糊子集定义为｛ＮＢ，ＮＳ，Ｚ，ＰＳ，ＰＢ｝，含义为｛不可能通过，比较危险，可以通过，比较安全，很安全ｌ，各模糊子集的隶属度函数如图４所示。模糊推理规则的建立如表１所示。
表１模糊规则表
去模糊化采用最小最大重心法
，
』ｓ舭。（ｓ。）ｄＳ
Ｓ∞＝‘－————一
（８）
ｋ（Ｓ。）ｄ＿ｓ
式中：ｓ。为输出的模糊子集，“（）为隶属度函数，ｓ。为最终得到的通过代价。通过计算代价函数选择可通行区域，代价函数值最小的即为最优可通行区域，但必须给这个最小值一个上限。当大于上限时说明代价太大，必须停车。
南京理工大学学报
第３ｌ卷第５期
ＬＲ＝｛ＬＡ：｝ｉ＝１，２，・“。４；
越疃描
ＲＲ＝ｌ兄Ａ，｝，＝１，２，…，“；
则取期望路径为ＣＲ＝｛ＣＡ。｝，其中
ｆ詈（“．一ＲＡ。）当ｉ≤ｍｉｎ（ｎ，ｍ）
眠。∞。刮当譬二黧∥’
式中ａ，ｂ为道路分割系数，且ａ＜ｂ。
２试验结果
图５为障碍区穿越试验结果，黑色物体是人为障碍，机器人的初始位置在图５中已经标出。由图５可以看到，机器人的穿越轨迹平稳光滑。图６是避障的几帧序列图片和规划结果。计算在
越哩
＿Ｉ｜Ｂ；
Ｐ４
２Ｇ机器上运行。在进行多次试验后，避障时
局部路径规划每次处理时间不超过４Ⅱ培，使得机器人导航有足够的反应时间响应环境变化。
０
最
（ｃ碍模糊子集
图４各模糊子集隶属度函数
通过代价函数计算获得的最优可通行区域中生成的局部路径时，采用了道路规划中的方法，可通行区域的左右弧边看作道路边缘，在左右边缘上均匀选择控制点，设左右路边点分别为
图５避障结果
囤６局部路径规划结果
试验统计数据列于表２。值得一提的是，避障成功率与各个模块都有关系，并非仅与局部路径规
路径规划提出的４个要求进行人为评定．避障失败与避障结果不符要求的都认为是不正确的。这种评价方法具有主观性，但更能反映算法性能。
划有关。正确避障成功率是按照第１节的对局部
表２越野避障试验统计结果
总第１５６期成伟明唐振民赵春霞陆建峰刘华军复杂环境中基于圆弧区域分解的局部路径规划５９９
（上接第５８９页）参考文献：
［１］辜永元，张洪钺，汪叔华．卡尔曼滤波与组合导航
原理［Ｍ］．西安：西北工业大学出版社，１９９８．［２］
杨大明．空间飞行器姿态控制系统［Ｍ］．哈尔滨：哈尔滨工业大学出版社，２０００．
［３］安世娇，江涌，姚宏瑛．捷联惯导＋星光修正组合
导航研究［Ｊ］．现代防御技术，２００４，３２（１）：３４
—３７．
［４］Ｋａｐｌａｎ
ＧＨ．Ｄｅｔｅｒｍｉｎｉｎｇｔｈｅｐｏｓｉｔｉｏｎａｎｄｍｏｔｉｏｎｏｆ
ｎ
ｖｅｓｓｅｌｆｒｏｍｃｅｌｅｓｔｉａｌＩｎｓｔｉｔｕｔｅｏｆ
ｏｂｓｅｒｖａｔｉｏｎｓ［Ｊ］．Ｊｏｕｒｎａｌ
０ｆＴｈｅ
Ｎａｖｉｇａｔｉｏｎ，１９９５，４２（４）：６３１－６３８．
［５］顾冬晴，王岩，周文君，等．多敏感器卫星姿态确定
的联邦滤波器设计［Ｊ］．中国空间科学技术，２００４
（３）：７—１３．
『６］ＳｅｈｏＵＳ．Ｓｔａｒ－ｆｉｅｌｄｉｄｅｎｔｉｆｉｃａｔｉｏｎｆｏｒａｕｔｏｎｏｍｏｕｓ砒ｄ—
ｒｕｄｅ
ｄｅｔｅｒｍｉｎａｔｉｏｎ［Ｊ］．ＪｏｕｒｎａｌｏｆＧｕｉｄａｎｃｅ，Ｃｏｎ—
ｔｒｏｌ。ａｎｄ
Ｄｙｎｍｕｉｃｓ，１９９５，１８（１）：６１—６５．
复杂环境中基于圆弧区域分解的局部路径规划
作者：作者单位：刊名：英文刊名：年，卷(期)：
成伟明， 唐振民， 赵春霞， 陆建峰， 刘华军， CHENG Wei-ming， TANG Zhen-min，ZHAO Chun-xia， LU Jian-feng， LIU Hua-jun
南京理工大学,计算机科学与技术学院,江苏,南京,210094南京理工大学学报（自然科学版）
JOURNAL OF NANJING UNIVERSITY OF SCIENCE AND TECHNOLOGY2007,31(5)
参考文献(7条)
1. 陈宗海;陈锋 一种不确定环境下移动机器人的避障规划算法[期刊论文]-机器人 2002(04)2. 唐振民;赵春霞;杨静宇 地面自主机动平台的局部路径规划 2001(07)
3. Iwan U;Johann B VFH *:Local obstacle avoidance with look ahead verification 20004. Wan U;Johann B VFH +:Reliable Obstacle Avoidance for Fast Mobile Robots 1998
5. Borenstein J;Koren Y The vector field histogram fast obstacle avoidance for mobile robots 1991(03)6. Brooks R;Lozano P T A subdivision algorithm in configuration space for findpath with rotation1985(02)
7. 翁妙凤;潘峻 面向对象的自主车越野路径规划的设计与实现[期刊论文]-计算机研究与发展 1996(07)
本文读者也读过(9条)
1. 高扬. 孙树栋. 黄伟峰. GAO Yang. SUN Shu-dong. HUANG Wei-feng 一种未知环境下的快速路径规划方法[期刊论文]-计算机应用研究2009,26(7)
2. 胡久乡. HU Jiu-Xiang 基于网格光顺的区域自动划分算法[期刊论文]-计算机学报1999,22(12)
3. 赵春霞. 唐振民. 陆建峰. 杨静宇. 刘传才 面向自主车辆的局部路径规划仿真系统[期刊论文]-南京理工大学学报2002,26(6)
4. 汪燕. 毛政元 基于核心估计的空间聚类算法及其应用研究[会议论文]-2006
5. 章小兵. 宋爱国. 唐鸿儒. Zhang Xiaobing. Song Aiguo. Tang Hongru 基于实时滚动亚目标的遥控移动机器人局部路径规划方法[期刊论文]-东南大学学报（自然科学版）2006,36(1)
6. 李威. 董健全. 武雪丽 P2P环境中区域划分结构及其算法描述[期刊论文]-计算机工程与应用2004,40(19)7. 基于对称极多项式曲线的移动机器人平滑路径生成[期刊论文]-机器人2005,27(5)8. 张明 管制扇区的最优划分方法研究[期刊论文]-南京航空航天大学学报2004,36(3)
9. 宋晓静. 范宁军. SONG Xiao-jing. FAN Ning-jun 基于几何和模糊控制合成算法的小型移动机器人局部路径规划[期刊论文]-合肥工业大学学报（自然科学版）2007,30(1)
本文链接：http://d.g.wanfangdata.com.cn/Periodical_njlgdxxb200705013.aspx
第３１卷第５期南京理工大学学报
Ｖ０１．３１Ｎｏ．５
１塑！篁！！旦墅！！型堡望！翼！竖望堕！！塑墅堕！！丝！些竺！！墼！型！墅垒丝；！坚坚
复杂环境中基于圆弧区域分解的局部路径规划
成伟明，唐振民，赵春霞，陆建峰，刘华军
（南京理工大学计算机科学与技术学院，江苏南京２１００９４）
摘要：该文根据轮式车的运动学特点，针对机器人导航中安全性问题以及算法实时性要求，提出了基于圆弧的区域分解方法。在此基础上引入了对区域安全性的模糊子集描述，建立了代价函数，得到了符合轮式车运动学特点的局部路径。在实际系统中的运行结果表明，该算法能很好地满足复杂环境下机器人自主导航的局部路径规划要求。关键词：自主导航；局部路径规划；避障；区域分解中图分类号：ＴＰ
２４
文章编号：１００５—９８３０（２００７）０５—０５９５一０５
ＡｒｃＲｅｇｉｏｎＤｅｃｏｍｐｏｓｉｔｉｏｎＢａｓｅｄＬｏｃａｌＰａｔｈＰｌａｎ
ｉｎＣｏｍｐｌｅｘＥｎｖｉｒｏｎｍｅｎｔ
ＣＨＥＮＧ
Ｗｅｉ—ｍｉｎｇ，ＴＡＮＧ
（Ｓｃｈｏｏｌ
Ｚｈｅｎ－ｍｉｎ，ＺＨＡＯＣｈｕｎ・ｘｉａ，ＬＵＪｉａｎ－ｆｅｎｇ，ＬＩＵ
Ｔｅｃｈｎｏｌｏｇｙ，ＮＵＳＴ，Ｎａｎｊｉｎｇ２１００９４，Ｃｈｉｎａ）
ａｒｃ
Ｈｕａ－ｊｕｎ
ｏｆＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅａｎｄ
Ａｂｓｔｒａｃｔ：Ｂａｓｅｄ
ｏｎ
ｔｈｅｋｉｎｅｍａｔｉｃｓｏｆｃａｒ・ｌｉｋｅｖｅｈｉｃｌｅ．ａｌｌｒｅｇｉｏｎｄｅｃｏｍｐｏｓｉｔｉｏｎｂａｓｅｄｍｏｔｉｏｎ
ｐｌａｎｓｔｒａｔｅｇｙｉｓａｄｏｐｔｅｄｔｏｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍｓｌｉｋｅｓａｆｅｔｙａｎｄｒｅａｌ・ｔｉｍｅｒｅｑｕｉｒｅｍｅｎｔｓ．Ｆｕｚｚｙｓｅｔｓｄｅ－ｓｃｒｉｂｉｎｇｔｈｅｓａｆｅｔｙｏｆｔｈｅ
ａｒｅ
ｒｅｇｉｏｎ
８ｔ－ｅ
ｃｏｎｓｔｒｕｃｔｅｄｗｉｔｈ
ａｃｏｓｔ
ｆｕｎｔｉｏｎｔｏｇｅｎｅｎｒａｔｅ
ａ
ｌｏｃａｌｐａｔｈｓｔａｆｆ一
ａＤｇ
印ｎｇ
ｃａｎ
ｋｉｎｅｍａｔｉｃｃｏｎｓｔｒａｉｎｔｏｆｔｈｅｍｏｂｉｌｅｒｏｂｏｔ．Ａｃｔｕａｌｅｘｐｅｒｉｍｅｎｔｓｈｏｗｓｔｈａｔｔｈｅｒｅｓｕｌｔｓｆｕｌｌｆｄｔｈｅｐａｔｈｐｌａｎｉｎｇｑｕｅｓｔｏｆａｕｔｏｎｏｍｏｕｓｎａｖｉｇａｔｉｏｎｉｎｃｏｍｐｌｅｘｅｎｖｉｒｏｍｅｎｔ．
ｎｉｃｅａｎｄ
Ｋｅｙｗｏｒｄｓ：ａｕｔｏｎｏｍｏｕｓｎａｖｉｇａｔｉｏｎ；ｌｏｃａｌｐａｔｈｐｌａｎ；ｏｂｓｔａｃｌｅａｖｏｉｄａｎｃｅ；ｒｅｇｉｏｎｄｅｃｏｍｐｏｓｉｔｉｏｎ
未知复杂环境下的移动机器人自主导航，作为机器人自主能力的一种重要体现，一直以来都是国内外自主导航研究的重点和热点。近年由
Ｍｅｌｌｏｎ
Ｕｎｉｖｅｒｓｉｔｙ，卡耐基梅隆大学）、Ｓｔａｎｆｏｒｄ
Ｕｎｉ－
ｖｅｒｓｉｔｙ等一批著名高校和研究机构的参与和关注。环境的复杂性要求使用更多更精确的传感器，以提供足够的环境地形信息；同时，进行环境理解与路径规划时。要求能够充分利用已有信息，及时弥补传感器缺陷，实时处理任何突发事件，以
ｎ删（Ｄｅｆｅｎｓｅ
ＡｄｖａｎｃｅｄＲｅｓｅａｒｃｈ
Ｐｒｏｊｅｃｔ
Ａｇｅｎｃｙ。
美国国防部高级研究计划局）举行的两届ＧｒａｎｄＣｈａｌｌｅｎｇｅ越野大赛吸引了来自ＣＭＵ（Ｃａｒｎｅｇｉｅ
收稿１３期：２００６—０３—２７
修回日期：２００７—０６—２２
作者简介：成伟明（１９８１一），男．江苏兴化人，博士生，主要研究方向：人工智能，路径规划．智能导航，Ｅ・ｍａｉｈ
Ｗｅ・
ｉｍｉｎ９１９８１＠１２６．哪；通讯作者：唐振民（１９６１一），男，教授，博士生导师，主要研究方向：人工智能，图
像处理，智能导航．Ｅ－ｍａｉｌ：ｔａｎｇ．拗＠ｍａｉｌ．ｎｊｕ毗，ｅｄｕ．ｃｎ。
南京理工大学学报第３ｌ卷第５期
对机器人提供最好的决策支持。
复杂环境下机器人的路径规划要综合考虑路程、时间、安全性、隐蔽性和机动性等指标，选择最佳路径，而不是简单地选择从起始点到目标点的最短无碰路径规划”］。早期的近似栅格法”１是目前应用较广的一种路径规划算法，但其计算量大．不适于实时动态环境。１９９１年，Ｂｏｒｅｎｓｔｅｉｎ等针对虚拟力场法（ｖｅｃｔｏｒ
ｆｉｅｌｄ
ｈｉｓｔｏｇｒａｍ，ＶＦＨ）的
缺点提出了向量场直方图法”ｏ，是目前多障碍物环境中局部路径规划广泛采用的一种方法。但ＶＨＦ未考虑机器人自身宽度和运动学特性，给出的路径实际上很难完成。针对ＶＦＨ的缺点，１ｗａｎ等又先后提出了ＶＦＨ＋”１和ＶＦＨ｝［５３算法。其目的都是希望通过简单的几何线条分解当前的局部环境，进行快速规划。
本文提出一种适于复杂环境下轮式车自主导航的局部路径规划算法。在全局规划的指导下，该算法通过基于圆弧的区域分割迅速将局部环境分解成可通行区域和不可通行区域。在此基础上，利用模糊子集对可通行区域的安全性进行描述，并建立了可通行区域的通过代价函数。算法的设计考虑了轮式车辆的非完整性约束对规划路径的要求，以及机器人自身的宽度对避障安全性
的影响。在实际试验中，该算法取得了令人满意
的效果。１
基于圆弧区域分解的局部路径规划
算法
图１为算法的试验环境。由于试验环境地形
相对复杂，没有道路环境中的白线或者路标等标识，在二维图像上很难找到明显的路边信息，可靠的环境信息一般来自于三维视觉。
图１算法试验环境
在本文的局部环境中，局部路径规划算法充分考虑并且满足以下４个要求：（１）算法实时性，
每次运行时间要尽可能短；（２）考虑机器人避障过程中的安全性；（３）路径对于控制模块可执行，是否违反了机器人自身的运动学约束；（４）满足以上条件的最短路径。
１．１基于圆弧的可通行区域生成
由于视觉传感器的视野范围有限，因此，试验中，比较准确的环境数据范围是机器人前方一块固定大小的矩形区域”’“。本文分解算法即针对当前这块可视区域，以车体中心为原点，当前航向为Ｙ轴正向，垂直于Ｙ轴向右为ｘ轴正向，分解算法描述如下：（１）先对每个障碍作包络圆弧，圆弧通过车体中心，并且与当前航向相切。圆弧所属圆方程为（』一Ｒ）２＋ｙ２＝Ｒ２（１）
式中月的计算方法如下
“一１０
。ｆ（《＋ｄ；）／（２ｄ，）ｄ。≠ｕ
…¨’
ｄ：：０
式中ｄ…ｄ为圆弧所经过的障碍顶点的坐标。这
里，Ｒ不是非负的，当顶点位于车体坐标左半边时Ｒ＜０，否则Ｒ＞０，圆弧半径大小为Ｉ冠ｌ。对于每个障碍物０６ｓ。，得２两条圆弧线段ｏＬ，和ＯＲ，构成该障碍物的不可通行区域，０为车体中心，Ｌ。（Ｌ。．ｘ，Ｌ，．Ｙ），Ｒ。（Ｒ。．ｘ，Ｒ．．Ｙ）分别是障碍物相应左右顶点，ＯＬ。，ＯＲ。方程如下
现。：Ｚｊ础＝（Ⅳ一Ｒｕ。ｈ）２＋Ｙ２一Ｒ２Ｊ曲＝ｏ
Ｙ＞０，Ｉｘｌ＜ＩＬ。．引
（３）ＯＲ。：Ｚ，ｇｈｔ＝（ｘ—Ｒｉ＿ｔｉｇｈｔ）２＋ｙ２一尺０ｍ＝ｏ
Ｙ＞０，Ｉｘｌ＜ＩＲ。．引
（４）
（２）将车辆由于自身约束无法达到的区域也增加到不可通行区域中。对于轮式车而言，存在最小转弯半径的问题，小于最小转弯半径的圆弧同样无法执行，应该也划为不可通行区域。对每次规划这是两个固定区域。（３）合并相互重叠的不可通行区域，对所得到的不可通行区域，用其左右圆弧的方程描述为：ｏｂｓ—ｚｏｎｅ。＝ｆ，ｊｍ（＊，Ｙ）＞０ｎ
几种（＊，Ｙ）＜０∥ｍ（ｘ，Ｙ）＝０，允ｍ（ｘ，Ｙ）＝０为
根据式（３）和式（４）获得的左右圆弧曲线。将所有不可通行区域从左到右排列，进行遍历。如果有相邻的区域方程相交则合并并且进行更新。重复这一过程直到不再有新的更新。
不可通行区域之间的区域即为可通行区域，
图２为传感器视场分解示意图。由图２可见，以机器人中心为切点，航向方向为切线方向，在局部
地图上获得若干弧形可通行区域。
总第１５６期成伟明唐振民赵春霞陆建峰刘华军复杂环境中基于圆弧区域分解的局部路径规划５９７
圉２传感器视场分解示意图
本文的分解方法有如下特点：（１）算法简单、快速，实时性好。复杂环境机器人自主导航试验实时性要求较高，算法必须满足其基本条件。（２）符合机器人平台的运动学规律，并且考虑了平台的约束，能够更好地与控制模块耦合。１．２可通行区选择与局部路径生成
可通行域的选择应该综合考虑以下因素：（１）可通行区域安全性；（２）可通性区域方向尽量接近目标点方向；（３）尽量保持车体的当前航向。设计如下的代价函数，对每个可通行区域计算其代价函数，进行可通行区域的选择，第ｉ个可通行区代价函数为
Ｃ。＝ｋ，Ｓ。＋ｋｑＱ。＋Ｉ疋
（５）
式中：ｓ。代表可通行区域安全性；Ｑ。代表可通行区域的方向与目标点方向的差异；正为可通行区
域方向与机器人当前航向差异；ｋ。…ｋ
ｔ。都是权
值系数且ｋ。…ｋ
ｋ。都非负，可根据３条原则的重
要性给出大小，本文试验认为原则（１）比原则
（２），（３）重要。
下面先给出Ｑ，和ｔ的计算方法，最后讨论如何计算可通行区域安全性Ｓ。。设该可通行区域
左右圆弧半径为尺ｕｍ与矗㈣。。首先利用式（２）
计算目标点所处圆弧半径Ｒ。，则Ｑ
＝
．星
Ｌ呻
（６）
丁
＝
咖
佳上‰百¨川引去ｋ，
（７）
对可通行区域的安全性描述采用模糊子集。影响可通行区域安全性的有２个主要因素：可通行区域宽度和可通行区域两边障碍物的位置，而且障碍物越近影响越大。
如图３所示，以车体中心为圆心、固定半径作圆弧．与可通行区域ｉ交于曰，ｃ两点，并与左右最小半径圆弧交于Ａ，Ｄ两点，设ＬＢｃ表示ＢＣ间的弧
长，Ｌ。Ｄ表示ＡＤ间的弧长。则定义陵可通行区域ｉ的宽度系数Ｅ＝￡。儿。。Ｅ的定义为可通行区的宽度提供了一个统一度量。
两边障碍物的影响定义如下：首先通过比较获得的较近的障碍物点，不妨设为Ｅ点，则障碍
系数Ｄ。＝（厶”×工础）／￡ｗ×ｋｏ—ｍ，五刚ｄｈ是车宽
系数，该式表示障碍附近的可通行区域宽度相对于车宽的倍数。
圉３可通行区域宽度计算示意
形与Ｄ。的模糊子集都定义为ｉＮＢ，ＮＳ，ＰＳ，ＰＢ｝，表示｛很窄，较窄，较宽，很宽｝。输出Ｓ的模糊子集定义为｛ＮＢ，ＮＳ，Ｚ，ＰＳ，ＰＢ｝，含义为｛不可能通过，比较危险，可以通过，比较安全，很安全ｌ，各模糊子集的隶属度函数如图４所示。模糊推理规则的建立如表１所示。
表１模糊规则表
去模糊化采用最小最大重心法
，
』ｓ舭。（ｓ。）ｄＳ
Ｓ∞＝‘－————一
（８）
ｋ（Ｓ。）ｄ＿ｓ
式中：ｓ。为输出的模糊子集，“（）为隶属度函数，ｓ。为最终得到的通过代价。通过计算代价函数选择可通行区域，代价函数值最小的即为最优可通行区域，但必须给这个最小值一个上限。当大于上限时说明代价太大，必须停车。
南京理工大学学报
第３ｌ卷第５期
ＬＲ＝｛ＬＡ：｝ｉ＝１，２，・“。４；
越疃描
ＲＲ＝ｌ兄Ａ，｝，＝１，２，…，“；
则取期望路径为ＣＲ＝｛ＣＡ。｝，其中
ｆ詈（“．一ＲＡ。）当ｉ≤ｍｉｎ（ｎ，ｍ）
眠。∞。刮当譬二黧∥’
式中ａ，ｂ为道路分割系数，且ａ＜ｂ。
２试验结果
图５为障碍区穿越试验结果，黑色物体是人为障碍，机器人的初始位置在图５中已经标出。由图５可以看到，机器人的穿越轨迹平稳光滑。图６是避障的几帧序列图片和规划结果。计算在
越哩
＿Ｉ｜Ｂ；
Ｐ４
２Ｇ机器上运行。在进行多次试验后，避障时
局部路径规划每次处理时间不超过４Ⅱ培，使得机器人导航有足够的反应时间响应环境变化。
０
最
（ｃ碍模糊子集
图４各模糊子集隶属度函数
通过代价函数计算获得的最优可通行区域中生成的局部路径时，采用了道路规划中的方法，可通行区域的左右弧边看作道路边缘，在左右边缘上均匀选择控制点，设左右路边点分别为
图５避障结果
囤６局部路径规划结果
试验统计数据列于表２。值得一提的是，避障成功率与各个模块都有关系，并非仅与局部路径规
路径规划提出的４个要求进行人为评定．避障失败与避障结果不符要求的都认为是不正确的。这种评价方法具有主观性，但更能反映算法性能。
划有关。正确避障成功率是按照第１节的对局部
表２越野避障试验统计结果
总第１５６期成伟明唐振民赵春霞陆建峰刘华军复杂环境中基于圆弧区域分解的局部路径规划５９９
（上接第５８９页）参考文献：
［１］辜永元，张洪钺，汪叔华．卡尔曼滤波与组合导航
原理［Ｍ］．西安：西北工业大学出版社，１９９８．［２］
杨大明．空间飞行器姿态控制系统［Ｍ］．哈尔滨：哈尔滨工业大学出版社，２０００．
［３］安世娇，江涌，姚宏瑛．捷联惯导＋星光修正组合
导航研究［Ｊ］．现代防御技术，２００４，３２（１）：３４
—３７．
［４］Ｋａｐｌａｎ
ＧＨ．Ｄｅｔｅｒｍｉｎｉｎｇｔｈｅｐｏｓｉｔｉｏｎａｎｄｍｏｔｉｏｎｏｆ
ｎ
ｖｅｓｓｅｌｆｒｏｍｃｅｌｅｓｔｉａｌＩｎｓｔｉｔｕｔｅｏｆ
ｏｂｓｅｒｖａｔｉｏｎｓ［Ｊ］．Ｊｏｕｒｎａｌ
０ｆＴｈｅ
Ｎａｖｉｇａｔｉｏｎ，１９９５，４２（４）：６３１－６３８．
［５］顾冬晴，王岩，周文君，等．多敏感器卫星姿态确定
的联邦滤波器设计［Ｊ］．中国空间科学技术，２００４
（３）：７—１３．
『６］ＳｅｈｏＵＳ．Ｓｔａｒ－ｆｉｅｌｄｉｄｅｎｔｉｆｉｃａｔｉｏｎｆｏｒａｕｔｏｎｏｍｏｕｓ砒ｄ—
ｒｕｄｅ
ｄｅｔｅｒｍｉｎａｔｉｏｎ［Ｊ］．ＪｏｕｒｎａｌｏｆＧｕｉｄａｎｃｅ，Ｃｏｎ—
ｔｒｏｌ。ａｎｄ
Ｄｙｎｍｕｉｃｓ，１９９５，１８（１）：６１—６５．
复杂环境中基于圆弧区域分解的局部路径规划
作者：作者单位：刊名：英文刊名：年，卷(期)：
成伟明， 唐振民， 赵春霞， 陆建峰， 刘华军， CHENG Wei-ming， TANG Zhen-min，ZHAO Chun-xia， LU Jian-feng， LIU Hua-jun
南京理工大学,计算机科学与技术学院,江苏,南京,210094南京理工大学学报（自然科学版）
JOURNAL OF NANJING UNIVERSITY OF SCIENCE AND TECHNOLOGY2007,31(5)
参考文献(7条)
1. 陈宗海;陈锋 一种不确定环境下移动机器人的避障规划算法[期刊论文]-机器人 2002(04)2. 唐振民;赵春霞;杨静宇 地面自主机动平台的局部路径规划 2001(07)
3. Iwan U;Johann B VFH *:Local obstacle avoidance with look ahead verification 20004. Wan U;Johann B VFH +:Reliable Obstacle Avoidance for Fast Mobile Robots 1998
5. Borenstein J;Koren Y The vector field histogram fast obstacle avoidance for mobile robots 1991(03)6. Brooks R;Lozano P T A subdivision algorithm in configuration space for findpath with rotation1985(02)
7. 翁妙凤;潘峻 面向对象的自主车越野路径规划的设计与实现[期刊论文]-计算机研究与发展 1996(07)
本文读者也读过(9条)
1. 高扬. 孙树栋. 黄伟峰. GAO Yang. SUN Shu-dong. HUANG Wei-feng 一种未知环境下的快速路径规划方法[期刊论文]-计算机应用研究2009,26(7)
2. 胡久乡. HU Jiu-Xiang 基于网格光顺的区域自动划分算法[期刊论文]-计算机学报1999,22(12)
3. 赵春霞. 唐振民. 陆建峰. 杨静宇. 刘传才 面向自主车辆的局部路径规划仿真系统[期刊论文]-南京理工大学学报2002,26(6)
4. 汪燕. 毛政元 基于核心估计的空间聚类算法及其应用研究[会议论文]-2006
5. 章小兵. 宋爱国. 唐鸿儒. Zhang Xiaobing. Song Aiguo. Tang Hongru 基于实时滚动亚目标的遥控移动机器人局部路径规划方法[期刊论文]-东南大学学报（自然科学版）2006,36(1)
6. 李威. 董健全. 武雪丽 P2P环境中区域划分结构及其算法描述[期刊论文]-计算机工程与应用2004,40(19)7. 基于对称极多项式曲线的移动机器人平滑路径生成[期刊论文]-机器人2005,27(5)8. 张明 管制扇区的最优划分方法研究[期刊论文]-南京航空航天大学学报2004,36(3)
9. 宋晓静. 范宁军. SONG Xiao-jing. FAN Ning-jun 基于几何和模糊控制合成算法的小型移动机器人局部路径规划[期刊论文]-合肥工业大学学报（自然科学版）2007,30(1)
本文链接：http://d.g.wanfangdata.com.cn/Periodical_njlgdxxb200705013.aspx