CN120027800A

CN120027800A - A three-dimensional low-altitude urban operation guidance method for UAVs based on lightweight mission templates

Info

Publication number: CN120027800A
Application number: CN202510483429.9A
Authority: CN
Inventors: 马宝萍; 孟庆民; 谢非
Original assignee: Nanjing Normal University
Current assignee: Nanjing Normal University
Priority date: 2025-04-17
Filing date: 2025-04-17
Publication date: 2025-05-23
Anticipated expiration: 2045-04-17
Also published as: CN120027800B

Abstract

The present invention discloses a method for guiding low-altitude urban operations of unmanned aerial vehicles based on lightweight task templates, including: after the UAV-Agent enters the geographic fence, it collects environmental information and constructs a three-dimensional rasterized graph structure, in which homogeneous nodes represent key points of plane paths and heterogeneous nodes represent three-dimensional spatial path relationships; dynamically updates the task template based on mobile edge computing and stores the guidance path information; the user machine requests the path from the navigation station through lightweight interaction, the navigation station matches the optimal guidance path and gives feedback, and the user machine autonomously navigates along the key points. The innovation of the present invention lies in: using a heterogeneous node graph structure to model the three-dimensional airspace of the city to achieve multi-layer path planning; based on the dynamic update mechanism of the lightweight task template, reducing communication overhead; combining the key point optimization algorithm of geometric topology to improve navigation safety. Compared with traditional route planning, this solution can significantly reduce the consumption of computing and communication resources.

Description

Unmanned aerial vehicle three-dimensional low-altitude city operation guiding method based on lightweight task template

Technical Field

The invention relates to unmanned aerial vehicle control, in particular to an unmanned aerial vehicle three-dimensional low-altitude city operation guiding method based on a lightweight task template.

Background

In existing unmanned aerial vehicle control schemes, unmanned aerial vehicle flight path planning typically requires static map data to obtain geographic basic information, such as longitude, latitude and altitude information, for each flight point in an initial path. However, in urban complex environments, unmanned aerial vehicles for logistics, courier, inspection and area coverage require dynamic unmanned aerial vehicle handling and dynamic path planning schemes. Thus, the unmanned aerial vehicle control system needs to perform periodic information interaction with various map data APIs through the mobile edge server to acquire geographic basic information different from the flying point on the initial path. For ground unmanned vehicles, such information interaction may solve existing problems in path planning. However, for unmanned aerial vehicles in urban three-dimensional complex environments, the information interaction needs to occupy a large amount of communication and calculation resources, and further, accurate unmanned aerial vehicle planning needs to be established and accessed by a large-scale high-precision dynamic map base platform. The high-precision dynamic map base platform is considered as a core support for realizing safe and efficient operation of unmanned aerial vehicle logistics and express delivery. There is no fully developed high-precision dynamic map platform special for unmanned aerial vehicles.

In order to meet the demands of logistics, express, inspection and regional coverage in urban complex environments, static and dynamic time-space data are required for unmanned aerial vehicle flight path planning. However, existing high-precision dynamic map platforms and bird's-eye view (BEV) databases are not mature, which limits the efficiency and safety of unmanned aerial vehicle low-altitude city planning.

Disclosure of Invention

Aiming at the defects, the invention provides the unmanned aerial vehicle three-dimensional low-altitude city operation guiding method based on the lightweight task template, which is high in control efficiency.

The invention adopts a three-dimensional low-altitude city operation guiding method of an unmanned aerial vehicle based on a lightweight task template, which comprises the following steps:

(1) The unmanned aerial vehicle intelligent Agent UAV-Agent enters the geofence and sends a starting point acquisition instruction to a navigation station in the geofence;

(2) After receiving the start point acquisition instruction, the navigation station feeds back start point and end point information in the geofence and correct receiving information ACK to the UAV-Agent;

(3) The UAV-Agent plans an initial path to run from a starting point to a terminal point according to the fed-back information, acquires environmental information in the geofence in the running process, constructs a preliminary task template according to the acquired environmental information, and updates the task template through a mobile edge server;

the task template comprises a graph structure obtained by rasterizing the three-dimensional low-void region map, a plurality of path key points and a plurality of guide paths planned according to the graph structure and the path key points;

(4) The updated task template is sent to a navigation station, and the navigation station adopts a path planning algorithm according to the path key points on the guide path in the task template to carry out path planning on the guide path so as to obtain a smooth navigation path;

(5) A user machine entering a starting point in the geofence sends a task request to a navigation station;

(6) After receiving the task request, the navigation station selects guide path data from the task template and feeds back the guide path to the user machine;

(7) After receiving the guide path data and the navigation path, the user machine starts the subsequent process of autonomous navigation and sequentially passes through the path key points on the guide path;

(8) When the navigation task is finished, the user machine informs the navigation station and the navigation station feeds back ACK to the user machine.

Further, the task template comprises a task type and a corresponding flow, a navigation station longitude and latitude and height, a geofence boundary, a longitude and latitude and height of a starting point and an ending point in the geofence, the number of guide paths, the longitude and latitude and height of a plurality of path key points, a plurality of guide paths, a region ID set after three-dimensional low-altitude region rasterization, a region ID index and a region topological relation.

Further, the construction steps of the graph structure in the task template are as follows:

(31) Dividing a three-dimensional low-altitude urban structure in a geofence into a plurality of grids containing geometric topological relations;

(32) Mapping the grid into a plurality of virtual roads, abstracting one virtual road into a graph structure of isomorphic nodes, and storing a single path and path key points on the path and graph calculation related to path planning in the graph structure of each isomorphic node, wherein the graph structure describes the connection relation of different areas in the environment;

