RU2843719C1 - Method of navigation in difficult places - Google Patents

Abstract

FIELD: navigation.

SUBSTANCE: invention relates to a method of navigation in difficult places. Method comprises collecting data using a quadcopter on which an RTK-GPS, a camera and a LiDAR sensor are installed. Quadcopter is moved over the target terrain, during the flight recording the current coordinates in EPSG 4326 coordinate system and simultaneously capturing synchronized images and point clouds along the movement path, using the LOAM (LiDAR Odometry and Mapping) algorithm to create the initial input map in EPSG 4326 coordinate system, which serves as the basis for further analysis and refinement using QGIS tools, complex geographic objects extraction from the points cloud data with the off-road routes identification, creating the intermediate map taking into account of all geographic objects in GeoTIFF format or in the pixel coordinate system, designating the initial location in EPSG 4326 block, geo-referencing data is received in GeoTIFF format. Global path planner uses the constructed intermediate map and user-defined regions to create real-time paths that meet kinematic constraints, after that, any off-road local scheduler for vehicle manoeuvring is integrated.

EFFECT: high real-time performance of the global scheduler, achieving kinematic feasibility and efficiency of using memory.

2 cl, 5 dwg

Description

AREA OF TECHNOLOGY

The invention relates to navigation methods, namely to navigation methods in hard-to-reach places.

PRIOR ART

To solve off-road navigation problems, hierarchical route planning methods are commonly used, combining global and local approaches, and have become the preferred method. However, each stage of route planning has its own specific challenges. Local route planning in off-road environments must cope with obstacles such as changing terrain elevations (e.g., potholes, ruts, and rocks), sudden environmental changes (e.g., rain), and the need for rapid replanning. On the other hand, global route planning faces the challenges of handling large topographic maps, accurately accounting for geographic features, planning over long periods, and avoiding local minima. While local route planning focuses on ensuring smooth vehicle maneuvers and avoiding abrupt movements, global route planning is concerned with creating long-term routes that help the local planner achieve his or her goals. Recently, various approaches to global route planning for off-road navigation have been proposed. One is an improved version of the A* algorithm designed for long off-road route planning, but it does not take into account the kinematic limitations of vehicles. Another approach is to integrate the maximum achievable vehicle speed and vertical acceleration into the RRT*-based route planning framework, which improves safety. However, RRT* faces scalability and memory usage issues when applied to large maps. To address these issues, ER-RRT*, an improved version of RRT*, was developed, but its probabilistic nature prevents it from working in real time.

Among the patent analogues of the proposed solution, a method and device for planning the path of an AGV are known (see CN 117555336 A, published 13.02.2024), used in the process of logistic storage. The method includes the following steps: constructing a grid map of the warehouse environment in which the AGV operates; based on the grid map, using the A* algorithm to complete the initial global path of the AGV; processing the initial global path using an improved A* algorithm and a smoothing method to obtain the initial global optimal path of the AGV; and assessing whether the AGV needs to avoid obstacles or not, based on the initial global optimal path using the artificial potential field method, if so, then performing the obstacle avoidance task of the AGV and cyclically performing the obstacle avoidance task until the AGV reaches the target position.

Also known are a method and device for planning a route of an unmanned vehicle (see CN 110333714 A, published 15.10.2019) The method for planning a path of an unmanned vehicle includes the following steps: S1, determining the location of the current vehicle: obtaining the location of the current unmanned vehicle as a starting point according to the differential GPS/INS system, then selecting a target point, loading global map data and reading the vehicle state information; S2, planning a global path: creating a global raster map according to the coordinate information of the starting and target points, using a modified artificial potential field-colony algorithm for planning a global path and creating a desired path; S3, driving and analyzing the current road condition of the vehicle, and analyzing and judging whether local path planning is necessary or not according to the received sensor information; S4, selecting a local path planning strategy; and S5, sending the generated path information to the vehicle control layer.

