CN108594858B - Unmanned aerial vehicle searching method and device for Markov moving target - Google Patents

Abstract

The invention discloses a UAV search method and device for a Markov moving target. After receiving a search task, all possible states and their probability distributions during the movement process of the Markov moving target and the UAV search process are obtained. ; Build a Markov model for UAV behavior prediction under search tasks, and establish a multi-stage heuristic strategy iteration algorithm based on Markov decision-making; obtain the most profitable search behavior strategy, and plan the optimal UAV search track . The invention overcomes the shortcoming of high search cost caused by the lack of strict mathematical definition of the motion law of the search target in the traditional search algorithm. The virtual target position to be searched in the next moment, and the search behavior strategy with the most profit can be obtained, which can be applied to search for moving targets, and the target can be successfully searched with a lower search cost.

Description

UAV search method and device for Markov moving target

technical field

The invention relates to the control field of unmanned aerial vehicles, in particular to a method and a device for searching for unmanned aerial vehicles of Markov moving targets.

Background technique

Today, the power of technology permeates all walks of life. As a new scientific and technological force, the application prospects of UAVs in all walks of life have attracted much attention. Among them, the search and rescue application of UAVs in military target search systems has been paid attention to by countries all over the world. Track planning is an important issue that must be considered in the application of UAV to target search system.

The track planning of the UAV target search system includes two categories, namely the track planning of the stationary target search system and the track planning of the moving target search system. At present, the research results of the trajectory planning of the UAV stationary target search system are relatively mature and have been widely used in practical problems. However, there are relatively few researches on the trajectory planning of the moving target search system. At present, the research direction of the trajectory planning problem of the moving target search system mainly focuses on the design and application of the search algorithm itself, but there is no strict mathematical definition for the problem of the movement law of the target in the search process. On the other hand, the ability of UAV to perform tasks independently is weak, and its intelligence is not enough to meet people's expectations in many cases. In the process of task execution, UAVs generally follow the pre-loaded procedures, and the adaptability is poor. Therefore, multi-UAV cooperative participation in tasks is a relatively reliable choice. This also makes the application of drones in search more and more closely aligned with practical applications.

Markov Decision Processes (MDP) is a Markov reward process with decision-making ability. In functional applications, it is theoretical knowledge used to solve sequential decision-making problems in uncertain environments. The sequential decision-making problem in uncertain environment refers to making decisions at a series of continuous or discrete moments (called decision moments). When people make decisions, they should not only consider the current effect of the decision, but also take into account the impact of the decision on the long-term interests. MDP is a very widely used decision-making process.

Traditional UAV search algorithms, such as scan line search algorithms, only focus on the design of the algorithm itself and lack strict mathematical definition of the motion law of the search target, which has the disadvantage of high search cost.

SUMMARY OF THE INVENTION

In order to overcome the deficiencies of the prior art, the purpose of the present invention is to provide a UAV search method and device for Markov moving targets, aiming to solve the problem that the existing traditional algorithms cannot satisfy the moving target search navigation when applied to the UAV search task. trace planning requirements or search for costly problems.

Purpose of the present invention adopts following technical scheme to realize:

A UAV search method for Markov moving targets, comprising:

In the target step, after receiving the search task, construct the probability model of the Markov moving target, so as to obtain all possible states and their probability distributions during the movement of the Markov moving target;

UAV step to obtain all possible states and their probability distributions during the UAV search process;

The construction step is to construct a Markov model for UAV behavior prediction under the search task according to all possible states and their probability distributions during the UAV search process and the Markov moving target movement process, and establish Markov-based decision-making. The multi-stage heuristic strategy iteration algorithm of ;

In the planning step, the multi-stage heuristic strategy iteration algorithm based on Markov decision is used to obtain the most profitable search behavior strategy, so as to plan the optimal search path of the UAV.

On the basis of the above embodiment, preferably, the target step is specifically:

After receiving the search task, the moving area of the target is divided into grids, the Markov moving target is modeled by probability theory, and the probability model of the Markov moving target is obtained, so as to obtain all the marks during the movement of the Markov moving target. The possible states and their probability distributions; the movement area of the target is equivalent to the search area of the UAV.

On the basis of any of the above-mentioned embodiments, preferably, the unmanned aerial vehicle step is specifically:

The flight behavior of the UAV is encoded and described, and the state of the UAV in the process of performing the search task is described, so as to obtain all possible states and their probability distributions during the UAV search process.

On the basis of any of the above-mentioned embodiments, preferably, the construction of a Markov model for predicting the behavior of the UAV under the search task is specifically:

Set the time set T={1,2,3,…} when the UAV search task is in progress;

Set the discrete state space S=(s ₁ , s ₂ , s ₃ ,...) of the UAV, which contains all possible states during the UAV search process and the Markov moving target movement process;

Let the action space A of the UAV = {a ₁ ,a ₂ ,...,a _x ,...,a _q }, which represents all possible actions of the UAV to change the state, where the element a _x represents the xth actions, q is the number of elements in the action space;

Suppose the feasible action set A(s _n ) of the UAV in the state _sn = {a ₁ (s _n ), a ₂ (s _n ), a ₃ (s _n ),...}, representing the UAV A collection of all actions that can be taken in a state;

Let T(s _n , a _x (s _n ), s _m ) represent the set of all state transition probabilities of the UAV, and any element p(s _m |s _n , a _x (s _n )) in the state s _n Next, the probability that the state changes to s _m after performing the available action a _x (s _n ),

Let any element r(s _n , a _x (s _n )) of the reward set R(s _n ) represent the reward for performing the action a _x (s _n ) in the state _sn ;

Then the Markov model for predicting the search behavior of the UAV under any search task is:

MDP={S,A,T(s _n ,a _x (s _n ),s _m ),R(s _n )}→π(s _n );

Among them, π is the strategy, which represents the mapping from the state set to the action set, π(s _n ) represents the mapping of the UAV from the state s _n to the action set, and → represents the output optimal strategy.

On the basis of the above embodiment, preferably, the planning step includes:

表示在从时刻t＝0开始无人机从状态s_n使用策略π后的折扣期望总报酬；Calculation steps: use the MDP discount model to calculate the reward utility function, where the discount factor γ satisfies: 0<γ<1; the reward function of the discount model

represents the discounted expected total reward after the UAV uses policy π from state sn from time _t =0;