(33) The edges of the graph structure are weighted.

Further, the path planning algorithm comprises an improved RRT-star algorithm, wherein the improved RRT-star algorithm assists sampling of sampling points in the RRT-star algorithm through path key points, and specifically comprises the following steps:

Sequentially taking the path key points on the guide path as priori positions;

For a section between a starting point and a path key point, acquiring a priori position, finding a node closest to the priori position, confirming coordinates of a target point, taking a rectangular area formed by the closest node and the target point as a sampling area, and performing target deflection sampling in the sampling area to obtain a new node;

and calculating a new local target position according to the scaling factor, the priori position and the coordinates of the nearest node for the interval between the two path key points, finding the node nearest to the new target position, taking a rectangular area formed by the node nearest to the new target position and the local target position as a sampling area, and performing target deflection sampling in the sampling area to obtain the new node.

Further, calculating the synthesis cost of the track planned by the improved RRT-star algorithm, and updating the weight of the edge in the graph structure through the synthesis cost, wherein the synthesis costThe calculation formula is as follows:

;

Wherein, Is a nodeIs used for the height value of the (c),Is a nodeIs used for the height value of the (c),As a function of the energy consumption caused by the height variation,For the distance of the trajectory from the nearest obstacle,、AndIs a weight coefficient.

Further, the path planning method adopted by the initial path in the step (3) comprises an A-type algorithm, a Dijkstra algorithm and an RRT algorithm, wherein the acquisition of environmental information in a geofence in the running process comprises image acquisition, position information request and geographic API call, and the acquisition of data of a path key point;

After the UAV-Agent reaches the end point, the acquired information is used for generating an initial task template, the initial task template is uploaded to a database of the mobile edge server MEC SERVER, the initial task template is calibrated and updated by MEC SERVER, the updated task template is fed back to the UAV-Agent, the UAV-Agent downloads the updated task template to the navigation station, and the UAV-Agent leaves a service area related to the geofence after receiving the ACK sent by the navigation station.

Further, the task template also includes space limitation boundaries, flow data, and weather data.

Further, in the step (6), after the navigation station receives the task request, when the navigation station collects the real-time congestion degree data, the navigation station performs graph calculation to obtain a suboptimal guiding path.

The invention also employs a computer device comprising a memory, a processor and a computer program stored on the memory and executable on the processor, the processor implementing the steps of the above method when executing the computer program.

The invention also employs a computer readable storage medium having stored thereon a computer program which when executed by a processor realizes the steps of the above method.

Compared with the prior art, the method has the advantages that the method effectively supports low-altitude unmanned aerial vehicle navigation and path planning through the navigation station with the lightweight task template, the user machine needs to interact with the navigation station once instead of periodically and dynamically receiving the instruction from the dynamic map API, and the method is beneficial to saving communication and calculation resources and improving the unmanned aerial vehicle control efficiency. And path planning is carried out by utilizing the priori key points, so that the safety of unmanned aerial vehicle low-altitude city planning is improved.

Drawings

FIG. 1 is a schematic diagram of a flow of information collection and processing in a lightweight mechanism according to the present invention.

FIG. 2 is a schematic diagram of the information transfer flow in a navigation task in the present invention.

Fig. 3 is a schematic diagram of a flight path of a low-altitude unmanned aerial vehicle or a ground vehicle running path in the invention.

FIG. 4 is a schematic diagram of a simulation process of the structure of FIG. 4 in the present invention.

Fig. 5 is a schematic diagram of a graph structure of a heterogeneous node in the present invention.

Fig. 6 is a schematic flow chart of a single-keypoint guided sampling method 1 according to the present invention.

Fig. 7 is a flow chart of the double-key-point guided sampling method 2 in the present invention.

Detailed Description

In this embodiment, an unmanned aerial vehicle three-dimensional low-altitude city operation guiding method based on a lightweight task template includes the following steps:

as shown in fig. 1, the process of collecting and processing lightweight geographic information is not used for constructing a high-precision dynamic map, but is used for constructing a low-altitude unmanned aerial vehicle navigation knowledge base for logistics, express delivery, inspection and other applications, and the information flow of each entity in fig. 1 is represented by an arrow.

(1) After the UAV-Agent entering the geofence sends a start acquisition instruction to the navigation station, the navigation station feeds back correct receiving information (ACK) to the UAV-Agent. The UAV-Agent will then fly from the start point to the end point along an initial path that may be derived from the use of path planning methods such as the a-algorithm, dijkstra algorithm, RRTs algorithm, etc. At the same time, UAV-Agent with conventional image processing or specific personal intelligence will perform image acquisition, position information request and geographic API call, and assign the key point data in the path to BEV image attribute to complete attribute labeling of the key points in the graph structure. ID2 taken 0 means that the UAV-Agent opens the camera to acquire BEV images. The map API call accesses a remote geographic database through MEC SERVER.

(2) After the UAV-Agent reaches the end point, the image acquisition is ended and an initial task template is generated, and is uploaded to a MEC SERVER database. Alternatively, if the UAV-Agent has specific personal intelligence, it can perform visual language navigation functions in real-time, such as using computer vision to implement context awareness and target recognition, parsing navigational intents in text, and uploading updated versions of the task template. When ID2 takes 3, its navigational intent is summarized as determining the 1 st path keypoint, and the 1 st path keypoint is within the line of sight of the origin. Optionally, the visual language navigation function can convert voice instructions into text to facilitate generating path keypoints for other conditions in combination with visual and linguistic information.