Most existing off-road navigation systems rely on OSM (OpenStreetMap) or DEM (Digital Elevation Model) data. These datasets often have poor coverage in remote or unexplored areas.

SUMMARY OF THE INVENTION

The present invention is aimed at solving the technical problem of overcoming the limitations of existing similar methods by developing a global planner that prioritizes three key aspects: real-time performance, kinematic feasibility, and memory efficiency. When solving off-road navigation problems, the main source of obtaining the necessary information about geographic features for understanding and creating routes is OpenStreetMap (OSM) and Digital Elevation Models (DEM). However, in some situations (e.g., when crossing uncharted territories or after natural disasters), this data may be unavailable or outdated.

The technical result of the invention is an increase in real-time performance, achievement of kinematic feasibility and efficiency of memory use.

The claimed technical result can be achieved by creating a method for navigation in difficult-to-reach places, including the collection of quadcopter data, the terrain data is collected using a quadcopter on which an RTK-GPS, a camera and a Livox Avia LiDAR sensor are installed, the quadcopter is moved over the target area of the terrain, during the flight, the current coordinates are recorded in the EPSG 4326 coordinate system and synchronized images and point clouds are simultaneously captured along the trajectory of movement, the LOAM (LiDAR Odometry and Mapping) algorithm is used to create an initial input map in the EPSG 4326 coordinate system, which serves as the basis for further analysis and refinement using QGIS tools, extracting complex geographic features from point cloud data with off-road route identification, providing a complete understanding of the terrain, creating an intermediate map taking into account all geographic features, which is a preprocessing task and stores information on whether the given location is passable or not, the intermediate map is made in GeoTIFF format or in a pixel coordinate system, designate the initial location in the EPSG 4326 block, to obtain the initial location, the functionality of the GDAL library was used, first, the georeferencing data is received in the GeoTIFF format, which is a standardized open format of geographic metadata information that allows georeferencing information to be included in TIFF images, the global path planner uses the constructed intermediate map and user-defined areas to create real-time paths that comply with kinematic constraints, then integrate any off-road local planner for maneuvering the vehicle.

In a particular implementation, the intermediate map is stored as a one-dimensional array.

BRIEF DESCRIPTION OF DRAWINGS

The essence of the invention is explained by drawings, in which:

Fig.1 – Proposed structure for off-road navigation;

Fig.2 – Quadcopter;

Fig.3 – Topographic map;

Fig.4 – An example of constructing a map using the proposed algorithm;

Fig.5 – Visual representation of Algorithm 1 for finding poses closer to the target pose on off-road terrain

In Fig.2, the positions indicate the following:

1 – Camera

2 – RTK-GPS

3 – Livox Avia LiDAR Sensor

4 – Control module.

These drawings do not cover and, moreover, do not limit the entire scope of options for implementing this technical solution, but represent only illustrative material of a particular case of its implementation.

EMBODIMENT OF THE INVENTION

According to an embodiment of the invention, a structure (Fig. 1) is proposed for a method of navigation in difficult-to-pass areas, which solves the problem of navigation in such geographic areas. To achieve the said objectives, an RTK-GPS, a camera and a Livox Avia sensor (Fig. 2) were installed on a quadcopter (T-Drones-M690B version) and the aircraft flew over the target area. During the traverse of the area, the current position was recorded in the EPSG 4326 coordinate system and synchronized images and point clouds were taken along the passage. The LiDAR odometry and mapping (LOAM) algorithm was used to build an initial input map in EPSG 4326, as a basis for further analysis and refinement using QGIS tools. Global Mapper software was used to extract complex geographic features from the point cloud data. The detection of off-road trails, water bodies and trees was included, providing a complete understanding of the terrain. The resulting topographic map is shown in Fig. 3.

