CN110823228B

CN110823228B - Path generation method and device

Info

Publication number: CN110823228B
Application number: CN201911130105.8A
Authority: CN
Inventors: 尹全军; 焦鹏; 鞠儒生; 谢旭; 许凯; 胡越; 曾云秀; 胡聪; 王鹏
Original assignee: National University of Defense Technology
Current assignee: National University of Defense Technology
Priority date: 2019-11-18
Filing date: 2019-11-18
Publication date: 2021-04-02
Anticipated expiration: 2039-11-18
Also published as: CN110823228A

Abstract

The embodiment of the invention discloses a path generation method and a path generation device, and on the first hand, nodes in a path obtained by planning on a zoom image are mapped into a sub-target graph, so that more details related to a deceptive path are reserved in the sub-target graph, path planning is carried out in the sub-target graph, the distortion condition is reduced, and the path planning accuracy is improved. In a second aspect, path planning is performed in the zoomed image and the sub-target image, which reduces the amount of computation compared to path planning in the original image. In a third aspect, the way of generating the sub-target graph is as follows: the convex corners in the original drawing are taken as the sub-targets, and the sub-targets meeting the preset conditions are connected, so that the calculation amount is small, and the calculation amount is further reduced.

Description

Path generation method and device

Technical Field

The present invention relates to the field of path planning technologies, and in particular, to a method and an apparatus for generating a path.

Background

The path planning means that a collision-free path from a starting node to a target node is searched in an environment with obstacles according to a certain evaluation standard. For example, optimal path planning needs to plan a path that consumes the least resources, and for example, deceptive path planning needs to plan a path that consumes more time or other resources of the other party, or plan a path that makes it difficult for the other party to determine a real path.

Existing path planning schemes generally include: the method comprises the steps of carrying out image acquisition aiming at a geographical area needing path planning, marking terrain conditions such as a starting node, a target node, a mountain, a plain and the like in the acquired image, and planning a path between the starting node and the target node based on the terrain conditions.

If the area of the geographic area is large, the original image is generally reduced in equal proportion, and a path is planned in the reduced image. However, in the process of scaling down, details of the original image are lost, distortion is easily caused, and the accuracy of the planned path is poor.

Disclosure of Invention

In view of the above, the present invention provides a method and an apparatus for path generation to reduce distortion and improve accuracy of path planning.

Based on the above object, the present invention provides a path generating method, including:

acquiring an image to be processed;

zooming the image to be processed to obtain a zoomed image;

performing path planning on the zoomed image to obtain a first path;

generating a sub-target map of the image to be processed as a first sub-target map; wherein, the sub-target map is: in the original drawing, convex corners in the original drawing are taken as sub-targets, and the sub-targets meeting preset conditions are connected to form a drawing;

mapping nodes in the first path to the first sub-target graph to obtain first path points in the first sub-target graph;

determining a node which meets a preset condition with the first path point in the first sub-target graph;

generating a sub-target graph of the first sub-target graph as a second sub-target graph based on the determined nodes and the first path points;

and planning a path on the second sub-target map to obtain a target path.

Optionally, the performing path planning on the zoomed image to obtain a first path includes:

determining an initial node, a real target node, a preset false target node and a plurality of intermediate nodes on the zoomed image;

based on a shortest path planning model and a recognition party behavior model, obtaining posterior probability distribution of a candidate node set under a given observation situation at each intermediate node position, wherein the candidate node set comprises the real target node and a preset false target node;

evaluating the deception magnitude of the intermediate node based on the posterior probability distribution;

solving candidate sub-paths under a preset objective function according to the deception magnitude of the intermediate node;

and combining the candidate sub-paths into a deception path as the first path, wherein the deception path takes the starting node as a starting point.

Optionally, the preset conditions are: in the parallelogram formed by the two nodes, no obstacles and other sub-targets exist.

Optionally, the performing path planning on the second sub-target map to obtain a target path includes:

performing path planning on the second sub-target graph to obtain a second path;

mapping the nodes in the second path to the image to be processed to obtain second path points in the image to be processed;

and performing deception path planning on the image to be processed based on the second path point to obtain the target path.

Optionally, the performing path planning on the second sub-target map to obtain a second path includes:

determining an initial node, a real target node, a preset false target node and a plurality of intermediate nodes on the second sub-target graph;

and combining the candidate sub-paths into a deception path as the second path, wherein the deception path takes the starting node as a starting point.

Based on the above object, the present invention further provides a path generating apparatus, including:

the acquisition module is used for acquiring an image to be processed;

