Looking for breakthrough ideas for innovation challenges? Try Patsnap Eureka!

Path planning method, path planning system, robot and storage medium

A technology for path planning and robotics, applied in the field of robotic algorithms, it can solve problems such as slow planning of large maps, and achieve the effects of improving preprocessing efficiency, improving search efficiency, and reducing search space.

Active Publication Date: 2022-02-11
杭州景吾智能科技有限公司
View PDF6 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

However, this patent document still has the defect that the planning speed under the large map is too slow

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Path planning method, path planning system, robot and storage medium
  • Path planning method, path planning system, robot and storage medium
  • Path planning method, path planning system, robot and storage medium

Examples

Experimental program
Comparison scheme
Effect test

Embodiment 1

[0056] A path planning method provided in this embodiment includes the following steps:

[0057] Step 1: Set the minimum expansion distance d_min and the maximum expansion distance d_max.

[0058] Step 2: Accept the original grid map that needs to be planned, and generate a new map type distmap according to d_min and d_max. Step 2 includes the following steps:

[0059] Step 2.1: Add all occupied grids in the original grid map to the pending queue occ_list, and initialize the dist value of the unoccupied grid to d_max, where the dist value is the distance from the unoccupied grid to the occupied grid The minimum distance, d_max is the maximum expansion distance;

[0060] Step 2.2: Record each occupied grid in occ_list as grid point p_i, add surrounding unoccupied grids to dist_expand_list, and calculate the dist value of each unoccupied grid from p_i; for example: if The coordinates of p_i are (p_i_x, p_i_y), and the unoccupied grid is (x_, y_), then dist is the distance betw...

Embodiment 2

[0073] On the basis of Embodiment 1, this embodiment provides a path planning system, adopting the path planning method provided in Embodiment 1, including the following modules:

[0074] Setting module: set the minimum expansion distance d_min and the maximum expansion distance d_max;

[0075] Mapping module: accept the original grid map that needs to be planned, and generate a new map type distmap according to d_min and d_max;

[0076] Input module: input the start point and end point in the distmap, and list the start point as the current point P';

[0077] Calculation module: judge whether the adjacent grid of the current point P' is passable, and calculate the cost value of the adjacent grid according to the new heuristic function O(x);

[0078] Heap building module: Add passable points near P' to the openlist queue, and build a minimum heap according to the cost value of each point;

[0079] Judging module: judging whether P' is the end point, otherwise repeatedly exec...

Embodiment 3

[0081] Those skilled in the art can understand this embodiment as a more specific description of Embodiment 1 and Embodiment 2.

[0082] Such as Figure 1~3 As shown, a path planning method provided in this embodiment includes the following steps:

[0083] Step 1: Set the minimum expansion distance d_min and the maximum expansion distance d_max;

[0084] Step 2: Accept the original grid map that needs to be planned, and generate a new map type distmap according to d_min and d_max (in this step, the search space for path planning is dynamically reduced);

[0085] Step 3: Enter the start point and end point, and list the start point as the current point P’;

[0086] Step 4: Determine whether the adjacent grid of the current point P’ is passable, and calculate the cost value of the adjacent grid according to the new heuristic function O(x) (where O(x) is the key to ensure the shortest route and path safety);

[0087] Step 5: Add the passable points near P' to the openlist queu...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

PUM

No PUM Login to View More

Abstract

The invention provides a path planning method, a path planning system, a robot and a storage medium, comprising the following steps: setting the minimum expansion distance d_min and the maximum expansion distance d_max; accepting the original grid map that needs to be planned, and generating a new grid map according to d_min and d_max The map type distmap; enter the starting point and the ending point in the distmap, and list the starting point as the current point P'; judge whether the adjacent grid of the current point P' is passable, and calculate the adjacent grid according to the new heuristic function O(x) cost value; add passable points near P' to the openlist queue, and build a minimum heap according to the cost value of each point; judge whether P' is the end point, otherwise repeat the above steps, and end the search if it is. The invention reduces the search space of the grid map, solves the problem of too slow planning speed under the large map, and self-adaptively selects a path that is far away from obstacles and is easier to pass and safer under the premise of ensuring trafficability.

Description

technical field [0001] The present invention relates to the technical field of robot algorithms, in particular to a path planning method, a path planning system, a robot and a storage medium. Background technique [0002] At present, the commonly used service robot path planning methods based on grid maps, such as dijstra and A*, have a slow planning speed (as the map area becomes larger, the planning speed decreases exponentially, see figure 1 ), the planned path is the shortest but not optimal (it is too close to obstacles and there are safety hazards, see figure 2 )The problem. In addition, the current path planning based on costmap has contradictions in the static expansion range of the shortest path and the path being too close to obstacles (see image 3 ). [0003] The patent document with the publication number CN110361009B discloses a path planning method, a path planning system and a mobile robot. By obtaining the obstacle position information in the environment...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to View More

Application Information

Patent Timeline
no application Login to View More
Patent Type & Authority Patents(China)
IPC IPC(8): G06F16/29G06Q10/04G01C21/20
CPCG06F16/29G01C21/20G06Q10/047
Inventor 刘宇星杨洪杰张晨博杨俊郭震
Owner 杭州景吾智能科技有限公司
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Patsnap Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Patsnap Eureka Blog
Learn More
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic, Popular Technical Reports.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap|About US| Contact US: help@patsnap.com