基于反复博弈的无人飞行器动态障碍规避方法与流程

1.本发明涉及无人飞行器技术领域，特别涉及一种基于反复博弈的无人飞行器动态障碍规避方法、电子设备和存储介质。


背景技术：

2.无人飞行器在飞行过程中能够通过传感器来感测周围环境信息，为了保障无人飞行器能够自主避开障碍物，需要设计适合的避障方法，使得无人飞行器根据障碍物位置、障碍物类型、自身位置等信息进行避障机动，进而保证无人飞行器在安全的前提下迅速避开障碍物。是否具备避障能力，是判断无人飞行器自主能力的关键指标之一。
3.现有的避障算法在较复杂的环境下的避障效果不理想，对环境的适应性较差，所以如何提高无人飞行器避障算法的性能是一个至关重要的问题。


技术实现要素：

4.为了解决现有技术存在的问题，本发明提供一种基于反复博弈的无人飞行器动态障碍规避方法，使得无人飞行器系统在面对移动障碍、移动目标时能够实时进行避障机动，较快地为无人飞行器计算出性能较优的运动路径，保障无人飞行器安全运行到各自的目标点。
5.为实现上述目的，本发明提供的一种基于反复博弈的无人飞行器动态障碍规避方法，包括以下步骤：
6.将无人飞行器作为博弈的参与者，建立博弈参与者集合；
7.根据所述博弈参与者之间的状态计算博弈收益值，通过计算博弈收益值衡量无人飞行器选取博弈策略的优劣；
8.使博弈参与者在反复博弈过程中快速收敛到最优策略，根据博弈参与者的决策更新混合策略，根据混合策略与博弈收益进行决策，使得博弈参与者的收益达到纳什均衡并选择对应的避障策略。
9.进一步地，所述将无人飞行器作为博弈的参与者，建立博弈参与者集合的步骤，还包括，
10.假设无人飞行器运行时遇到h个障碍物obh(h＝1,
…
,h)，无人飞行器当前位置坐标为(xr，yr)，每个障碍物距离无人飞行器最近点的坐标为(xh，yh)，博弈参与者集合为a，将无人飞行器放入博弈参与者集合a；
11.计算无人飞行器与障碍物的距离，当满足公式1时则障碍物进入无人飞行器的安全范围，与无人飞行器进行博弈避障；
[0012][0013]
其中，d
safe
为安全距离，当无人飞行器距障碍物的距离小于等于d
safe
时将障碍物obh放入博弈参与者集合a，进行避障机动；
[0014]
在进行避障时，将工作环境中出现在无人飞行器的安全范围内的原始障碍物视为博弈参与者。
[0015]
进一步地，还包括，
[0016]
博弈参与者选择的策略集合包含四种策略集合；
[0017]
第一策略集合为博弈参与者改变自身的速度，并保持其他状态不变；
[0018]
第二策略集合为博弈参与者改变自身的运行方向，并保持其他状态不变；
[0019]
第三策略集合为博弈参与者运行速度、运行方向均保持不变；
[0020]
第四策略集合为停止策略，所述博弈参与者保持当前位置不变。
[0021]
进一步地，所述根据所述博弈参与者之间的状态计算博弈收益值，通过计算博弈收益值衡量无人飞行器选取博弈策略的优劣的步骤，还包括，
[0022]
假设共有a个博弈参与者，其收益计算公式为：
[0023][0024]
其中，r为判断策略是否保证无人飞行器安全的系数，当所选取的策略可以保证安全时r＝1，当不能保证安全时r＝0；d
safe
为无人飞行器的安全距离范围；aved为ai与其他博弈参与者之间距离的平均值；mind为ai与其他博弈参与者之间距离的最小值；ai为博弈参与者i所采取的策略；a-i
为除了博弈参与者i以外的博弈参与者所采取的策略；x(ai)为不同策略的消耗值。
[0025]
进一步地，所述使博弈参与者在博弈过程中快速收敛到最优策略，根据博弈参与者的决策更新混合策略，根据混合策略与博弈收益进行决策，使得博弈参与者的收益达到纳什均衡并选择对应的避障策略的步骤，还包括，
[0026]
设反复博弈的次数为t，当前博弈次数为t，博弈参与者可选策略为n个，初始化博弈参与者ai的混合策略，t＝1且博弈参与者ai的初始概率为：
[0027][0028]
其中，n为博弈参与者可选的策略个数；分别为博弈参与者在初始时刻选择第1个、第2个、
…
、第n个策略的概率。
[0029]
进一步地，还包括，
[0030]
将混合策略与每次迭代博弈参与者的决策进行结合，使博弈参与者ai的概率随着迭代次数的变化而变化，计算公式为：
[0031][0032]
其中，参数函数i(τi)(i＝1,2,
…
,n)为决策记录函数，包括记录前t-1次迭代中选择当前策略的次数和不选择当前策略的次数，计算公式为：
[0033][0034]
其中，pri为博弈参与者ai的博弈优先级；β为大于0的常数，用于记录博弈参与者选择当前或其他策略的次数；当博弈参与者为静态障碍物时，pr为0。
[0035]
进一步地，还包括，
[0036]
博弈参与者初始优先级pr为0，根据优先级计算公式更改优先级，所述优先级计算公式为：
[0037][0038]
其中，li为博弈参与者ai到目标点的距离，d
pr
为判断优先级的距离，当博弈参与者的优先级为1时，选择第三策略集合。
[0039]
更进一步地，每个所述博弈参与者的信息包括，参与者当前位置(i＝1,2,
…
,a)，运行速度运行方向与x轴的夹角θ，优先级pr。
[0040]
为实现上述目的，本发明还提供一种电子设备，包括存储器和处理器，所述存储器上储存有在所述处理器上运行的程序，所述处理器运行所述程序时执行上述的基于反复博弈的无人飞行器动态障碍规避方法的步骤。
[0041]
为实现上述目的，本发明还提供一种计算机可读存储介质，其上存储有计算机指令，所述计算机指令运行时执行上述的基于反复博弈的无人飞行器动态障碍规避方法的步骤。
[0042]
本发明的基于反复博弈的无人飞行器动态障碍规避方法，具有以下有益效果：
[0043]
采用了反复博弈的方式进行避障策略的选择，每个博弈参与者都根据混合策略来选取自身应采取的行为，使得各个博弈者均能快速收敛到最优策略，安全可靠，能适应多种复杂环境，能够有效地解决无人飞行器系统的协同动态障碍规避问题，进而高效且安全的避开所有障碍物。
[0044]
本发明的其它特征和优点将在随后的说明书中阐述，并且，部分地从说明书中变得显而易见，或者通过实施本发明而了解。
附图说明
[0045]
附图用来提供对本发明的进一步理解，并且构成说明书的一部分，并与本发明的实施例一起，用于解释本发明，并不构成对本发明的限制。在附图中：
[0046]
图1为根据本发明的基于反复博弈的无人飞行器动态障碍规避方法的流程图；
[0047]
图2为根据本发明实施例的基于反复博弈论的无人飞行器避障流程示意图；
[0048]
图3为根据本发明实施例的三个无人飞行器进行第一组避障博弈过程的示意图；
[0049]
图4为根据本发明实施例的三个无人飞行器进行第二组避障博弈过程的示意图。
具体实施方式
[0050]
以下结合附图对本发明的优选实施例进行说明，应当理解，此处所描述的优选实施例仅用于说明和解释本发明，并不用于限定本发明。
[0051]
实施例1
[0052]
博弈论又被称为对策论、游戏论，它起源于象棋、桥牌、赌博等游戏，多用于对经济学、计算机科学进行策略分析。冯
·
诺依曼最早证明了博弈论的原理，并对博弈论的基础和理论体系进行完善。博弈论主要研究在一定环境下，个体根据当前情况按照一定规则选择应对策略，使得博弈双方利益最大化从而达到平衡状态。
[0053]
图1为根据本发明的基于反复博弈的无人飞行器动态障碍规避方法流程图，下面将参考图1，对本发明的基于反复博弈的无人飞行器动态障碍规避方法进行详细描述。
[0054]
在步骤101，将无人飞行器视为博弈的参与者，建立博弈者集合。
[0055]
优选地，假设无人飞行器在运行时遇到h个障碍物obh(h＝1,
…
,h)，无人飞行器当前位置坐标为(xr，yr)，每个障碍物距离无人飞行器最近点的坐标为(xh，yh)。令博弈参与者集合为a，将无人飞行器放入博弈者集合a。
[0056]
优选地，计算无人飞行器与障碍物的距离，当满足公式1时认为障碍物进入无人飞行器的安全范围，需要与无人飞行器进行博弈避障。在进行避障过程中，当工作环境中原始障碍物出现在无人飞行器的安全范围内也被视为博弈参与者。
[0057][0058]
其中，d
safe
为安全距离，当机无人飞行器距障碍物的距离小于等于d
safe
时需要将障碍物obh放入博弈参与者集合a，进行避障机动。
[0059]
优选地，博弈参与者可选的策略集合为s，博弈者的s包含四种策略集合，如公式2所示。
[0060]
s＝{cv，cd,nc，st}
ꢀꢀꢀ
公式2
[0061]
优选地，第一策略集合cv策略代表博弈参与者改变自身的速度，并保持其他状态不变。
[0062]
本实施例中，当无人飞行器选择cv策略时，当前博弈者速度减少υ，即将速度调整为v＝v-υ。参数υ的大小与无人飞行器所处环境有关，υ＝ρ
×
mind。da
i,k
为博弈参与者ai与其他参与者间的距离，计算公式如公式3所示，mind为da
i,k
中的最小值，mind＝min(da
i,k
)。
[0063]
da
i，k
＝||a
i-aj||(j＝1，
…
i-1，i+1、...a k＝1，2，...，a-1)
ꢀꢀꢀ
公式3
[0064]
优选地，第二策略集合cd策略代表博弈参与者的改变自身运行方向，并保持其他状态不变。
[0065]
本实施例中，当无人飞行器选择cd策略时，l
k-i
为障碍物k与博弈者i间的连线，l
k-i
的方向由k指向i；θk为l
k-i
与x轴的夹角；θ
ave
为所有夹角的平均值，如公式4所示；l
ave
为θ
ave
对应的直线；θ
an
是无人飞行器运行方向l
run
与x轴的夹角；θ为l
ave
与l
run
间小于180
°
的夹角。根据公式5计算修正后的角度。
[0066][0067][0068]
优选地，第三策略集合nc策略代表博弈参与者运行速度、运行方向均不发生任何改变，博弈者按照原来的速度和方向继续运行。
[0069]
优选地，第四策略集合st策略代表停止策略，此时博弈者保持当前位置不改变。当障碍物是静态时，默认选择st策略，此时需要无人飞行器自己调整运行状态进行避障。当障碍物是动态时，将动态障碍物看成一个无人飞行器，此时两个无人飞行器需要进行博弈避障。
[0070]
在步骤102，无人飞行器选取博弈策略的优劣通过博弈收益值来衡量，而收益值通过收益函数来计算。
[0071]
优选地，假设共有a个博弈者，其收益计算公式如公式6所示。
[0072][0073]
其中，r为判断策略是否保证无人飞行器安全的系数，当所选取的策略可以保证安全时r＝1，当不能保证安全时r＝0；d
safe
为避障距离即安全距离；aved为ai与其他博弈参与者间距离的平均值；mind为ai与其他博弈参与者之间距离的最小值；ai为博弈参与人(即无人飞行器)i所采取的策略，a-i
为除了参与人i以外的博弈参与人所采取的策略；x(a)为不同策略的消耗值。
[0074]
在步骤103，使所有博弈参与者都可以达到纳什均衡，需要运用反复博弈算法，使得博弈参与者间进行多次博弈，最终得出最优的策略。
[0075]
优选地，设反复博弈的次数为t，当前博弈次数为t，博弈参与者可选策略为n个。初始化博弈参与者ai的混合策略。t＝1且博弈参与者ai的初始概率如公式7：
[0076][0077]
其中，n为博弈者可选的策略个数；分别为博弈参与者在初始时刻选择第1个、第2个、
…
、第n个策略的概率。
[0078]
优选地，将混合策略与每次迭代博弈者的决策结合起来，使博弈参与者ai的概率随着迭代次数的变化而变化，计算公式如下：
[0079][0080]
其中，参数函数i(τi)(i＝1,2,
…
,n)为决策记录函数，主要记录前t-1次迭代中选择当前策略的次数和不选择当前策略的次数，具体计算如公式9所示：
[0081][0082]
其中，pri代表博弈参与者ai的博弈优先级；β为大于0的常数，用于记录博弈参与者选择当前或其他策略的次数，一般可取β＝0.5；当博弈参与者为静态障碍物时，pr一直为0。
[0083]
优选地，博弈参与者初始优先级pr＝0，然后参考公式10对优先级进行更改，d
pr
为判断优先级的距离。当博弈者的优先级为1时，默认选择nc策略。
[0084][0085]
其中，li为博弈参与者ai到目标点的距离。
[0086]
每个博弈参与者的信息包括：参与者当前位置(i＝1,2,
…
,a)，运行速
度运行方向与x轴的夹角θ，优先级pr。无人飞行器自主感测周围环境，感测距离d
safe
同时为无人飞行器的安全范围。
[0087]
本实施例中，机器无人飞行器在运行过程中遇到其他无人飞行器或障碍物时要进行博弈，博弈完成后无人飞行器再寻回原始路径继续运行，具体步骤如下：
[0088]
步骤一：无人飞行器沿路径运行并判断是否到达目标点，如果到达目标点转到步骤八，否则转到步骤二；
[0089]
步骤二：无人飞行器对周围环境进行感测，如果感测到障碍物时进行博弈避障转到步骤三，否则转到步骤一；
[0090]
步骤三：令t＝1，根据公式7初始化p(1)，设置反复博弈次数t，博弈可选策略s(含有n个策略)；
[0091]
步骤四：根据公式1建立博弈参与者集合a，集合中有a个局中人；
[0092]
步骤五：根据公式6计算u，根据p和u选择最大收益对应的策略，记录当前选则策略同时更新i(τ1)；
[0093]
步骤六：令t＝t+1，如果t《t则根据公式8更新p(t)并返回步骤四，如果t≥t则输出最后一次迭代选择的策略；
[0094]
步骤七：完成当前博弈，判断是否避障成功，若成功则无人飞行器向原始路径靠近并转到步骤一，否则转到步骤三。
[0095]
步骤八：无人飞行器安全到达目标点，规划结束。
[0096]
实施例2
[0097]
参考图2的环境为例进行说明，其中起始点用“*”表示，目标点用
“★”
表示。本次实验涉及到三个无人飞行器和一个环境中原有的静态障碍物，信息如下表1所示。
[0098]
表1无人飞行器任务信息此次实验产生了两组博弈避障过程，第一组包括三次避障场景。如图3(c)所示，无人飞行器-1和无人飞行器-2沿预先设计的路径运行，两者相遇产生第一次博弈决策过程，此次博弈有2个局中人参与，具体避障信息如表2所示。无人飞行器-1和无人飞行器-2进行三轮博弈过程，最后避障成功。两个博弈参与者向原始路径回归。
[0099][0100]
表2避障策略信息
[0101][0102]
第二组包括三次避障，避障环境如图3所示。
[0103]
(1)如图3(b)所示无人飞行器-2、无人飞行器-3相遇，此时两者都感测到障碍物，此次博弈有3个局中人无人飞行器-2、无人飞行器-3和障碍-1。障碍-1默认选择静止不动的策略，无人飞行器-2、无人飞行器-3选择改变运动方向的策略，然后无人飞行器-2、无人飞行器-3向原始路径回归；
[0104]
(2)如图3(c)此时又相遇，此次博弈有3个局中人，障碍-1默认选择静止不动的策略，无人飞行器-2选择静止不动，无人飞行器-3选择改变运动方向的策略，无人飞行器-3向原始路径回归；
[0105]
(3)无人飞行器-2因为上次博弈选择静止所以与障碍-1开始第三次博弈，此次博弈有2个局中人障碍-1默认选择静止不动的策略，无人飞行器-2选择改变运动方向的策略，无人飞行器-2成功避开障碍且向目标点运行，本组博弈完成。
[0106]
表3避障策略信息
[0107][0108]
通过上述仿真结果可以看出，在任意环境下，基于反复博弈论的动态避障算法使无人飞行器快速有效的避开其他博弈参与者。所以该避障算法可以有效解决无人飞行器系统的碰撞问题，保证无人飞行器安全运行到目标点。
[0109]
本发明提出了一种基于反复博弈的无人飞行器动态障碍规避方法。当无人飞行器作为博弈参与者面对动态障碍物进行博弈策略选择时，博弈参与者之间可能存在多个均衡状态。本发明针对无人飞行器的实时动态避障问题，提出了基于反复博弈的无人飞行器动态障碍规避方法。其目的在于提供一种有效的多无人飞行器协同避障方法，首先建立了无人飞行器动态避障策略库，然后根据博弈参与者之间的状态计算博弈收益。为了使博弈参与者在反复博弈过程中快速收敛到最优策略，根据博弈参与者的决策更新混合策略，根据混合策略与博弈收益进行决策，使得博弈者的收益达到纳什均衡并选择对应的避障策略。该方法能够使无人飞行器在面临各种障碍时均能快速且安全地避开障碍。
[0110]
本发明还提供一种电子设备，包括存储器和处理器，所述存储器上储存有在所述处理器上运行的程序，所述处理器运行所述程序时执行上述的基于反复博弈的无人飞行器动态障碍规避方法的步骤。
[0111]
本发明还提供了一种计算机可读存储介质，其上存储有计算机指令，所述计算机指令运行时执行上述的基于反复博弈的无人飞行器动态障碍规避方法的步骤，所述基于反复博弈的无人飞行器动态障碍规避方法参见前述部分的介绍，不再赘述。
[0112]
本领域普通技术人员可以理解：以上所述仅为本发明的优选实施例而已，并不用于限制本发明，尽管参照前述实施例对本发明进行了详细的说明，对于本领域的技术人员来说，其依然可以对前述各实施例记载的技术方案进行修改，或者对其中部分技术特征进行等同替换。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