the zooming module is used for zooming the image to be processed to obtain a zoomed image;

the first planning module is used for planning a path on the zoom image to obtain a first path;

the first generation module is used for generating a sub-target map of the image to be processed as a first sub-target map; wherein, the sub-target map is: in the original drawing, convex corners in the original drawing are taken as sub-targets, and the sub-targets meeting preset conditions are connected to form a drawing;

a mapping module, configured to map a node in the first path to the first sub-target graph to obtain a first path point in the first sub-target graph;

a determining module, configured to determine, in the first sub-target graph, a node that meets a preset condition with the first path point;

a second generating module, configured to generate a sub-target map of the first sub-target map as a second sub-target map based on the determined node and the first path point;

and the second planning module is used for planning a path on the second sub-target map to obtain a target path.

Optionally, the first planning module is specifically configured to:

Optionally, the second planning module includes:

the first planning submodule is used for planning a path on the second sub-target map to obtain a second path;

the mapping submodule is used for mapping the nodes in the second path to the image to be processed to obtain second path points in the image to be processed;

and the second planning submodule is used for carrying out deception path planning on the image to be processed based on the second path point to obtain the target path.

Optionally, the first planning sub-module is specifically configured to:

By applying the embodiment of the invention, on the first hand, the nodes in the path planned on the zoom image are mapped to the sub-target graph, so that more details related to the deceptive path are reserved in the sub-target graph, the path planning is carried out in the sub-target graph, the distortion is reduced, and the accuracy of the path planning is improved. In a second aspect, path planning is performed in the zoomed image and the sub-target image, which reduces the amount of computation compared to path planning in the original image. In a third aspect, the way of generating the sub-target graph is as follows: the convex corners in the original drawing are taken as the sub-targets, and the sub-targets meeting the preset conditions are connected, so that the calculation amount is small, and the calculation amount is further reduced.

Drawings

In order to more clearly illustrate the embodiments of the present invention or the technical solutions in the prior art, the drawings used in the description of the embodiments or the prior art will be briefly described below, it is obvious that the drawings in the following description are only some embodiments of the present invention, and for those skilled in the art, other drawings can be obtained according to the drawings without creative efforts.

Fig. 1 is a schematic flowchart of a path generation method according to an embodiment of the present invention;

fig. 2 is a schematic structural diagram of a path generating device according to an embodiment of the present invention.

Detailed Description

In order to make the objects, technical solutions and advantages of the present invention more apparent, the present invention is described in further detail below with reference to specific embodiments and the accompanying drawings.

It should be noted that all expressions using "first" and "second" in the embodiments of the present invention are used for distinguishing two entities with the same name but different names or different parameters, and it should be noted that "first" and "second" are merely for convenience of description and should not be construed as limitations of the embodiments of the present invention, and they are not described in any more detail in the following embodiments.

In order to achieve the above object, embodiments of the present invention provide a method and an apparatus for generating a path, which may be applied to various electronic devices, and are not limited specifically. First, a path generation method provided by an embodiment of the present invention will be described in detail.

Fig. 1 is a schematic flow chart of a path generation method provided in an embodiment of the present invention, including:

s101: and acquiring an image to be processed.

For example, image acquisition may be performed for a geographic area in which path planning is required, and the acquired image is referred to as an image to be processed. The image may be a map, a grid map, etc., and the specific image format is not limited.

S102: and zooming the image to be processed to obtain a zoomed image.

For example, the image to be processed may be scaled equally, such as discretizing the image to be processed into a grid map D, and then scaling D by equal-scale k times to the scaled image D_miniK can be 2, 3, etc., and the specific value can be set according to actual conditions.

S103: and planning a path on the zoomed image to obtain a first path.

For example, the path planning in S103 may be an optimal path planning, a deceptive path planning, and the like, which is not limited specifically. Taking the spoofed path plan as an example, in one embodiment, S103 may include:

For example, a real target node may be understood as a real end point of a path, and a preset dummy target node may be understood as a dummy end point for confusing a recognizer. When a deception path needs to be generated, an initial node and a real target node are known; a false target node may be preset based on actual geographic conditions.

Generally, the generated fraud path is located in an area, which may be a city, a province, or other administrative area, or the area where the fraud path is located may be preset based on actual geographic conditions. The area is divided into a plurality of intermediate nodes, for example, the area may be uniformly divided into one node every 1 km, and the nodes are intermediate nodes, or the intermediate nodes may be understood as the minimum unit of division in the area. Because the plan of the scheme is a deception path instead of an optimal path, each position in the area is possible to be a node between the starting node and the real target node in the deception path, and therefore, the minimum units in the area can be used as intermediate nodes.