The task templates are subclasses in the standardized interfaces, and the standardized interfaces are defined, so that interoperability among modules is ensured, and the integration difficulty is reduced. The task template facilitates interoperability of the Large Language Model (LLMs) and various modules in the Agent's unmanned aerial vehicle control system. The unmanned aerial vehicle steering system includes a user machine, a navigation station, an unmanned aerial vehicle intelligent Agent (UAV-Agent), and a mobile edge server (MEC SERVER).

Autonomous navigational vehicles on the ground and low-altitude UAVs (un-managed AERIAL VEHICLE) are represented by User machines (User machines) and can communicate with a navigational station through a wireless interface. A navigation station (The Navigation Station) integrating a wireless interface and a wired interface may communicate with the UAV-Agent or with MEC SERVER. Table 1 is a semantic entity, i.e., a task template, designed to relate navigation scenario semantic understanding to data acquisition and processing flows.

TABLE 1 initial task template

The set of ID1 for the acquisition and navigation task is {0,1, & gt, m_id1}. When ID1 takes 0 and 1, the acquisition task and the navigation task are represented, respectively.

The ID2 set for navigation and operation tasks is {0,1, & gt, m_id2}. When ID2 takes 0 and 1, flow 1 (see fig. 1) employed in collecting a task and flow 2 (see fig. 2) employed in navigating a task are represented, respectively. When ID2 takes 1, the UAV-Agent opens the camera for environmental perception to obtain the BEV and calculate the building height. Optionally, the UAV-Agent turns on the lidar sensor in order to more accurately estimate building contours and altitude values. When the ID2 is taken to be 2, based on the flow 2, the unmanned aerial vehicle in the navigation task opens a camera to perform environment sensing, data processing and dynamic autonomous navigation.

The ID2 fetch 3 case is discussed in some detail in this embodiment, as it requires the UAV-Agent to possess specific visual language navigation functionality, depending on what LLMs dense model it employs. When ID2 takes 3, based on flow 2, in the geofence, the 1 st path keypoint is located on the origin line of sight (see fig. 3). The ID2 get 4 case is optional, where the navigation station in the navigation mission interacts with the UAV-Agent, which can dynamically update the knowledge base in the navigation station to cope with sudden low-altitude traffic congestion events.

ID3 contains the longitude and latitude and altitude of the navigation station, the longitude and latitude and altitude of the start point and end point, the geofence boundary and area ID set, and the number of guide paths. The Region (Region) here is an extension of the conventional three-dimensional grid concept. Referring to fig. 4, the projections of a plurality of successive three-dimensional grids on one guide path are rectangular areas and the height parameters are identical, and referring to fig. 5, a three-dimensional grid with the same height parameters is defined as an area. The number of guide paths in the geofence is M_ID3, the longitude, latitude and altitude of the navigation station are tuples (x, y, z), and the guide paths represent paths from the start point to the end point.

ID4 contains a guide path i, an area ID index, and an area topology relationship.

ID5 contains the number of keypoints in the guide path i.

ID6 contains various types of keypoints such as the longitude, latitude, and altitude of the keypoints of a path, a low-altitude obstacle (e.g., wire, tree), and a ground building type obstacle. On a guiding path, these key points are sequential.

ID7 contains airspace restriction (e.g., no-fly zone) boundaries, traffic data, and corresponding weather data. It is herein noted that airspace restriction (e.g., no-fly) boundaries and geofence boundaries are conceptually interchangeable. When the geofence boundary is physically present, it is a airspace-limited boundary, and when the geofence boundary is virtual, a boundary is added to the BEV map for region division, labeling, and subsequent search interval definition of RRT-star.

Alternatively, ID8 and thereafter is defined similarly to ID4-ID 7. But ID8 guide path i+1 may correspond to other path planning requirements, such as unmanned path planning at other altitudes, unmanned path planning for low-altitude emergency roads, etc. LLMs and agents can be used to help understand the different path planning requirements, as the inputs to these requirements may be text and images. Thus, the geofence boundary definition for ID3 in Table 1 may employ a sort of hybrid linked list. The linked list may contain the individual region labels and the keypoint labels in each region and it may also contain a link to a BEV graph with semantic labels.

The UAV-Agent is responsible for basic low-altitude geographic data acquisition and partial data processing. When the number of the guide paths is greater than 1, the guide path i and the guide path i+1 will adopt different path tracks, which causes the linked list length of table 1 to be increased continuously, and also causes great complexity of storing and searching the guide path and the key point. To facilitate data processing and analysis in geographic information collection, UAV-agents need to employ LLMs and agents to efficiently extract geographic information parameters from linked lists and to facilitate ensuring inter-module interoperability in the unmanned aerial vehicle navigation system involved.

Table 1 divides the low altitude into a plurality of grids containing geometric topological relations, and each grid of rectangular solid is expressed as the left lower corner vertex, the longitude and latitude of the right upper corner vertex and the height of the left lower corner vertex. For the convenience of evaluation, it is assumed that the range d_h of the vertical direction of each grid is the same. Then, d_h is the distance between two neighbors in the vertical direction or the lane safety interval. This forms a virtual lane in urban low air.

The grid is mapped into a graph structure, and the table 1 mainly defines semantic information of the low-altitude city planning, and the graph structure is a data structure which is convenient for storing, searching and calculating geographic information data of the low-altitude city planning. As shown in fig. 4, the simulation of grids, graph structures and found guide paths or trajectories in low-altitude city planning is shown in order from top to bottom.

The method comprises the steps of storing a graph structure, carrying out fast direction shortest path of an RRT-star algorithm under the assistance of key points, updating edge weights in the graph structure by the output of the RRT-star algorithm, and carrying out graph calculation to recalculate the synthesis cost of path planning and evaluate the synthesis cost of unmanned aerial vehicle switching of adjacent heights. Further, since the LLM agent can process the collected measured data at the navigation station, static map structure updates and map calculations in the navigation knowledge base are performed sequentially, the output of which will include the shortest path and the switch predictions of the nearby low-altitude roads, etc.