以及最优动作值函数方程

并根据两个最优函数方程建立最优搜索策略函数方程

According to the optimal equation of the MDP discount model, the optimal state value function equation of the UAV's search operation revenue in the search task under the state _sn is established

and the optimal action value function equation

And establish the optimal search strategy function equation according to the two optimal function equations

Given step: divide the collaborative search area into grids, determine the discrete state space S of the MDP model, and give the number of UAVs participating in the search task g, where g and i are positive integers, and s _UAV(i) is the i-th UAV(i) is the current state of a UAV, s _UAV(i) ∈ S, A(s _UAV(i) ) is the action set of the i-th UAV in the state s _UAV(i) , and K _i is the i-th UAV The maximum search step size of the machine; given the discount factor γ and the end condition ε of the strategy iteration, let the number of iterations b = 0;

Initial step: determine the initial position of the target movement and the position where each drone starts to search; each drone obtains the target existence probability distribution in the entire area according to the initial position of the target movement and the target movement heuristic information, so as to determine The virtual target position that each drone will search for at the next moment;

Iterative step: each UAV calculates its own state value function V ^b+1 (s _UAV(i) ) iteratively according to its own virtual target position and its current state s _UAV(i) , let the number of iterations b =b+1;

Judgment step: if ||V ^b+1 (s _UAV(i) )-V ^b (s _UAV(i) )||<ε, end the iteration and enter the traversal step; otherwise, go to the iteration step;

Traversal step: each UAV traverses A(s _UAV(i) ) according to the final state value function V ^b+1 (s _UAV( i) ) to obtain Q(s _UAV(i) , a _i ), and finally finds get the most profitable search behavior strategy π _i (t+1) ^* ;

转移到

同时，无人机获得立即报酬r_i(s_UAV(i),a_i)，此时令t＝t+1，令第i架无人机搜索步长k_i＝k_i+1；Transition step: according to the required optimal strategy π _i (t+1) ^* execute action a _i , the state is given by

move to

At the same time, the UAV obtains an immediate reward ri (s _{UAV(i) ,} a _i ), at this time, let t=t+1, and let the i-th UAV search step _ki = _ki +1;

i＝1,2,...,n，则搜索任务失败，算法结束；所述目标当前模拟位置为根据马尔科夫运动目标运动过程中所有可能出现的状态及其概率分布获取的目标当前最可能出现的位置。Ending step: If at a certain time t, the position s _UAV(i) of the i-th UAV is the same as the current simulated position s _target of the target, then the i-th UAV successfully searches for the target, the search task is completed, and the algorithm ends; If the search step

i=1,2,...,n, then the search task fails and the algorithm ends; the current simulated position of the target is the current maximum position of the target obtained according to all possible states and their probability distributions during the movement of the Markov moving target. possible location.

A UAV search device for Markov moving targets, comprising:

The target module is used to construct the probability model of the Markov moving target after receiving the search task, so as to obtain all possible states and their probability distributions during the movement of the Markov moving target;

The UAV module is used to obtain all possible states and their probability distributions during the UAV search process;

The building block is used to construct a Markov model for UAV behavior prediction under the search task according to all possible states and their probability distributions during the UAV search process and the Markov moving target movement process. multi-stage heuristic policy iteration algorithm for decision-making;

The planning module is used to use the multi-stage heuristic strategy iteration algorithm based on Markov decision to obtain the most profitable search behavior strategy, so as to plan the optimal search path of the UAV.

On the basis of the above embodiment, preferably, the target module is used for:

After receiving the search task, the moving area of the target is divided into grids, the Markov moving target is modeled by probability theory, and the probability model of the Markov moving target is obtained, so as to obtain all the marks during the movement of the Markov moving target. The possible states and their probability distributions; the movement area of the target is equivalent to the search area of the UAV.

On the basis of any of the above embodiments, preferably, the UAV module is used for:

The flight behavior of the UAV is encoded and described, and the state of the UAV in the process of performing the search task is described, so as to obtain all possible states and their probability distributions during the UAV search process.

On the basis of any of the above-mentioned embodiments, preferably, the construction of a Markov model for predicting the behavior of the UAV under the search task is specifically:

Set the time set T={1,2,3,…} when the UAV search task is in progress;

Set the discrete state space S=(s ₁ , s ₂ , s ₃ ,...) of the UAV, which contains all possible states during the UAV search process and the Markov moving target movement process;

Let the action space A of the UAV = {a ₁ ,a ₂ ,...,a _x ,...,a _q }, which represents all possible actions of the UAV to change the state, where the element a _x represents the xth actions, q is the number of elements in the action space;

Suppose the feasible action set A(s _n ) of the UAV in the state _sn = {a ₁ (s _n ), a ₂ (s _n ), a ₃ (s _n ),...}, representing the UAV A collection of all actions that can be taken in a state;

Let T(s _n , a _x (s _n ), s _m ) represent the set of all state transition probabilities of the UAV, and any element p(s _m |s _n , a _x (s _n )) in the state s _n below, the probability that the state changes to s _m after performing the available actions a _x (s _n ), where i,j=1,2,3,...,

Let any element r(s _n , a _x (s _n )) of the reward set R(s _n ) represent the reward for performing the action a _x (s _n ) in the state _sn ;

Then the Markov model for predicting the search behavior of the UAV under any search task is:

MDP={S,A,T(s _n ,a _x (s _n ),s _m ),R(s _n )}→π(s _n );

Among them, π is the strategy, which represents the mapping from the state set to the action set, π(s _n ) represents the mapping of the UAV from the state s _n to the action set, and → represents the output optimal strategy.

On the basis of the above embodiment, preferably, the planning module includes:

表示在从时刻t＝0开始无人机从状态s_n使用策略π后的折扣期望总报酬；The calculation unit is used to: calculate the reward utility function with the MDP discount model, where the discount factor γ satisfies: 0<γ<1; the reward function of the discount model

represents the discounted expected total reward after the UAV uses policy π from state sn from time _t =0;

以及最优动作值函数方程

并根据两个最优函数方程建立最优搜索策略函数方程

According to the optimal equation of the MDP discount model, the optimal state value function equation of the UAV's search operation revenue in the search task under the state _sn is established

and the optimal action value function equation

And establish the optimal search strategy function equation according to the two optimal function equations