The shortest path planning model and the identification party behavior model are obtained in advance, and the specific obtaining mode is not limited.

In one embodiment, the posterior probability distribution may be calculated using the following equation:

wherein P (G | O) represents the posterior probability distribution, G represents the candidate node set, O represents an observation sequence corresponding to a given observation situation, α represents a normalization factor, β represents a preset constant, β is greater than 0, s represents the start node, G represents the real target node and the preset false target node, costdif_RGRepresents the difference in the intended cost, optc represents the optimal cost from s to g for the identified person's behavior to be consistent with observation O,

representing the optimal cost from s to g for the identified person's behavior not consistent with observation O. The intent is also the possible target nodes, including the real target node and the pre-set dummy target node.

In the present embodiment, the posterior probability of an intention can be defined based on the cost difference (cost difference) with which the person to be identified realizes the intention under two conditions: one is the cost of the identified person's behavior being consistent with the observation, and the other is the cost of the inconsistency, see equation 2 above.

The smaller the cost difference, the greater the probability that the intent is a true intent, so a probability distribution over a set of possible intents (a set of candidate nodes) can be generated by comparing the cost differences of different intents. For example, Boltzmann distribution (Boltzmann distribution) assumptions can be employed, namely:

from this, the posterior probability distribution of the possible intention set (candidate node set) can be obtained by the above equations 1 and 2.

Alternatively, in another embodiment, the cost difference between the two optimal paths for each intent, compliant and non-compliant (or partially non-compliant) observations, which reflects the intent uncertainty of each node, may be determined separately. In this embodiment, the a posteriori probability distribution is denoted as P (G | N), N comprising the start node s, the set of candidate nodes G and intermediate nodes,

Y＝costdif_MS(s，g，n)；

wherein P (G | N) represents the posterior probability distribution, N includes the start node s, the candidate node set G and the intermediate node, α represents a normalization factor, β represents a predetermined constant, β is greater than 0, costdif_MsA cost difference representing an intention, s represents the starting node, g represents the real target node and the preset fake target node, n represents a position where the identified party is observed recently, and n is o^|o|And O represents the observation sequence corresponding to a given observation scenario.

costdif_RGAnd costdif_MSRespectively representing the cost difference of intentions calculated by different algorithms, and the corner mark RG and the corner mark MS can be understood as different algorithm identifications.

In this embodiment, the path planning problem field may be defined as a triplet D<N，E，c>Where N is a non-empty set of nodes, N includes a start node s, a candidateA node set G and intermediate nodes;

e is the set of edges between nodes; c represents the specific cost of passing each edge.

In the path planning problem domain, path pi is expressed as node order pi ═ n_o，n₁……n_kSo that for each node i ∈ 0, 1 … … k-1; (n)_i，n_i+1)∈E。πⁱRepresenting the ith node of path pi. | π | represents the path length, and likewise the number of edges in path π, π^|π|＝n_k. The cost of path pi is the cost of passing all edges, i.e.

The set of all paths is defined as pi, all starting from node pi⁰＝n₁Terminates at pi^|π|＝n₂Has a path set of pi (n)₁,n₂)。

A path planning problem may be defined as a < D, s, g > triplet, where D is < N, E, c >, D is the path planning problem domain, s belongs to N, s represents the start node, g belongs to N, and g represents the target node (real target node).

The solution or solution path of the path planning problem is the corresponding problem domain D, which satisfies pi⁰S and pi^|π|G-path pi. The set of these path solutions is Π (s, g). The optimal path is the least costly path of all solution paths. The optimal cost between two nodes is the optimal path cost between the two nodes, node n_iTo n_jIs defined as optc (n)_i,n_j). The optimal path may be determined using the a-star algorithm (a-star algorithm, a direct search method for solving shortest paths in static road networks).

Taking fraud into account in path planning, it can be understood that there is some hostile observer trying to learn the path trend. The probabilistic intent recognition problem, i.e., tuple, in the path planning problem domain is given below<D，G，s，O，Prob>WhereinD is the problem domain of the path planning,

represents an intention set, i.e. a set of candidate nodes, s ∈ N, s represents a start node, O ═ O₁……o_mE N, where m is greater than 0, O represents the observation sequence, and Prob represents the prior probability of the target node, which can be assumed to be equiprobable.

Probability distribution of intent G: pr (G | O) is the solution to the above problem, representing the probability that G ∈ G is the true target given the observation sequence O. g_rE G represents the true intention of the identified party, or G_rRepresenting the real target node, and determining the quality of the solution according to whether the solution can be applied to all the G e G/G_rGuarantee Pr (g) in_rO) is equal to or greater than Pr (g | O).