In short, the above expression forms a different unmanned aerial vehicle navigation method from the previous one, namely a process that allows the navigation system to simulate, monitor and optimize performance in real time, and the closed loop advantage thereof makes the static diagram structure adaptable to dynamic space-time flow.

The global access order defines the geometry of four adjacent grids. For height i, the rectangular areas from left to right are area 0, area 1 and area 2, and area 3 in that order. Region 1 is identical to the left edge line of region 2, which indicates that region 1 is adjacent to region 2 to the right, region 0, and that there is an intersection on the map where the left edge line of region 0 is located, the left and right branches (of region 0) reaching regions 1 and 2, respectively. The roads of the height i and the height i+1 are in an up-down topological relationship.

Implementation of isomorphic diagrams in a static isomorphic type of diagram structure, each node represents a rectangular region (projection of a three-dimensional grid) with lane safety intervals, node attributes see constructor __ init __,

def __init__(self, rect_id, attr0=Node((0,0)), attr1=Node((0,0)), attr2=0, attr3=0, attr4=0, attr5=Node((0,0)), attr6=Node((0,0)), attr7=Node((0,0))):

The constructor __ init __ is used to initialize the instance of the node_rect class, whose definition can be further optimized according to the actual requirements. It accepts parameters such as:

rect_id, unique identifier of rectangular region.

Attr0, longitude and latitude of the left lower corner of the rectangular area, and default value is (0, 0).

Attr1, longitude and latitude of the right upper corner of the rectangular area, and default value is (0, 0).

Attr2 number of reference points in rectangular area, default value is 0.

Attr3, the height of the rectangular area, default value is 0.

Attr4, the congestion index of the rectangular area, such as the number of obstacles, defaults to 0.

Attr5, latitude and longitude of reference point 0, default value is (0, 0).

Attr6, latitude and longitude of reference point 1, default value is (0, 0).

Attr7, latitude and longitude of reference point 2, default value is (0, 0).

Edge type definitions in a dynamic graph structure typically include connection relationships (e.g., road to intersection connections), traffic flow, speed limits, and congestion levels. In the evaluation experiment, the synthesis cost is used so that the definition of the static isomorphic map can be extended to the dynamic iso-composition.

Implementation of iso-patterning a Directed Acyclic Graph (DAG) is constructed by a method similar to isomorphic diagrams to simulate rectangular region relationships (with lane safety intervals) in three-dimensional geographic space. Referring to fig. 5, an example of an implementation of a heterogeneous graph for evaluating road switching is outlined below, which contains defining node classes and rectangular node classes, creating nodes and building connection relationships, creating graph structures using NetworkX, merging graph structures, drawing graphs using Matplotlib, calculating shortest paths, and so forth.

A functional description of creating nodes and constructing connection relations is as follows, two sets of nodes node0_0, node1_0, node2_0, node3_0 and node0_1, node1_1, node2_1, node3_1 are created, representing rectangular areas on two levels, respectively.

Using NetworkX to create a functional description of the graph structure is as follows:

Two directed graphs G0 and G1 are created, representing graph structures on two height layers, respectively. Nodes and edges are added to the graph and weights are given to the edges.

The functional description of the merging graph structure is as follows:

a new directed graph G is created, adding the nodes and edges of G0 and G1 to G. The addition of the edge between G0 and G1 represents the switching of the drone between the different height layers.

Functional descriptions of drawing graphics using Matplotlib are as follows:

The location pos and label labels of the node are defined. Common nodes and heterogeneous nodes are represented using different shapes and colors. And drawing the nodes and the edges, and displaying the labels in the center of the nodes.

The functional description of calculating the shortest path is as follows:

the shortest path and path length from node 0 to node 4, node 4 to node 7, and node 7 to node 3 are calculated using a path planning algorithm. These paths are combined to give the complete path and total length from node 0 to node 3 through nodes 4 and 7.

Optionally, the heterograph-based path planning may take into account a variety of factors such as shortest path, least time, least congestion, etc. Note that in actual unmanned aerial vehicle path planning processes greater than 10 meters, the local environmental information found by the cameras and lidar is typically fused to further improve the performance of the single feature (euclidean distance) based path planning scheme.

The heterograph-based path planning may be based on a priori knowledge, i.e., one or more key points on the guided path, to effectively reduce reliance on predicted trajectories, which typically contain a large number of sample points. Unmanned aerial vehicle navigation system design should also take into account how to deal with the problem of dead reference points in the predicted trajectory if the time-variant of low-altitude obstacle position is not negligible.

In particular, the output of the a priori RRT-star simulation shown in this embodiment is fed back into the graph structure so that the edge weights can be updated according to the measured data.

Considering that the accuracy of BEV scene understanding based on conventional image processing is poor, the present embodiment proposes a key point selection strategy. Considering that BEV scene understanding can roughly identify four edge lines of a rectangular area, such as up, down, left and right, and the like, selecting a position with a horizontal coordinate slightly larger than the midpoint of the left edge line of the rectangular area as a first key point of each rectangular area can avoid recognition errors of BEV scene understanding over a certain length. Of course, more reference points can be taken per rectangular area. The horizontal range of the area 0 in fig. 3 is greater than 150 meters, so that the area 0 contains 3 reference points (start point 1, path key point 9, navigation station 10), and the area 0 contains building type obstacles (3, 4, 5, 6), low-altitude unmanned suspension type obstacle 7, and low-altitude wire type obstacle 8. In addition, LLMs and agents can be used to parse the navigation intent in the text, improving the accuracy of BEV scene understanding.