The given unit is used to: rasterize the collaborative search area, determine the discrete state space S of the MDP model, given the number of UAVs participating in the search task g, s _UAV(i) is the i-th UAV The current state, s _UAV(i) ∈ S, A(s _UAV(i) ) is the action set of the i-th UAV in the state s _UAV(i) , and K _i is the maximum search of the i-th UAV Step size; given the discount factor γ and the end condition ε of the strategy iteration, let the number of iterations b = 0;

The initial unit is used to: determine the initial position of the target movement and the position where each drone starts to search; each drone obtains the existence probability distribution of the target in the entire area according to the initial position of the target movement and the target movement heuristic information , so as to determine the virtual target position that each UAV will search for at the next moment;

The iterative unit is used for: each UAV based on its own virtual target position and its current state s _UAV(i) , iteratively calculates its own state value function V ^b+1 (s _UAV(i) ), let The number of iterations b=b+1;

The judgment unit is used for: if ||V ^b+1 (s _UAV(i) )-V ^b (s _UAV(i) )||<ε, end the iteration and call the traversal unit, otherwise, call the iteration unit;

Traversal unit for: each UAV traverses A(s _UAV(i) ) according to the final state value function V ^b+1 (s _UAV( i) ) to obtain Q(s _UAV(i) , a _i ) , and finally obtain the search behavior strategy with the largest profit π _i (t+1) ^* ;

转移到

同时，无人机获得立即报酬r_i(s_UAV(i),a_i)，此时令t＝t+1，令第i架无人机搜索步长k_i＝k_i+1；The transition unit is used to: execute the action a _i according to the required optimal strategy π _i (t+1) ^* , the state is given by

move to

At the same time, the UAV obtains an immediate reward ri (s _{UAV(i) ,} a _i ), at this time, let t=t+1, and let the i-th UAV search step _ki = _ki +1;

i＝1,2,...,n，则搜索任务失败，算法结束；所述目标当前模拟位置为根据马尔科夫运动目标运动过程中所有可能出现的状态及其概率分布获取的目标当前最可能出现的位置。The end unit is used for: if at a certain time t, the position s _UAV(i) of the i-th UAV is the same as the current simulated position S _target of the target, then the i-th UAV successfully searches for the target, and the search task is completed, The algorithm ends; if the search step is

i=1,2,...,n, then the search task fails and the algorithm ends; the current simulated position of the target is the current maximum position of the target obtained according to all possible states and their probability distributions during the movement of the Markov moving target. possible location.

Compared with the prior art, the beneficial effects of the present invention are:

The invention discloses a UAV search method and device for a Markov moving target. After a search task is received, a probability model of the Markov moving target is constructed to obtain all possible states and states during the movement of the Markov moving target. Its probability distribution; obtain all possible states and their probability distributions in the UAV search process; build a Markov model for UAV behavior prediction under search tasks, and establish a multi-stage heuristic strategy iteration algorithm based on Markov decision ; Use the multi-stage heuristic strategy iteration algorithm based on Markov decision to obtain the most profitable search behavior strategy, so as to plan the optimal search path of the UAV.

The present invention can use the MDP discount model to determine the probability set of the existence state transition of the UAV under the search task and the reward set of the flight behavior operation in the transfer process, calculate the reward utility function, establish the optimal equation of the UAV behavior benefit under the search task, and carry out Iterative calculation and judgment are used to obtain the most profitable search behavior strategy, and the optimal search path of the UAV is planned.

The invention overcomes the major shortcomings of traditional search algorithms, such as scan line search algorithms, which only focus on the design of the algorithm itself and lack strict mathematical definition of the motion law of the search target, which leads to high search costs. The existence probability distribution of the Kov moving target in the search area determines the position of the virtual target that the UAV will search for at the next moment, and obtains a set of UAV’s search behavior operation sequence. This sequence is the search behavior strategy with the greatest behavioral benefit. , which can be applied to search for moving targets, and can successfully search for targets with low search cost.

Description of drawings

The present invention will be further described below with reference to the accompanying drawings and embodiments.

FIG. 1 shows a schematic diagram of grid division of a search area provided by an embodiment of the present invention;

Figures 2a-2d respectively show the existence probability distribution diagrams of the Markov moving objects provided by the embodiments of the present invention at different times;

3 shows a schematic diagram of a theoretical framework structure of an MDP-MSHPI algorithm provided by an embodiment of the present invention;

4 shows a flowchart of a single UAV searching for a Markov target using the MSHPI algorithm according to an embodiment of the present invention;

FIG. 5 shows a flowchart of a plurality of unmanned aerial vehicles searching for Markov targets by using the MSHPI algorithm according to an embodiment of the present invention;

FIG. 6 shows a schematic structural diagram of a UAV search device for a Markov moving target provided by an embodiment of the present invention.

Detailed ways

The present invention will be further described below with reference to the accompanying drawings and specific embodiments. It should be noted that, on the premise of no conflict, the embodiments or technical features described below can be combined arbitrarily to form new embodiments. .

Specific embodiment one

An embodiment of the present invention provides a method for searching an unmanned aerial vehicle for a Markov moving target, including:

In the target step, after receiving the search task, construct the probability model of the Markov moving target, so as to obtain all possible states and their probability distributions during the movement of the Markov moving target;

UAV step to obtain all possible states and their probability distributions during the UAV search process;

The construction step is to construct a Markov model for UAV behavior prediction under the search task according to all possible states and their probability distributions during the UAV search process and the Markov moving target movement process, and establish Markov-based decision-making. The Multi-Stage Heuristic Strategy Iteration Algorithm (MDP-MSHPI);

In the planning step, the multi-stage heuristic strategy iteration algorithm based on Markov decision is used to obtain the most profitable search behavior strategy, so as to plan the optimal search path of the UAV. In this embodiment of the present invention, the number of drones may be one, two or more.

The invention overcomes the major shortcomings of traditional search algorithms, such as scan line search algorithms, which only focus on the design of the algorithm itself and lack strict mathematical definition of the motion law of the search target, which leads to high search costs. The existence probability distribution of the Kov moving target in the search area determines the position of the virtual target that the UAV will search for at the next moment, and obtains a set of UAV’s search behavior operation sequence. This sequence is the search behavior strategy with the greatest behavioral benefit. , which can be applied to search for moving targets, and can successfully search for targets with low search cost.