The deceptive path plan attempts to minimize the probability that its true target node is identified.

A Deceptive Path Planning (DPP) problem can be represented as a tuple<<D,s,g_r>,G,P>Wherein:

<D,s,g_r>representing a path planning problem, in which D ═<N，E，c>D is the path planning problem domain, s belongs to N, s represents the starting node,

representing an intention set, i.e. a candidate node set, P (G | O.n) representing the posterior probability of the target nodes (true target nodes and pre-set false target nodes) given the observation sequence O, P representing the shortest path planning model and the identifier behavior model described above.

Spoofing is a "distortion of perceived reality" and has two implementations: "fake representation" and "hidden truth", also known as "negation" and "spoofing", wherein fake representation can be understood as: giving the viewer an impression of moving to other objects; the Tibetan language can be understood as follows: obscuring the planner's true goals.

The solution of the DPP problem is planned to obtain a path with deceptive performance, and the quality of the solution can be measured by three different indexes of magnitude, density and degree.

A step in the path is true (true step), if and only if, at the node, the true target probability g_rGreater than the probability of other possible target points, i.e. all G ∈ G \ G_r}，P(g_r|O.n)>P (g | O.n). Otherwise the step is fraudulent.

When the probability of a certain false target node is strictly greater than that of a real target node g_rProbability is false (Simulation) spoofing. Namely, the existence of G epsilon G \ G_rAre such that P (g)_r|O.n)<P(g|O.n)。

The pseudo-nature can be quantitatively described in terms of the degree to which a false target node dominates a true target node. The higher the dominance, the stronger the false fraud.

Where O denotes an observation sequence corresponding to a given observation situation, n denotes a position at which the identified party was most recently observed, and n ═ O^|o|，g_rRepresenting the true target node, and P (G | O) representing the posterior probability distribution. The simulation (O.n) represents the spoofing magnitude corresponding to location n and derived based on the spoofing policy. n can be understood as a point location, and an intermediate node can also be understood as a point location, and the intermediate node is corresponding to n, so that the deception magnitude of the intermediate node is obtained.

If the fake spoofing strategy is successful, the identification party can only deploy the resource to the wrong position.

When the target node g is real_rWhen the difference between the probability of (1) and the probability of other false target nodes is less than a certain threshold value tau, the method is a hidden true (fraud). Namely, the existence of G epsilon G \ G_rIs made | P (g)_r|O.n)-P(g|O.n)|<τ。

Strict spoofing occurs when τ is equal to 0, meaning that there is a false target node whose recognition probability is consistent with the probability of a true target node. Since this occurs only a few times in the probabilistic model, it may allow for spoofing to occur within an acceptable interval, e.g., the posterior recognition probability of a real target is not dominant over other false targets. Genuine fraud can be described quantitatively using Shannon's entropy:

the dismembership (O.n) indicates the magnitude of spoofing based on the hidden-truth policy corresponding to location n. n can be understood as a point location, and an intermediate node can also be understood as a point location, and the intermediate node is corresponding to n, so that the deception magnitude of the intermediate node is obtained.

If the hidden-truth strategy is successful, the identification party cannot judge the deployment position of the resource due to the fact that different intents have similar posterior probabilities. At this point, the identifying party will make a decision under the assumption that there is no observed information.

In an embodiment, the evaluating the spoofing magnitude of the intermediate node based on the pseudo-indicative policy and the posterior probability distribution may specifically include:

using equation 5, the spoofing magnitude of the intermediate node is evaluated:

in another embodiment, the evaluating the spoofing magnitude of the intermediate node based on the hidden-truth policy and the posterior probability distribution may specifically include:

using equation 6, the spoofing magnitude of the intermediate node is evaluated:

in another embodiment, the evaluating the spoofing magnitude of the intermediate node based on the fake and hidden policies and the posterior probability distribution may specifically include:

where O denotes an observation sequence corresponding to a given observation situation, n denotes a position at which the identified party was most recently observed, and n ═ O^|o|，g_rRepresents the real target node, P (g)_iL O.n) represents the posterior probability distribution, G represents the candidate node set, simulation represents the deception magnitude obtained based on the pseudo-representation strategy, and dispulation represents the deception magnitude obtained based on the hidden-truth strategy, and omega₁Representing a preset first weight value, ω₂Indicating a preset second weight value. Omega₁And ω₂The specific value of (c) can be set according to actual conditions, but ω is required₁₊ω₂At 1, combi indicates the magnitude of spoofing based on the fake and hidden-genuine policies.