In fig. 3, the a priori RRT-star algorithm can find the trajectory of the start 1 to end 2, the output of which is fed back into the graph structure at the cost of synthesis (see definition later). Assuming a constant drone height h ₁, the three-dimensional grid is projected as a two-dimensional rectangular area, the rectangular areas traversed by the trajectory are area 0 (region 0) area 1 and area 3, respectively, because of the high degree of congestion assumed in area 2. In a future urban ultra-low altitude scenario, such as in the 1 meter to 45 meter altitude range, unmanned aerial vehicle flights encounter a large number of unpredictable dynamic obstacles in addition to static obstacles, which makes the timeliness of the output trajectories of static path planning algorithms challenging, which also results in difficult realization of path planning targets accurate to sub-meter and sub-second levels. Therefore, according to the actual requirements, the actual path planning algorithm needs to run at regular time to acquire the latest navigation track.

To quickly give a demonstration of the use of a task template (only when ID2 takes 3), in the geofence, the 1 st path keypoint is located on the starting point line of sight. The 1 st and 2 nd path keypoints are referred to as a drone a priori position 1 and a priori position 2, respectively, and the navigation station is located at a priori position 2.

The reference RRT-star (2) to (4) steps are modified using the example, with reduced sampling random points with key points or a priori positions from the pilot path data, compared to the reference RRT-star (see RRT-star and its modifications below). Second, the method is characterized by the following steps. It also integrates target bias sampling. The method is a key point guided RRT-star path planning method, and is designed as follows in detail.

Considering the autonomous navigation scene of a low-altitude unmanned aerial vehicle in an urban street or an urban canyon, the unmanned aerial vehicle faces the challenges of lack of high-precision dynamic maps, weak GPS signals and cellular communication signals, different change of space-time low-altitude interference from ground navigation and the like. The unmanned aerial vehicle path planning framework combining the graph structure and the RRT-star algorithm is considered, and the framework not only provides key points on a suboptimal path for the unmanned aerial vehicle, but also can timely generate a temporary path when a pre-planned path cannot be used. Even, at the origin only, the user machine needs to interact once with the navigation station, rather than periodically and dynamically receiving instructions from the dynamic map API, which helps save communication and computing resources. By using the priori key points, the unmanned aerial vehicle and the navigation station can simulate path planning, so that the shortest path is calculated before navigation. However, since the navigation station can acquire real-time road conditions of beyond-sight distance, the simulation at the navigation station can acquire more effective track prediction, thereby playing the role of traffic lights in urban low altitude.

The method comprises the steps of (1) initializing a tree, namely taking a starting point as a root node of the tree, (2) sampling the random point, namely randomly generating a point in a search space, (3) expanding the tree, namely finding the nearest node in the tree and expanding a new node towards the random point, (4) reconnecting, namely checking nodes in a certain range around the new node, attempting reconnection through the new node to reduce the path length, and (5) updating the path cost, namely updating the path cost of all affected nodes in the tree. And (3) repeatedly iterating the steps (2) to (4), and finally finding an optimal path from the starting point to the target to serve as a navigation path.

The advantage of the euclidean distance based, probabilistic sampled and incremental sampled reference RRT-star is that it can quickly find the initial path and then optimize it continuously as the number of samples increases. They have moderate computational complexity and can find solutions without using explicit information about obstacles in the configuration space. They rely on a collision-checking module and construct a roadmap of feasible trajectories by connecting together a set of points sampled from the unobstructed space.

In general, the reference RRT-star needs to be expanded from the aspects of obstacle avoidance requirements, flight dynamic constraints, environmental complexity, real-time performance and the like, so as to effectively process the safety requirements and flight constraints of the unmanned aerial vehicle in the urban complex three-dimensional environment. In particular, the idea of visual language navigation is introduced into the information flow and the device of the unmanned aerial vehicle navigation system, and a key point assisted RRT-star path planning example is provided, and the innovative strategy is a single key point assisted sampling method 1 and a double key point assisted sampling method 2 as follows. Referring to fig. 3, at the beginning of a navigation task, the navigation station selects one or more guidance path data according to the need and issues the guidance path data to the user equipment. See table 1 for the case of ID2 taken 3, where the guidance path data contains a definition of the key point. Sampling-based method 1 is used from the start point to the 1 st key point, and sampling-based method 2 is used from the 1 st key point to the 2 nd key points. When the key point is more than 2, recycling the method 2.

Aiming at navigation tasks, the sampling method 1 for key point guidance is provided, and a more direct straight line path is provided for the unmanned aerial vehicle with a certain probability. The local node expansion method can quickly find the initial path using the priors provided by the single key point (SingleKeypoint) to reduce random space exploration and avoid redundancy of the reference RRT-star in local sampling. This strategy typically requires a quick finding of routes greater than 10 meters in combination with the output of a camera or lidar.

The prior location is used to guide the sampling process, unlike the sampling random point step in the reference RRT-star algorithm. By sampling near the pre-test location, the user machine can more effectively explore the region of interest, improving the efficiency of path planning or graphics processing. When ID2 takes 3, a priori position 1 is the keypoint 1 and a priori position 2 is the keypoint 2 (navigation station position). When ID2 takes 4, then it is a functional extension of ID2 taking 3, which is not discussed here. The following sequentially illustrates the function of the single-key-point guided sampling method 1 and the function of the double-key-point guided sampling method 2, and finally the description refers to a sampling strategy crossing the boundary of two areas.

Function parameters of single-keypoint guided sampling method 1:

There is only one parameter self in the definition of the method. It is used in this function to access and manipulate the instance variables and methods of the RrtStar classes.

The method comprises the following steps:

1) The method is defined as follows:

This is an example method. It has no parameters (other than self described above) and will operate using the attributes of the class.

2) Computing a priori indices

Self.priority_locations is a list containing a priori locations, self.index_ref is a reference index (which in this patent implementation refers to the keypoint index). The index of a priori position is obtained by subtracting len (self.priority_locations) -self index_ref. When self.index_ref <0, indicating that the keypoint has been exhausted, the proposed keypoint guided RRT-star will perform (2), (3), (4) and (5) of the reference RRT-star.

3) Acquiring a priori position

And (3) extracting the element with index of index_priority from the prior position list, and transmitting the coordinates to the Node class instance node_rand.

4) Finding the nearest node

The node_nearest nearest to node_rand is found using the nearest_neighbor method, possibly as a list or set containing all nodes.

5) Defining target point and sampling region boundaries

Target_local is the coordinates of the target point, bounds _local defining the boundary of the sampling area. Here the boundary is a rectangular area constituted by the closest node and the target point.

6) Sampling target bias

Target bias sampling is performed within a defined sampling region using goal _biased_sampling method. goal _bias_prob is the probability of target biased sampling, provided by self. The sample result sample is used to create a new node new.

7) Returning the result

The method returns the prior position priority_pos, the nearest node_near, and the newly sampled node_new.

A flow chart of the single-keypoint guided sampling method 1 is shown in fig. 6.

For a priori sampling in a specific local area, i.e. target biased sampling based on dual keypoints and local scale parameters and generating new sampling points.

Functional parameters of the double-keypoint guided sampling method 2:

self, an instance of a class is commonly referred to, indicating that this is a class approach.

Prior_pos, a priori position, represents the double-key point (longitude, latitude and altitude) referenced at the time of sampling.

Node_near-the node closest to a certain target point.

Local scale-local scale parameter for controlling the range of the sampling region.

The method comprises the following steps:

1) Initializing a new node list

An empty list node new list is created for storing the newly generated nodes.

2) Cyclic sampling

The local_scale is cycled through, generating a new sampling point each time.

3) Calculating new local target positions

A scaling factor scale is calculated based on the current number of loops freit and local_scale, and then the new local target position target_local_new is calculated using the factor and the coordinates of the prior position priority_pos and the nearest node_near.

4) Finding the node closest to the new target

The nearest node to the new target position target_local_new is found using the nearest_neighbor method and node_near is updated.

5) Defining a sampling range

The sampling ranges bounds _local, i.e., the ranges of x and y, are defined as the coordinates of node_near and target_local_new, respectively. As described above, the use example of the task template omits the height parameter z.

6) Sampling target bias

And performing target bias sampling within a defined range by using goal _used_sampling method to generate a new sampling point sample. goal _bias_prob is a probability parameter for target biased sampling.

7) Adding a new node to a list

And converting the generated sampling point sample into a Node object, and adding the Node object into a node_new_list list.

8) Returning a new node list

A list node new list is returned containing all newly generated nodes.

Supplement to the implementation of the path planning method:

1) The search_neighbor and goal _embedded_sampling are defined in two related codes, which need to be implemented in advance. The nearest_neighbor is used to find the nearest node.

2) Goal _biased_sampling is used to sample target bias within a specified range.

3) Self.vertex is a list or data structure containing all nodes.

4) Self. Direct_prob is a probability parameter for the target to bias towards the sample, used to control the degree of bias towards the target at the time of sampling.

5) The method assumes that Node is a custom class containing x and y attributes for representing coordinates (longitude and latitude) of the Node. As described above, the use example of the task template omits the height parameter z.

A flow chart of the dual keypoint guided sampling method 2 or strategy is shown in fig. 7

The evaluation experiment adopts a synthesis cost. By comprehensively considering the distance, the height, the energy consumption and the obstacle distance, an RRT-star cost function meeting actual requirements is designed, and the selection of the weight coefficient is required to be adjusted according to specific application scenes. The synthesis cost is as follows:

;

Where h ₁ and h ₂ are the height values of nodes q ₁ and q ₂, respectively, E (h ₁,h₂) is an energy consumption function caused by the change in height, generally proportional to the difference in height, d (q ₁,q₂) in the obstacle distance penalty term is the distance of the trajectory from the nearest obstacle, and λ ₁、λ₂ and λ ₃ are weight coefficients for balancing the effects of each.

(3) MEC SERVER feeds back updated versions of the task templates to the UAV-Agent.

Because of the complex environment of low-altitude cities, UAV-Agent's environmental awareness and target identification information may deviate, airspace limitations may be updated in real-time and new navigational vision language inputs. Therefore, MEC SERVER is required for calibration and update.

(4) The UAV-Agent downloads an updated version of the task template to the navigational station.

Through the UAV-Agent, the navigation station will acquire a low-altitude unmanned aerial vehicle navigation knowledge base.

(5) After receiving the ACK sent by the navigation station, the UAV-Agent leaves the service area related to the geofence.

The UAV-Agent cruises in several geofences of the urban grid to download a low-altitude unmanned aerial vehicle navigation knowledge base to the distributed navigation stations.

The key point of fig. 1 is to demonstrate the information transfer process between the entities and how to cooperatively complete the construction of the low-altitude unmanned aerial vehicle navigation knowledge base. This is necessary to understand the working mechanism of the unmanned aerial vehicle navigation system and the light-weight interactions between the various components.