As shown in FIG. 1 and FIG. 2 , preferably, the target step may be specifically: after receiving the search task, divide the moving area of the target into a grid, and use probability theory to model the Markov moving target, Obtain the probability model of the Markov moving target, so as to obtain all possible states and their probability distributions during the movement of the Markov moving target; the moving area of the target is equivalent to the search area of the UAV. The advantage of this is that it can simulate the motion law of the moving target, and obtain all possible states and their probability distributions during the movement of the Markov moving target. For example, the most likely position of the moving target at a certain moment can be obtained. .

Preferably, the unmanned aerial vehicle step may be specifically: coding and describing the flying behavior of the unmanned aerial vehicle, and describing the state of the unmanned aerial vehicle in the process of executing the search task, so as to obtain the information of the unmanned aerial vehicle in the search process. All possible states and their probability distributions. The advantage of this is that the possible states of the drone during the search process and their probability distribution can be obtained.

Preferably, the step of constructing the Markov model for predicting the behavior of the UAV under the search task may be specifically:

Set the time set T={1,2,3,…} when the UAV search task is in progress;

Set the discrete state space S=(s ₁ , s ₂ , s ₃ ,...) of the UAV, which contains all possible states during the UAV search process and the Markov moving target movement process;

Let the action space A of the UAV = {a ₁ ,a ₂ ,...,a _x ,...,a _q }, which represents all possible actions of the UAV to change the state, where the element a _x represents the xth actions, q is the number of elements in the action space;

Suppose the feasible action set A(s _n ) of the UAV in the state _sn = {a ₁ (s _n ), a ₂ (s _n ), a ₃ (s _n ),...}, representing the UAV A collection of all actions that can be taken in a state;

Let T(s _n , a _x (s _n ), s _m ) represent the set of all state transition probabilities of the UAV, and any element p(s _m |s _n , a _x (s _n )) in the state s _n Next, the probability that the state changes to s _m after performing the available action a _x (s _n ),

Let any element r(s _n , a _x (s _n )) of the reward set R(s _n ) represent the reward for performing the action a _x (s _n ) in the state _sn ;

Then the Markov model for predicting the search behavior of the UAV under any search task is:

MDP={S,A,T(s _n ,a _x (s _n ),s _m ),R(s _n )}→π(s _n );

Among them, π is the strategy, which represents the mapping from the state set to the action set, π(s _n ) represents the mapping of the UAV from the state s _n to the action set, and → represents the output optimal strategy.

Preferably, the planning step may include:

表示在从时刻t＝0开始无人机从状态s_n使用策略π后的折扣期望总报酬；Calculation steps: use the MDP discount model to calculate the reward utility function, where the discount factor γ satisfies: 0<γ<1; the reward function of the discount model

represents the discounted expected total reward after the UAV uses policy π from state sn from time _t =0;

以及最优动作值函数方程

并根据两个最优函数方程建立最优搜索策略函数方程

According to the optimal equation of the MDP discount model, the optimal state value function equation of the UAV's search operation revenue in the search task under the state _sn is established

and the optimal action value function equation

And establish the optimal search strategy function equation according to the two optimal function equations

Given step: divide the collaborative search area into grids, determine the discrete state space S of the MDP model, and give the number of UAVs participating in the search task g, where g and i are positive integers, and s _UAV(i) is the i-th UAV(i) is the current state of a UAV, s _UAV(i) ∈ S, A(s _UAV(i) ) is the action set of the i-th UAV in the state s _UAV(i) , and K _i is the i-th UAV The maximum search step size of the machine; given the discount factor γ and the end condition ε of the strategy iteration, let the number of iterations b = 0;

Initial step: determine the initial position of the target movement and the position where each drone starts to search; each drone obtains the target existence probability distribution in the entire area according to the initial position of the target movement and the target movement heuristic information, so as to determine The virtual target position that each drone will search for at the next moment;

Iterative step: each UAV calculates its own state value function V ^b+1 (s _UAV(i) ) iteratively according to its own virtual target position and its current state s _UAV(i) , let the number of iterations b =b+1;

Judgment step: if ||V ^b+1 (s _UAV(i) )-V ^b (s _UAV(i) )||<ε, end the iteration and enter the traversal step; otherwise, go to the iteration step;

Traversal step: each UAV traverses A(s _UAV(i) ) according to the final state value function V ^b+1 (s _UAV( i) ) to obtain Q(s _UAV(i) , a _i ), and finally finds get the most profitable search behavior strategy π _i (t+1) ^* ;

转移到

同时，无人机获得立即报酬r_i(s_UAV(i),a_i)，此时令t＝t+1，令第i架无人机搜索步长k_i＝k_i+1；Transition step: according to the required optimal strategy π _i (t+1) ^* execute action a _i , the state is given by

move to

At the same time, the UAV obtains an immediate reward ri (s _{UAV(i) ,} a _i ), at this time, let t=t+1, and let the i-th UAV search step _ki = _ki +1;

i＝1,2,...,n，则搜索任务失败，算法结束；所述目标当前模拟位置为根据马尔科夫运动目标运动过程中所有可能出现的状态及其概率分布获取的目标当前最可能出现(所处)的位置。Ending step: If at a certain time t, the position s _UAV(i) of the i-th UAV is the same as the current simulated position s _target of the target, then the i-th UAV successfully searches for the target, the search task is completed, and the algorithm ends; If the search step

i=1,2,...,n, then the search task fails and the algorithm ends; the current simulated position of the target is the current maximum position of the target obtained according to all possible states and their probability distributions during the movement of the Markov moving target. where it might appear.

The advantage of this is that the MDP discount model can be used to determine the probability set of UAV existence state transition under the search task and the reward set of the flight behavior operation during the transfer process, calculate the reward utility function, and establish the maximum value of the UAV behavior benefit under the search task. The optimal equation is used to perform iterative calculation and judgment to obtain the most profitable search behavior strategy, and to plan the optimal search path of the UAV.

An application scenario of the present invention may be:

1. Perform grid division on the moving area of the target (also the search area of the UAV), and the divided area model is shown in Figure 1; use the knowledge of probability theory to model the Markov moving target, and obtain the Markov moving target. The probability model of the Markov moving target, the existence probability of the Markov moving target in the moving area after moving a certain number of steps is shown in Figure 2a ~ 2d, in which Figure 2a is the initial moment, Figure 2b is after one step of movement, Figure 2c is After 5 steps of exercise, Figure 2d shows after 10 steps of exercise;