combi (O.n) indicates the spoofing magnitude corresponding to location n based on the spoofing and hiding policies. n can be understood as a point location, and an intermediate node can also be understood as a point location, and the intermediate node is corresponding to n, so that the deception magnitude of the intermediate node is obtained.

Depending on the subjective intensity of the intended concealment or fraud, people often mix both false and false-hiding effects in their behavior. In this embodiment, a comprehensive strategy is proposed: when the target node g is real_rIs not greater than the sum of the identification probability of other false target nodes and the threshold τ, it is a Combination, i.e., a Combination of false and true representation. Namely, the existence of G epsilon G \ G_rIs made | P (g)_r|O.n)≤τ+P(g|O.n)|。

This strategy quantification is described as a linear combination of the explicit and implicit strategies, with reference to equation 7 above. Compared with a fake showing strategy and a real hiding strategy, the comprehensive strategy is more flexible and comprehensive, and not only can express a fake intention, but also can hide a real intention.

Spoofing in path planning can be achieved by maximizing the area of the parcel under its magnitude curve:

for a discrete scene, equation 8 may be expressed as:

where i denotes a node in the path, Δ L denotes the length of the time slice, and t denotes the time.

Based on the similar idea of equation 9, a deception maximization model based on deception magnitude is introduced below, which is denoted as MDM-P, and in the model solving process, the following assumed conditions exist: the outcome of the action is deterministic; for both parties to be identified, the behavioral model is observable; the rogue is rational in the rogue path planning.

The mathematical form of the model is:

the problems are as follows: in a directed network N along the s-g_rPaths resource-constrained maximize magnitude expectations of spoofing; the directed network N can be understood as the area where the generated spoofed path is located.

Parameters are as follows: i e N, i denotes a node in the network (including the start node s, G ═ G { (G))_r、g₁……g_|G|-1G denotes a candidate node set, G_rAnd representing a real target node, wherein other nodes in the G are preset false target nodes, k ∈ E represents an edge in the network, j represents another node in the network, k ∈ FS (i) represents an edge-out set of the node i, and k ∈ RS (i) represents an edge-out set of the node i.

Data: mag_kRepresents a value of the spoofing level on edge k, - ∞ < mag_kLess than + ∞; rk is greater than 0, and rk represents the resources required by the passing edge k, namely the initial length of the edge; r represents s-g_rTotal amount of resources available for the path.

Variables are as follows: if edge k is passed, x_k1, otherwise x_k＝0。

The magnitude-based deception maximization model is:

(objective function);

wherein X { X ∈ { (0, 1}^|E||r^Tx ≦ R }, and equation 10 may be understood as a constraint. The rogue (identified party) follows a path s-g under a resource constraint R_rMaximizing the expected magnitude of spoofing. The objective function of MDM-P can be understood as: with the spoof magnitude being a function of the target maximum.

In the field of path planning, edges in the network can be regarded as actions, and therefore in the above model, the spoofing magnitude of the edge k ═ i, j is the same as that of the node j, so that the spoofing magnitude defined on the node can be converted to the edge or the action in the network. The constraint condition is flow balance constraint, and ensures that the path generated by optimization starts from a node s to a node g_rAnd (6) terminating. In addition, the constraint conditions also guarantee the set N \ s, g₁……g_mThe access of node i in } is the same as the number of leaves.

The advantages of applying the above model MDM-P are the following: the deception on each node is described quantitatively by using the magnitude index, and a common calculation basis is provided for subsequent different deception strategies, so that the adaptability of the model under different scenes is expanded; second, defining spoofed magnitude on the nodes allows spoofed paths to be planned in a global fashion over the complete network.

Two other models, MDM-P1 and MDM-P2, are presented below:

wherein, the MDM-P1 may be:

(objective function);

the constraint condition refers to equation 10 above. The objective function of the MDM-P model only requires maximization of the expected magnitude, but the constraint (equation 10) cannot guarantee that the edges generated by optimization are connected with the complete path. And the MDM-P1 can solve the problem by reconstructing the MDM-P as a dual-target optimization problem.

The MDM-P2 may be:

(objective function);

the constraint condition refers to equation 10 above. MDM-P2 also solves the problems described above with MDM-P.

And the optimization complexity of the MDM-P2 model is lower than that of the MDM-P1 model, the calculation amount of the MDM-P2 model is low, and the efficiency is high.

The objective functions of MDM-P1 and MDM-P2 can be understood as: the maximum spoof magnitude and the longest path are the functions of the target.

The calculation results of the MDM-P, MDM-P1 model, the MDM-P2 model and the like are optimized variables X, wherein the non-zero elements in X represent the edges passed by the cheater, and the edges form a cheating path, so the edges are called candidate sub-paths.

The candidate sub-paths obtained by the hypothesis solution form a set E'. If no loop exists, the starting node s and the real target node g are given_rA deception path can be generated in an end-to-end mode; for example, let E { (s, n)₁)，(n₁，n₂)，(n₂，g_r) Is s → n, the corresponding path is s → n₁→n₂→g_r。

However, loops exist in most of the deceptive paths, and in one embodiment, the loops combined by the candidate sub-paths can be identified based on preset loop conditions; and generating a deception path consisting of candidate sub-paths based on the starting node, the real target node and the identified loop.

In one embodiment, all sequential combinations of edges that may cover the set E' may be traversed. For example, let E { (s, n)₁)，(n₁，n₃)，(n₁，n₂)，(n₂，n₁)，(n₃，g_r) Get the path s → n by traversing all possible sequential combinations of edges₁→n₂→n₁→n₃→g_r. However, if multiple loops exist in the spoofing path, the complexity is high by using the traversal method.

The inventors found that the presence of a loop satisfies the following condition:

fs(s) | - | rs(s) | 1, and | fs(s) | > 1; or

|FS(g_r)|-|RS(g_r) 1 and RS (g)_r) I > 1; or

