Path planning method and related navigation device

• US 10,635,913 B2
• Filed: 10/17/2017
• Issued: 04/28/2020
• Est. Priority Date: 10/17/2016
• Status: Active Grant

• Current Assignee: MediaTek, Inc.
• Original Assignee: MediaTek, Inc.
• Inventors: Yang, Kai-Min, Chang, Chih-Kai, Liu, Tsu-Ming
• Primary Examiner(s): Melton, Todd M
• Application Number:
  US15/786,559
• Publication Number:
  US 20180107226A1
• Time in Patent Office: 924 Days
• CPC Class Codes: B64U 2201/10 autonomous, i.e. by navigating independently from ground or air stations, e.g. by using inertial navigation systems [INS]
• CPC Class Codes: G05D 1/0088 characterized by the autonomous decision making process, e.g. artificial intelligence, predefined behaviours using knowledge based models G06N5/00
• CPC Class Codes: G05D 1/0246 using a video camera in combination with image processing means
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G05D 1/042 specially adapted for aircraft
• CPC Class Codes: G05D 1/0676 specially adapted for landing
• CPC Class Codes: G06V 20/58 Recognition of moving objects or obstacles, e.g. vehicles or pedestrians; Recognition of traffic objects, e.g. traffic signs, traffic lights or roads
• CPC Class Codes: G08G 5/0069 specially adapted for an unmanned aircraft
• CPC Class Codes: G08G 5/045 Navigation or guidance aids, e.g. determination of anti-collision manoeuvers radar or analogous systems specially adapted for anti-collision between aircraft G01S13/933

Abstract

A path planning method applied to a navigation device includes acquiring a two-dimensional depth map, transforming the two-dimensional depth map into a gray distribution map via statistics of pixel values on the two-dimensional depth map, computing a space matching map by arranging pixel counts on the gray distribution map, and computing a weighting value about each angle range of the space matching map in accordance with a distance from location of a pixel count to a reference point of the space matching map. The weighting value represents existential probability of an obstacle within the said angle range and a probable distance between the navigation device and the obstacle.

Claims

1. A path planning method applied to a navigation device, the path planning method comprising:

acquiring a two-dimensional depth map;

dividing an effective region on the two-dimensional depth map into a plurality of analyzed areas;

classifying pixel values inside each analyzed area in accordance with a predetermined gray value range;

arranging a classifying result into a gray interval along variation of the predetermined gray value range;

forming a gray distribution map by merging gray intervals transformed from the plurality of analyzed areas, wherein a summation of pixel counts inside the gray interval is equal to an amount of the pixel values inside the corresponding analyzed area;

computing a space matching map by arranging the pixel counts on the gray distribution map; and

computing a weighting value about each angle range of the space matching map in accordance with a distance from location of a pixel count to a reference point of the space matching map, wherein the weighting value represents existential probability of an obstacle within the said angle range and a probable distance between the navigation device and the obstacle.

2. The path planning method of claim 1, wherein transforming the two-dimensional depth map into the gray distribution map comprises:

selecting the effective region on the two-dimensional depth map; and

counting the pixel values inside the effective region to establish the gray distribution map.

3. The path planning method of claim 1, wherein computing the space matching map by arranging the pixel counts on the gray distribution map is redistributing the pixel counts of the gray distribution map along a specific direction in accordance with a vision depth of a viewable range on the space matching map.

4. The path planning method of claim 1, wherein computing the space matching map by arranging the pixel counts on the gray distribution map comprises:

selecting a grid on the space matching map;

computing a distance from the selected grid to the reference point; and

picking the pixel count on the gray distribution map in accordance with the computed distance to fill in the selected grid.

5. The path planning method of claim 4, wherein a row of elements of the gray distribution map is directly related to a corresponding element'"'"'s distance from a reference point on the space matching map.

6. The path planning method of claim 1, wherein computing the space matching map by arranging the pixel counts on the gray distribution map comprises:

selecting a grid on the space matching map;

searching a corresponding pixel count on the gray distribution map related to the selected grid; and

applying a predetermined mask onto the corresponding pixel count and adjacent pixel counts to acquire a computed value filled in the selected grid.

7. The path planning method of claim 6, wherein the predetermined mask comprises a central weight and a plurality of adjacent weights, the central weight is greater than the plurality of adjacent weights.

8. The path planning method of claim 1, wherein the existential probability of the obstacle is inversely proportional to the distance from each pixel count to the reference point.

9. The path planning method of claim 1, wherein the space matching map is divided into a plurality of angle ranges, the weighting value of the obstacle within each angle range is computed in accordance with a product of the pixel counts inside the said angle range and the distance from each pixel count to the reference point.