The proposed off-road navigation system accepts several types of input files. First, the georeferencing information is accepted as GeoTIFF, which is a standardized open source geographic metadata that allows georeferencing information to be integrated into TIFF (Tag Image File Format) images (Fig. 3). The geographic metadata includes the transformation between the actual location in space and the pixel location in the image. In addition, it includes horizontal and vertical datums, coordinate reference system (CRS), ellipsoids and geoids, and map projection information. Second, the proposed off-road navigation system accepts geographic features (Fig. 3), such as roads, buildings, rivers, water bodies, and user-restricted (or closed) areas, as GeoJSON files. GeoJSON is an open standard geographic feature interchange format that represents geographic features using simplified geometric shapes such as polygons, lines, points, and multipolygons in a coordinate reference system. In the proposed framework, the World Geodetic System 1984 (WGS 84) [WGS84] reference system is adopted as the desired coordinate reference system.

The intermediate map is created taking into account all the provided geographic objects (Fig. 3). Therefore, the creation of the intermediate map is a prerequisite task that helps to achieve real-time performance.

The intermediate map stores information about whether the given location is passable or not. Since the georeferencing information is received as GeoTIFF, the intermediate map generation can be done either in the provided CRS or in the pixel coordinate system. The proposed system generates the intermediate map in the pixel coordinate system for two main reasons. First, storing the necessary map information in an efficient data structure facilitates real-time path planning. Second, the pixel coordinate system provides higher location accuracy compared to the WGS84 (or EPSG 4326) latitude and longitude system. This is because a small change in latitude or longitude can result in a significant shift in the local coordinate system (or Universal Transverse Mercator (UTM)) if the coordinates are not scaled appropriately. The following transformation is used to convert between the two mentioned coordinate systems (WGS84 and pixel coordinate systems).

where the desired latitude and longitude are denoted as lat and lon, respectively. The terms x _origin and y _origin denote the location of the origin in the EPSG 4326 block. GDAL library functions were used to obtain the location of the origin. The geographic reference area in the pixel coordinate system, represented by the variables pixel width and pixel height, was stored as geographic metadata in GeoTIFF. All geographic features were transformed into the pixel coordinate system (Fig. 3). Then, all geographic features are used to estimate the traversable area, which is stored in the intermediate map. To reduce the memory footprint of the intermediate map, which improves the speed of pathfinding, the intermediate map is stored as a one-dimensional array of pixel width × pixel height instead of a two-dimensional array of pixel width and pixel height.

Given a starting position (s _d ) and a target position (t _d ), it is quite difficult to obtain an optimal position closer to the off-road tracks. Consider the example shown in Fig. 4. In this example, the closest pose to the off-road tracks does not provide the shortest path between position s _d and position t _d .

An approach (Algorithm1) is proposed to correctly estimate the optimal closest pose to the target location (start or target).

According to Algorithm1, when a target location is specified, all points inside the corresponding polygon are selected. Then, these points are grouped into clusters using the DBSCAN algorithm (as shown in Fig. 5), and one point from each cluster is determined as the closest to the target location. If multiple points fall into the same cluster, the intersection between the polygon and the off-road trails is calculated, and the intersected points are selected as the closest points (Fig. 5).

Finally, Dijkstra's algorithm is used to plan a path between the selected points and calculate the distance between them.

To reduce computational overhead and memory usage, Dijkstra's algorithm uses a downsampled map to generate the distance map.

Initially, the A* or JSP algorithm is applied to find intermediate points whose constructed path is not kinematically feasible because the vehicle kinematics were not included in the path planning between s _o and t _o .

It is not possible to use dynamic path planning approaches directly due to the high computational costs. Typically, the map resolution is between 10,000 and 30,000 pixels, which corresponds to 1-6 kilometers in latitude-longitude form. Therefore, once the waypoints are determined, it is crucial to determine which path segments require replanning to ensure the kinematic implementation of the entire path.

The intermediate map can be very large, so to reduce the computational cost of loading and processing it, only the required map slice is extracted for processing. If path planning cannot be performed within the extracted map, the parameters d _y and d _x are increased by a factor to extract a new, larger map slice for path planning of each of the sliced maps.