As shown in fig. 2, the navigation task is performed, and the information transfer flows between the user machine, the navigation station, the UAV-Agent, and MEC SERVER, four of which represent the user machine, the navigation station, the UAV-Agent, and MEC SERVER, respectively. There are multiple arrows between each boundary line, representing different messaging procedures.

(1) The user machine entering the beginning of the geofence sends a navigation task request to the navigation station. Here, the user machine has a low-level visual language navigation function, and can issue different forms of navigation task requests, such as instructions, text, and even voice memos.

(2) After receiving the request, the navigation station selects guide path data from the task template and feeds back the guide path to the user machine. When the navigation station collects real-time congestion degree data, the navigation station will execute graph calculation to obtain suboptimal navigation paths. When the navigation task request of the user machine is text or even a voice prompt, the navigation station utilizes the local personal intelligent module to understand the navigation task request. Thus, the navigation station is a device having a medium or high-level visual language navigation function.

(3) After receiving the guiding path data, the user machine starts the subsequent process of autonomous navigation. It passes in turn through the path keypoints on the guiding path and utilizes low-level control to fine tune the (virtual) lanes within 10 meters to cope with disturbances in three-dimensional space, such as static ground buildings, wind-moving wires and branches and surrounding drones.

(4) When the navigation task is finished, the user machine informs the navigation station and the navigation station feeds back ACK to the user machine.

(5) Finally, UAV-Agent communicates with MEC SERVER, stores path trajectories, updates task templates, and the like.

FIG. 2 illustrates the information transfer process between the user machine, the navigational station, the UAV-Agent, and MEC SERVER, illustrating how the low-altitude UAV and its ground autonomous navigational vehicle share information with the navigational station via a wireless interface. The dynamic interaction of the navigational station with the UAV-Agent (when ID2 takes 4) is not reflected here, and it is optional. This is important for understanding both the workflow and the communication mechanism of autonomous navigation systems.

When ID2 is 1, 2,3 and 4, the unmanned aerial vehicle control system utilizes the constructed unmanned aerial vehicle navigation knowledge base. When ID2 takes 3, the key point is also referred to as a priori (priority) position. With the assistance of other components or sensors (e.g., cameras, lidar, millimeter wave radar, etc.), the navigation station will be responsible for coordinating navigation and path planning of the drone within the geofence. The geofence may contain 1 navigation station or a plurality of navigation stations, the drone being not specifically located within the viewable range of the navigation stations.

In path planning experiments, a class is used to define environmental parameters and obstacles. Setting a longitude and latitude related coordinate range x_range= [ -20,250] and y_range= [ -40,40] (meter), taking the height z_range to be 15-45 meters, and initializing boundary barriers, rectangular barriers and circular barriers through the obs_boundary, obs_circle and obs_rectangle functions to realize the configuration of environmental constraint conditions required to be considered when planning a path. Geofences take a number of rectangles of different heights. Referring to fig. 3, each rectangular area in the benchmarking includes 1 or more rectangular obstacles in addition to the boundary obstacles simulating the geofence. The navigation station is located between 2 rectangular obstacles and it is not within the line of sight of the origin.

The task templates referred to in Table 1 and the graph structures referred to in FIGS. 4 and 5 are further described and supplemented in two paragraphs below. Table 1 is a semantic entity which is suitable for carrying out semantic understanding of navigation scenes by LLMs and agents and relates to a data acquisition and processing flow, and a graph structure is a data structure which is convenient for modeling three-dimensional (virtual) roads and lanes, and the three-dimensional airspace of a city is modeled by using heterogeneous nodes, so that multi-layer path planning at different heights is convenient to realize. The UAV-Agent is responsible for the first task template build, and the semantic entity it outputs is the initial entity, but the low-altitude flight management system under consideration can dynamically update the task template based on the mobile edge calculation. The task templates and graph structures are downloaded to the navigation station. The navigation station can perform not only graph calculation but also RRT-star simulation. As previously described, the guided path in table 1 contains several path keypoint parameters, but the nodes of the graph structure are not directly equivalent to the path keypoints in table 1. Referring to the two-dimensional plane in fig. 3, the midpoint of the left boundary of an area is only one of the path keypoints. The guidance paths referred to in table 1 are merely a static, initial set of path planning parameters, and do not necessarily contain coordinates of a large number of points in the trajectory, nor do they take into account kinematic constraints and dynamic obstacles in local scope navigation. In short, the need for a safe and smooth path is not separated by the RRT-star algorithm, and the pilot path is simply a sample of the trace output by the RRT-star. Second, the definition of the initial graph structure requires the use of the parameters in table 1. After the RRT-star is executed, the edge weights of the original graph structure will be reset to the edge weights of the new graph structure.

The above description and additions are continued. The navigation station adopts RRT-star algorithm to carry out path planning by utilizing the key points of the guiding paths in the table 1. The purpose of setting the guide path in the task template is planning across multiple areas. Thus, the task templates focus on semantic region guidance, the graph structure facilitates evaluating multi-layer path planning to accommodate dynamic low-altitude traffic, while RRT-star focuses on local navigation planning. Because the boundaries of the two regions may be different, conventional RRT-star algorithms are very sensitive to boundary parameters and tend to trap local traps at the boundaries of the two regions. At this time, another target biased RRT-star algorithm, namely a sampling strategy crossing the boundary of two areas, can be realized by using the prior reference points provided by the task template.

For the summary of the two paragraphs, the invention creatively designs the semantic entity, the graph structure realization and the target biased RRT-star, and enables the three phases to complement each other.

Claims

1. A method for guiding three-dimensional low-altitude urban operations of unmanned aerial vehicles based on lightweight mission templates, characterized in that it comprises the following steps:

(1) The UAV-Agent enters the geo-fence and sends a starting point collection command to the navigation station within the geo-fence;

(2) After receiving the start point collection command, the navigation station feeds back the start point and end point information within the geographic fence and the correct reception information ACK to the UAV-Agent;

(3) The UAV-Agent plans the initial path from the starting point to the end point based on the feedback information. During the operation, it collects environmental information within the geographic fence and builds a preliminary task template based on the collected environmental information. The task template is then updated through the mobile edge server.

The task template includes a graph structure obtained by rasterizing a three-dimensional low-altitude area mapping, a number of key points on a path, and a number of guide paths planned according to the graph structure and the key points on the path;

(4) Sending the updated task template to the navigation station, the navigation station uses a path planning algorithm based on the key points on the guidance path in the task template to plan the guidance path and obtain a smooth navigation path;

(5) The user machine entering the starting point of the geographic fence sends a task request to the navigation station;

(6) After receiving the task request, the navigation station selects guidance path data from the task template and feeds back the navigation path to the user machine;

(7) After receiving the guidance path data and the navigation path, the user machine starts the subsequent process of autonomous navigation and passes through the key points on the guidance path in sequence;

(8) When the navigation task is completed, the user machine notifies the navigation station and the navigation station sends an ACK to the user machine.

2. According to claim 1, the three-dimensional low-altitude urban operation guidance method of an unmanned aerial vehicle based on a lightweight mission template is characterized in that the mission template includes the mission type and corresponding process, the longitude and latitude and altitude of the navigation station, the geographic fence boundary, the longitude and latitude and altitude of the starting point and the end point within the geographic fence, the number of guidance paths, the longitude and latitude and altitude of several key points of the path, several guidance paths, a set of regional IDs after rasterization of the three-dimensional low-altitude area, a regional ID index, and a regional topological relationship.

3. The method for guiding three-dimensional low-altitude urban operation of unmanned aerial vehicles based on lightweight task templates according to claim 2, characterized in that the steps of constructing the graph structure in the task template are:

(31) Divide the three-dimensional low-altitude urban structure within the geographic fence into multiple grids with geometric topological relationships;

(32) Mapping the grid into multiple virtual roads, abstracting a virtual road into a graph structure of homogeneous nodes, each homogeneous node graph structure stores a single path and its key points on the path and implements graph calculations related to path planning; the graph structure describes the connection relationship between different areas in the environment; virtual roads of different heights are abstracted into a graph structure of heterogeneous nodes, and the graph structure of heterogeneous nodes includes several paths, and each path has a different height;

(33) Assign weights to the edges of the graph structure.

4. The method for guiding three-dimensional low-altitude urban operations of unmanned aerial vehicles based on lightweight mission templates according to claim 3 is characterized in that the path planning algorithm includes an improved RRT-star algorithm; the improved RRT-star algorithm assists the sampling of sampling points in the RRT-star algorithm through path key points, specifically:

The key points of the path on the guidance path are used as prior positions in sequence;

For the interval between the starting point and the key point of the path, obtain the prior position, find the node closest to the prior position, confirm the coordinates of the target point, use the rectangular area formed by the nearest node and the target point as the sampling area, perform target biased sampling in the sampling area, and sample to obtain a new node;

For the interval between two key points of the path, the new local target position is calculated by the scaling factor, the prior position and the coordinates of the nearest node, the node closest to the new target position is found, and the rectangular area formed by the node closest to the new target position and the local target position is used as the sampling area. Target biased sampling is performed within the sampling area to obtain a new node.

5. The method for guiding three-dimensional low-altitude urban operations of unmanned aerial vehicles based on lightweight mission templates according to claim 4 is characterized in that the synthesis cost of the trajectory planned by the improved RRT-star algorithm is calculated, and the weight of the edge in the graph structure is updated by the synthesis cost; the synthesis cost The calculation formula is:

;

in, For Node The height value of For Node The height value of is the energy consumption function caused by altitude change, is the distance between the trajectory and the nearest obstacle, , and is the weight coefficient.

6. The method for guiding three-dimensional low-altitude urban operations of unmanned aerial vehicles based on lightweight mission templates according to claim 5 is characterized in that the path planning method used for the initial path in step (3) includes: A* algorithm, Dijkstra algorithm, RRT algorithm;

The environmental information collected within the geo-fence during the operation includes image acquisition, location information request and geographic API call to obtain data of key points of the path;

After the UAV-Agent arrives at the destination, it generates an initial task template with the collected information and uploads it to the database of the mobile edge server MEC server. The MEC server calibrates and updates the initial task template and feeds back the updated task template to the UAV-Agent. The UAV-Agent transmits the updated task template to the navigation station. After receiving the ACK sent by the navigation station, the UAV-Agent leaves the service area involved in the geographic fence.

7. The method for guiding three-dimensional low-altitude urban operations of unmanned aerial vehicles based on lightweight mission templates according to claim 6 is characterized in that the mission template also includes spatial restriction boundaries, traffic data and meteorological data.

8. According to the lightweight mission template-based three-dimensional low-altitude urban operation guidance method for unmanned aerial vehicles in claim 7, it is characterized in that in the step (6), after the navigation station receives the mission request, when the navigation station collects real-time congestion data, the navigation station will perform graph calculation to obtain a suboptimal guidance path.

9. A computer device, comprising a memory, a processor, and a computer program stored in the memory and executable on the processor, wherein the processor implements the steps of the method described in any one of claims 1 to 8 when executing the computer program.

10. A computer-readable storage medium having a computer program stored thereon, wherein when the computer program is executed by a processor, the steps of the method according to any one of claims 1 to 8 are implemented.