The theoretical framework of the MDP-MSHPI algorithm is shown in Figure 3;

2. Code and describe the flight behavior of the UAV, and describe the state of the UAV in the process of performing the search task;

3. Build a Markov model for UAV behavior prediction under search tasks. In this step, the following contents need to be defined in advance:

Definition 1: Let T={1,2,3,…} represent the time set;

Definition 2: Set S=(s ₁ , s ₂ , s ₃ ,...), the state space contains all possible states during the UAV search process and the Markov moving target movement process;

Definition 3: Let A(s _n )={a ₁ (s _n ), a ₂ (s _n ), a ₃ (s _n ),...}, it means that the UAV is in the state _sn that can be taken A collection of all actions;

Definition 4: Let T(s _n , a _x (s _n ), s _m ) represent the set of all state transition probabilities of the UAV, and its element p(s _m |s _n , a _x (s _n )) represents the state s Under _n , the probability of the UAV state changing to s _m after performing the available actions a _x (s _n ), and assuming

Definition 5: Let R(s _n ) represent the reward set, where any element r(s _n , a _x (s _n )) represents the reward for performing the action a _x (s _n ) in the state _sn ;

Definition 6: Let A={a ₁ ,a ₂ ,...,a _q }, A represents the action space of the UAV, including all possible actions of the UAV to change the state of the UAV, among which the element a _x Represents the xth action, q is the number of elements in the action space x=1,2,3,...q;

The Markov model that predicts the search behavior of the UAV to perform any search task is as follows:

MDP={S,A,T(s _n ,a _x (s _n ),s _m ),R(s _n )}→π(s _n );

Among them, π is the strategy, which represents the mapping from the state set to the action set, and π(s _n ) represents the mapping of the UAV from the state s _n to the action set;

4. Determine the state transition probability set T(s _n , a _x (s _n ), s _m ) of the UAV under the search task, and determine the reward set R(s _n ) in the state transition process according to the search task requirements;

According to the current state s _n of the UAV, establish the optimal state value function equation of the search operation revenue under the UAV search task;

该函数表示系统在t＝0时刻从s_n状态下，使用策略π后无人机的折扣期望总报酬，其中效用函数为有界函数；The present invention uses the MDP discount model when calculating the reward utility function, that is, after a strategy is determined and executed, the decision maker will obtain a certain reward at time T according to a certain probability, and the cumulative reward is the utility function of the system, where the The discount factor in the discount model is represented by γ, and 0<γ<1, the utility function of the MDP discount model is expressed as

This function represents the discounted expected total reward of the UAV after using the strategy π from the state of sn at _t =0, where the utility function is a bounded function;

以及最优动作值函数方程

并根据两个最优函数模型建立最优搜索策略函数方程

According to the optimal equation of the MDP discount model, the optimal state value function equation of the search operation revenue in the process of the UAV performing the search task in the state _sn is established.

and the optimal action value function equation

And establish the optimal search strategy function equation according to the two optimal function models

5. Initialization parameters; given the number of UAVs participating in the search task g, s _UAV(i) is the current state of the ith UAV, s _UAV(i) ∈ S, and A(s _UAV(i) ) is the current state of the ith UAV. The action set of i UAV in state s _UAV(i) ; K _i is the maximum search step size of the i-th UAV; given the discount factor γ and the end condition ε of the strategy iteration, let the number of iterations b = 0; where i is a positive integer;

6. Determine the initial position of the target movement and the position where each drone starts to search; each drone obtains the target's existence probability distribution in the entire area according to the initial position of the target's movement and the target movement heuristic information; The virtual target position that the drone will search for at the next moment;

7. According to its own virtual target position and its current state s _UAV(i) , each UAV obtains V ^b+1 (s _UAV(i) ) by calculating the optimal state value function equation of the search operation revenue The number of iterations b=b+1;

8. If ||V ^b+1 (s _UAV(i) )-V ^b (s _UAV(i) )||<ε, end the iteration and go to the next step, otherwise, go to step 7;

9. Each UAV traverses A(s _UAV(i) ) according to the final state value function V ^b+1 (s _UAV( i) ) to obtain Q(s _UAV(i) , a _i ), and finally obtains The most profitable behavior strategy π _i (t+1) ^* ; each UAV can find the optimal search behavior strategy at the next moment according to the above steps, as shown in Figure 4;

转移到

于此同时，无人机获得立即报酬r_i(s_UAV(i),a_i),t＝t+1，第i架无人机搜索步长k_i＝k_i+1；10. According to the required optimal strategy π _i (t+1) ^* execute action a _i , the state is given by

move to

At the same time, the UAV obtains an immediate reward ri (s _{UAV(i) ,} a _i ), t=t+1, and the i-th UAV searches for a step size _ki = _ki +1;

i＝1,2,...,n，则搜索失败，算法结束；多架无人机协同搜索Markov运动目标的程序框图如图5所示。11. If at a certain time t, the position s _UAV(i) of the i-th UAV is the same as the real position of the target s _target , then the i-th UAV successfully searches for the target, the search task is completed, and the algorithm ends; step size

If i=1,2,...,n, the search fails and the algorithm ends; the block diagram of the coordinated search of Markov moving targets by multiple UAVs is shown in Figure 5.

In the above-mentioned specific embodiment 1, a UAV search method for a Markov moving target is provided. Correspondingly, the present application also provides a UAV search device for a Markov moving target. Since the apparatus embodiment is basically similar to the method embodiment, the description is relatively simple, and reference may be made to part of the description of the method embodiment for related parts. The apparatus embodiments described below are merely illustrative.

Specific embodiment two

As shown in FIG. 6 , an embodiment of the present invention provides a UAV search device for a Markov moving target, including:

The target module 201 is configured to construct a probability model of the Markov moving target after receiving the search task, so as to obtain all possible states and their probability distributions during the movement of the Markov moving target;

The UAV module 202 is used to obtain all possible states and their probability distributions in the UAV search process;

The building module 203 is used to construct a Markov model for predicting the behavior of the UAV under the search task according to all possible states and their probability distributions during the UAV search process and the Markov moving target movement process, and establish a Markov model based on Markov behavior prediction. Multi-stage heuristic policy iteration algorithm for Kov decision;