技术特征：
1.基于反复博弈的无人飞行器动态障碍规避方法，包括以下步骤：将无人飞行器作为博弈的参与者，建立博弈参与者集合；根据所述博弈参与者之间的状态计算博弈收益值，通过计算博弈收益值衡量无人飞行器选取博弈策略的优劣；使博弈参与者在反复博弈过程中快速收敛到最优策略，根据博弈参与者的决策更新混合策略，根据混合策略与博弈收益进行决策，使得博弈参与者的收益达到纳什均衡并选择对应的避障策略。2.根据权利要求1所述的基于反复博弈的无人飞行器动态障碍规避方法，其特征在于，所述将无人飞行器作为博弈的参与者，建立博弈参与者集合的步骤，还包括，假设无人飞行器运行时遇到h个障碍物ob
h
(h＝1,
…
,h)，无人飞行器当前位置坐标为(x
r
，y
r
)，每个障碍物距离无人飞行器最近点的坐标为(x
h
，y
h
)，博弈参与者集合为a，将无人飞行器放入博弈参与者集合a；计算无人飞行器与障碍物的距离，当满足公式1时则障碍物进入无人飞行器的安全范围，与无人飞行器进行博弈避障；其中，d
safe
为安全距离，当无人飞行器距障碍物的距离小于等于d
safe
时将障碍物ob
h
放入博弈参与者集合a，进行避障机动；在进行避障时，将工作环境中出现在无人飞行器的安全范围内的原始障碍物视为博弈参与者。3.根据权利要求2所述的基于反复博弈的无人飞行器动态障碍规避方法，其特征在于，还包括，博弈参与者选择的策略集合包含四种策略集合；第一策略集合为博弈参与者改变自身的速度，并保持其他状态不变；第二策略集合为博弈参与者改变自身的运行方向，并保持其他状态不变；第三策略集合为博弈参与者运行速度、运行方向均保持不变；第四策略集合为停止策略，所述博弈参与者保持当前位置不变。4.根据权利要求1所述的基于反复博弈的无人飞行器动态障碍规避方法，其特征在于，所述根据所述博弈参与者之间的状态计算博弈收益值，通过计算博弈收益值衡量无人飞行器选取博弈策略的优劣的步骤，还包括，假设共有a个博弈参与者，其收益计算公式为：其中，r为判断策略是否保证无人飞行器安全的系数，当所选取的策略可以保证安全时r＝1，当不能保证安全时r＝0；d
safe
为无人飞行器的安全距离范围；aved为a
i
与其他博弈参与者之间距离的平均值；mind为a
i
与其他博弈参与者之间距离的最小值；a
i
为博弈参与者i所采取的策略；a-i
为除了博弈参与者i以外的博弈参与者所采取的策略；x(a
i
)为不同策略的消耗值。
5.根据权利要求1所述的基于反复博弈的无人飞行器动态障碍规避方法，其特征在于，所述使博弈参与者在博弈过程中快速收敛到最优策略，根据博弈参与者的决策更新混合策略，根据混合策略与博弈收益进行决策，使得博弈参与者的收益达到纳什均衡并选择对应的避障策略的步骤，还包括，设反复博弈的次数为t，当前博弈次数为t，博弈参与者可选策略为n个，初始化博弈参与者a
i
的混合策略，t＝1且博弈参与者a
i
的初始概率为：其中，n为博弈参与者可选的策略个数；分别为博弈参与者在初始时刻选择第1个、第2个、
…
、第n个策略的概率。6.根据权利要求5所述的基于反复博弈的无人飞行器动态障碍规避方法，其特征在于，还包括，将混合策略与每次迭代博弈参与者的决策进行结合，使博弈参与者a
i
的概率随着迭代次数的变化而变化，计算公式为：其中，参数函数i(τ
i
)(i＝1,2,
…
,n)为决策记录函数，包括记录前t-1次迭代中选择当前策略的次数和不选择当前策略的次数，计算公式为：其中，pr
i
为博弈参与者a
i
的博弈优先级；β为大于0的常数，用于记录博弈参与者选择当前或其他策略的次数；当博弈参与者为静态障碍物时，pr为0。7.根据权利要求6所述的基于反复博弈的无人飞行器动态障碍规避方法，其特征在于，还包括，博弈参与者初始优先级pr为0，根据优先级计算公式更改优先级，所述优先级计算公式
为：其中，l
i
为博弈参与者a
i
到目标点的距离，d
pr
为判断优先级的距离，当博弈参与者的优先级为1时，选择第三策略集合。8.根据权利要求1-7所述的基于反复博弈的无人飞行器动态障碍规避方法，其特征在于，每个所述博弈参与者的信息包括，参与者当前位置运行速度运行方向与x轴的夹角θ，优先级pr。9.一种电子设备，其特征在于，包括存储器和处理器，所述存储器上储存有在所述处理器上运行的程序，所述处理器运行所述程序时执行权利要求1-8任一项所述的基于反复博弈的无人飞行器动态障碍规避方法的步骤。10.一种计算机可读存储介质，其上存储有计算机指令，其特征在于，所述计算机指令运行时执行权利要求1-8任一项所述的基于反复博弈的无人飞行器动态障碍规避方法的步骤。

技术总结
本发明提供一种基于反复博弈的无人飞行器动态障碍规避方法，包括以下步骤：通过将无人飞行器作为博弈的参与者，建立博弈参与者集合；根据所述博弈参与者之间的状态计算博弈收益值，通过计算博弈收益值衡量无人飞行器选取博弈策略的优劣；使博弈参与者在反复博弈过程中快速收敛到最优策略，根据博弈参与者的决策更新混合策略，根据混合策略与博弈收益进行决策，使得博弈参与者的收益达到纳什均衡并选择对应的避障策略。本发明基于反复博弈的无人飞行器动态障碍规避方法，使得无人飞行器系统在面对移动障碍、移动目标时能够实时进行避障机动，较快地为无人飞行器计算出性能较优的运动路径，保障无人飞行器安全运行到各自的目标点。点。点。


技术研发人员：武应华 赵国宏 焦巍 谢天宇
受保护的技术使用者：中国人民解放军96901部队
技术研发日：2023.01.30
技术公布日：2023/7/26