The process of finding a path that is physically possible for a vehicle to follow is called kinematic path planning.

Kinematic path planning is applied using the Hybrid A* algorithm to each identified path segment, considering only the corresponding sliced map. Path curvature is improved after applying Hybrid A*-based path planning, since protrusions and corners are removed along certain path segments.

Paths generated using JPS, A*, or Dijkstra's algorithms are not asymptotically optimal. Therefore, several factors are taken into account when smoothing the planned path. First, the path must be adjusted to maintain a safe distance from nearby obstacles, whether in narrow or wide passages. Second, while hybrid A* planning segments may cope well with curvature, other path segments may experience abrupt changes in curvature that must be minimized or eliminated during smoothing. Third, JPS or A* may only create a few intermediate points along the path, so the distance between successive points must be minimized. These considerations combine to improve the smoothness of the planned path.

Both passable and bounded areas can be defined using the graphical user interface (GUI). These areas can be convex or concave. Therefore, the number of turns algorithm is used to find the area that belongs to the specified shape within the intermediate map and update it accordingly.

In particular, areas restricted by the user are designated as obstacles, and areas traversable by the user are designated as free spaces.

To illustrate and evaluate the performance of the proposed software framework, several different types of experiments were conducted.

The experiments were conducted on a computer with the following specifications: Intel(R) Core(TM) i5-8265U CPU and 16 GB RAM. For preprocessing and generating the initial intermediate map, the proposed framework was written in C++, adhering to the C++17 specification. We used Ubuntu as the operating system to run the framework. Therefore, the framework is not tied to a specific operating system.

Two different maps were used for all experiments described in the following sections. Map 1 had a resolution of 5000 × 16000, and Map 2 had a resolution of 6000 × 4000. Both maps were converted to a pixel coordinate system before conducting the experiments. Both maps cover several square kilometers. Both Map 1 and Map 2 consist of several geographic features, including trees, off-road trails, rivers, water bodies, and areas with restricted user access.

To evaluate the performance of our off-road navigation framework, we measured two key metrics: average execution time and memory usage for global path planning. Average execution time is the average execution time required for global planning. Memory usage is the amount of memory used for global planning. We used the Procpath1 profiler to track these metrics. The intermediate map was built in a pixel-based coordinate system, so we can easily use either planning technique for validation purposes. For a comprehensive comparison, two graph search methods were used: A* and JPS, as well as two sampling methods: RRT* and Informed RRT*. These metrics are crucial to assess the efficiency and practicality of each algorithm, especially in terms of kinematic feasibility and real-time processing capabilities. We initially selected 100 different start and target positions on each map, ensuring that the minimum offset between any two start and target points was at least 1 1A Profiling tool https://pypi.org/project/Procpath/.

The A* algorithm exhibits relatively low average computation time and memory usage on both maps, making it suitable for real-time applications. Specifically, on Map 1, A* requires 1.3567 seconds and 1.25 GB of memory, while on Map 2 it requires 0.7467 seconds and 0.95 GB of memory.

Its deterministic and bounded exploration approach contributes to its efficiency, although it may not handle complex kinematic constraints as efficiently as other methods. In comparison, the JPS (Jump Point Search) algorithm shows slightly better performance than A* in terms of both computation time and memory usage. For Map 1, JPS requires 1.1459 seconds and 1.12 GB of memory, while for Map 2, it requires 0.5641 seconds and 0.85 GB of memory. JPS, like A*, is deterministic and uses bounded exploration, but its improvements allow for more efficient pathfinding and memory usage.

On the other hand, the RRT* and Informed RRT** algorithms exhibit significant limitations. Both fail to generate feasible paths within the ten-second limit, as indicated by their "Inf" values for computation time and memory usage. This failure suggests that these probabilistic algorithms, whether or not they are bounded in their search strategies, are not suitable for real-time applications in their current forms.

