JPH067366B2 - Optimal Route Search Method for Mobile Robot System - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Industrial field of application] The present invention provides an optimal route search in a mobile robot system that allows a mobile robot such as an autonomous unmanned vehicle to quickly go to a work point where a work request is generated. Regarding the method.

[Prior Art] Currently, mobile robots are being actively developed, and it is an important issue to improve the performance of the mobile robot system as a whole, not to mention the performance of the mobile robot itself.

A typical mobile robot system of this type is composed of a plurality of mobile robots and one central station that controls the mobile robots. Then, each mobile robot travels to a work point and performs a predetermined work according to an instruction from the central station. The central station manages the map information of the moving area of the mobile robot, monitors the current position of all the mobile robots and the status such as whether or not they are working, and communicates with the mobile robots by wireless or wired communication means. Give work instructions.

That is, when a work request occurs at any work point,
The central station gives a command by selecting the most suitable mobile robot to reach the work point from among the mobile robots that are not working. Here, as a method of selecting the mobile robot, a simple method of selecting the mobile robot having the shortest linear distance to the work point, or the central station calculating the optimum route for each mobile robot to reach the work point, There is a method of selecting the most suitable mobile robot for this work.

[Problems to be Solved by the Invention] By the way, among the above-mentioned conventional selection methods, the method of selecting the mobile robot closest to the work point may cause a large route even if the straight line distance is short. There are also cases where the mobile robot is not selected. For example, as shown in FIG. 3, although the current position of the mobile robot 1 and the work point 2 are extremely close to each other, the route 3 makes a large turn, so that the optimum mobile robot is the mobile robot 4. This is the case.

On the other hand, for all mobile robots that are not currently working, the central station searches for the optimal route to the work point and selects the optimal mobile robot from among them. There has been a problem that the search time is lengthened proportionately and rapid processing cannot be performed.

The present invention has been made in view of such a background, and an object thereof is to provide an optimum route search method in a mobile robot system, which can quickly determine a mobile robot to move to a work point.

[Means for Solving Problems] In order to solve the above problems, the present invention comprises a central station and a plurality of mobile robots that move to a work point designated by the central station and perform a predetermined work. In the robot system described above, a first step in which the central station commands each mobile robot to perform a route search and its evaluation, and a mobile robot in a standby state among the mobile robots is operated in parallel according to the command. And a second step of searching for an optimal route from each current position to the work point, the mobile robot in the standby state calculates an evaluation value corresponding to the length of the searched optimal route, and The third step of sending to the central station, the central station compares the evaluation value sent from the mobile robot in the standby state and sends the best evaluation value to the mobile robot. A fourth step of selecting, said central station, and having a fifth step of instructing to move to the machining point on the selected mobile robot.

[Operation] According to the above configuration, the processing for the optimum route search is distributed to the plurality of mobile robots in the standby state and is performed in the form of parallel processing, so that the processing efficiency is improved and the search can be performed in an extremely short time. finish. Further, during the search process, the processing load of the central station is significantly reduced as compared with the conventional case, so that the central station can perform other processing.

Since each mobile robot returns an evaluation value to the central station, not the search route, the central station can quickly determine the mobile robot at the optimum position. Also, while the central station makes this determination, each mobile robot can prepare for movement based on the route searched for when it is selected.

Embodiments Embodiments of the present invention will be described below with reference to the drawings.

FIG. 1 is a block diagram showing the configuration of an embodiment of the present invention. In the figure, 11 is a central station, 12-k (k = 1,2 ... n)
Are n mobile robots, and the central station 11 and each mobile robot 12-k are connected by wireless or wired communication selection 13-k.

The central station 11 has a CPU and a memory, and keeps track of the current position of each mobile robot 12-k and the status of whether or not work is in progress. Further, it is connected to each work point, receives a work request from the work point, and transmits this information to each mobile robot 12-k.

On the other hand, the mobile robot 12-k has the configuration shown in FIG. In the figure, reference numeral 21 denotes a traveling device of the mobile robot 12-k, and the traveling device 21 has a CP for controlling the traveling thereof.
U22 is connected. A memory 23 is connected to the CPU 22, and the memory 23 stores the coordinates of each work point and map data indicating the connection relationship of the work points.

The CPU 22 searches for a route from the current work point to the target work point. In this search, the node is selected by the following calculation and the evaluation value Hs is calculated.

First, let s be the starting node, G be the destination node, and Vi and Vj be consecutive intermediate nodes, and an evaluation function H (Vi, Vjx) for selecting the node Vj from the nodes Vi is defined by the following formula.

H (Vi, Vjx) = Wa * A (Vjx, G) + Wb * B (Vi, Vjx) ... (1) However, A (Vjx, G) = 1 (Vjx, G) / L ... (2) B (Vi, Vjx) = 1 (Vi, Vjx) / L (3) where 1 (Vjx, G) is the distance between the next candidate node Vjx and the destination node G, and 1 (Vi, Vjx) is the current node. Vi is the distance between the next candidate node Vjx and L is the maximum distance between the nodes, that is, in the case of the map model as shown in FIG. 4, for example, the distance between the node 1 and the node 16 or the distance between the node 4 and the node 13. Is. Therefore, the value A (Vjx,
G) and B (Vi, Vjx) are normalized by the distance L, take a value of 0 to 1, and the smaller the value, the better the evaluation.
0 is the best and 1 is the worst. Wa and Wb are coefficients for weighting the variables A (Vjx, G) and B (Vi, Vjx).

At this time, in the map model shown in FIG.
It is assumed that the distances between adjacent nodes of .about.16 are equidistant, and the above values B (Vi, Vjx) are all equal. Further, it is assumed that the departure node S is the node 10 and the destination node G is the node 4.

In this case, the next candidate nodes Vjx of the departure node 10 are the nodes 6, 9, 11, and 14. When the equation (1) is applied to these next candidate nodes 6, 9, 11, and 14, A (Vj
Nodes 6 and 11 are selected as the next candidate node Vjx that minimizes x, G).

Next, the node 7 is selected as the next candidate node Vjx of the node 6 among the nodes 2, 5 and 7 as the one that minimizes A (Vjx, G). Further, as the next candidate node Vjx of the node 11, of the nodes 7, 12, 15
Node 7 is selected as the one that minimizes A (Vjx, G). Similarly, the nodes 3 and 8 are selected next to the node 7, and the destination node 4 is selected next to them.

Thus, as an optimal route, 10 → 6 → 7 → 3 → 4, 1
0 → 6 → 7 → 8 → 4, 10 → 11 → 7 → 3 → 4 or 10 → 11 → 7 → 8 → 4 is searched.

Then, with respect to the optimum route thus obtained, the sum total of the values of the evaluation function H (Vi, Vjx) from the starting node 10 to the destination node 4, that is, the evaluation value Hs is calculated by the following expression (4).

Hs = ΣH (Vi, Vjx) (4) The smaller the evaluation value Hs, the better the evaluation as the searched optimum route. The evaluation values Hs of the four optimum routes searched in this example are all equal.

In this way, the evaluation values Hs of the optimum routes are calculated for the mobile robots located at different departure nodes S, respectively.

In such a configuration, when a work request is generated at a certain work point, the work request is transmitted to the central station 11, and the central station 11 instructs all the mobile robots 12-k on standby to search for the optimum route. CPU 22 of mobile robot 12-k instructed to search
Calculates the evaluation value Hs by searching the route from the starting work point (that is, the current position of the user's own body) S to the target work point G by the above equations (1) to (4). Then, the route that gives the best evaluation value Hs is recorded, and this best evaluation value Hs is transmitted to the central office 11.

The central station 11 compares the evaluation values Hs sent from the mobile robots 12-k, selects the best evaluation value Hs from the evaluation values Hs, and sends the best evaluation value Hs.
Send move command to -k. Mobile robot 1 that receives a movement command
2-k follows the searched route and moves to the target work point G.

In addition, in the above embodiment, the map data is built in each mobile robot, but the mobile robot may be configured to receive the map data from the central station if necessary.

[Effects of the Invention] As described above, according to the present invention, since the optimum route search is performed in parallel in each mobile robot, the search can be completed in an extremely short time. Further, during the search process, the processing load of the central station is significantly reduced as compared with the conventional case, so that the central station can perform other processing.

Since each mobile robot returns an evaluation value to the central station, not the search route, the mobile robot at the optimal position in the central station can be quickly determined. Also, while the central station makes this determination, each mobile robot can prepare for movement based on the route searched for when it is selected.

In this way, it is possible to effectively utilize the mobile robot as a resource, reduce the load on the central station, and improve the responsiveness of the entire system. Further, the central station can detect the abnormality of each mobile robot depending on whether or not the mobile robot returns the search result.

[Brief description of drawings]

FIG. 1 is a block diagram showing the configuration of a mobile robot system according to an embodiment of the present invention, and FIG. 2 is a mobile robot 12.
-k is a block diagram showing the configuration, FIG. 3 is a plan view for explaining the positional relationship between a work point and a mobile robot, and FIG. 4 is a conceptual diagram showing an example of a map model. 11 ... Central station, 12-k ... Mobile robot.

Claims (1)

[Claims] 1. A robot system comprising a central station and a plurality of mobile robots that perform a predetermined work by moving to a work point designated by the central station, wherein the central station searches for a route to each mobile robot. A first step instructing to perform the evaluation, and a mobile robot in a standby state among the mobile robots searches for an optimum route from each current position to the work point in parallel according to the command. A second step, a third step in which the mobile robot in the standby state calculates an evaluation value corresponding to the length of the searched optimum path, and a third step of sending the evaluation value to the central station; A fourth step of comparing the evaluation values sent from the mobile robot in the standby state and selecting the mobile robot having sent the best evaluation value; and the central station selecting the selected mobile robot. Optimum route searching method in a mobile robot system, comprising a fifth step of instructing to move to the working point to the mobile robot.