-1-
无约束运动体多目标路径规划1
郭锋，田彦涛，王红睿，
吉林大学通信工程学院，长春 (130025)
摘 要：本文通过对板球系统实验平台中无约束运动体多目标路径规划问题的研究，提出了
一种基于熵权理论与 Djikstra算法相结合的多目标路径规划方法。本文从无约束运动体运动
不确定性特点出发，给出了考虑路径长度，碰到障碍物等因素的路径规划方法。通过仿真结
果证明了方法能够较好的满足板球系统无约束运动体路径规划的要求。
关键词：板球系统 多目标决策 路径规划 熵权法
中图分类号：
1．引言
板球系统（Ball and Plate System）是指通过动态地调整平板的倾斜角度，从而控制在平
板上的小球的位置和运动状态的机械系统[1-4]。在板球系统中，被控对象是一个不受约束的
小球，球除了和平板表面接触外，不受任何约束，它可以在平板上自由运动。在此板球系统
中，进行障碍物环境下的轨迹规划与跟踪是板球系统的要完成的任务之一。在板球系统实验
平台上设置形状不同、位置随机的障碍物，给定起始点与终止点，要求系统自动规划出一条
路径使小球快速，平稳的到达终止点。
随着平台硬件设备的改进，板球系统的任务内容也逐渐丰富。同时板球系统中的路径规
划问题虽然与机器人的研究有相通之处，但是也有很多不同之处。机械手或者移动机器人等
控制对象，受机械机构的约束，在没有外部指令的作用下不能自行动作，而在板球系统中，
受控的小球不受机械约束，平板的倾斜使其在上面自由运动，其运动具有不确定性，在进行
轨迹跟踪过程中，小球可能会碰到距离路径较近的障碍物，因此，在规划小球这类无约束运
动体路径时，要充分的考虑小球碰到障碍物的危险程度等信息，仅以路径长度作为单一指标
进行路径规划已经难以满足需求。并且小球本身没有传感器，没有认识外界的能力。吉林大
学控制理论与智能系统实验室自主研发的 BPVS-JLU 系列板球系统采用视觉伺服系统实时
获取无约束物体位置、速度等信息。而视觉传感器在反馈信息过程中通常由于图像采集与处
理时间使信息反馈存在一定的滞后，与机械臂或者移动机器人的传感器信息反馈相比实时性
一般较差。因此板球系统的路径规划任务有其特有的问题需要解决。
对于多目标路径规划近年来涌现出很多方法和思想，在文献[5]中，José Maria A.
Pangilinan等研究了进化算法解决网络节点间的多目标路径规划问题。路径节点构成的网络，
其网络节点间具有多个目标值，作者运用遗传算法解决了多目标上述网络的多目标最短路径
问题。在文献[6]中，，运用模糊多目标决策的方法实现了施工机械的
路径规划问题，根据耗费、安全、可见度三个指标评估决策路径。并且利用模糊方法确定各
个指标的权重。在文献[7]中，Amar Khoukhi，Kudret Demirli等人利用模糊神经网络研究了
机器人跟踪规划问题，模糊神经网络系统通过学习与捕获机器人的多目标动态行为进行实时
轨迹规划。
本文分为四部分进行介绍，在第一部分中给出问题的描述，第二部分中给出基于熵权理
论的多目标路径规划方法，第三部分进行了仿真结果对比与分析，第四部分进行总结。
1本课题得到高等学校博士学科点专项科研基金（项目编号：20060183006）的资助。
-2-
2．问题描述
以板球系统运行环境下的运动轨迹规划为研究对象，为了使球能平稳安全快速的由起
始点运动到目标点，需要对给定轨迹进行规划。板球系统环境下的路径规划任务如图 1所示，
球是一个无约束运动体，平板通过绕 x轴和 y轴的旋转控制球的运动，从而使球能够跟踪预
先规划好的给定轨迹到达目标点。因此对于给定轨迹的规划要考虑球的运动特性。应该使球
的位移尽量短；使球的运动速度尽量快，提高任务的完成质量。同时，由于球的大部分自由
度没有约束，容易产生较大的跟踪误差，所以在规划给定轨迹时应考虑其碰到障碍物的危险
程度。因此规划任务的目的就是综合位移，速度，碰障危险程度等信息，规划出一条满意度
较高的给定轨迹保证球的跟踪任务能够顺利高效的完成。
图1 小球在板球系统BPS-JLU II上多目标路径规划任务示意图
Task of multi-objective path planning for ball and plate system BPS-JLU II.
为使球运动的时间尽量短，首先要对路径的总长度进行优化，路径的总长度用 1( )F x 表
示；要尽量保证轨迹平滑，才能减少运动中速率的频繁变化，提高平稳性，同样也是球能以
较快速度运动的前提条件。路径的平滑程度用 2 ( )F x 表示；同时为了尽可能减少小球碰撞障
碍物的可能，需要用危险性程度函数 3 ( )F x 来度量路径的安全性，同理，对第 n 个优化指标
有目标函数 ( )nF x 。
为了便于描述，认为球的运动环境为二维空间，设起点为 s，目标点为 g。多目标路径
规划问题可以表述为寻找可行路径 P，使得
1 2 3( ) min[ ( ), ( ), ( ) ( )]nF P F P F P F P F P= K，， (1)
并且
1 , np s p g= = (2)
式中 ( 1, 2, , )jp j n= L 为路径 P经过的所有点。
上述优化问题多个目标之间是相互矛盾的，因此很难甚至无法找到一个解能使得多
个目标同时达到最优，因此要引入有效解即 Pareto 最优解，一个多目标优化问题通常存
在多个 Pareto 最优解,这些解共同构成了问题的 Pareto 最优解集。优化的任务就是要产生
一组有效的 Pareto最优路径解[8]。
3．基于熵权多目标的路径规划方法
本文介绍的基于熵权多目标决策的运动轨迹规划问题的解决分以下几个部分：
-3-
A 地图建立
B 建立多目标以及约束条件
C 熵权理论应用的方法以及步骤
D 运用搜索算法进行求解
路径规划任务过程如图 2所示，路径长度和危险度指标通过改进栅格法建立的地图中获
得。
图 2 路径规划结构图
Structure of path planning
地图建立
为了更好的从环境中获得有效的信息，需要在地图建立时尽可能多的建立重要信息，例
如位移，危险度等。同时减小求解时的搜索空间。综合以上需要，本文提出了一种改进的栅
格环境建模方法。
图 3 路径长度信息栅格地图
Grid map including distance information
传统的栅格法如图 3所示常用的栅格法在建立地图编码时只能体现长度信息，而不能够
将更多的环境信息体现在编码中，因此本文提出一种更加全面的方法。即在栅格法的基础上
将栅格分别扩展成三个对应的映射关系图，分别命名为位移栅格图，危险度栅格图，具体介
绍如下。
(1) 栅格位移图：
按照传统栅格建立方法进行环境模型的建立。其目的是为了表述地图中的位置以及位移
信息。
(2) 栅格危险度图：
建立方法为：定义一危险度函数W ,以障碍物形成的连通域边缘栅格为基准，每个边缘
-4-
栅格相邻八个栅格中，除障碍物所占栅格外，其余空白栅格记为第一危险度层，以此原则建
立第一层后，同样原则在第一层的基础上，建立第二层危险度，每层W 值递减。如图 4所
示。分别建立的栅格地图如图 5所示，在栅格地图中分别表示距离信息与危险度信息。
危险度图具体的建立步骤如下：
1 建立栅格节点 M×N矩阵 R(x,y)；
2 建立障碍物栅格节点;
3 建立第一层的危险系数值（该值经过归一化后即为危险度），例如 ValueH=10;
4 while (all the element of R(x,y) is not zero) do {
5 for (iÎ[2,N-1]) do {
6 if (R(i,j) == ValueH OR R(i,j) == Obstacle) then{
7 for (i_numÎ[-1,1])
do {
8 for (j_numÎ[-1,1])
do {
9 if(R((i+i_num),(j+j_num)) < ValueH) then {
10 R((i+i_num),(j+j_num)) = ValueH – 1
11 }end if
12 }end for
13 }end for
14 }end if
15 }end for
16 ValueH = ValueH-1;
17 }end while
图 4 危险度计算示意图
Illustration of hazard calculation
图 5 栅格距离信息与危险度信息
Examples of distance map and hazard map.
-5-
建立多目标以及约束条件
设路径中经过的栅格数为 m，根据任意栅格到 ig 终点栅格 tg 的距离可建立距离目标，
目标函数为
Min
1
1
( , )
m
j t
j
d g g
-
=
å (3)
其中 d可以表示为
2 2( , ) ( ) ( )i j i j i jd g g x x y y= - + - (4)
危险度目标函数定义为
Min Min
1
( )
m
j
j
h g
=
å (5)
其中，h(gj)由上述栅格地图中建立危险度的方法得到。
约束条件为
( , ) / 2g ij ijf x y = <a a p ， ija 表示的是 1 1, ,i i ip p p- + 间的夹角， ip表示第 i个栅格。
1
1
| | 1
| | 1
i i
i i
x x
y y
+
+
- =
- =
(6)
熵权理论应用的方法以及求解步骤[8, 9]
本文通过利用熵的概念来衡量某一评价指标对信息系统集成方案优劣的影响程度以及
客观权重的特点，对多目标进行综合，最后求出总的综合属性最佳的一组解。
设该问题有 m个可选方案，n个评估指标，按照定性与定量相结合的原则取得多对象关
于多指标的评价矩阵
' ' '
11 12 1
' ' '
21 22 2
' ' '
1 2
'
n
n
m m mn
r r r
r r r
R
r r r
é ù
ê ú
ê ú=
ê ú
ê ú
ê úë û
L
L
M M M
L
(7)
即评价指标值矩阵
' '( )ij mnR r= ，由于前文中路径规划任务框图中给出熵权法与 Dijkstra相结
合的方法进行求解，因此在对于栅格地图中路径规划任务，以 Dijkstra算法每次搜索的父节
点为中心，其每一个父节点周围有八个子节点，如图 6所示。
图 6 栅格节点
Grid nodes for cells
因此，可以对每一组子节点建立路径长度与危险度的函数表，如表 1所示
-6-
表 1 栅格节点距离以及危险度函数值
Distance and hazard values for nodes
子节点 路径长度指标 危险度指标
1 d(i-1,j+1) h(i-1,j+1)
2 d(i,j+1) h(i,j+1)
3 d(i+1,j+1) h(i+1,j+1)
4 d(i-1,j) h(i-1,j)
5 d(i+1,j) h(i+1,j)
6 d(i-1,j-1) h(i-1,j-1)
7 d(i,j-1) h(i,j-1)
8 d(i+1,j-1) h(i+1,j-1)
由表 1可以建立评价矩阵
( 1, 1) ( 1, 1)
( , 1) ( , 1)
( 1, 1) ( 1, 1)
( 1, ) ( 1, )
( 1, ) ( 1, )
( 1, 1) ( 1, 1)
( , 1) ( , 1)
( 1, 1) ( 1, 1)
d i j h i j
d i j h i j
d i j h i j
d i j h i j
D
d i j h i j
d i j h i j
d i j h i j
d i j h i j
- + - +é ù
ê ú+ +ê ú
+ + + +ê ú
ê ú- -ê ú=
ê ú+ +
ê ú- - - -ê ú
ê ú- -
ê ú
+ - + -ë û
由于各评价指标数据之间具有不可公度性难以进行直接比较，必须对这些指标进行标准化。
一般情况下可分别按下列公式对知阵D进行标准化。设标准化后的决策矩阵为 ( )ij mnR r= 。
其中
8
1
( 1,2; 1,...,8)ijij
kj
k
D
r i j
D
=
= = =
å
(8)
经过标准化得：
( )ij m nR r ´=
式中， ijr 称为第 i个评价对象的第 j个评价指标值，又 [0,1]ijr Î
定义 1(评价指标的熵)：在有 m个被评价对象，n个评价指标的评估问题中(以下简称(m，
n)评价问题)，第 j个评价指标的熵定义为：
1
ln ( 1, , )
m
j ij ij
j
E k f f j n
=
= - =å L (9)
式中
1
1,
ln
ij
ij m
ij
i
r
f k
mr
=
= =
å
并假定，当 0ijf = 时， ln 0ij ijf f = ，也可以选择 k，使得0 1jE£ £ 。
定义 2(评价指标的熵权)：在(m，n)评价问题中，第 j个评价指标的熵权 jw 定义为：
1
1 j
j n
j
j
E
n E
w
=
-
=
- å
(10)
-7-
jw 的确定取决于各个方案的固有信息，因此称之为客观权重。设每个节点的综合属性为Z ，
则每个节点的综合属性度即为
1
n
i j ij
j
Z rw
=
= å (11)
图 7所示的为子节点与父节点之间的综合属性度。
图 7 栅格节点树
Nodes tree
结合 Dijkstra搜索算法，选取总体综合属性度最优的一条路径
1
n
i
i
J Z
=
= å (12)
本文采用 Dijkstra[10]算法进行求解上述问题。Dijkstra算法是常用的最短路径搜索算法，
是广度优先算法的一种改进，其算法完备性与时间复杂度等同于广度优先搜索[11,12]。利用
Dijkstra 搜索整个栅格节点树，最后得到一条综合属性度最优的栅格节点组合，即为栅格地
图下的最有路径。
根据总体综合属性度搜索得到的规划路径，其示意图如图 8所示，灰色栅格为被选择的
路径，黑色表示障碍物。
图 8 栅格地图路径规划示意图
Path planning on grid map
同时由图 8可以看到，规划得到的路径是栅格地图中的路径，该路径是由栅格节点进行
表示，因此路径是由一系列离散点构成的。对于板球系统无约束运动体轨迹规划任务，需要
给出一条具有速度信息的连续的轨迹。因此本章还需对轨迹进行平滑。利用三次 B 样条插
值进行轨迹平滑，从而实现为小球运动提供给定轨迹。
4．仿真、实验结果与分析
本文的路径规划问题在上述板球系统实验平台上加以讨论。图 9 为板球系统实验平台
-8-
视觉传感器拍摄得到的图像。利用拍摄到得图像生成环境地图。并通过仿真计算得到一条兼
顾路径长度与安全的路径。同时，在此平台上还进行了以路径长度为单目标的路径规划。单
目标规划方法利用 A*算法。
仿真程序是在 平台下进行的，建立了 100×100 栅格的地图。在仿真中分别
进行了多目标路径规划任务与单目标路径规划任务。
路径规划结果如图 10所示。A*算法规划得到的路径较多目标方法规划得到的路径短。
但是，当小球跟踪较短的路径时，距离障碍物较近，因此跟踪过程中碰到障碍物的危险度增
大。因此，距离最短的路径有可能是很危险的路径。同时，多目标规划方法得到的结果可以
看到，该方法并没有单纯的优化其中一个指标，而是在熵权法给出的权重为根据，对两各指
标同时进行优化。
两种算法规划得到的路径每个栅格节点的危险度如图 11和图 12所示。多目标方法规划
得到的路径的危险度在 之间，而 A*算法规划得到的路径危险度在 -1之间。表 II
对两种规划方法进行了进一步的比较。
图 9 板球系统 BPVS-JLU II数字摄像机拍摄图片
An image collected by the digital camera on
BPVS-JLU II
图 10 多目标方法与 A*算法规划路径结果
Result of multi-objective path planning using
entropy weight method and A*method
图 11 多目标方法规划路径的危险度
Hazard of Grid nodes with entropy method
图 12 A*算法规划路径的危险度
Fig 12 Hazard of Grid nodes with A* method
通过对比可以看出，多目标方法规划得到的路径的平均危险度小于 A*算法规划得到路
径的平均危险度，而路径长度指标则是 A*算法规划得到的路径更短。同时，多目标方法计
-9-
算时间更长，但是对于全局路径规划问题，计算时间在相差不大的情况下，该指标并不是非
常值得关注的。
综上所述，由于多目标规划方法充分考虑了路径长度以及危险度指标，从而给出规划路
径，它能够尽量满足无约束运动体由于运动不确定性而对轨迹跟踪的特殊要求。同时，虽然
本文只对路径长度以及危险度指标进行了考虑，但本文提出的方法可以推广到更多目标的路
径规划问题。
表 2 两种方法获得的距离与危险度
Distance and hazard for two methods
Method Total Distance Average Hazard time-consuming(s)
A*
Multi-objective
将上述路径经过插值后便可以在板球系统实验平台 BPVS-JLU II 上进行轨迹规划与跟
踪实验，实验平台软件为研究室在 VC++ 下开发，平台控制器采用模糊控制器，实验结
果如图 13、图 14所示。
图 13 A*算法实验效果
Experiment result of A*method
图 14 多目标路径规划实验结果
Experiment result of multi-objective path
planning method
表 3为三种情况下路径规划运行时间，本文取 5次实验的平均值作为路径长度、运动时
间以及平均跟踪误差的对比实验。
表 2 实验平均指标对比
Experiment result of two method compartment
算法 运行时
间（s）
路径
长度
（mm）
平均
危险度
X轴平均跟踪
误差
（mm）
Y轴平均跟踪
误差
（mm）
A*算法
多目标路径规划
由上述对比结果可以得出第二种规划方法在危险度指标中较小，在运行时间指标中较
大。需要说明的是，通常人们习惯于以路径长度衡量路径规划结果的优劣，但是对于多目标
规划问题，绝大多数情况下，很难找到几个指标同时达到最优的解，因此，多数情况规划的
结果是路径长以及危险度等在非劣解集中的一组解。通过多次实验得到，小球跟踪 A*算法
规划的路径的过程中，其碰到障碍物的次数要多于跟踪无主观权重多目标方法规划的路径，
因此可以得出多目标方法规划的路径更加“安全”的结论。同时多目标算法规划出的路径整
-10-
体上转弯较平缓，因此跟踪误差也较小。
5．总结
本文在板球系统实验平台上研究了无约束运动体多目标路径规划算法。考虑了路径长度
以及碰到障碍物的危险程度指标。本文首先建立了环境地图；接下来建立了目标函数与约束
条件；然后利用熵权法与 Dijkstra方法相结合求解多目标路径规划问题。最后在本文章最后
给出了仿真结果对比，将本文给出的多目标路径规划算法与 A*算法进行对比。由于无约束
运动体不受外界的机械约束，因此其运动不确定性表现尤为明显，对于此类无约束运动体路
径跟踪问题要充分的考虑其运动不确定性，因此给出的路径在尽量短的前提下还要尽量远离
障碍物。本文给出的方法能够对上述问题进行初步的解决，并得到预期效果。同时，当需要
优化目标增多时，同样可以采用本文给出的方法进行多目标路径规划。
参考文献
[1] , , . Trajectory tracking control for unconstrained objects based on supervisory fuzzy
scheme[C]. In Proc. of Int. Conf. on Sensing, Computing and Automation, May, 2006.
[2] Hongrui Wang, Yantao Tian and etc, “Tracking control of ball and plate system with a double feedback loop
structure,” Proceedings of the 2007 IEEE International Conference on Mechatronics and Automation, 2007,
(2):1114-1119.
[3] Hongrui Wang, Yantao Tian and etc, “Output regulation of ball and plate system with a nonlinear velocity
observer,” Proceedings of the 7th World Congress on Intelligent Control and Automation,2008,2164-2169.
[4] Hongrui Wang, Yantao Tian and etc, “Nonlinear Control for Output Regulation of Ball and Plate System,”
Proceedings of the 27th Chinese Control Conference,2008,(1):382-387
[5] José Maria A. Pangilinan, and Gerrit K. Janssens Evolutionary Algorithms for the Multiobjective Shortest
Path Problem[J]. International Journal of Computer and Information Science and Engineering Volume 1
Number 1,54-59
[6] . Soltani, T. Fernando, “A fuzzy based multi-objective path planning of construction sites,” Automation in
Construction, , 2004, -734.
[7] Khoukhi, A., Demirli, K., Baron, L., Balazinski, M. Nuero-fuzzy multi-objective trajectory planning of
redundant manipulators[C]. Systems, Man and Cybernetics, 2007. ISIC. IEEE International Conference on
7-10 Oct. 2007 Page(s):2831 – 2836
[8] Jingwen Huang, “Combining Entropy Weight and TOPSIS Method for Information System Selection,”
Automation and Logistics, 2008. ICAL 2008. IEEE International Conference on Publication Date: 1-3 Sept.
2008, pp. 1965-1968
[9] 邱苑华. 管理决策与应用熵学[M]. 机械工业出版社, 2002, 193-196
[10] Michael Barbehenn, “A Note on the Complexity of Dijkstra’s Algorithm for Graphs with Weighted Vertices,”
IEEE Transactions on Computers, vol. 47, No. 2, February 1998,
[11] S. Russell, P. Norvig, “Artificial Intelligence: A Modern Approach,” Prentice-Hall, New Jersey, 1995.
[12] . Soltani, T. Fernando, “A fuzzy based multi-objective path planning of construction sites,” Automation in
Construction, , 2004, -734.
On Multi-Objective Path Planning of Unconstrained Mobile
Guo Feng，Tian Yantao，Wang Hongrui
School of Communication Engineering, Jilin University, ChangChun, (130025)
Abstract
Problem of multi-objective path planning is investigated in this paper for the underactuated ball and
plate system. The purpose of multi-objective path planning is to obtain the safe and shortest path for the
ball to track. Workspace is represented by distance map and hazard map. Weights for multi-objectives
are calculated by entropy method for each grid node. Dijkstra algorithm is employed to solve the
multi-objective path planning problem finally. As illustrated by simulation results, the path obtained
by multi-objective method proposed in this paper is much safer compared with single-objective A*
algorithm.
Keywords: Ball and Plate System, Multi-Objective Decision, Path Planning, Entropy Method
