Path search method
First Claim
Patent Images
1. A path search method of a mobile object in a grid map having a plurality of cells, each having an identical size, comprising:
- generating a block map having a plurality of blocks by merging a specific number of cells in the grid map to create each block;
obtaining a block path by finding a path from a starting position to a destination position in the block map; and
obtaining a final path of the mobile object by performing a cell-based path search on cells in the blocks on the block path,wherein generating a block map includes;
setting a block size based on the number of cells in the grid map occupied by the mobile object;
dividing the grid map into the blocks each having the block size; and
setting, based on cell states of the cells in each of the blocks in the block map, a block state for each of the blocks as either a blocked block or an empty block.
1 Assignment
0 Petitions
Accused Products
Abstract
A path search method of a mobile object in a grid map having a plurality of cells, each having an identical size, is provided. The path search method includes: generating a block map having a plurality of blocks by merging a specific number of cells in the grid map; obtaining a block path by finding a path from a starting position to a destination position in the block map; and obtaining a final path of the mobile object by performing a cell-based path search on cells in the blocks on the block path.
9 Citations
8 Claims
-
1. A path search method of a mobile object in a grid map having a plurality of cells, each having an identical size, comprising:
-
generating a block map having a plurality of blocks by merging a specific number of cells in the grid map to create each block; obtaining a block path by finding a path from a starting position to a destination position in the block map; and obtaining a final path of the mobile object by performing a cell-based path search on cells in the blocks on the block path, wherein generating a block map includes; setting a block size based on the number of cells in the grid map occupied by the mobile object; dividing the grid map into the blocks each having the block size; and setting, based on cell states of the cells in each of the blocks in the block map, a block state for each of the blocks as either a blocked block or an empty block. - View Dependent Claims (2, 3)
-
-
4. A path search method of a mobile object in a grid map having a plurality of cells, each having an identical size, comprising:
-
generating a preprocessed map by extending, based on the number of cells in the grid map occupied by the mobile object, a blocked region in the grid map to create each block; generating a block map having a plurality of blocks by merging a specific number of cells in the preprocessed map to create each block; obtaining a block path of the mobile object by finding a path from a starting position to a destination position in the block map; and obtaining a final path of the mobile object by performing a cell-based path search on cells in the blocks on the block path, wherein generating a preprocessed map includes; setting a window size W to the number of cells occupied by the mobile object such that a window has a center cell and W−
1 neighboring cells; andsetting, while moving the window in the grid map, a cell state for each of the center cells in the window to an empty cell if all of the center cell and neighboring cells are the empty cells, and to a block cell if at least one of the center cell and neighboring cells is the blocked c, wherein generating a block map includes; setting a block size based on the number of cells in the grid map occupied by the mobile object; dividing the preprocessed map into the blocks each having the block size; and setting, based on cell states of the cells in each of the blocks in the block map, a block state for each of the blocks as either a blocked block or an empty block. - View Dependent Claims (5, 6, 7, 8)
-
Specification