Path planning of coal mine rescue robot based on improved A* algorithm
-
摘要: 路径规划是煤矿救援机器人研究的重要内容之一。针对灾后煤矿环境非结构化的特点，以及传统A*算法规划的路径长度非最短、拐弯次数多和平滑度较差等问题，提出一种基于改进A*算法的煤矿救援机器人路径规划方法。对真实环境中的地图信息进行二值化处理，构建栅格地图；判断当前点与目标点的相对位置，利用改进A*算法进行路径规划，得到一条从当前点到目标点的路径；利用Douglas-Peucker（D−P）算法提取路径上的关键节点，采用三次样条插值函数对关键节点进行拟合，完成对路径的平滑处理。改进A*算法将传统A*算法的8邻域搜索扩展为有目的性的13邻域搜索，在进行路径搜索时，先对当前点和目标点的位置关系进行判断，从而减少路径节点，减小路径长度，提升路径平滑度。Matlab仿真结果表明：与8邻域A*算法、24邻域A*算法、48邻域A*算法相比，改进A*算法在路径长度、拐弯次数、平滑度等方面有一定优化，更适用于煤矿救援机器人路径规划；与Fuzzy算法相比，改进A*算法路径规划所用时间更短，规划的路径长度更短，拐弯次数更少。Abstract: Path planning is one of the important contents of research on coal mine rescue robots. A path planning method for coal mine rescue robots based on improved A* algorithm is proposed to address the unstructured features of post disaster coal mine environments and the problems of non-shortest path length, multiple turns, and poor smoothness of path planned by traditional A* algorithm. The method constructs raster maps by binarizing map information in real environments, determines the relative position between the current point and the target point, and uses the improved A* algorithm for path planning. Then a path from the current point to the target point is obtained. Douglas-Pucker (D-P) algorithm is used to extract key nodes on the path, and cubic spline interpolation function is used to fit the key nodes, thereby completing the smooth processing of the path. The improved A* algorithm expands the traditional A* algorithm's 8 neighborhood search to a purposeful 13 neighborhood search. When conducting path search, the position relationship between the current point and the target point is first determined, thereby reducing path nodes and length, and improving path smoothness. The Matlab simulation results show that compared with the 8 neighborhood A* algorithm, 24 neighborhood A* algorithm, and 48 neighborhood A* algorithm, the improved A* algorithm has certain optimizations in path length, number of turns and smoothness. It is more suitable for path planning of coal mine rescue robots. Compared with the Fuzzy algorithm, the improved A* algorithm achieve shorter path planning time, shorter planned path length, and fewer turns.
-
0. 引言
矿井通风系统是煤矿安全的重要保障系统，担负着将新鲜空气送入井下、保证人员正常呼吸、稀释并排出有害气体、调节作业场所温湿度等作用[1]。要实现上述作用，必须保证矿井内各用风地点风量时刻满足需风量要求。然而，开采作业是动态变化过程，随着矿井周围环境变化，各巷道实际风量和需风量都是不断改变的，当巷道实际风量不满足需风量要求时，存在安全隐患。随着煤矿智能化发展，如何快速、智能地确定安全、高效、准确的风量调控方案，是矿井通风领域亟待解决的重大问题[2]。
近年来，元启发式算法由于其无需梯度信息、鲁棒性强等特点，被广泛应用于矿井风量调控优化问题。Wang Jinmiao等[3]以通风机功率最小为目标，建立了矿井通风系统网络优化的无约束数学模型，并利用黑燕鸥优化算法进行模型求解。吴新忠等[4]以目标用风分支风量可调最大化为目标，建立了风量调控数学模型，结合风网灵敏度的衰减特征[5-7]，确定了模型中待优化风量的最优调节分支集及其风阻调节范围，缩小了可行域范围，提高了模型解算速度，同时提出了多策略融合麻雀搜索算法对模型进行求解。Li Junqiao等[8]通过引入权重系数，提出了基于通风机最小功耗和目标用风分支最大风量需求的目标函数，并应用改进粒子群优化（Particle Swarm Optimization，PSO）算法进行求解，在尽可能降低通风系统功率消耗的同时，增大了目标用风分支的风量。此外，灰狼优化算法[9]、鲸群优化算法[10]等元启发式算法也被应用于求解矿井风量调控优化模型。但采用元启发式算法求解无约束优化数学模型存在收敛速度较慢的问题。
本文提出了一种基于改进人工蜂群（Artificial Bee Colony，ABC）算法的矿井风量按需调控智能决策方法。构建以目标用风分支风量与理想风量差距最小为目标的矿井风量按需调控智能决策模型，利用拉格朗日松弛方法[11]、冲突数方法[12]、随机搜索方法[13]和元启发式算法[14]对模型进行优化，并采用改进ABC算法求解模型，可实现对矿井风量的快速、精准调控。
1. 矿井风量按需调控智能决策模型
1.1 矿井风量按需调控智能决策需求
为方便分析，将矿井巷道分为3类：目标用风分支、其他用风分支和一般分支。目标用风分支即需要通过风量调控决策使该分支风量达到预定值的巷道；其他用风分支即除目标用风分支外的采煤工作面、掘进工作面、独立通风硐室等用风地点需风量要求严格的巷道；一般分支即行人巷道、行车巷道和辅运巷等对风量不做要求的巷道。
矿井风量调控的目的是改变某一条或某几条目标用风分支的风量，使其满足安全生产需求。为达到该目的，在矿井的日常风量调控中，在总风量满足需求时，常通过调控风窗面积以改变巷道风阻，从而实现对目标用风分支的风量调节。因此，在保证其他用风分支和一般分支风量满足需风量要求的前提下，求解符合目标用风分支理想风量的矿井风阻调控方案，即矿井风量按需调控智能决策的实质。
1.2 矿井风量按需调控智能决策模型建立
假设第$ x $（$ x $=1，2，$\cdots $，v，v为矿井风阻调控方案总数）个矿井风阻调控方案$ {R_x} = \{ {r_{x,1}},{r_{x,2}}, \cdots ,{r_{x,n}}\} $，其中$ {r_{x,j}} $为第$ x $个风阻调控方案中第$ j $（$ j $=1，2，$\cdots $，n，n为通风网络分支总数）个分支风阻，此时第$ x $个矿井风阻调控方案中第$ j $个分支的风量$ {q_{x,j}} $与$ {R_x} $存在函数关系$ {f_j} $（·）：
$$ {q_{x,j}} = {f_j}({R_x}) $$ (1) 矿井风量按需调控智能决策模型的目标函数可描述为
$$ F({R_x}) = \sum\limits_{t = 1}^{{z}} S_{ x,t} $$ (2) $$ S_{ x,t}=\left\{\begin{array}{l}\mathrm{min}(\left|f_t(R_x)-a_t\right|,\left|f_t(R_x)-b_t\right|) \quad f_t(R_x) < a_t \text{或}\\ \quad f_t(R_x) > b_t \\ 0\ \ \ \ a_t\leqslant f_t(R_x)\leqslant b_t\end{array}\right. $$ (3) 式中：$ {S_{ x,t}} $为第$ x $个矿井风阻调控方案中第t（t=1，2，$\cdots $，z，z为目标用风分支总数）个目标用风分支风量与其理想风量的差值；$f_t(R_x) $为第x个矿井风阻调控方案中第t个目标用风分支风量；$ {a_t} $，$ {b_t} $分别为第$ t $个目标用风分支风量的下限和上限。
矿井风量按需调控智能决策模型可建立为
$$ \left\{\begin{array}{l}\mathrm{min}F\text{(}R_x\text{)} \\ \mathrm{s.t.}\text{ }f_s(R_x)\leqslant b_s \qquad s=1,2,\cdots,n-z \\ \quad\;\; l_s(R_x)\leqslant c_s \\ \quad\;\;\displaystyle\sum_{j=1}^nd_{i,j}f_j(R_x)=0\text{ } \qquad i=1,2,\cdots,m-1 \\ \quad\;\;\displaystyle\sum_{j=1}^ne_{g,j}r_{x,j}\left|f_j(R_x)\right|f_j(R_x)-h_{{\mathrm{N}}j}=0 \qquad g=1,2,\cdots,\\ \qquad\quad n-m-1\\ \quad\;\; R_x\in G \end{array}\right. $$ (4) $$ {d}_{i,j}=\left\{\begin{array}{*{20}{l}}1& i节点为j分支端点且风量{q}_{x,j}流入该节点\\ -1& i节点为j分支端点且风量{q}_{x,j}流出该节点\\ 0& i节点不属于j分支的端点 \end{array} \right.$$ (5) $$ {e}_{g,j}=\left\{\begin{array}{*{20}{l}}1& j分支在g回路中且与g回路同向\\ -1& j分支在g回路中且与g回路反向\\ 0& j分支不属于g回路\end{array}\right.$$ (6) 式中：$ {f_s}({R_x}) $为第$ x $个矿井风阻调控方案中第$ s $个其他用风分支或一般分支风量；$ {b_s} $为第$ s $个其他用风分支或一般分支风量上限；$ {l_s}({R_x}) $为$ {f_s}({R_x}) $的负值；$ {c_s} $为第$ s $个其他用风分支或一般分支风量下限$ {a_s} $的负值；$ m $为通风网络节点数；$ h_{\mathrm{N}j} $为第j个分支自然风压；$ G $为矿井风阻调控方案集合，$ G=\left\{R_1,R_2,\cdots,R_v\right\} $。
1.3 矿井风量按需调控智能决策模型优化
1.3.1 基于拉格朗日松弛方法的模型优化
式（4）中第3个和第4个约束可由通风网络解算方法[15-16]进行求解，第5个约束是对决策变量$ {R_x} $取值的限制，且决策变量为连续变量。因此将第3个至第5个约束视为“简单”约束，第1个和第2个约束视为“难”约束。运用拉格朗日松弛方法，将难处理的约束通过拉格朗日乘子移到目标函数上，可将式（4）优化为
$$ \left\{\begin{array}{l}\mathrm{min}\text{ }F(R_x)+\displaystyle\sum_{s=1}^{n-{\textit{z}}}\lambda_s(f_s(R_x)-b_s)+\displaystyle\sum_{s=1}^{n-{\textit{z}}}\mu_s(l_s(R_x)-c_s) \\ \mathrm{s.t.}\text{ }\displaystyle\sum_{j=1}^nd_{i,j}f_j(R_x)=0 \\ \quad\;\;\displaystyle\sum_{j=1}^ne_{g,j}r_{x,j}\left|f_j(R_x)\right|f_j(R_x)-h_{{\mathrm{N}}j}=0\text{ } \\ \quad\;\;\lambda_s,\mu_s\geqslant0 \\ \quad\;\; R_x\in G\end{array}\right. $$ (7) 式中$ {\lambda _s} $，$ {\mu _s} $为第$ s $个其他用风分支或一般分支对应的拉格朗日乘子。
由式（7）可知，将式（4）中的第1个和第2个约束通过拉格朗日乘子移到目标函数上后，可行解将不需满足其他用风分支和一般分支风量符合各自需风量这一约束。此时，矿井风量按需调控智能决策模型的一个可行解为一组处于$ G $集合内，同时满足节点风量平衡定理和回路风压平衡定理的风阻集合。因此，该模型的可行域可利用通风网络解算中的Scott−Hinsley法进行刻画。
1.3.2 基于冲突数方法的模型优化
式（7）中的目标函数反映的是各分支风量与其风量上下限（需风量范围）之间的函数关系。为简化该式，引入冲突数的概念：在矿井风量按需调控智能决策模型中，冲突数可理解为矿井风阻调控方案下，风量不处于其需风量范围的分支数。若某分支的风量不处于其需风量范围，则认为该分支的风量与实际需风量发生了冲突，此时该分支的冲突数$ {T_{x,j}} $为1，反之为0。总冲突数$ P({R_x}) $表示在第$ x $个矿井风阻调控方案下矿井所有分支发生冲突情况的总数，当$ P({R_x}) $为0时，代表在第$ x $个矿井风阻调控方案下，通风网络中每条分支风量均处于其需风量范围中，此时对应的矿井风阻调控方案即为最优的矿井风量按需调控决策。
运用冲突数方法可将式（7）中的目标函数改进为
$$ P({R_x}) = \sum\limits_{j = 1}^n {{T_{x,j}}} $$ (8) $$ T_{x,j}=\left\{\begin{gathered}1\text{ }\ \ f_j(R_x)\notin[a_j,b_j] \\ 0\text{ }\ \ f_j(R_x)\in[a_j,b_j] \\ \end{gathered}\right. $$ (9) 则式（7）可优化为
$$ \left\{\begin{gathered}\min\text{ }P(R_x) \\ \mathrm{s.t.\text{ }}\sum\limits_{j=1}^nd_{i,j}f_j(R_x)=0 \\ \quad\;\;\sum\limits_{j=1}^ne_{g,j}r_{x,j}\left|f_j(R_x)\right|f_j(R_x)-h_{{\mathrm{N}}j}=0 \\ \quad\;\; R_x\in G \\ \end{gathered}\right. $$ (10) 1.3.3 基于随机搜索方法的模型优化
由于式（1）的函数关系是假设的，目前并没有一个方程能够准确描述$ {q_{x,j}} $与$ {R_x} $之间的关系，所以难以讨论式（10）中目标函数和约束条件的凹凸性、导数信息、KKT条件的约束规范、有效集等性质，导致无法利用矿井风阻调控方案$ {R_x} $对应的矿井风量$ {Q_x} $=$ \left\{ {{q_{x,1}},{q_{x,2}}, \cdots ,{q_{x,n}}} \right\} $的变化趋势精确求解矿井风阻调控方案$ {R_x} $的搜索方向和搜索步长，不能通过最速下降法和共轭梯度法求解矿井风量按需调控智能决策模型。因此，采用无需利用$ q{}_{x,j} $与$ {R_x} $之间的函数关系，也可获得矿井风阻调控方案$ {R_x} $的搜索方向和搜索步长的随机搜索方法，将式（10）优化为
$$ \left\{\begin{gathered}\min\text{ }P(Q_x) \\ \mathrm{s.t.}\text{ }\sum\limits_{j=1}^nd_{i,j}q_{x,j}=0 \\ \quad\;\;\sum\limits_{j=1}^ne_{g,j}r_{x,j}\left|q_{x,j}\right|q_{x,j}-h_{{\mathrm{N}}j}=0 \\ \quad\;\; R_x\in G \\ \end{gathered}\right. $$ (11) 1.3.4 基于元启发式算法的模型优化
由式（8）和式（9）可知，当任何分支风量不处于该分支的需风量范围时，都会使目标函数值增加1，即式（8）并不能体现出目标用风分支、其他用风分支和一般分支这3类巷道的区别。由式（8）计算出的目标函数值并不会引导寻优方案优先向使目标用风分支满足其需风量范围的可行解移动。为使目标函数值在目标用风分支维度下降得更迅速，对不同类型的分支依据其需风量范围，引入权重系数$ {p_j} $，最终将式（11）优化为
$$ \left\{\begin{gathered}\min\text{ }P(Q_x) \\ \mathrm{s.t.}\text{ }\sum\limits_{j=1}^nd_{i,j}q_{x,j}=0 \\ \qquad\sum\limits_{j=1}^ne_{g,j}r_{x,j}\left|q_{x,j}\right|q_{x,j}-h_{\mathrm{N}j}=0 \\ \qquad R_x\in G \\ \end{gathered}\right. $$ (12) $$ P({Q_x}) = \sum\limits_{j = 1}^n {{p_j}{T_{x,j}}} $$ (13) 2. 矿井风量按需调控智能决策
2.1 基于ABC算法的矿井风量按需调控智能决策
ABC算法是通过模拟自然界蜜蜂分工采蜜行为而得到的一种元启发式算法，具有结构简单、控制参数少、鲁棒性强等优点[17]，在应对高维度非线性优化问题上表现出优秀的求解能力[18]。
将矿井风量按需调控智能决策模型中的矿井风阻调控方案$ {R_x} $视为蜜源位置，目标函数$ P({Q_x}) $视为蜜源质量（由式（12）可知$ P({Q_x}) $越小，蜜源质量越优），则基于ABC算法的矿井风量按需调控智能决策的寻优过程如下：
1） 种群初始化。通过初始化方程生成矿井风阻调控方案集合$ G $。
$$ r_{x,j}=r_{j\min}+\mathrm{rand}(0,1)(r_{j\max}-r_{j\min}) $$ (14) 式中：rand（0，1）为[0，1]上的随机数；$ r_{j\mathrm{m}\text{ax}},r_{j\min} $分别为第$ j $个分支风阻的上下限。
2） 采蜜行为。采蜜蜂在可行域内局部搜索新的矿井风阻调控方案，具体搜索方程可表示为
$$ {r'_{x,j}} = {r_{x,j}} + \phi ({r_{x,j}} - {r_{k,j}}) $$ (15) 式中：$ {r'_{x,j}} $为经搜索后的第$ x $个新的矿井风阻调控方案$ {R'_x} $中第$ j $个分支的风阻，$ {R'_x} = \{ {r'_{x,1}},{r'_{x,2}}, \cdots ,{r'_{x,n}}\} $；$ \phi $为[−1，1]上均匀分布的随机数；$ {r_{k,j}} $为随机选出的第$ k $$ (k \ne x) $个矿井风阻调控方案中第$ j $个分支的风阻。
若$ {R'_x} $的目标函数值优于$ {R_x} $，$ {R'_x} $将取代原矿井风阻调控方案$ {R_x} $，否则继续以$ {R_x} $作为矿井风阻调控方案。
3） 跟随行为。当采蜜蜂完成搜索后，会将新的蜜源信息分享给跟随蜂，每一只跟随蜂都会根据每个矿井风阻调控方案的目标函数值，以一定的概率选择适应度值较大的优质矿井风阻调控方案，在其周围采用搜索方程（式（15））进行局部搜索。每个矿井风阻调控方案的适应度函数$ H({R_x}) $及跟随蜂选择对应优质矿井风阻调控方案的概率$ {w_x} $分别为
$$ H({R_x}) = \frac{1}{{1 + P({Q_x})}}{\text{ }} $$ (16) $$ {w_x} = \frac{{H({R_x})}}{\displaystyle \sum_{x = 1}^v {H({R_x})} }{\text{ }} $$ (17) 4） 侦察行为。若某一矿井风阻调控方案在经历$ L $只蜜蜂搜索后仍未找到比它适应度值更大的优质矿井风阻调控方案，此时认为该矿井风阻调控方案为局部最优解。为跳出局部最优解，采蜜蜂会转变为侦察蜂，利用式（14）在整个可行域搜索新的矿井风阻调控方案，直到找到目标函数值更优的矿井风阻调控方案。
2.2 基于改进ABC算法的矿井风量按需调控智能决策
由于ABC算法中引入了较多的随机因子，导致该算法的探索能力较强而利用能力不足，在求解矿井风量按需调控智能决策模型时存在收敛速度较慢的问题。为平衡ABC算法的探索能力和利用能力，结合PSO算法[19]和一般反向学习（Generalized Opposition-based Learning，GOBL）策略[20]对ABC算法进行改进。
2.2.1 采蜜行为改进
PSO算法的灵感来源于鸟群或鱼群通过群体协助进行觅食的行为，在PSO算法中粒子根据个体历史最优值和群体历史最优值调整搜索方向，PSO算法拥有很强的利用能力，因此在蜜蜂的采蜜行为中引入群体历史最优值对搜索方向进行引导，将采蜜行为的搜索方程改进为
$$ {r'_{x,j}} = {r_{x,j}} + \phi ({r_{x,j}} - {r_{k,j}}) + \varphi ({r_{{\mathrm{best}},j}} - {r_{x,j}}){\text{ }} $$ (18) 式中：$ \varphi $为[0，1.5]上均匀分布的随机数；$ r_{\mathrm{best},j} $为当前最优的矿井风阻调控方案$ R_{\mathrm{best}} $在第$ j $个分支的风阻。
2.2.2 侦察行为改进
GOBL策略的核心机制：针对当前种群中的候选解，同步生成其一般反向解，通过贪婪准则选择适应度值更优的解作为下一代种群个体。该策略可提升算法的探索能力，从而提高算法收敛到全局最优解的概率。为保留原局部最优解的有用信息，将侦察行为的搜索方程改进为
$$ {\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{r} _{x,j}} = {\mathrm{rand}}(0,1)({r_{j\min }}+{r_{j\max }}) - {r_{x,j}} $$ (19) 式中$ {\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{r} _{x,j}} $为第$ x $个矿井风阻调控方案的反向解$ {\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{R} _x} $中第$ j $个分支的风阻。
若一般反向解$ {\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{r} _{x,j}} $未在边界调节范围$ [{r_{j\min }},{r_{j\max }}] $内，则采用随机生成的方法进行重置：
$$ {\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{r} _{x,j}} = {\mathrm{rand}}({r_{j\min }},{r_{j\max }}) $$ (20) 式中$ \mathrm{rand}(r_{j\min},r_{j\max}) $为区间$ [{r_{j\min }},{r_{j\max }}] $上的随机数。
将一般反向解和利用式（14）产生的随机解进行比较，择优选择新蜜源的位置，该过程可表示为
$$ {R_x} = \left\{ \begin{gathered} {{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{R} }_x}\quad P({{\overset{\lower0.5em\hbox{$\smash{\scriptscriptstyle\smile}$}}{R} }_x}) < P({R_x}) \\ {R_x}\quad {\text{其他}} \\ \end{gathered} \right. $$ (21) 3. 实验与分析
3.1 实验参数
实验目标：求解使目标用风分支风量调节至32 m3/s的风量调控决策。实验所用通风网络拓扑如图1所示，该通风网络初始数据见表1，各分支类型、风阻和风量调节范围见表2。为验证改进ABC算法性能，与ABC算法、PSO算法、基于全局最优的人工蜂群（Gbest-guided Artificial Bee Colony，GABC）算法[21]和基于一般反向学习的人工蜂群（Artificial Bee Colony with Generalized Opposition-Based Learning，ABC−GOBL）算法[22]进行对比。各算法主要参数设置：种群规模为100，最大抛弃次数为60，最大迭代次数为200。
表 1 通风网络初始数据Table 1. Ventilation network initial data分支
编号风阻/
（N·s2·m−8）风量/
（m3·s−1）分支
编号风阻/
（N·s2·m−8）风量/
（m3·s−1）1 0.006455 129.50 9 0.114862 12.32 2 0.004709 29.96 10 0.085501 14.27 3 0.009727 20.85 11 0.001561 62.09 4 0.001339 73.38 12 0.001391 73.38 5 1.572439 5.31 13 0.015521 50.81 6 0.001562 62.10 14 0.005727 129.50 7 0.232000 11.28 15 0 129.50 8 0.013821 35.51 表 2 通风网络各分支类型、风阻和风量调节范围Table 2. Branch types, air resistance, and airflow regulation range of the ventilation network分支编号 分支类型 风阻调节范围/（N·s2·m−8） 风量调节范围/（m3·s−1） 1 一般分支 0.006455 129.50 2 其他用风分支 0.004709 26.96～32.96 3 其他用风分支 0.009727 18.77～22.94 4 一般分支 0.001339 3.94～126.00 5 一般分支 1.572439 3.94～126.00 6 一般分支 0.001562 3.94～126.00 7 其他用风分支 0.040940 ～0.884324 10.15～12.41 8 一般分支 0.013821 ～0.844314 3.94～126.00 9 其他用风分支 0.016615 ～0.577616 11.09～13.55 10 目标用风分支 0.085501 31.50～32.50 11 一般分支 0.001561 3.94～126.00 12 一般分支 0.001391 3.94～126.00 13 一般分支 0.004964 ～0.714323 3.94～126.00 14 其他用风分支 0.005727 129.50 15 虚拟分支 0 129.50 3.2 实验结果分析
实验中每个算法独立运行30次，不同算法的迭代收敛曲线如图2所示，不同算法下模型求解结果见表3。
表 3 不同算法下模型求解结果Table 3. Model solution results under different algorithms算法 算法成功率/% 平均收敛代数 平均寻优时间/s 改进ABC 100 42 132.72 GABC 87 53 167.48 ABC−GOBL 100 122 385.52 ABC 100 158 516.68 PSO 0 － － 由图2和表3可知：改进ABC算法能在132.72 s稳定将目标函数值收敛到0，这是由于改进ABC算法在引入全局最优解对搜索方向进行引导的同时，加入一般反向解保留搜索经验，能使算法在保持较高探索能力的同时，提高算法的利用能力；GABC算法虽然能在167.48 s实现寻优，但在解算时会出现早熟现象，这是由于GABC算法虽然采用全局最优解提高了算法的利用能力，但在求解矿井风量按需调控模型时仍存在不能跳出局部最优解的情况；ABC−GOBL算法和ABC算法均能稳定收敛但速度较慢，平均收敛时间分别为385.52 s和516.68 s，而ABC−GOBL算法收敛速度快于ABC算法，这是由于该算法在侦查蜂阶段保留了种群记忆；PSO算法无法正常求解矿井风量按需调控智能决策模型，这是由于PSO算法同时利用个体最优解和全局最优解引导搜索，过度提升了算法的利用能力，导致该算法容易陷入局部最优解。
由改进ABC算法求解出的最优矿井风阻调控方案见表4。可看出当分支风阻r7，r8，r9，r13分别为0.871 307，0.209 715，0.571 217，0.051 381 N·s2/m8时，目标用风分支（第10个分支）的风量由14.27 m3/s增加至31.51 m3/s，该风量满足目标用风分支的需风量（31.50～32.50 m3/s）要求，与目标用风分支的期望风量32 m3/s仅有0.49 m3/s的误差，且调控后各分支风量均能满足需风量要求。
表 4 改进ABC算法求解出的最优矿井风阻调控方案Table 4. Optimal mine ventilation resistance control scheme solved by the improved artificial bee colony algorithm分支
编号风阻/
（N·s2·m−8）风量/
（m3·s−1）分支
编号风阻/
（N·s2·m−8）风量/
（m3·s−1）1 0.006455 129.50 9 0.571217 12.21 2 0.004709 27.25 10 0.085501 31.51 3 0.009727 18.96 11 0.001561 64.23 4 0.001339 74.83 12 0.001391 74.83 5 1.572439 8.49 13 0.051381 46.21 6 0.001562 64.23 14 0.005727 129.50 7 0.871307 10.60 15 0 129.50 8 0.209715 20.51 4. 结论
1） 以目标用风分支风量与理想风量差距最小为目标，建立了矿井风量按需调控智能决策模型，并运用拉格朗日松弛方法优化模型的约束条件，采用冲突数方法优化模型的目标函数，利用随机搜索方法和元启发式算法优化模型的搜索策略。
2） 针对ABC算法探索能力和利用能力不平衡的问题，在采蜜蜂局部寻优时引入群体历史最优解引导采蜜行为，并利用GOBL策略保存侦查蜂的搜索经验，提出了一种改进ABC算法。
3） 将改进ABC算法用于求解矿井风量调控决策模型，相较于PSO，ABC，GABC，ABC−GOBL等算法具有更高的收敛速度和稳定性，且寻优精度高。
-
![]()
图 2 当前点与目标点的位置关系
Figure 2. The positional relationship between the current point and the target point
![]()
图 5 简单环境下不同邻域A*算法规划的路径
Figure 5. Paths planned by different neighborhoods A* algorithm in simple environment
![]()
图 6 复杂环境下不同邻域A*算法规划的路径
Figure 6. Paths planned by different neighborhoods A* algorithm in complex environment
![]()
图 7 同一环境下不同算法规划的路径对比
Figure 7. Comparison of paths planned by different algorithms in the same environment
表 1 简单环境下不同邻域A*算法的性能对比
Table 1 Performance comparison of different neighborhoods A* algorithm in simple environment
算法 时间/s 路径平滑
前长度/m路径平滑
后长度/m路径节点数 路径平滑前拐弯次数 路径平滑后拐弯次数 8邻域A*算法 0.464 617.904 605.288 96 17 2 24邻域A*算法 0.748 602.761 597.613 74 10 2 48邻域A*算法 0.823 602.023 598.903 72 8 2 本文算法 0.619 602.761 597.613 74 10 2 
下载: 导出CSV
表 2 复杂环境下不同邻域A*算法的性能对比
Table 2 Comparison of the performance of different neighborhoods A* algorithm in complex environment
算法 时间/s 路径平滑
前长度/m路径平滑
后长度/m路径节点数 路径平滑前
拐弯次数路径平滑后
拐弯次数8邻域A*算法 0.807 707.696 699.431 121 15 8 24邻域A*算法 1.212 677.411 672.739 87 11 6 48邻域A*算法 1.361 676.673 672.739 85 11 6 本文算法 1.009 677.411 672.739 87 11 6
下载: 导出CSV
表 3 本文算法与Fuzzy算法的性能对比
Table 3 Performance comparison between the algorithm in this article and Fuzzy algorithm
算法 路径长度/m 时间/s 拐弯次数 Fuzzy算法 695.297 1.067 5 本文算法 534.322 0.826 3
下载: 导出CSV
-
[1] 朱华,由韶泽. 新型煤矿救援机器人研发与试验[J]. 煤炭学报,2020,45(6):2170-2181. DOI: 10.13225/j.cnki.jccs.zn20.0352 ZHU Hua,YOU Shaoze. Research and experiment of a new type of coal mine rescue robot[J]. Journal of China Coal Society,2020,45(6):2170-2181. DOI: 10.13225/j.cnki.jccs.zn20.0352
[2] 徐兴,俞旭阳,赵芸,等. 基于改进遗传算法的移动机器人全局路径规划[J]. 计算机集成制造系统,2022,28(6):1659-1672. DOI: 10.13196/j.cims.2022.06.006 XU Xing,YU Xuyang,ZHAO Yun,et al. Global path planning of mobile robot based on improved genetic algorithm[J]. Computer Integrated Manufacturing Systems,2022,28(6):1659-1672. DOI: 10.13196/j.cims.2022.06.006
[3] 王梓强,胡晓光,李晓筱,等. 移动机器人全局路径规划算法综述[J]. 计算机科学,2021,48(10):19-29. DOI: 10.11896/jsjkx.200700114 WANG Ziqiang,HU Xiaoguang,LI Xiaoxiao,et al. Overview of global path planning algorithms for mobile robots[J]. Computer Science,2021,48(10):19-29. DOI: 10.11896/jsjkx.200700114
[4] SHANG E,DAI Bin,NIE Yiming,et al. An improved A-star based path planning algorithm for autonomous land vehicles[J]. International Journal of Advanced Robotic Systems,2020,17(5):1-13.
[5] 张瑜,宋荆洲,张琪祁. 基于改进动态窗口法的户外清扫机器人局部路径规划[J]. 机器人,2020,42(5):617-625. DOI: 10.13973/j.cnki.robot.190649 ZHANG Yu,SONG Jingzhou,ZHANG Qiqi. Local path planning of outdoor cleaning robot based on an improved DWA[J]. Robot,2020,42(5):617-625. DOI: 10.13973/j.cnki.robot.190649
[6] MIN Huasong,LIN Yunhan,WANG Sijing,et al. Path planning of mobile robot by mixing experience with modified artificial potential field method[J]. Advances in Mechanical Engineering,2015,7(12):1-17.
[7] 郭晓静,杨卓橙. 基于邻域拓展的静态路径规划A*算法研究[J]. 计算机工程与应用,2022,58(8):168-174. DOI: 10.3778/j.issn.1002-8331.2010-0222 GUO Xiaojing,YANG Zhuocheng. Improved A* algorithm based on neighbor extension in static environment[J]. Computer Engineering and Applications,2022,58(8):168-174. DOI: 10.3778/j.issn.1002-8331.2010-0222
[8] 崔宝侠,王淼弛,段勇. 基于可搜索24邻域的A*算法路径规划[J]. 沈阳工业大学学报,2018,40(2):180-184. DOI: 10.7688/j.issn.1000-1646.2018.02.11 CUI Baoxia,WANG Miaochi,DUAN Yong. Path planning for A* algorithm based on searching 24 neighborhoods[J]. Journal of Shenyang University of Technology,2018,40(2):180-184. DOI: 10.7688/j.issn.1000-1646.2018.02.11
[9] 刘小佳,狄梦然,梁利东,等. 基于象限判别下的改进A*算法路径规划[J]. 常州工学院学报,2020,33(2):26-30,35. DOI: 10.3969/j.issn.1671-0436.2020.02.005 LIU Xiaojia,DI Mengran,LIANG Lidong,et al. On the improved path planning of A* algorithm based on quadrant discrimination[J]. Journal of Changzhou Institute of Technology,2020,33(2):26-30,35. DOI: 10.3969/j.issn.1671-0436.2020.02.005
[10] 槐创锋,郭龙,贾雪艳,等. 改进A*算法与动态窗口法的机器人动态路径规划[J]. 计算机工程与应用,2021,57(8):244-248. DOI: 10.3778/j.issn.1002-8331.2008-0063 HUAI Chuangfeng,GUO Long,JIA Xueyan,et al. Improved A* algorithm and dynamic window method for robot dynamic path planning[J]. Computer Engineering and Applications,2021,57(8):244-248. DOI: 10.3778/j.issn.1002-8331.2008-0063
[11] 程传奇,郝向阳,李建胜,等. 融合改进A*算法和动态窗口法的全局动态路径规划[J]. 西安交通大学学报,2017,51(11):137-143. CHENG Chuanqi,HAO Xiangyang,LI Jiansheng,et al. Global dynamic path planning based on fusion of improved A* algorithm and dynamic window approach[J]. Journal of Xi'an Jiaotong University,2017,51(11):137-143.
[12] 陶德俊,姜媛媛,刘延彬,等. 煤矿救援机器人路径平滑算法研究[J]. 工矿自动化,2019,45(10):49-54. DOI: 10.13272/j.issn.1671-251x.2019050069 TAO Dejun,JIANG Yuanyuan,LIU Yanbin,et al. Research on path smoothing algorithm of coal mine rescue robot[J]. Industry and Mine Automation,2019,45(10):49-54. DOI: 10.13272/j.issn.1671-251x.2019050069
[13] 李枭扬,周德云,冯琦. 基于分级规划策略的A*算法多航迹规划[J]. 系统工程与电子技术,2015,37(2):318-322. DOI: 10.3969/j.issn.1001-506X.2015.02.14 LI Xiaoyang,ZHOU Deyun,FENG Qi. Multiple routes planning for A* algorithm based on hierarchical planning[J]. Systems Engineering and Electronics,2015,37(2):318-322. DOI: 10.3969/j.issn.1001-506X.2015.02.14
[14] FU Bing,CHEN Lin,ZHOU Yuntao,et al. An improved A* algorithm for the industrial robot path planning with high success rate and short length[J]. Robotics & Autonomous Systems,2018,106:26-37.
[15] LI Chengming,GUO Peipei,WU Pengda,et al. Extraction of terrain feature lines from elevation contours using a directed adjacent relation tree[J]. International Journal of Geo-Information,2018,7(5):163-177. DOI: 10.3390/ijgi7050163
[16] ZHAO Liangbin,SHI Guoyou. A method for simplifying ship trajectory based on improved Douglas-Peucker algorithm[J]. Ocean Engineering,2018,166(15):37-46.
[17] 杨敏,陈媛媛,金澄,等. 保持移动速度特征的轨迹线化简方法[J]. 测绘学报,2017,46(12):2016-2023. DOI: 10.11947/j.AGCS.2017.20170023 YANG Min,CHEN Yuanyuan,JIN Cheng,et al. A method of speed-preserving trajectory simplification[J]. Acta Geodaetica et Cartographica Sinica,2017,46(12):2016-2023. DOI: 10.11947/j.AGCS.2017.20170023
[18] 胡峥楠,佘锋. 一种基于样条插值的局部路径规划模型与实现[J]. 微型电脑应用,2020,36(11):106-110. DOI: 10.3969/j.issn.1007-757X.2020.11.032 HU Zhengnan,SHE Feng. A local path planning model and implementation based on spline interpolation[J]. Microcomputer Applications,2020,36(11):106-110. DOI: 10.3969/j.issn.1007-757X.2020.11.032
[19] 高晓,杨志强,库新勃,等. 基于三次样条插值实现无人机高动态运动轨迹插值[J]. 全球定位系统,2020,45(1):37-42. DOI: 10.13442/j.gnss.1008-9268.2020.01.006 GAO Xiao,YANG Zhiqiang,KU Xinbo,et al. 3D-coordinate interpolation for UAV high dynamic positioning based on cubic spline interpolation[J]. GNSS World of China,2020,45(1):37-42. DOI: 10.13442/j.gnss.1008-9268.2020.01.006
[20] 张金泽. 水面无人艇路径规划及避障策略的研究[D]. 大连: 大连海事大学, 2022. ZHANG Jinze. Research on path planning and obstacle avoidance strategy of unmanned surface vehicle[D]. Dalian: Dalian Maritime University, 2022.
[21] 刘胜,张豪,晏齐忠,等. 基于ACO−SA算法的变电站巡检机器人路径规划[J]. 南方电网技术,2022,16(9):75-82. DOI: 10.13648/j.cnki.issn1674-0629.2022.09.009 LIU Sheng,ZHANG Hao,YAN Qizhong,et al. Path planning of inspection robot in substation based on ACO-SA algorithm[J]. Southern Power System Technology,2022,16(9):75-82. DOI: 10.13648/j.cnki.issn1674-0629.2022.09.009
计量
- 文章访问数: 843
- HTML全文浏览量: 34
- PDF下载量: 64