10. The path planning method of claim 9, wherein the weighting value of the plurality of angle ranges are utilized to form an obstacle probability histogram.

11. The path planning method of claim 10, wherein a predefined threshold is set on the obstacle probability histogram, the weighting value of a specific angle range lower than the predefined threshold represents the specific angle range is a positive path, and the weighting value of a designated specific angle range greater than the predefined threshold represents the designated angle range is a negative path.

12. The path planning method of claim 11, wherein when the obstacle is a dense mesh, the pixel counts of grids nearest the reference point are increased so that the gray distribution map has a great quantity of pixel counts with high gray level, and the path planning method determines the weighting value of the plurality of angle ranges are greater than the predefined threshold because variation of a coverage ratio of the dense mesh is proportional to the weighting value.

13. The path planning method of claim 11, wherein when the obstacle is a loose mesh, the pixel counts of grids nearest the reference point are decreased so that the gray distribution map has a small quantity of pixel counts with high gray level, and the path planning method determines a part of the weighting value of the plurality of angle ranges are lower than the predefined threshold for a positive path because variation of a coverage ratio of the loose mesh is proportional to the weighting value.

14. The path planning method of claim 1, wherein the two-dimensional depth map is divided into a plurality of stripes along a specific direction, and each of the plurality of stripes is transformed into a related obstacle probability histogram.

15. The path planning method of claim 14, wherein obstacle probability histograms of the plurality of stripes are used to determine a steering direction and a steering speed of the navigation device.

16. The path planning method of claim 1, further comprising:

forming an obstacle probability histogram in accordance with the weighting value of angle ranges of the space matching map;

determining whether a target related to the obstacle is located in a cavity or a non-cavity on the obstacle probability histogram; and

stretching the target in accordance with a determining result to set a steering direction and a steering angle of depression and elevation of the navigation device.

17. The path planning method of claim 16, further comprising:

setting a steering speed of the navigation device as zero for staying at a current position while the weighting value of the angle ranges are located in the non-cavity.

18. The path planning method of claim 17, further comprising:

setting at least one of huge rotation and inverse turn; and

executing the huge rotation or the inverse turn for the navigation device while the steering speed is set as zero.

19. The path planning method of claim 16, wherein while the target is located in the cavity, first intervals of opposite sides of the target relative to the non-cavity are computed, the target is stretched a circular distance toward a wider first interval, an initial location and a final location of stretched motion of the target are moved inversely, and a center of the moved initial location and the moved final location is represented as the steering direction.

20. The path planning method of claim 19, wherein while the first intervals are identical, the target is stretched toward a first interval overlapped with the last steering direction of the navigation device.

21. The path planning method of claim 16, wherein while the target is located in the non-cavity, second intervals of opposite sides of the target relative to the cavity are computed, the target is stretched a circular distance toward a narrow second interval, an initial location and a final location of stretched motion of the target are moved inversely, and a center of the moved initial location and the moved final location is represented as the steering direction.

22. The path planning method of claim 21, wherein while the second intervals are identical, the target is stretched toward a second interval overlapped with the last steering direction of the navigation device.

23. The path planning method of claim 16, wherein stretched motion of the target is suspended while the target is overlapped with a boundary between the cavity and the non-cavity.

24. The path planning method of claim 1, wherein the weighting value is analyzed to determine a steering direction and a steering speed of the navigation device, the path planning method further comprises:

setting a cut-off directional variation; and

decreasing the steering speed while the steering direction is greater than the cut-off directional variation.

25. The path planning method of claim 1, wherein the weighting value is analyzed to determine a steering direction and a steering speed of the navigation device, the path planning method further comprises:

setting a cut-off distance between the navigation device and the obstacle; and

decreasing the steering speed while the navigation device is approached to the cut-off distance.

26. A navigation device with a path planning function, the navigation device comprising:

a data communication unit adapted to acquire a two-dimensional depth map; and

a computing processor electrically connected with the data communication unit and adapted to analyze a two-dimensional depth map, to transform the two-dimensional depth map into a gray distribution map via statistics of pixel values on the two-dimensional depth map, to select a grid on the space matching map, to search a corresponding pixel count on the gray distribution map related to the selected grid, to apply a predetermined mask onto the corresponding pixel count and adjacent pixel counts to acquire a computed value filled in the selected grid, and to acquire a weighting value about each angle range of the space matching map in accordance with a distance from location of a pixel count to a reference point of the space matching map;

wherein the weighting value represents existential probability of an obstacle within the said angle range and a probable distance between the navigation device and the obstacle.