基于协作协进化和多种群遗传算法的多机器人路径规划系统

摘要

一种基于协作协进化和多种群遗传算法的多机器人路径规划系统，机器人的一条路径采用一个染色体表示，染色体就表示成节点的链表形式，即[(x，y)，time]，(x，y，time∈R)，(x，y)表示机器人的位置坐标，time部分表示从前一个结点移动本结点需要的时间消耗，开始节点的time部分等于0，每个机器人个体的染色体除了初始节点的初始位置，结束节点的目标位置固定以外，中间节点和节点个数都是可变的；将最短路径、平滑度和安全距离作为设计路径适应度函数的三个目标每个机器人采用所述适应度函数，通过Messy遗传算法优化得到最优路径。本发明采用分布式结构，通用性强、灵敏度高、稳定性好、可实现多机器人动态避障。

主权项

1.一种基于协作协进化和多种群遗传算法的多机器人路径规划系统，其特征在于：机器人的一条路径采用一个染色体表示，染色体就表示成节点的链表形式，即[(x，y)，time]，(x，y，time∈R)，(x，y)表示机器人的位置坐标，time部分表示从前一个节点移动本节点需要的时间消耗，开始节点的time部分等于0，每个机器人个体的染色体除了初始节点的初始位置，结束节点的目标位置固定以外，中间节点和节点个数都是可变的；每个机器人Robot(i)的路径path(j)的适应度函数表示成φ(p_i，j)：$\phi \left(p_{i,j}\right)=e^{-[w_l\times |\left|p_{i,j}\right||+w_f\times \psi \left(p_{i,j}\right)]}---\left(1\right)$||p_i，j||＝Dis tan ce(P_i，j)+w_s×smooth(p_i，j)+w_t×Time(p_i，j)(2)其中，φ(p_i，j)是一个非线性函数，路径的消耗越大则φ(p_i，j)越大；p_i，j表示Robot(i)的路径path(j)；||p_i，j||是距离、平滑度和时间消耗的线性组合，w_s是平滑加权因子，w_t是时间加权因子；$\mathrm{Dis}\tan \mathrm{ce}\left(p_{i,j}\right)=\underset{k=1}{\overset{\mathrm{Length}\left(p_{i,j}\right)-1}{\Sigma }}s(p_{i,j}^k,p_{i,j}^{k+1})---\left(3\right)$$\mathrm{smooth}\left(p_{i,j}\right)=\underset{k=2}{\overset{\mathrm{Length}\left(p_{i,j}\right)-1}{\Sigma }}a({\theta }_{i,j}^k-\partial )---\left(4\right)$$a=\mathrm{MAX}(\frac{A}{2\times O_A},2)---\left(5\right)$$\mathrm{Time}\left(p_{i,j}\right)=\underset{j=1}{\overset{\mathrm{length}}{\Sigma }}{\mathrm{time}}_{p_{i,j}^k}---\left(6\right)$其中，Dis tan ce(p_i，j)表示路径长度，表示Robot(i)的路径path(j)中线段节点和节点的长度，表示Robot(i)的路径path(j)中第k个节点，表示Robot(i)的路径path(j)中第k+1个节点；smooth(p_i，j)表示路径的平滑度，Length(p_i，j)表示Robot(i)的路径path(j)的路径线段总数，a为中间参数，A表示障碍物的个数，O_A表示所有障碍物的总面积，表示线段的转角度数，表示期望转角；Time(p_i，j)是路径p_i，j的时间消耗；ψ(p_i，j)是约束条件定义成惩罚函数的形式，如公式(7)所示形式：ψ(p_i，j)＝ψ₁(p_i，j)+ψ₂(p_i，j)+ψ₃(p_i，j)(7)其中，ψ₁(p_i，j)用于评估机器人Robot(i)是否超速，ψ₂(p_i，j)表示是否有机器人-障碍物碰撞情况存在，ψ₃(p_i，j)表示发生碰撞的机器人个数总和；${\psi }_1\left(p_{i,j}\right)=\left\{\begin{array}{cc}\underset{k^{*}}{\Sigma }{s}_{i,j}^{k^{*}}/\left|\right|t_{i,j}^{k^{*}}\left|\right|,& \exists k^{*},s_{i,j}^{k^{*}}/\left|\right|t_{i,j}^{k^{*}}\left|\right|>v_{i,\max }\\ 0,& \mathrm{otherwise}\end{array}\right.---\left(8\right)$公式中，表示上一个节点node(k^*-1)到当前节点node(k^*)的距离；是上一个节点node(k^*-1)到当前节点node(k^*)所需要的时间消耗，k^*表示路径线段，因此就定义了机器人在路径上的移动速度，v_i，max用于指示机器人Robot(i)的最大速度，ψ₁(p_i，j)则是所有超速的总和；${\psi }_2(p_{i,j},o_l)=\left\{\begin{array}{cc}\underset{k^{*}}{\Sigma }{\delta }_1^{-1}(s_{i,j}^k,o_l),& \exists k^{*},s(p_{i,j}^{k^{*}},o_l)\le 0\\ 0,& \mathrm{otherwise}\end{array}\right.---\left(9\right)$${\delta }_1(s_{i,k^{*}}^j,o_l)=\left\{\begin{array}{cc}\left|\right|\mathrm{Area}\left(o_l^1\right)-\mathrm{Area}\left(o_l^2\right)\left|\right|,& s(s_{i,k^{*}}^j,o_l)\le 0\\ \mathrm{MaxNum},& \mathrm{otherwise}\end{array}\right.---\left(10\right)$其中，表示路径线段和障碍物o_l之间的距离，和表示路径线段将障碍物o_l分成两块后两块的面积大小，则表示障碍物o_l两块面积之差的绝对值，MaxNum是障碍物o_l的面积；利用ψ₂(p_i，j，o_l)来评估是否有机器人-障碍物碰撞情况存在，假设存在路径线段k^*使得机器人和障碍物的距离等于0或者小于0，表示存在着机器人和障碍物的碰撞；根据公式(9)，如果ψ₂(p_i，j，o_l)等于0，表示机器人避障成功，如果ψ₂(p_i，j，o_l)不等于0，利用ψ₂(p_i，j，o_l)来评价机器人和障碍物避免碰撞需要克服的距离；${\psi }_3(p_{i,j},p_l^{*})=\left\{\begin{array}{cc}1,& \exists s_{l,r}\in p_l^{*},{\delta }_2(s_{i,j}^k,s_{l,r})=0;\\ 0,& \mathrm{otherwise}\end{array}\right.---\left(11\right)$其中，表示两个机器人在同一个时间的相对距离，通过协进化的共享机制得到其他机器人代表的位置，随后计算他们与自己的距离得到，如果在同一时间有多于两个机器人出现在同一个坐标位置，则等于发生碰撞的机器人个数总和；每个机器人采用所述适应度函数，通过Messy遗传算法优化得到最优路径。