Patent ID: 7953551

Claim:
A method of moving a mobile appliance in a shortest path using a grid map, the method comprising: calculating a move cost to a goal, from each of a plurality of cells comprised in a space in which the mobile home appliance moves, and planning a neighbor-cell based movement direction to the goal according to the minimum move cost while maintaining a size of each of the plurality of cells; determining one or more via points at which a direction changes on the neighbor-cell based movement direction; planning the shortest path from an apart-cell based movement direction by selecting one or more shortest-distance via points from the via points; and moving the mobile home appliance according to the apart-cell based movement direction, wherein the neighbor-cell based movement direction is calculated from a central cell and a neighbor cell, wherein the apart-cell based movement direction is calculated from the central cell and an apart cell, wherein the shortest path determining initial via points is planned using the neighbor-cell based movement direction, and then the shortest path is planned using both the neighbor-cell based movement direction and the apart-cell based movement direction, wherein the planning of the shortest path comprises: determining whether a straight movement is possible between a first via point and a second via point which do not neighbor each other; and erasing a via point existing between the first via point and the second via point in response to determining that the straight movement therebetween is possible, and wherein the method is performed using at least one processor.