Fs (i) | rs (i) | > 1, where N 'is the set of nodes where the edge set E' appears.

Nodes satisfying the above conditions may be identified, and included in the set N ", that is, the nodes in N" are located in the loop of the spoof path.

Because i belongs to N' \ { g_r}, | fs (i) | 2, and i ═ g_rWhen | fs (i) | is 1, there always exists an edge j ∈ fs (i), and the end node of the edge has a path returning to the node i; thus, for node i ∈ N "\ { g }_rThere is always | fs (i) | -1 (or i ═ g }_r，i，g_rIf the path belongs to N, | FS (i) |), i is returned from the end node of the edge e ∈ FS (i).

In one embodiment, when encountering node i ∈ N ″, it may first find a traversable path from the end node of an edge in the set fs (i) to node i, add the covered edges on the paths into the ordered edge set, and loop this step until there is no element in fs (i) that can return to node i.

For example, the loop formed by the combination of candidate sub-paths may be identified as follows:

suppose given original road network D ═<N，E，c>An initial node s and a real target node g_rAnd in the case of the candidate node set G, a spoofed path with a loop is identified from the optimization result X. Firstly, the methodAnd extracting the sub-net D '═ (N', E ', c') from the D and the X, and initializing the ordered edge set Path. The recognition process is terminated when all edges in the set E' are added to Path. For nodes not on the path with loop path, add them to Pat in an end-to-end manner. And for the nodes on the loop, generating all Path tracks starting from the end node j of a certain edge of FS (temp) according to the judgment of the conditions, and adding the set coverEdgeSet of the track covering edge into the Path. For both cases (nodes not on the looped path trace and nodes on the loop), two additional steps need to be performed: first, delete from set E' already covering the edge; second, temp is located to the new node.

Thus, a finally generated spoofed path is obtained, and for the purpose of description differentiation, the spoofed path is referred to as a first path_mini。

S104: generating a sub-target map of the image to be processed as a first sub-target map; wherein, the sub-target map is: in the original drawing, convex corners in the original drawing are used as sub-targets, and the sub-targets meeting preset conditions are connected to form the drawing.

For example, the preset condition can be understood as a Direct-h-reachable attribute, that is: in the parallelogram formed by the two nodes, no obstacles and other sub-targets exist. S103 may include, in processing the image, determining convex corners as sub-targets, and connecting the sub-targets satisfying the Direct-h-reachable attribute to obtain a first sub-target map D_SSG。

S105: and mapping the nodes in the first path to the first sub-target graph to obtain first path points in the first sub-target graph.

The first path obtained in S103_miniIs mapped to the first sub-target graph D_SSGFor convenience of description, the mapped point is referred to as a first path point.

S106: and in the first sub-target graph, determining nodes meeting preset conditions with the first path point.

For example, the preset condition can be understood as a Direct-h-reachable attribute, that is: in the parallelogram formed by the two nodes, no obstacles and other sub-targets exist.

S107: and generating a sub-target graph of the first sub-target graph as a second sub-target graph based on the determined nodes and the first path points.

