PATH SEARCH METHOD

• US 20110010083A1
• Filed: 12/17/2007
• Published: 01/13/2011
• Est. Priority Date: 07/03/2007
• Status: Active Grant

• Current Assignee: Electronics and Telecommunications Research Institute
• Original Assignee: Electronics and Telecommunications Research Institute
• Inventors: Lee, Jae-Yeong, Yu, Won Pil
• Granted Patent: US 8,296,064 B2
• Time in Patent Office: Days
• US Class Current: 701/200
• CPC Class Codes: G05D 1/0274 using mapping information stored in a memory device navigation using map-matching G01C21/30

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.

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;

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.

2. The method of claim 1, 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.

3. The method of claim 2, wherein when the mobile object occupies m×

m cells in the grid map, the block size is set to be equal to ore smaller than (m+1)/2×

(m+1)/2 cells.

4. The method of claim 2, wherein in setting a block state, the block state is set to the empty block if the block has only empty cells, and the block state is set to the blocked block if the block has at least one blocked cell.

5. 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;

generating a block map having a plurality of blocks by merging a specific number of cells in the preprocessed map;

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.

6. The method of claim 5, 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; and

setting, 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 cell.

7. The method of claim 5, 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.

8. The method of claim 7, wherein the block size is set to be equal to or smaller

than a difference of the size of the blocked regions in the grid map and in the pre-processed map.

9. The method of claim 8, wherein when the mobile object occupies m×

m cells in the grid map, the difference of the size of the blocked regions is set to (m+1)/2 cells.

10. The method of claim 7, wherein in setting a block state, the block state is set to the blocked block if the block has only blocked cells, and the block state is set to the empty block if the block has at least one empty cell.