The planning module 204 is configured to use the multi-stage heuristic strategy iterative algorithm based on Markov decision to obtain the search behavior strategy with the greatest profit, thereby planning the optimal search track of the UAV.

The embodiment of the present invention overcomes the major shortcomings of traditional search algorithms, such as scan line search algorithms, which only focus on the design of the algorithm itself and lack strict mathematical definition of the motion law of the search target, which leads to high search costs. At this moment, the existence probability distribution of the Markov moving target in the search area determines the position of the virtual target that the UAV will search for at the next moment, and obtains a sequence of search behaviors of the UAV. This sequence is the search with the greatest behavioral benefit. The behavior strategy can be applied to search for moving targets, and the target can be successfully searched with low search cost.

Preferably, the target module 201 can be used to: after receiving the search task, perform grid division on the moving area of the target, use probability theory to model the Markov moving target, and obtain the probability model of the Markov moving target , so as to obtain all possible states and their probability distributions during the movement of the Markov moving target; the movement area of the target is equivalent to the search area of the UAV.

Preferably, the UAV module 202 can be used to: encode and describe the flight behavior of the UAV, and describe the state of the UAV in the process of executing the search task, so as to obtain the information of the UAV in the process of searching for the UAV. All possible states and their probability distributions.

Preferably, the construction of the Markov model for predicting the behavior of the UAV under the search task may be specifically:

Set the time set T={1,2,3,…} when the UAV search task is in progress;

Set the discrete state space S=(s ₁ , s ₂ , s ₃ ,...) of the UAV, which contains all possible states during the UAV search process and the Markov moving target movement process;

Let the action space A of the UAV = {a ₁ ,a ₂ ,...,a _x ,...,a _q }, which represents all possible actions of the UAV to change the state, where the element a _x represents the xth actions, q is the number of elements in the action space;

Suppose the feasible action set A(s _n ) of the UAV in the state _sn = {a ₁ (s _n ), a ₂ (s _n ), a ₃ (s _n ),...}, representing the UAV A collection of all actions that can be taken in a state;

Let T(s _n , a _x (s _n ), s _m ) represent the set of all state transition probabilities of the UAV, and any element p(s _m |s _n , a _x (s _n )) in the state s _n , the probability that the state changes to s _m after performing the available actions a _x (s _n ), where

Let any element r(s _n , a _x (s _n )) of the reward set R(s _n ) represent the reward for performing the action a _x (s _n ) in the state _sn ;

Then the Markov model for predicting the search behavior of the UAV under any search task is:

MDP={S,A,T(s _n ,a _x (s _n ),s _m ),R(s _n )}→π(s _n );

Among them, π is the strategy, which represents the mapping from the state set to the action set, π(s _n ) represents the mapping of the UAV from the state s _n to the action set, and → represents the output optimal strategy.

Preferably, the planning module 204 may include:

表示在从时刻t＝0开始无人机从状态s_n使用策略π后的折扣期望总报酬；The calculation unit is used to: calculate the reward utility function with the MDP discount model, where the discount factor γ satisfies: 0<γ<1; the reward function of the discount model

represents the discounted expected total reward after the UAV uses policy π from state sn from time _t =0;

以及最优动作值函数方程

并根据两个最优函数方程建立最优搜索策略函数方程

According to the optimal equation of the MDP discount model, the optimal state value function equation of the UAV's search operation revenue in the search task under the state _sn is established

and the optimal action value function equation

And establish the optimal search strategy function equation according to the two optimal function equations

The given unit is used to: rasterize the collaborative search area, determine the discrete state space S of the MDP model, given the number of UAVs participating in the search task g, s _UAV(i) is the i-th UAV The current state, s _UAV(i) ∈ S, A(s _UAV(i) ) is the action set of the i-th UAV in the state s _UAV(i) , and K _i is the maximum search of the i-th UAV Step size; given the discount factor γ and the end condition ε of the strategy iteration, let the number of iterations b = 0;

The initial unit is used to: determine the initial position of the target movement and the position where each drone starts to search; each drone obtains the existence probability distribution of the target in the entire area according to the initial position of the target movement and the target movement heuristic information , so as to determine the virtual target position that each UAV will search for at the next moment;

The iterative unit is used for: each UAV based on its own virtual target position and its current state s _UAV(i) , iteratively calculates its own state value function V ^b+1 (s _UAV(i) ), let The number of iterations b=b+1;

Judging unit, used for: if ||V ^b+1 (s _UAV(i) )-V ^b (s _UAV(i) )||<ε, end the iteration and call the traversal unit; otherwise, call the iteration unit;

Traversal unit for: each UAV traverses A(s _UAV(i) ) according to the final state value function V ^b+1 (s _UAV( i) ) to obtain Q(s _UAV(i) , a _i ) , and finally obtain the search behavior strategy with the largest profit π _i (t+1) ^* ;

转移到

同时，无人机获得立即报酬r_i(s_UAV(i),a_i)，此时令t＝t+1，令第i架无人机搜索步长k_i＝k_i+1；The transition unit is used to: execute the action a _i according to the required optimal strategy π _i (t+1) ^* , the state is given by

move to

At the same time, the UAV obtains an immediate reward ri (s _{UAV(i) ,} a _i ), at this time, let t=t+1, and let the i-th UAV search step _ki = _ki +1;

i＝1,2,...,n，则搜索任务失败，算法结束；所述目标当前模拟位置为根据马尔科夫运动目标运动过程中所有可能出现的状态及其概率分布获取的目标当前最可能出现的位置。The end unit is used for: if at a certain time t, the position s _UAV(i) of the i-th UAV is the same as the current simulation position s _target of the target, then the i-th UAV successfully searches for the target, and the search task is completed, The algorithm ends; if the search step is

i=1,2,...,n, then the search task fails and the algorithm ends; the current simulated position of the target is the current maximum position of the target obtained according to all possible states and their probability distributions during the movement of the Markov moving target. possible location.

The present invention is explained from the viewpoints of purpose of use, efficiency, progress and novelty, etc. The practical progress of the present invention has met the functional enhancement and use requirements emphasized by the patent law. The above description and drawings of the present invention are only for The preferred embodiments of the present invention are not intended to limit the present invention. Therefore, all structures, devices, and waiting lists are similar or similar to those of the present invention, that is, any equivalent replacement or modification made according to the scope of the patent application of the present invention. etc., shall all fall within the scope of protection of the patent application of the present invention.