For example, the node determined in S106 may be connected to the first path point in the first sub-target graph, so as to obtain a new sub-target graph D'_SSGFor differentiating description, D'_SSGReferred to as the second sub-target map.

S108: and planning the path on the second sub-target map to obtain the target path.

Planning the path on the second sub-target graph, and for distinguishing description, referring the obtained path as the second path_ssg(ii) a In one embodiment, the second path may be directly used as the target path, that is, the path planning result of the present solution.

In another embodiment, a node in the second path may be mapped to the image to be processed to obtain a second path point in the image to be processed; and performing deception path planning on the image to be processed based on the second path point to obtain the target path.

In the present embodiment, the second path is used_ssgThe node in (b) is mapped back to the original image (i.e., the image to be processed in S101), and for convenience of description, the mapped point is referred to as a second path point. And in the original image, carrying out deception path planning based on the second path point, and finally connecting the deception path points end to obtain a target path, namely a path planning result of the scheme.

For example, the path planning in S108 may be an optimal path planning, a deceptive path planning, and the like, which is not limited specifically. Taking the spoofed path plan as an example, in one embodiment, S108 may include:

The spoofed path planning has already been described in detail in the foregoing, and is not described in detail here.

By applying the embodiment of the invention, the nodes in the path obtained by planning on the zoom image are mapped into the sub-target graph, so that more details related to the deceptive path are reserved in the sub-target graph, the path planning is carried out in the sub-target graph, the distortion condition is reduced, and the path planning accuracy is improved.

In some existing schemes, if the area of the geographic area is large, in order to reduce the distortion, path planning is directly performed on the original image acquired for the geographic area, so that the calculation amount is large. In the scheme, on the first hand, path planning is carried out in the zoomed image and the sub-target image, and compared with the path planning carried out in the original image, the calculation amount is reduced; in a second aspect, the way of generating the sub-target graph is as follows: the convex corners in the original drawing are taken as the sub-targets, and the sub-targets meeting the preset conditions are connected, so that the calculation amount is small, and the calculation amount is further reduced.

Corresponding to the foregoing method embodiment, an embodiment of the present invention further provides a path generating apparatus, as shown in fig. 2, including:

an obtaining module 201, configured to obtain an image to be processed;

a scaling module 202, configured to scale the image to be processed to obtain a scaled image;

a first planning module 203, configured to perform path planning on the zoomed image to obtain a first path;

a first generating module 204, configured to generate a sub-target map of the image to be processed as a first sub-target map; wherein, the sub-target map is: in the original drawing, convex corners in the original drawing are taken as sub-targets, and the sub-targets meeting preset conditions are connected to form a drawing;

a mapping module 205, configured to map a node in the first path to the first sub-target graph, so as to obtain a first path point in the first sub-target graph;

a determining module 206, configured to determine, in the first sub-target graph, a node that meets a preset condition with the first path point;

a second generating module 207, configured to generate a sub-target map of the first sub-target map as a second sub-target map based on the determined node and the first path point;

and the second planning module 208 is configured to perform path planning on the second sub-target map to obtain a target path.

As an embodiment, the first planning module 203 is specifically configured to:

As an embodiment, the preset condition is: in the parallelogram formed by the two nodes, no obstacles and other sub-targets exist.

As an embodiment, the second planning module 208 includes: a first planning submodule, a mapping submodule, and a second planning submodule (not shown), wherein,

As an embodiment, the first planning submodule is specifically configured to:

The apparatus of the foregoing embodiment is used to implement the corresponding method in the foregoing embodiment, and has the beneficial effects of the corresponding method embodiment, which are not described herein again.

Those of ordinary skill in the art will understand that: the discussion of any embodiment above is meant to be exemplary only, and is not intended to intimate that the scope of the disclosure, including the claims, is limited to these examples; within the idea of the invention, also features in the above embodiments or in different embodiments may be combined, steps may be implemented in any order, and there are many other variations of the different aspects of the invention as described above, which are not provided in detail for the sake of brevity.

In addition, well known power/ground connections to Integrated Circuit (IC) chips and other components may or may not be shown within the provided figures for simplicity of illustration and discussion, and so as not to obscure the invention. Furthermore, devices may be shown in block diagram form in order to avoid obscuring the invention, and also in view of the fact that specifics with respect to implementation of such block diagram devices are highly dependent upon the platform within which the present invention is to be implemented (i.e., specifics should be well within purview of one skilled in the art). Where specific details (e.g., circuits) are set forth in order to describe example embodiments of the invention, it should be apparent to one skilled in the art that the invention can be practiced without, or with variation of, these specific details. Accordingly, the description is to be regarded as illustrative instead of restrictive.

