Apparatus and method of cell-based path planning for mobile body
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
18 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18)
-
Specification