The proposed method represents a balanced compromise between efficiency and kinematic feasibility. It shows a moderate increase in computation time and memory usage compared to A* and JPS, but it provides important advantages in terms of kinematic feasibility and real-time capabilities. For Map 1, this method requires 1.6990 seconds and 1.28 GB of memory, while for Map 2, it requires 0.8901 seconds and 1.14 GB of memory. Although it is less efficient than JPS and A*, it compensates for this by offering a solution that meets the kinematic constraints required for complex off-road scenarios.

In summary, the analysis shows that A* and JPS are efficient online algorithms suitable for real-time applications, with JPS outperforming A* in computation time and memory usage. However, the proposed approach prioritizes kinematic feasibility while maintaining reasonable performance: its average execution time and memory usage are slightly higher than those of graph search methods, and it guarantees a collision-free, maneuverable path for the vehicle (unlike A* and JPS). This trade-off is achieved through the following additional operations: distance map construction, which provides an efficient path cost estimate, hybrid A* for curvature enhancement, which provides smoother, kinematically feasible paths, and path smoothing, which further refines the path for a feasible traversal.

These additional operations enable the framework to guarantee kinematic feasibility while maintaining acceptable real-time performance. The choice of algorithm should be based on the specific needs of the application, including real-time processing requirements and the ability to handle kinematic constraints.

The proposed method takes into account key factors beyond the traditional objectives of minimizing path length and travel time, including real-time performance, kinematic feasibility, and efficient memory usage. This framework is memory efficient and average computation time efficient while maintaining the primary objective of optimal path finding. The integration of preprocessing and intermediate map generation functions based on the provided geographic features further enhances the practicality of the proposed method. A key area for future work will be the development of local path planning strategies that take into account traversability in unstructured environments.

While the global planner effectively manages large-scale path planning, incorporating local path planning into the framework will allow for more detailed and accurate navigation over shorter horizons. This step is critical to improving the robot’s ability to handle dynamic and complex terrain where real-time adaptability is required.

Moreover, while the current focus is on optimizing memory usage and computation time, future research could explore advanced methods to further reduce these parameters without compromising the quality of path planning. In addition, addressing the problem of traversability in unstructured environments, such as those with sudden changes in terrain or environmental conditions, will be critical. Implementing a robust approach to local path planning will require a balance between real-time performance and the requirements of high memory usage and computation time, as these factors often interact in complex ways.

INDUSTRIAL APPLICABILITY

The claimed invention can be used in a wide range of applications, including search and rescue operations, agriculture and forestry, construction and engineering surveys. Unlike road navigation, off-road driving is often associated with crossing unknown and complex terrain.

Claims (2)

1. A method for navigation in difficult-to-reach places, including collecting data from a quadcopter, characterized in that the terrain data is collected using a quadcopter on which an RTK-GPS, a camera and a LiDAR sensor are installed, the quadcopter is moved over a target area of the terrain, during the flight, the current coordinates are recorded in the EPSG 4326 coordinate system and synchronized images and point clouds are simultaneously captured along the trajectory of movement, the LOAM (LiDAR Odometry and Mapping) algorithm is used to create an initial input map in the EPSG 4326 coordinate system, which serves as a basis for further analysis and refinement using QGIS tools, extracting complex geographic features from point cloud data with the identification of off-road routes, providing a complete understanding of the terrain, creating an intermediate map taking into account all geographic features, which is a preprocessing task and stores information on whether the given location is passable or not, the intermediate map is made in GeoTIFF format or in a pixel coordinate system, the initial location is designated in the block EPSG 4326, to obtain the initial location, the functionality of the GDAL library was used, first accepting georeferenced data in GeoTIFF format, which is a standardized open format for geographic metadata information that allows georeferencing information to be included in TIFF images, the global path planner uses the constructed intermediate map and user-defined areas to create real-time paths that meet kinematic constraints, then integrating any off-road local planner for vehicle maneuvering. 2. The navigation method according to item 1, characterized in that the intermediate map is stored as a one-dimensional array.