Moving route planning method and navigation method for avoiding dynamic hindrances for mobile robot device

The present invention disclosed a moving route planning method for mobile robot device, which provides the moving route on a physical site for the mobile robot device. The method includes a first and a second steps; in which, the first step is to generate a relative mesh grid diagram based on a physical site, and the mesh grid map comprises a plurality of map grids containing hindrance parameter values, wherein the hindrance parameter values for each map grid are determined by the locations of hindrances within the physical site at relative locations; and, the second step is to continuously expand the map grid from the start point and the target point toward the neighbored map grids until the expanded map grids meet with each other, and to define each map grid in the expansion traces for meeting with each other as the moving route.

FIELD OF THE INVENTION

The present invention relates to a moving route planning method and navigation method, and particularly relates to a moving route planning method and navigation method for avoiding dynamic hindrances for a mobile robot device.

BACKGROUND OF THE INVENTION

As for the subject of mobile robot device, such as a mobile robot, the route planning means to find a suitable route in a working environment with hindrances, that is, the moving route from the start point to the target point. In the route, the robot device can bypass all the hindrances safely and without collision in the moving process.

In one of the conventional techniques, it will re-plan the route when encountering new hindrances, and abort the original planned route. In another conventional technique, it will define a straight line between the start point and the target point as the planned route. If there is any hindrance on the straight line, it will turn left or turn right to bypass the hindrances. However, when encountering continuous hindrances, such as a wall, it will possibly not bypass the hindrances, that is, it will not reach the target point. Or, even it can bypass the hindrances to reach the target point that it will usually waste a lot of moving distances.

In view of the related conventional techniques having to be improved, the inventors of the present invention worked hard and proposed a moving route planning method and navigation method for avoiding dynamic hindrances for the mobile robot device, so as to eliminate the defects of the above-mentioned conventional techniques.

SUMMARY OF THE INVENTION

The first object of the present invention is to provide a moving route planning method applied in a mobile robot device, so that the mobile robot device in a physical site can plan a moving route at the start point and at the target point.

The second object of the present invention is to provide a navigation method for avoiding dynamic hindrances applied in a mobile robot device, so that the mobile robot device in a physical site can plan a moving route at the start point and at the target point, and avoid the dynamic hindrances to continuously move toward the destination.

In order to accomplish the first object of the present invention, the present invention provides a moving route planning method for mobile robot device as described in claim1.

In order to accomplish the second object of the present invention, the present invention provides a navigation method for avoiding dynamic hindrances for mobile robot device as described in claim7.

DETAILED DESCRIPTION OF THE INVENTION

FIG. 1shows a flow chart of the moving route planning method for a mobile robot device according to the present invention, andFIG. 2A˜2Dshow the application diagrams of the moving route planning method in a physical site according to the present invention. The moving route planning method10for a mobile robot device according to the present invention includes the step101and step103. Step101generates a relative mesh grid diagram20based on a physical site5. The mesh grid diagram20comprises a plurality of map grids201containing hindrance parameter values, in which the hindrance parameter values for each map grid201are determined by the locations of hindrances in the physical site5at the relative location.

Please refer toFIG. 2A. The physical site5includes the hindrances12a˜12b. The mobile robot device (not shown), such as a robot, first reads the plane map of the physical site5and generates the relative mesh grid diagrams20based on the physical site5. In the mesh grid diagram20, it comprises a plurality of map grids201containing hindrance parameter values. The size for each map grid201can use 1 cm*1 cm, for example.

After completion of route planning, in order to provide the coordinate information about the moving route, the plurality of map grids201in the mesh grid diagram20can be given an identification number.

The hindrances12a˜12bappeared in the physical site5must be labeled in the mesh grid diagram20for the locations occupied by the hindrances12a˜12b. The hindrance parameter values for each map grid201are determined by the locations of the hindrances12a˜12bin the physical site5at the relative location. As for the block16labeled with hatched lines shown inFIG. 2B, the hindrance parameter values for the map grids201belonging to the block16will be all configured as “1”, for example, and the hindrance parameter values for other unoccupied map grids201will be all configured as “0”, for example. Moreover, in order to avoid the mobile robot device from moving outside the mesh grid diagram20, the edges of the mesh grid diagram20can be defined as continuous hindrances, and the hindrance parameter values of these map grids201will be all configured as “1.”

Step103is to continuously expand the map grid201from the start point14aand the target point14btoward the neighbored map grid201until the expanded map grids201meet with each other, and to define each map grid201in the expansion trace for meeting with each other as the moving route.

Please refer toFIG. 2C. According to the previous processing result in Step101, the map grids201from the start point14aand the target point14bcontinuously expand toward the neighbored map grids until the expanded map grids201meet with each other, and defining each map grid201in the expansion trace for meeting with each other as the moving route18. In other words, it just looks like the expansion of water waves by throwing two stones into a pool, and encountering at last. For example, when the map grids201continuously expand from the start point14aand the target point14btoward the neighbored map grids201, the map grid201at the start point14aand the map grid201at the target point14bwill continuously expand toward the map grids201in a cross shape, that is, up, down, left and right. The expanded map grids201will continuously expand toward the four neighbored map grids201in up, down, left and right directions until the expanded map grids201from the start point14aand the target point14bmeet with each other, that is the location of the meeting point18a.

Then, the location at the meeting point18awill be divided into two directions, which are respectively back to the start point14aand the target point14b, and forming the expansion trace from the meeting point18aback to the start point14aand the target point14b, which are the passed map grids201, and defining the two traces as the moving route18, as shown inFIG. 2D.

Except of continuously expanding toward the neighbored map grids201in a cross shape, it can also continuously expand toward the eight neighbored map grids201in a “*” shape instead.

Because the mobile robot device occupies a certain projection area, such as 40 cm*40 cm, it should relatively adjust the occupied map grids201outwardly for the map grids occupied by the hindrances12a˜12bin the mesh grid diagram5according to the size of the mobile robot device. For example, it will expand outwardly 20 cm from the center point of the mobile robot device, and will add the protection range of 10 cm, so it will totally expand 30 cm outwardly, that is, the map grids occupied by the hindrances12a,12bwill relatively be adjusted with 30 cm outwardly, and thus further adjusting to increase the occupied map grids201. Similarly, the map grids201located on the edges of the mesh grid diagram20will be relatively adjusted with 30 cm outwardly, so as to further adjust to increase the occupied map grids201.

Ideally, the planned moving route18can avoid the existed hindrances. However, in order to avoid the dynamic hindrances, which don't belong to the originally existed hindrances12a,12bin the physical site5, the mobile robot device can be configured with sensors, such as infrared sensor or ultrasonic sensor, so as to anytime detect the dynamic hindrances encountered in the moving process.

FIG. 3shows a flow chart of the navigation method for avoiding dynamic hindrances applied in the mobile robot device according to the present invention, andFIG. 4A˜4Cshow the diagrams of the moving route in a physical site for the mobile robot device with the navigation method according to the present invention. The navigation method30for avoiding dynamic hindrances applied in the mobile robot device according to the present invention includes the moving route planning step31and the moving step33for avoiding dynamic hindrances. The two steps311,313of the moving route planning step31are respectively identical with the steps101,103, which will not be repeatedly described.

Referring toFIG. 4A, if there is not any dynamic hindrance in the moving route18, the mobile robot device moving with the step333and the step335will move through the map grids201with identification numbers201a,201b,201c,201d,201e,201f,201g,201n,201oand201p, and finally reach the target point14b.

In the step331of moving step33for avoiding dynamic hindrances, when moving along the moving route18from the moving route planning step31and before entering the midway location, it will detect the hindrances originally not belonging to the physical site, and then define the hindrances as dynamic hindrances20. Referring toFIG. 4B, at the midway location in the moving route18, the map grid201corresponding to the midway location with identification number201dhas a hindrance. The mobile robot device will move along the moving route18from the moving route planning step31, and move through the map grids201with identification numbers201a˜201c. Before the mobile robot device moves to the midway location, that is, the map grid201with identification number201c, the hindrance will be detected and defined as dynamic hindrance20.

Next, in the step333of moving step33for avoiding dynamic hindrances, the turning direction is equal to that of the next turning location. The mobile robot device turns the turning direction at the location where it detects the dynamic hindrance20. After turning, it will continue moving along the right-hand dynamic hindrance20if the previous turning direction was a left turn; and, it will continue moving along the left-hand dynamic hindrance20if the previous turning direction was a right turn.

Please refer toFIG. 4BandFIG. 5. As for the midway location, the next turning location at the midway location is the map grid201with identification number201g. The turning direction at the map grid201with identification number201gis a right turn. The mobile robot device will turn right at the map grid201with identification number201caccording to the turning direction at the next turning location. After the turning, the mobile robot device will determine which side of the dynamic hindrance to move along. If the previous turning direction was a left turn, it will continue moving along the right-hand dynamic hindrance20; and, if the previous turning direction was a right turn, it will continue moving along the left-hand dynamic hindrance20.

Following the example description ofFIG. 4B, the mobile robot device will turn right at the map grid201with identification number201c. After the right turn, then the mobile robot device will determine if the previous turning direction was a right turn, it will continue moving along the left-hand dynamic hindrance20, and move through the map grids201with identification numbers201h,201i,201jand201e.

Furthermore, in the step335of moving step33for avoiding dynamic hindrances, if the mobile robot device has detected another new dynamic hindrance in the front and can not continue move along the dynamic hindrance20, it will turn backward at the location. After turning backward, then it will continue moving along the-other-hand dynamic hindrance.

Please refer toFIG. 4CandFIG. 5. After detecting the dynamic hindrance20, due to the right turn at the next turning point, the mobile robot device turned right at that time, and moved along the dynamic hindrance20, which is the left-hand side of the mobile robot device. If the map grids occupied by the dynamic hindrances20are so many that the mobile robot device must still continue moving along the left-hand hindrance, for example the dynamic hindrance20inFIG. 4Coccupies the map grids201d,201i, and if another dynamic hindrance20′ is detected in front of the mobile robot device, i.e. the map grid201qinFIG. 4Chas been occupied by the dynamic hindrance20′, that is, the mobile robot device will still encounter the hindrance moving along the left wall. Under such a circumstance, the mobile robot device will turn around.

At this time, the mobile robot device will turn backward at the map grid201with identification number201h, that is 180° turn. After turning backward, then it will continue moving along the-other-hand dynamic hindrance20, and the-other-hand side is the right-hand side. The mobile robot device continuing moving along the right-hand dynamic hindrance20will move through the map grids201with identification numbers201c,201k,201l,201mand201e.

Next, in the step337of the moving step33for avoiding dynamic hindrances, when moving in the step333and the step335, the mobile robot device will determine if it has reached the moving route18; if so, it will continue moving along the moving route18.

The mobile robot device moving with the step333and the step335will reach the map grid with identification number201e. When reaching the map grid201with identification number201e, the mobile robot device will determine it has reached the moving route18.

Then, in the step339of moving step33for avoiding dynamic hindrances, it will repeat the step331to337until reaching the target point. The mobile robot device avoiding the dynamic hindrances20,20′ will move through the map grids201with identification numbers201f,201g,201n,201oand201pwith the moving method from step331to step337, and finally reach the target point14b.

FIG. 6shows the structural diagram of the mobile robot device applying with the method according to the present invention. The hardware composition of the mobile robot device applying with the method according to the present invention may employ the prior art. The moving route planning method10and the navigation method30according to the present invention can be programmed into program codes, and the program codes are written in a flash memory403. At least one sensor405is used to detect the hindrances. The controller401executes the program codes, and receives the signal generated by the sensors405. The moving mechanism unit409is used to at least drive the mobile robot device moving forward, turning and stopping moving, and the moving mechanism unit409is controlled by the controller401. Because the digital data for the relative mesh grid diagram20generated based on the physical site5is stored in the memory407, and the memory407can employ the volatile memory and non-volatile memory.

In a summary, the moving route planning method and the navigation method for avoiding dynamic hindrances according to the present invention can be applied in the mobile robot device. Thus, it only needs to enter the digital map data corresponding to the physical site into the mobile robot device, and the mobile robot device will be able to plan the moving route from the start point to the target point, and rapidly avoid the dynamic hindrances based on the navigation method, and continue moving toward the destination, which is the benefit of the present invention.

The detailed description for the preferred embodiments are used to clearly describe the features and spirit of the prevent invention, but not limit the scope of the present invention with these disclosed preferred embodiments. On the opposite, the object is to cover all kinds of changes and equivalent arrangements within the scope of the claims applied in the present invention.