It should be noted that the embodiments of the present invention and the features of the embodiments may be combined with each other under the condition of no conflict. Although this invention has been described to a certain extent, it will be apparent that suitable changes in various conditions may be made without departing from the spirit and scope of the invention. It is to be understood that the invention is not limited to the embodiments described, but is to be included within the scope of the claims, which include equivalents for each of the elements described. For those skilled in the art, various other corresponding changes and deformations can be made according to the technical solutions and concepts described above, and all these changes and deformations should fall within the protection scope of the claims of the present invention.

Claims (6)

1. An unmanned aerial vehicle searching method for a Markov moving target is characterized by comprising the following steps:

a target step, namely after receiving a search task, constructing a probability model of the Markov moving target so as to obtain all possible states and probability distribution thereof in the moving process of the Markov moving target;

the unmanned plane step, obtaining all possible states and probability distribution thereof in the unmanned plane searching process;

a construction step, wherein a Markov model for predicting unmanned aerial vehicle behaviors under a search task is constructed according to all possible states and probability distribution thereof in the unmanned aerial vehicle search process and the Markov moving target movement process, and a multi-stage heuristic strategy iterative algorithm based on Markov decision is established;

a planning step, namely acquiring a search behavior strategy with the maximum profit by using a multi-stage heuristic strategy iterative algorithm based on Markov decision, so as to plan the optimal search track of the unmanned aerial vehicle;

the establishment of the Markov model for unmanned aerial vehicle behavior prediction under the search task specifically comprises the following steps:

setting a time set T ═ 1,2,3, … } when the unmanned aerial vehicle search task is in progress;

let the discrete state space S ═ S of unmanned aerial vehicle (S)₁，s₂，s₃…) containing all possible states during drone search and during markov moving target motion;

let action space A ═ a of unmanned aerial vehicle ═ a₁，a₂，...，a_x，...，a_qRepresents all possible state-changing actions of the drone, element a_xRepresents the x-th action, and q is the number of elements in the action space;

let unmanned aerial vehicle be in state s_nSet of possible actions A(s) of_n)＝{a₁(s_n)，a₂(s_n)，a₃(s_n) ,., representing the set of all actions that a drone can take in a certain state;

let T(s)_n，a_x(s_n)，s_m) Represents the set of all state transition probabilities of the drone, with any element p(s)_m|s_n，a_x(s_n) Is in state s)_nNext, perform available action a_x(s_n) After that, the state changes to s_mThe probability of (a) of (b) being,

set of remunerations R(s)_n) Any element r(s) of_n，a_x(s_n) Is in state s)_nPerforming action a_x(s_n) A reward of (1);

the markov model for predicting the search behavior of the unmanned aerial vehicle executing any search task is as follows:

MDP＝{S，A，T(s_n，a_x(s_n)，s_m)，R(s_n)}→π(s_n)；

where π is the policy, which represents the mapping from the state set to the action set, π(s)_n) Slave state s for unmanned aerial vehicle_nMapping to action set, → representing the output optimal strategy;

the planning step comprises:

a calculation step: calculating a reward utility function with the MDP discount model, wherein the discount factor γ satisfies: gamma is more than 0 and less than 1; reward function for discount model

Representing the discount expectation total reward after the unmanned aerial vehicle uses the strategy pi from the state sn from the moment t-0;

according to the optimal equation of the MDP discount model, an optimal state value function equation of the search operation income of the unmanned aerial vehicle in the search task under the state sn is established

And an optimal action value function equation

And establishing an optimal search strategy function equation according to the two optimal function equations

The method comprises the following steps: rasterizing a collaborative search area, determining a discrete state space S of an MDP model, giving the number g, g and i of unmanned aerial vehicles participating in a search task as positive integers, and giving S_UAV(i)For the ith unmanned plane current state, s_UAV(i)∈S，A(s_UAV(i)) For the ith unmanned plane at state s_UAV(i)Set of actions of_iThe maximum search step length of the ith unmanned aerial vehicle is set; giving a discount factor gamma and a strategy iteration ending condition, and enabling the iteration number b to be 0;

the method comprises the following initial steps: determining an initial position of target motion and a position where each unmanned aerial vehicle starts to search; each unmanned aerial vehicle obtains the existence probability distribution of the target in the whole area according to the initial position of the target starting to move and the heuristic information of the target movement, so that the virtual target position to be searched at the next moment of each unmanned aerial vehicle is determined;

iteration step: each unmanned aerial vehicle is positioned according to the virtual target and the current state s_UAV(i)Iteratively calculating respective state value functions V^b+1(s_UAV(i)) Making the iteration number b equal to b + 1;

a judging step: if V | |^b+1(s_UAV(i))-V^b(s_UAV(i)) If | is less, ending the iteration and entering the traversal step; otherwise, turning to the iteration step;

traversing: each unmanned aerial vehicle obtains a state value function V according to the final result^b+1(s_UAV(i)) Traverse A(s)_UAV(i)) Obtaining Q(s)_UAV(i)，a_i) Finally, the search behavior strategy pi with the maximum profit is obtained_i(t+1)^*；

A transfer step: according to the optimal strategy pi_i(t+1)^*Performing action a_iThe state is given by

Is transferred to

At the same time, the drone gets an immediate reward r_i(s_UAV(i)，a_i) When t is t +1, the ith unmanned aerial vehicle searches for step length k_i＝k_i+1；

And (5) finishing the steps: if at a certain moment t, the ith unmanned aerial vehicle position s_UAV(i)With the current simulated position s of the target_targetIf the number of the unmanned aerial vehicles is the same as the number of the unmanned aerial vehicles, the unmanned aerial vehicle of the ith frame successfully searches the target, the search task is completed, and the algorithm is ended; if the search step size is

The search task fails and the algorithm ends; and the current simulation position of the target is the current most likely position of the target obtained according to all likely states and probability distribution of the Markov motion target in the motion process.

2. The unmanned aerial vehicle searching method for a markov moving target according to claim 1, wherein the target step specifically is:

after receiving a search task, rasterizing a motion area of a target, modeling a Markov motion target by using probability theory, and acquiring a probability model of the Markov motion target so as to obtain all possible states and probability distribution of the Markov motion target in the motion process; the motion area of the target is equal to the search area of the unmanned aerial vehicle.

