Apparatus and method of cell-based path planning for mobile body

• US 9,116,523 B2
• Filed: 11/23/2011
• Issued: 08/25/2015
• Est. Priority Date: 02/25/2011
• Status: Active Grant

• Current Assignee: Dongguk University Industry-Academic Cooperation Foundation
• Original Assignee: Dongguk University Industry-Academic Cooperation Foundation
• Inventors: Jung, Jin-Woo, So, ByungChul
• Primary Examiner(s): Shaawat, Mussa A
• Application Number:
  US13/303,620
• Publication Number:
  US 20120221237A1
• Time in Patent Office: 1,371 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544

Abstract

Disclosed are an apparatus and method of cell-based path planning for a mobile body and a computer-readable recording medium storing the method therein. The method includes receiving a configuration space including a start point and a goal point of the mobile body and position information of obstacles, determining a search order of the obstacles located in the configuration space, performing cell decomposition by repeatedly connecting a vertex of one of the obstacles to a vertex of another obstacle according to the determined search order, and performing cell decomposition by making an extended line from each of non-connected vertices in a direction of dividing vertical angle of each of the non-connected vertices into two.

Claims

1. A path planning method for a mobile body having a path finding mechanism, the path finding mechanism planning a path for the mobile body according to a method comprising:

receiving a configuration space comprising a start point and a goal point of the mobile body and position information of obstacles, at least one of the obstacles having a plurality of vertices;

determining a search order of the obstacles located in the configuration space;

performing cell decomposition, using a processor, by repeatedly connecting a vertex of one of the obstacles to a vertex of another obstacle according to the determined search order; and

performing cell decomposition, using a processor, by making an extended line from each of non-connected vertices in a direction of dividing vertical angle of each of the non-connected vertices into two.

2. The path planning method of claim 1, wherein the performing of cell decomposition by repeatedly connecting a vertex of one of the obstacles to a vertex of another obstacle comprises:

connecting a vertex of a first obstacle to a vertex of a second obstacle located nearest to the vertex of the first obstacle if the vertex of the second obstacle is present within vertical angle of the vertex of the first obstacle using the position information; and

connecting a vertex of a third obstacle to a vertex of a fourth obstacle located nearest to the vertex of the third obstacle within vertical angle of the vertex of the third obstacle using the position information among vertices which are not connected.

3. The path planning method of claim 2, wherein the connecting of a vertex of a first obstacle to a vertex of a second obstacle comprises:

searching a vertex of a second obstacle located nearest to the vertex of the first obstacle using the position information;

determining if the vertex of the second obstacle is located within the vertical angle of the vertex of the first obstacle using the position information; and

selectively connecting the vertex of the first obstacle to the vertex of the second obstacle according to the determination result.

4. The path planning method of claim 2, wherein the connecting of a vertex of a third obstacle to a vertex of a fourth obstacle comprises:

searching all vertices present within vertical angle of a vertex of a third obstacle, the vertex of the third obstacle is among the vertices which are not connected using the position information;

calculating distances between the vertex of the third obstacle and each of the searched vertices; and

connecting the vertex of the third obstacle to the vertex of the fourth obstacle located nearest to the vertex of the third obstacle based on the calculated distance.

5. The path planning method of claim 2, wherein if the connection made between the vertices is determined to be present within vertical angle of each of the vertices based on the position information, the vertices are no longer considered as vertices to be further connected.

6. The path planning method of claim 2, wherein if it is determined based on the position information that a vertex of interest already has two connection lines to other vertices and an angle made by the two connection lines and the vertex of interest is below 180°

, the vertex of interest is no longer considered as a vertex to be further connected.

7. The path planning method of claim 1, wherein the performing of cell decomposition by making an extended line comprises:

dividing vertical angle of each of the non-connected vertices into two from each of the non-connected vertices; and

making an extended line from each of the non-connected vertices to a decomposing line, an obstacle or a boundary line of the configuration space, which is located nearest to each of the non-connected vertices in the direction of dividing the vertical angle of each of the non-connected vertices into two, using the position information.