While the present invention has been described in conjunction with specific embodiments thereof, many alternatives, modifications, and variations of these embodiments will be apparent to those of ordinary skill in the art in light of the foregoing description. For example, other memory architectures (e.g., dynamic ram (dram)) may use the discussed embodiments.

The embodiments of the invention are intended to embrace all such alternatives, modifications and variances that fall within the broad scope of the appended claims. Therefore, any omissions, modifications, substitutions, improvements and the like that may be made without departing from the spirit and principles of the invention are intended to be included within the scope of the invention.

Claims

1. a path generation method, is characterized in that, comprises:

Get the image to be processed;

zooming the to-be-processed image to obtain a zoomed image;

Perform path planning on the zoomed image to obtain a first path;

A sub-target map of the image to be processed is generated as the first sub-target map; wherein, the sub-target map is: in the image to be processed, the convex corner in the image to be processed is taken as a sub-target, and will satisfy the A graph formed by connecting sub-goals of preset conditions;

mapping the nodes in the first path to the first sub-goal graph to obtain a first path point in the first sub-goal graph;

In the first sub-goal graph, determine a node that satisfies a preset condition with the first path point;

Based on the determined node and the first path point, a sub-goal graph of the first sub-goal graph is generated as a second sub-goal graph;

Perform path planning on the second sub-goal graph to obtain a target path.

2. The method according to claim 1, wherein the performing path planning on the zoomed image to obtain the first path comprises:

On the zoomed image, determine a starting node, a real target node, a preset false target node and a plurality of intermediate nodes;

Based on the shortest path planning model and the behavior model of the recognizer, obtain the posterior probability distribution of the candidate node set at the position of each intermediate node under a given observation situation, where the candidate node set includes the real target node and the preset false target node;

assessing the magnitude of deception of the intermediate node based on the posterior probability distribution;

According to the deception magnitude of the intermediate node, solve the candidate sub-path under the preset objective function;

Combining the candidate sub-paths into a spoofed path as the first path, the spoofed path takes the starting node as a starting point.

3 . The method according to claim 1 , wherein the preset condition is: there are no obstacles and other sub-targets in a parallelogram formed by two nodes. 4 .

4. The method according to claim 1, wherein the performing path planning on the second sub-goal graph to obtain a target path, comprising:

Perform path planning on the second sub-goal graph to obtain a second path;

mapping the nodes in the second path to the image to be processed to obtain a second path point in the image to be processed;

On the to-be-processed image, deception path planning is performed based on the second path point to obtain the target path.

5. The method according to claim 4, wherein the performing path planning on the second sub-goal graph to obtain the second path, comprising:

On the second sub-target graph, determine a starting node, a real target node, a preset false target node and a plurality of intermediate nodes;

Combining the candidate sub-paths into a spoofed path as the second path, the spoofed path takes the starting node as a starting point.

6. A path generation device, characterized in that, comprising:

The acquisition module is used to acquire the image to be processed;

a scaling module for scaling the to-be-processed image to obtain a scaled image;

a first planning module, configured to perform path planning on the zoomed image to obtain a first path;

a first generating module, configured to generate a sub-target map of the to-be-processed image as a first sub-target map; wherein, the sub-target map is: in the to-be-processed image, a convex corner in the to-be-processed image is used is a sub-goal, and a graph formed by connecting sub-goals that meet the preset conditions;

a mapping module, configured to map the nodes in the first path to the first sub-goal graph to obtain a first path point in the first sub-goal graph;

a determining module, configured to determine, in the first sub-goal graph, a node that satisfies a preset condition with the first path point;

a second generating module, configured to generate a sub-goal graph of the first sub-goal graph based on the determined node and the first path point, as a second sub-goal graph;

The second planning module is configured to perform path planning on the second sub-goal graph to obtain a target path.

7. The device according to claim 6, wherein the first planning module is specifically used for:

8 . The device according to claim 6 , wherein the preset condition is: there are no obstacles and other sub-targets in a parallelogram formed by two nodes. 9 .

9. The apparatus according to claim 6, wherein the second planning module comprises:

a first planning submodule, configured to perform path planning on the second sub-goal graph to obtain a second path;

a mapping submodule, configured to map the nodes in the second path to the image to be processed to obtain the second path point in the image to be processed;

The second planning submodule is configured to perform deception path planning on the image to be processed based on the second path point to obtain the target path.

10. The apparatus according to claim 9, wherein the first planning sub-module is specifically used for: