JPH05101035A - Optimum route searching method for mobile robot - Google Patents

Abstract

PURPOSE:To reduce the danger of selecting a route to be a detour by selecting the route to advance at a branch node based on the total evaluation of respective routes to the next node. CONSTITUTION:Assuming that a branch node Vi (a node 1, for example,) is reached while searching the route from a start node S to a target node G, in this case, a CPU 22 executes the total evaluation of the respective routes between the current node Vi and the next node (node 6, for example,) connected to this node. The evaluation of move throughout respective nodes 1-9, G and S is executed as follows; namely, evaluation functions H (Vi and Vjx) are applied to the current node Vi and a next candidate node Vjx, and the evaluation is executed concerning the move between the current node Vi and the next candidate node Vjx. In this way, the total evaluation value of the respective routes between the additional branch nodes (nodes 1 and 6, for example,) of evaluation values for the move throughout the respective nodes 1-9, G and S is calculated and based on this value, the route is selected. Thus, the more suitable route selection is enabled without selecting the detour.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a method for searching an optimum route of a mobile robot, which is suitable for application to a mobile robot such as an autonomous unmanned vehicle.

[0002]

2. Description of the Related Art In order to efficiently operate a mobile robot system, it is necessary that the mobile robot always follow an optimum route with minimum time loss when the mobile robot is moved from its present position to its destination. is there. Therefore, various studies have been made on the problem of searching for the optimum route between two points on the map, and various methods for solving this problem have been proposed. For example, in a memory built in the mobile robot, data indicating a straight line distance between each node existing on the map and a connection relationship between each node is stored, and based on these data, the current position node Vi A method has been proposed for determining the node Vj to go to. This optimum route search method proceeds according to the procedure described below. (1) Each route from the departure node S to the destination node G is searched by a known method such as vertical search or horizontal search.
Then, from among the nodes connected to the intermediate node Vi, the candidate node Vjx (x = 1, 1) of the node Vj to be advanced next.
2, ...) is selected. (2) Evaluate each movement operation that proceeds from the current position node Vi to each candidate node Vjx, and select the node Vj having the highest evaluation value. (3) This operation is repeated until the destination node G is reached.

[0003]

By the way, when the optimum route search is performed by the above-described optimum route search method, the next step is performed only by the evaluation performed on the branch point node and each next candidate node directly connected to the branch point node. Since the node to go to is decided, there is a problem that a non-optimal route may be searched. For example, in FIG.
When proceeding from the departure node S to the branch node 1, either the node 2 or the node 5 is selected. At this point, traveling to node 2 will be accompanied by a loss due to a direction change. However, even if the evaluation value when this loss proceeds to the node 2 is lowered, if the term related to the distance to the target node G effectively acts to increase the evaluation value, the node 2 is selected. .. However, once the node 2 is selected, the non-optimal routes S, 1, 2, 3, 4,
6, 7, 8, 9, and G are searched. The optimum routes in this case are S, 1, 5, 6, 7, 8, 9, and G. The present invention has been made in view of the above circumstances, and does not select a detouring route,
It is an object of the present invention to provide an optimal route search method for a mobile robot that can search the optimal route more accurately.

[0004]

An optimum route searching method according to the present invention is a mobile robot which determines a route based on map information stored in advance and travels during route searching.
When a branch node is reached, the next node to be advanced is determined according to the evaluation up to the next branch node.

[0005]

According to the above method, a comprehensive evaluation is performed for each route between the branch node and each branch node connected thereto, and based on the result of this comprehensive evaluation, the next node to be advanced from the branch node concerned. Node of is determined. In this way, the target of evaluation at the time of route selection was expanded to a wide range of nodes,
The risk of choosing a detour route is reduced.

[0006]