8. The path planning method of claim 7, wherein the extended line is made to divide the vertical angle in half.

9. The path planning method of claim 1, wherein the vertex for cell decomposition has an acute angle, and the connection between vertices is made with respect to vertices located within vertical angle of the vertex to generate a cell formed of a convex polygon.

10. The path planning method of claim 1, wherein the cell decomposition is performed with no restriction on a decomposing angle and a decomposing direction.

11. The path planning method of claim 1, further comprising generating a point dividing the connection line into two to be used as a candidate node for a motion path of the mobile body.

12. A non-transitory computer-readable recording medium recording a program for implementing a path planning method on a computer comprising a path finding mechanism, said computer-readable recording medium having computer-executable program code portions stored therein, the computer-executable program code portions comprising program code instructions for configuring the path finding mechanism to:

receiving a configuration space comprising a start point and a goal point of the mobile body and position information of obstacles, at least one of the obstacles having a plurality of vertices;

determining a search order of the obstacles located in the configuration space;

performing cell decomposition, using a processor, by repeatedly connecting a vertex of one of the obstacles to a vertex of another obstacle according to the determined search order; and

performing cell decomposition, using a processor, by making an extended line from each of non-connected vertices in a direction of dividing vertical angle of each of the non-connected vertices into two.

13. A path planning apparatus for a mobile body, comprising:

a storage configured to receive and store a configuration space comprising a start point and a goal point of the mobile body and position information of obstacles; and

a processor configured to plan a search path for the mobile body based on the configuration space stored in the storage,

wherein the processor comprises;

a search order determination unit configured to determine a search order of obstacles located in the configuration space, at least one of the obstacles having a plurality of vertices; and

a cell decomposition unit configured to perform cell decomposition by repeatedly connecting a vertex of an obstacle to a vertex of another obstacle in the determined search order and by making an extended line from each of non-connected vertices in a direction of dividing vertical angle of each of the non-connected vertices into two.

14. The path planning apparatus of claim 13,

wherein the cell decomposition unit performs cell decomposition by connecting a vertex of a first obstacle to a vertex of a second obstacle located nearest to the vertex of the first obstacle if the vertex of the second obstacle is present within vertical angle of the vertex of the first obstacle using the position information, and

wherein for the non-connected vertices, the cell decomposition unit performs cell decomposition by connecting a vertex of a third obstacle to a vertex of a fourth obstacle located nearest to the vertex of the third obstacle if the vertex of the fourth obstacle is located within vertical angle of the vertex of the third obstacle using the position information.

15. The path planning apparatus of claim 14, wherein the cell decomposition unit is configured to connect the vertex of the first obstacle to a vertex of a second obstacle by searching the vertex of the second obstacle located nearest to the vertex of the first obstacle using the position information, determining if the vertex of the second obstacle is located within the vertical angle of the vertex of the first obstacle using the position information, and selectively connecting the vertex of the first obstacle to the vertex of the second obstacle according to the determination result.

16. The path planning apparatus of claim 14, wherein the cell decomposition unit is configured to connect a vertex of a third obstacle to a vertex of a fourth obstacle among the non-connected vertices by searching all vertices located within vertical angle of the vertex of the third obstacle using the position information, calculating distances between the vertex of the third obstacle and each of the searched vertices, and connecting the vertex of the third obstacle to a vertex of a fourth obstacle located nearest to the vertex of the third obstacle based on the calculated distance.

17. The path planning apparatus of claim 13, wherein the cell decomposition unit performs cell decomposition by dividing vertical angle of each of the non-connected vertices into two from each of the non-connected vertices, and making an extended line from each of the non-connected vertices to a decomposing line, an obstacle or a boundary line of the configuration space, which is located nearest to each of the non-connected vertices in the direction of dividing the vertical angle of each of the non-connected vertices into two, using the position information.

18. The path planning apparatus of claim 13,

wherein the cell decomposition is performed with no restriction on a decomposing angle and a decomposing direction, and

wherein the vertex for cell decomposition has an acute angle, and the connection between vertices is made with respect to vertices located within vertical angle of the vertex to generate a cell formed of a convex polygon.