3. The unmanned aerial vehicle searching method for a markov moving target according to claim 1 or 2, wherein the unmanned aerial vehicle comprises:

the flight behavior of the unmanned aerial vehicle is coded and described, and states of the unmanned aerial vehicle in the process of executing a search task are described, so that all possible states and probability distribution of the states in the process of searching the unmanned aerial vehicle are obtained.

4. An unmanned aerial vehicle searching device for Markov moving targets, comprising:

the target module is used for constructing a probability model of the Markov moving target after receiving the search task so as to obtain all possible states and probability distribution of the Markov moving target in the moving process;

the unmanned aerial vehicle module is used for acquiring all possible states and probability distribution thereof in the searching process of the unmanned aerial vehicle;

the building module is used for building a Markov model for predicting the behavior of the unmanned aerial vehicle under a search task according to all possible states and probability distribution thereof in the unmanned aerial vehicle search process and the Markov moving target motion process, and building a multi-stage heuristic strategy iterative algorithm based on Markov decision;

the planning module is used for acquiring a search behavior strategy with the maximum profit by utilizing a multi-stage heuristic strategy iterative algorithm based on Markov decision, so as to plan the optimal search track of the unmanned aerial vehicle;

the establishment of the Markov model for unmanned aerial vehicle behavior prediction under the search task specifically comprises the following steps:

setting a time set T ═ 1,2,3, … } when the unmanned aerial vehicle search task is in progress;

let the discrete state space S ═ S of unmanned aerial vehicle (S)₁，s₂，s₃…) containing all possible states during drone search and during markov moving target motion;

let action space A ═ a of unmanned aerial vehicle ═ a₁，a₂，...，a_x，...，a_qRepresents all possible state-changing actions of the drone, element a_xRepresents the x-th action, and q is the number of elements in the action space;

let unmanned aerial vehicle be in state s_nSet of possible actions A(s) of_n)＝{a₁(s_n)，a₂(s_n)，a₃(s_n) ,., representing the set of all actions that a drone can take in a certain state;

let T(s)_n，a_x(s_n)，s_m) Represents the set of all state transition probabilities of the drone, with any element p(s)_m|s_n，a_x(s_n) Is in state s)_nNext, perform available action a_x(s_n) After that, the state changes to s_mWherein, the probability of

Set of remunerations R(s)_n) Any element r(s) of_n，a_x(s_n) Is in state s)_nPerforming action a_x(s_n) A reward of (1);

the markov model for predicting the search behavior of the unmanned aerial vehicle executing any search task is as follows:

MDP＝{S，A，T(s_n，a_x(s_n)，s_m)，R(s_n)}→π(s_n)；

where π is the policy, which represents the mapping from the state set to the action set, π(s)_n) Slave state s for unmanned aerial vehicle_nMapping to action set, → representing the output optimal strategy;

the planning module comprises:

a computing unit to: calculating a reward utility function with the MDP discount model, wherein the discount factor γ satisfies: gamma is more than 0 and less than 1; reward function for discount model

Indicating that the drone starts from state s at time t-0_nDiscounts after strategy π are used to expect a total reward;

establishing a state s according to an optimal equation of the MDP discount model_nOptimal state value function equation for searching operation income of unmanned aerial vehicle in search task

And an optimal action value function equation

And establishing an optimal search strategy function equation according to the two optimal function equations

A given unit for: rasterizing a collaborative search area, determining a discrete state space S of an MDP model, and giving the number g, S of unmanned aerial vehicles participating in a search task_UAV(i)For the ith unmanned plane current state, s_UAV(i)∈S，A(s_UAV(i)) For the ith unmanned plane at state s_UAV(i)Set of actions of_iThe maximum search step length of the ith unmanned aerial vehicle is set; giving a discount factor gamma and a strategy iteration ending condition, and enabling the iteration number b to be 0;

an initial unit configured to: determining an initial position of target motion and a position where each unmanned aerial vehicle starts to search; each unmanned aerial vehicle obtains the existence probability distribution of the target in the whole area according to the initial position of the target starting to move and the heuristic information of the target movement, so that the virtual target position to be searched at the next moment of each unmanned aerial vehicle is determined;

an iteration unit to: each unmanned aerial vehicle is positioned according to the virtual target and the current state s_UAV(i)Iteratively calculating respective state value functions V^b+1(s_UAV(i)) Making the iteration number b equal to b + 1;

a determination unit configured to: if V | |^b+1(s_UAV(i))-V^b(s_UAV(i)) If the | is less, ending the iteration and calling the traversal unit, otherwise, calling the iteration unit;

a traversal unit to: each unmanned aerial vehicle obtains a state value function V according to the final result^b+1(s_UAV(i)) Traverse A(s)_UAV(i)) Obtaining Q(s)_UAV(i)，a_i) Finally get outMaximum benefit search behavior strategy pi_i(t+1)^*；

A transfer unit for: according to the optimal strategy pi_i(t+1)^*Performing action a_iThe state is given by

Is transferred to

At the same time, the drone gets an immediate reward r_i(s_UAV(i)，a_i) When t is t +1, the ith unmanned aerial vehicle searches for step length k_i＝k_i+1；

An ending unit configured to: if at a certain moment t, the ith unmanned aerial vehicle position s_UAV(i)With the current simulated position s of the target_targetIf the number of the unmanned aerial vehicles is the same as the number of the unmanned aerial vehicles, the unmanned aerial vehicle of the ith frame successfully searches the target, the search task is completed, and the algorithm is ended; if the search step size is

The search task fails and the algorithm ends; and the current simulation position of the target is the current most likely position of the target obtained according to all likely states and probability distribution of the Markov motion target in the motion process.

5. The Markov moving target drone searching device of claim 4, wherein the target module is to:

after receiving a search task, rasterizing a motion area of a target, modeling a Markov motion target by using probability theory, and acquiring a probability model of the Markov motion target so as to obtain all possible states and probability distribution of the Markov motion target in the motion process; the motion area of the target is equal to the search area of the unmanned aerial vehicle.

6. A Markov moving target drone search device as claimed in claim 4 or 5, wherein the drone module is to:

the flight behavior of the unmanned aerial vehicle is coded and described, and states of the unmanned aerial vehicle in the process of executing a search task are described, so that all possible states and probability distribution of the states in the process of searching the unmanned aerial vehicle are obtained.

Images