BEST MODE FOR CARRYING OUT THE INVENTION An optimum route searching method for a mobile robot according to an embodiment of the present invention will be described below with reference to the drawings.
FIG. 1 is a block diagram showing the configuration of a mobile robot to which the optimum route searching method is applied. In the figure, reference numeral 21 denotes a traveling device of a mobile robot, and a CPU (central processing unit) 22 for controlling the traveling is connected to the traveling device 21. A memory 23 is connected to the CPU 22,
The memory 23 stores the coordinates of each node illustrated in FIG. 2 and map data indicating the connection relationship between the nodes. The CPU 22 receives a work instruction (target node G and work to be performed by the target node G) from an external control station. Then, referring to the map data stored in the memory 23, the optimum route from the departure node S to the destination node G is searched.

The method for searching for the optimum route according to this embodiment will be described below with reference to the case shown in FIG. It is assumed that the branch node Vi (for example, the node 1) is reached during the route search. In this case, comprehensive evaluation is performed on each path between the current node Vi and the next branch node (for example, node 6) connected to the current node Vi. In this comprehensive evaluation, the evaluation of the movement between the nodes is performed as follows. That is, the current node V
The evaluation function H (Vi, Vjx) shown in the following formula is applied to i and the next candidate node Vjx to evaluate the movement between the current node Vi and the next candidate node Vjx.

[Equation 1] In the above formula 1, A (Vjx, G) is the next candidate node V
A loss term B determined by the distance between jx and the target node G, B
(Vi, Vj) is the current node Vi and the next candidate node Vjx
It is a loss term determined by the distance between and. Also, C
(Θ) is a loss term determined by an angle θ formed by the traveling direction at the node Vi (that is, the direction of the line segment connecting the previous node and the current node Vi) and the line segment connecting the nodes Vi and Vj. Wa, Wb and Wc are coefficients for weighting. However, the next candidate node Vjx
If is not a branch node, Wa = 0 in the above mathematical expression 1
The evaluation function is used to evaluate. This is because it is meaningless to evaluate a node that is not a branch node in consideration of the distance from the target node. By adding the evaluation values of the movements between the respective nodes obtained in this way, a comprehensive evaluation of each route between the branch nodes is performed, and a route is selected based on the comprehensive evaluation value.

In the example shown in FIG. 2, when the search proceeds to the branch node 1, according to the evaluation function with Wa = 0 in the evaluation function of the above equation 1, movement between the nodes 1 and 2, movement between the nodes 2 and 3, Calculate with each evaluation value for the movement between the nodes 3 and 4. Then, the evaluation value for the movement between the nodes 4 and 6 is calculated by the evaluation function of the above mathematical expression 1. The respective evaluation values thus obtained are added to obtain the total evaluation value of the route passing through the nodes 1, 2, 3, 4, and 6. By the same method, the respective evaluation values for the movement between the nodes 1 and 5 and the movement between the nodes 5 and 6 are calculated and added to obtain the total evaluation value of the route passing through the nodes 1, 5, and 6. Then, the route with the higher overall evaluation value is selected. By selecting this route, the route search to the branch node 6 also ends at the same time.

[0009]

As described above, according to the optimum route searching method of the present invention, in a mobile robot which determines a route based on map information stored in advance and travels,
When a branch node is reached during route search, the node to proceed to next is determined according to the evaluation up to the next branch node, so the risk of selecting a detour route is reduced, and the optimal circuit is searched more accurately. The effect is that you can.

[Brief description of drawings]

FIG. 1 is a block diagram showing a configuration of a mobile robot to which an optimum route search method according to an embodiment of the present invention is applied.

FIG. 2 is a diagram illustrating a traveling path of a mobile robot.

[Explanation of symbols]

 C: control station, R1 to Rn: mobile robot.

Claims (1)

[Claims] 1. A mobile robot that travels by determining a route based on pre-stored map information, and when a branch node is reached during a route search, the node to proceed to is determined according to the evaluation up to the next branch node. A method for searching an optimal path for a mobile robot, which is characterized by making a decision.