JP6948632B2 - Information processing equipment, information processing system, movement route determination method and program - Google Patents

Description

The present invention relates to an information processing device, an information processing system, a movement route determination method and a program.

Conventionally, various methods such as an exploratory method (for example, a genetic algorithm) have been proposed as a method for finding an optimum route for patrolling a plurality of points with a plurality of moving bodies.

Further, for example, in Patent Document 1, an optimum route for patrolling a plurality of points by a plurality of moving bodies is created based on an evaluation index using the degree of interference as an evaluation function, and an optimum route is created between the moving bodies in the created optimum route. A method has been proposed in which the evaluation index is changed and the optimum route is recreated until the interference disappears.

However, in the conventional technique as described above, the occurrence of interference between the moving bodies is avoided by changing the route. That is, in the conventional technique as described above, since the occurrence of interference between the moving bodies is avoided by detouring, the route avoiding the occurrence of interference is suitable from the viewpoint of the moving distance and the moving time of the moving bodies. Not necessarily.

The present invention has been made in view of the above circumstances, and is an information processing device and an information processing system capable of avoiding interference between mobile bodies so that the movement path of the entire moving body is more preferred. , It is an object of the present invention to provide a method and a program for determining a movement route.

In order to solve the above-mentioned problems and achieve the object, the information processing apparatus according to one aspect of the present invention includes a generation unit that generates a movement path for each of the plurality of moving bodies, and the plurality of the plurality of moving bodies. A determination unit that determines whether or not interference occurs between at least two or more moving bodies among the plurality of moving bodies as the movement of the moving path occurs, and if the interference occurs, the two or more moving bodies. The generation unit includes an update unit that updates the movement route so as to avoid the interference by temporarily making one of the moving objects wait on the movement route, and the generation unit moves between a plurality of nodes. The plurality of movement paths are generated on a one-layer network composed of connecting arcs, and the update unit is a network in which the one-layer network is multi-layered, and the node on which the interference occurs and the update unit. On a multi-layered network where entry into the arc is prohibited, the movement path of the one moving body is updated so as to avoid the interference, and the waiting is represented by the movement between layers in the multi-layered network. Ru .

According to the present invention, there is an effect that interference between mobile bodies can be avoided so that the movement path of the entire moving body is more preferred.

FIG. 1 is a block diagram showing an example of the configuration of the information processing system of the first embodiment. FIG. 2 is a block diagram showing an example of the hardware configuration of the information processing apparatus of the first embodiment. FIG. 3 is a block diagram showing an example of the functional configuration of the information processing apparatus of the first embodiment. FIG. 4 is a flowchart showing an example of the movement route generation process performed in the information processing system of the first embodiment. FIG. 5 is an explanatory diagram of an example of the network configuration of the first embodiment. FIG. 6 is an explanatory diagram of an example of a node ID, a robot ID, and a transit time registered in association with the auxiliary storage device. FIG. 7 is an explanatory diagram of an example of the interference determination method of the first embodiment. FIG. 8 is an explanatory diagram of an example of the interference determination method of the first embodiment. FIG. 9 is an explanatory diagram of an example of the interference determination method of the first embodiment. FIG. 10 is an explanatory diagram of an example of the interference determination method of the first embodiment. FIG. 11 is an explanatory diagram of an example of the interference determination method of the first embodiment. FIG. 12 is a flowchart showing an example of the movement route determination process performed by the information processing apparatus of the first embodiment. FIG. 13 is a block diagram showing an example of the functional configuration of the information processing apparatus of the second embodiment. FIG. 14 is an explanatory diagram of an example of the interference determination method of the second embodiment. FIG. 15 is an explanatory diagram of an example of the interference determination method of the second embodiment. FIG. 16 is an explanatory diagram of an example of the interference determination method of the second embodiment. FIG. 17 is an explanatory diagram of an example of the movement route updating method of the second embodiment. FIG. 18 is an explanatory diagram of an example of the movement route updating method of the second embodiment. FIG. 19 is an explanatory diagram of an example of the movement route updating method of the second embodiment. FIG. 20 is an explanatory diagram of an example of the movement route updating method of the second embodiment. FIG. 21 is an explanatory diagram of an example of the movement route updating method of the second embodiment. FIG. 22 is an explanatory diagram of an example of the movement route updating method of the second embodiment. FIG. 23 is an explanatory diagram of an example of the movement route updating method of the second embodiment. FIG. 24 is a flowchart showing an example of the movement route determination process performed by the information processing apparatus 10 of the second embodiment.

Hereinafter, embodiments of the information processing apparatus, information processing system, movement route determination method, and program according to the present invention will be described in detail with reference to the accompanying drawings.

In each of the following embodiments, the avoidance of interference between the moving bodies in the moving path of each moving body for patrolling a plurality of points existing on the moving path with the plurality of moving bodies will be described as an example, but the present invention is limited to this. It is not something that will be done. Specifically, the movement path is a movement path in the warehouse, and a plurality of points existing on the movement path are points where a plurality of products distributed and stored in the warehouse are arranged, and a plurality of movements. The body is a robot (cart) distributed and arranged in a warehouse to collect (pick) the plurality of products, and a picking operation of picking a plurality of products stored in the warehouse with a plurality of robots. Will be explained as an example, but the present invention is not limited to this. More specifically, the movement path in the warehouse is a network-like path composed of a plurality of nodes and an arc connecting the nodes, and the goods and the robot are arranged in any node. However, the explanation is not limited to this. In the case of such a network-shaped path, there are two patterns of interference between robots, one is when two or more robots enter the same node at the same time, and the other is when two or more robots pass each other on the same arc. Can be mentioned. Further, in each of the following embodiments, the case where the robot (cart) is a moving body that automatically moves independently will be described as an example, but the present invention is not limited to this, and the robot (cart) is manually moved by the user. There may be.

(First Embodiment)
FIG. 1 is a block diagram showing an example of the configuration of the information processing system 1 of the first embodiment. As shown in FIG. 1, the information processing system 1 includes an information processing device 10, a terminal device 20, and output devices 30-1 to 30-n (n is a natural number of 2 or more). The information processing device 10, the terminal device 20, and the output devices 30-1 to 30-n are connected via the network 2. The network 2 can be realized by, for example, the Internet or a LAN (Local Area Network). In the following description, when it is not necessary to distinguish the output devices 30-1 to 30-n, they may be simply referred to as the output device 30.

The information processing device 10 generates and updates the movement paths of each of the plurality of robots for patrolling and collecting a plurality of products existing on the movement path by the plurality of robots. For example, one or more of them. It can be realized by a computer.

FIG. 2 is a block diagram showing an example of the hardware configuration of the information processing apparatus 10 of the first embodiment. The information processing device 10 includes a control device 101 such as a CPU (Central Processing Unit) and a GPU (Graphics Processing Unit), a main storage device 102 such as a ROM (Read Only Memory) and a RAM (Random Access Memory), and an HDD (Hard). Auxiliary storage devices 103 such as Disk Drive) and SSD (Solid State Drive), display devices 104 such as displays, input devices 105 such as keyboards and mice, and communication devices 106 such as communication interfaces are provided. It has a hardware configuration that uses a normal computer.

The terminal device 20 specifies a plurality of products to be collected with respect to the information processing device 10, and examples thereof include a PC (Personal Computer) and a smart terminal.

The output device 30 outputs a movement path determined by the information processing device 10. In the first embodiment, each output device 30 is associated with (equipped with) a robot, and outputs a movement path for the robot. Examples of the output device 30 include a display and a speaker provided in the robot, and a smart terminal owned by the user when the user moves the robot. The movement path may be output in any output mode such as display output, audio output, projection output, and print output.

FIG. 3 is a block diagram showing an example of the functional configuration of the information processing apparatus 10 of the first embodiment. As shown in FIG. 3, the information processing apparatus 10 includes a generation unit 151, a determination unit 153, an update unit 155, and a transmission unit 157. The generation unit 151 and the transmission unit 157 can be realized by, for example, a control device 101, a main storage device 102, a communication device 106, and the like. The determination unit 153 and the update unit 155 can be realized by, for example, the control device 101 and the main storage device 102.

The generation unit 151 generates a movement path for each of the plurality of moving bodies. In the first embodiment, the generation unit 151 generates a movement path for each of the plurality of robots for patrolling and collecting a plurality of products existing on the movement path by the plurality of robots. In the first embodiment, the generation unit 151 generates a plurality of movement paths on a one-layer network composed of a plurality of nodes and arcs connecting the nodes.

Examples of the one-layer network include a First layer network having the network configuration shown in FIG. The Second layer network having the network configuration shown in FIG. 5 will be described later. Further, in the network configuration shown in FIG. 5, points represent nodes, and lines connecting the points represent arcs. In the first embodiment, it is assumed that the distance between the nodes connected by the arc is 1.

In the first embodiment, the movement paths of a plurality of robots may be generated by any method, but the time required for generation is short, and the movement time (movement distance) of the entire movement path can be shortened as much as possible. Such a method is preferable. For this reason, it is preferable to generate a movement route using an algorithm for generating a movement route that satisfies the above conditions, but even if a movement route is generated using a genetic algorithm as long as the generation time constraint is satisfied. I do not care. It is assumed that the moving speed of each moving body is fixed at a constant speed.

FIG. 4 is a flowchart showing an example of the movement route generation process performed by the information processing system 1 of the first embodiment. The flowchart shown in FIG. 4 is a flowchart of a movement route generation process by an algorithm for generating a movement route satisfying the above conditions. According to this algorithm, it is possible to generate a movement path in which the time required for generation is short and the total movement time (movement distance) can be shortened as much as possible.

First, prior to the generation of the movement path, the generation unit 151 generates the movement start position information and the movement end position information of each of the plurality of robots, the collection target position information of each of the plurality of products collected by the plurality of robots, and the movement path. Acquire information (step S101).

The movement start position information indicates the movement start position of the robot, the movement end position information indicates the movement end position of the robot, the collection target position information indicates the position of the product, and the movement path information indicates the robot can move. The moving path (the above-mentioned network) is shown.

Subsequently, the generation unit 151 uses the acquired plurality of movement start position information, the plurality of movement end position information, the plurality of collection target position information, and the movement path information for each of the plurality of robots for each product. The minimum movement amount required for the robot to move on the movement path, collect the goods from the movement start position, and reach the movement end position is calculated (step S103).

In the first embodiment, the case where the minimum movement amount and the movement amount described later are time will be described as an example, but the present invention is not limited to this, and the distance may be used. Further, in the first embodiment, the calculation of the minimum movement amount may be performed by using a known technique such as the Dikstler method or the A * Star method. In addition, when there are a plurality of movement routes with the minimum movement amount, all movement routes shall be obtained.

Subsequently, the generation unit 151 assigns the product having the maximum minimum movement amount among the plurality of products to the robot having the minimum movement amount required to collect the product among the plurality of robots (step). S105).

Subsequently, in the generation unit 151, the product not assigned to the collecting robot is placed on the movement path for the assigned robot to collect the product with the minimum movement amount and reach the movement end position with the minimum movement amount. If there is, the goods that are not assigned to the collecting robot are further assigned to the assigned robot (step S107).

Subsequently, there are still products that are not assigned to the robot to be collected (Yes in step S109), and the generation unit 151 collects the products having the maximum minimum movement amount among the remaining one or more products. If the robot that minimizes the minimum movement amount required for is not assigned (Yes in step S111), the product that maximizes the minimum value of the minimum movement amount is assigned to the robot (step S113). Then, the process returns to step S107.

On the other hand, in the generation unit 151, the robot that minimizes the minimum movement amount required for collecting the product having the maximum minimum movement amount among the remaining one or more products is not assigned (No. in step S111). ), If there is one or more robots that satisfy the determination formula for determining the degree of dispersion and no product is assigned (Yes in step S115), the minimum value of the minimum movement amount is the maximum among the one or more robots. The product having the maximum minimum movement amount is assigned to the robot having the minimum movement amount required for collecting the product (step S117). Then, the process returns to step S107.

The determination formula for determining the degree of dispersion includes, but is limited to, the minimum movement amount between the robot X and the product Q = the distance between the robot X and the robot Y + the minimum movement amount between the robot Y and the product Q. It's not a thing. The robot X is a robot that is a target of whether or not the determination formula is satisfied, the product Q is a product to be assigned, and the robot Y is an arbitrary robot.

When the above-mentioned determination formula is satisfied, it is determined that the arrangement of the robot X and the robot Y is local, and the robot X and the robot Y are recognized as being included in the group. In this case, since the product Q is assigned to the robot X instead of the robot Y, it is possible to prevent the product from being assigned to the robot Y in a biased manner.

If the generation unit 151 satisfies the determination formula for determining the degree of dispersion and there is no one or more robots to which the product is not assigned (No in step S115), the generation unit 151 has one or more remaining robots among the plurality of robots. The minimum movement amount of the product is such that the minimum movement amount required to collect the product with the maximum minimum movement amount is the minimum, and the robot with the minimum movement amount has the minimum increase in the movement amount. The product having the maximum minimum value is assigned (step S119). Then, the process returns to step S107.

Regarding the process of step S119, the movement amount is increased to the robot that collects the product having the shortest distance on the movement path with the product having the maximum minimum movement amount among the remaining one or more products. May be assigned so that the minimum value of the minimum movement amount is the maximum.

Further, regarding the process of step S119, the robot having the smallest movement amount among the one or more robots closest to the product having the maximum minimum movement amount among the remaining one or more products and the one or more robots closest to each other on the movement path. , The product that maximizes the minimum value of the minimum movement amount may be assigned so that the increase in the movement amount is minimized.

In step S109, when there are no products left that are not assigned to the robots to be collected (No in step S109), the generation unit 151 generates movement paths for a plurality of robots based on the allocation result (step S121).

The determination unit 153 determines whether or not interference occurs between at least two or more moving bodies among the plurality of moving bodies due to the movement of the plurality of moving paths by the plurality of moving bodies. Specifically, the determination unit 153 may simultaneously enter the same node among at least two or more robots among the plurality of robots as the plurality of robots move a plurality of movement paths. And determine if they may pass each other on the same arc. The determination unit 153 determines that interference occurs between two or more robots when they enter the same node at the same time or pass each other on the same arc.

When the determination unit 153 determines that interference occurs, the update unit 155 temporarily causes one of the two or more moving bodies to stand by on the moving path to avoid the interference. To update.

Specifically, the update unit 155 is a multi-layered network of one layer used for generating the movement paths of each of the plurality of robots by the generation unit 151, and enters the node and the arc where interference occurs. Update the movement path of one robot to avoid interference on a multi-layered network where is prohibited. The waiting of the robot on the movement path is represented by the movement between layers, and more specifically, the movement of one layer corresponds to the waiting of one step (the waiting for the time required for the movement of the distance 1). In the first embodiment, the case where the multi-layer network is a two-layer network will be described as an example, but the present invention is not limited thereto.

In the case of the example shown in FIG. 5, the generation unit 151 generates the movement path of each robot in the network of the First layer, but the update unit 155 determines that interference occurs by the determination unit 153. On a two-layer network in which the First layer network is multi-layered with the Second layer network, the movement path of one robot is updated so as to avoid interference. More specifically, the update unit 155 prohibits the entry into the node and the arc where the interference occurs on the First layer network, and can move from the First layer network to the Second layer network, but the Second player can move to the Second layer network. Under the rule that it is impossible to move from the layer network to the First layer network, the movement path of one robot is updated.

Further, when updating the movement route, the updating unit 155 may use a known technique capable of calculating the movement route that minimizes the movement time and the movement distance, such as the Dikstraler method and the A * star method. In general, algorithms such as the Dyxtrar method and the A * Star method cannot stay on the same node or return to the same node, but as in the first embodiment, by layering the network, they can be placed on the same node. Waiting can be represented by moving between layers.

That is, as described above, the movement path of one robot is set by using the Dikstrar method, the A * Star method, etc. on a multi-layered network that prohibits entry into nodes and arcs where interference occurs. By updating, it is possible to calculate the movement route that minimizes the movement time and the movement distance from the movement routes that avoid the interference points by detour and the movement routes that avoid the interference points by waiting.

In addition, when avoiding the interference point by detour, at least two or more even-numbered steps of avoidance action are required (although the movement time and movement distance increase by the even-numbered steps of two or more steps), the interference point is waited for. When avoiding with, the avoidance action from one step becomes possible. Therefore, it is possible to shorten the movement time and the movement distance of the movement route and to make the movement route more suitable by avoiding the interference point not only by detouring but also by using at least standby.

Hereinafter, a method of updating the movement path so as to avoid interference and determining the movement path of each robot will be specifically described.

The determination unit 153 sets a priority for each movement route generated by the generation unit 151, and determines the movement route while performing interference determination in the order of priority. The priority may be determined by any method, and the method does not matter.

First, the determination unit 153 determines that, for the movement route having the highest priority, the ID of each node constituting the movement route, the ID of the robot moving on the movement route having the highest priority, and the robot passing through the node. It is registered (stored) in the auxiliary storage device 103 in association with the time to be performed. The determination unit 153 determines the movement route with the highest priority without interference determination.

Subsequently, the determination unit 153 also includes the ID of each node constituting the movement route, the ID of the robot moving on the movement route having the highest priority, and the node, even for the movement route having the second highest priority. Is registered (stored) in the auxiliary storage device 103 in association with the time when the robot passes through.

FIG. 6 is an explanatory diagram of an example of a node ID, a robot ID, and a transit time registered in association with the auxiliary storage device 103. In the example shown in FIG. 6, the movement path of the robot whose ID is "Robot 1" has the highest priority. The movement path of the robot of "Robot1" is composed of nodes whose node IDs are "Node [i] [j]" and "Node [i] [j + 1]", and is "Node [i] [j]". Is associated with "Robot 1" and transit time (Time) "0", and "Node [i] [j + 1]" is associated with "Robot 1" and transit time (Time) "1". That is, the robot of "Robot1" is located at the node of Node [i] [j] at the time of Time "0", and is located at the node of Node [i] [j + 1] at the time of Time "1". You can see that it moves like this.

Further, in the example shown in FIG. 6, the movement path of the robot whose ID is "Robot2" has the second highest priority. The movement path of the robot of "Robot2" is composed of nodes whose node IDs are "Node [i] [j + 2]" and "Node [i] [j + 1]", and is "Node [i] [j + 2]". Is associated with "Robot 2" and transit time (Time) "1", and "Node [i] [j + 1]" is associated with "Robot 2" and transit time (Time) "2". That is, the robot of "Robot2" is located at the node of Node [i] [j + 2] at the time of Time "1", and is located at the node of Node [i] [j + 1] at the time of Time "2". You can see that it moves like this.

Then, the determination unit 153 uses the ID of the node, the ID of the robot, and the transit time registered in association with the auxiliary storage device 103 for the movement route having the second highest priority, and uses the robot of "Robot 1" and the transit time. Interference determination between robots of "Robot 2" is performed.

Specifically, in the determination unit 153, the robot of "Robot2" and the robot of "Robot1" are the same in each node constituting the movement path (movement path of the robot of "Robot2") having the second highest priority. Determine if it is located at the time. If this condition is satisfied, the same node will be entered at the same time, so the determination unit 153 determines that the robot of "Robot 2" interferes with the robot of "Robot 1".

Further, in the determination unit 153, in each set of two consecutive nodes constituting the movement path having the second highest priority (the movement path of the robot of "Robot 2"), "Robot 2" is set to one node at the time. At the time t, "Robot1" is located at the time t + 1, and at the other node, it is determined whether "Robot1" is located at the time t + 1 and "Robot1" is located at the time t. If this condition is satisfied, the robots of "Robot2" will interfere with the robot of "Robot1" because they will pass each other on the same arc.

Then, when the determination unit 153 determines that interference occurs between the robot of "Robot 1" and the robot of "Robot 2", the update unit 155 uses the above-mentioned method to avoid the interference of "Robot 2". The movement path of the robot is updated, and the determination unit 153 determines the movement path of the robot of "Robot 2".

Hereinafter, the above-mentioned processing is repeated in the order of the movement routes having the highest priority, and the movement routes of each robot are determined.

When the network is made into two layers, the determination unit 153 needs to perform the interference determination not only in the first layer network but also in the second layer network, but it is associated with the auxiliary storage device 103. Since the information of the node ID, robot ID, and transit time registered in the above corresponds to the information on the first layer network, the information obtained by delaying this information by one step is added to the information on the second layer network. The interference may be determined by using it as information.

Further, it is conceivable that various timings are possible for the timing of waiting to avoid interference (for example, the standby may be performed in the first step or the standby may be performed in the second step. From the viewpoint of shortening the travel time and travel distance of the travel route as much as possible, it is preferable to wait at the timing immediately before the interference occurs as much as possible.

For example, consider the case shown in FIG. In the example shown in FIG. 7, it is assumed that the robot A moves from A to A', the robot B moves from B to B', and the robot C moves from C to C'. The circles indicate nodes and the lines indicate arcs. In this case, the movement path that does not consider the interference of each robot is as shown in FIG. 8, and in the fourth step, the interference between the robot A and the robot B occurs at the node 13.

Here, when the robot A is made to stand by in the third step immediately before the interference occurs to avoid the interference, it is as shown in FIG. 9, and the maximum step of the movement path of each robot is 7 steps.

On the other hand, when the robot A is made to stand by in the first step at the start time to avoid the interference, as shown in FIG. 10, the interference between the robot A and the robot B at the node 13 can be avoided, but in the third step. , A new interference between the robot A and the robot C occurs at the node 3. Therefore, when the robot C is also made to stand by at the first step at the start time to avoid new interference, it is as shown in FIG. 11, and the maximum step of the movement path of each robot is 8 steps.

In this way, it is better to wait at the timing immediately before the interference occurs to suppress the probability of new interference occurring. Therefore, from the viewpoint of shortening the movement time and the movement distance of the movement route as much as possible, immediately before the interference occurs as much as possible. It is preferable to wait at the timing of.

When the moving route of each moving body is determined by the determination unit 153, the transmitting unit 157 transmits the moving route information indicating the moving route of the moving body to the output device 30 associated with the moving body for each moving body. Send.

Each output device 30 outputs the movement path indicated by the movement route information transmitted from the information processing device 10.

FIG. 12 is a flowchart showing an example of the movement route determination process performed by the information processing apparatus 10 of the first embodiment.

First, the generation unit 151 generates a movement path of each robot (however, the occurrence of interference between robots is not considered) for patrolling and collecting a plurality of products existing on the movement path by a plurality of robots. (Step S10).

Subsequently, the determination unit 153 sets the priority order for each movement route generated by the generation unit 151 (step S20).

Subsequently, if the interference determination of all the robots is not completed (No in step S30), the determination unit 153 updates the robot to be determined for interference (step S40). This update is performed in descending order of priority of the movement route.

Subsequently, the determination unit 153 determines whether or not interference occurs in the robot to be determined (step S50). If the robot to be determined is a robot that moves on the movement route with the highest priority, it is determined that interference does not occur, and the robot to be determined is a robot that moves on the movement route with the second highest priority. If, it is determined whether or not interference occurs with the robot that moves on the movement route with the highest priority, and the robot to be determined is the robot that moves on the movement route with the third highest priority. In some cases, it is determined whether or not interference occurs between the robot moving on the movement route having the highest priority and the robot moving on the movement route having the second highest priority.

Subsequently, when the determination unit 153 determines that interference does not occur in the determination target robot (No in step S50), the determination unit 153 determines (determines) the movement path of the determination target robot, and returns to step S30.

On the other hand, when the determination unit 153 determines that interference occurs in the robot to be determined (Yes in step S50), the determination unit 153 avoids the interference on the two-layer network in which the interference-occurring node and the arc are prohibited from entering. The determination (confirmation) is made by updating the movement path of the robot to be determined (step S60), and the process returns to step S30.

Then, the determination unit 153 ends the process when the interference determination of all the robots is completed (Yes in step S30) and the movement paths of all the robots are determined.

As described above, according to the first embodiment, since the interference point is avoided not only by detouring but also by waiting, interference between moving bodies is avoided so that the moving path of the entire moving body is more preferred. be able to.

In the first embodiment, the case where the multi-layer network is a two-layer network has been described as an example, but the present invention is not limited to this, and a network having three or more layers may be used. In particular, the update unit 155 increases the number of layers of the multi-layer network to avoid interference when the movement path of one of the moving bodies cannot be updated so as to avoid interference on the multi-layer network. The movement route of the moving body may be updated.

When multiple robots are locally concentrated at the same time, the frequency of interference between robots increases, but under such circumstances, interference cannot be avoided by detouring or waiting for one step, that is, the movement path. May not be generated (updated). Therefore, when the movement route cannot be generated (cannot be updated), the update unit 155 increases the number of layers by 1 (makes it possible to wait for one step extra) until the movement route can be generated, and performs the movement route generation process. You may do it. By doing so, since the movement route can be generated eventually, it is possible to avoid the occurrence of the situation where the movement route cannot be generated.

Further, in the first embodiment, an example of a rule that it is possible to move from the First layer network to the Second layer network in the two-layer network, but it is not possible to move from the Second layer network to the First layer network. As explained above, it may be possible to move from the Second layer network to the First layer network. In this way, the reciprocating movement between layers becomes possible, so that it is possible to represent a standby of two steps or more without increasing the number of layers.

(Second Embodiment)
In the first embodiment, an example of determining interference in units of moving objects has been described, but in the second embodiment, an example of determining interference in units of steps will be described. In the following, the differences from the first embodiment will be mainly described, and the components having the same functions as those of the first embodiment will be given the same names and codes as those of the first embodiment and will be described. Is omitted.

FIG. 13 is a block diagram showing an example of the functional configuration of the information processing apparatus 1010 of the second embodiment. As shown in FIG. 13, in the information processing apparatus 1010 of the second embodiment, the determination unit 1153 and the update unit 1155 are different from those of the first embodiment.

The determination unit 1153 determines whether or not interference occurs between at least two or more moving bodies among the plurality of moving bodies for each unit movement amount of the plurality of moving paths. In the second embodiment, the determination unit 1153 determines whether or not interference occurs between at least two or more robots among the plurality of robots for each movement step of the movement path of each robot.

When the determination unit 1153 determines that interference occurs, the update unit 1155 temporarily causes one of the two or more moving bodies to stand by on the moving path to avoid the interference. To update. Further, when the interference cannot be avoided due to the standby, the updating unit 1155 updates the moving route so as to avoid the interference by bypassing one of the two or more moving bodies. In the second embodiment, when the determination unit 1153 determines that interference occurs, the update unit 1155 causes one of the two or more robots to temporarily stand by on the movement path to avoid the interference. If the movement route cannot be avoided due to standby, the movement route is updated so that the interference can be avoided by bypassing one of the robots.

For example, consider the case shown in FIG. In the example shown in FIG. 14, the robot A collects the product α and returns to the original position, the robot B collects the product β and returns to the original position, and the robot C collects the product γ and returns to the original position. It shall return to the position of. The circles indicate nodes and the lines indicate arcs. In this case, the movement path that does not consider the interference of each robot is as shown in FIG. 15, and the determination unit 1153 determines the interference for each step. In the second embodiment, the determination unit 1153 sets the priority order in ascending order of the number of steps of the moving route (in ascending order of moving time and moving distance). In the second embodiment, the higher the numerical value, the higher the priority.

Then, the determination unit 1153 determines (determines) the movement path of each robot in the corresponding step if interference does not occur, and when interference occurs, the update unit 1155 has a priority among the robots in which interference occurs. The movement path of the lower robot is updated, and the determination unit 1153 redoes the interference determination.

In the example shown in FIG. 15, since the interference (simultaneous approach) between the robot A and the robot B occurs at the node 19, the determination unit 1153 determines the interference between the robot A and the robot B at the node 19 in the second step. Judge that interference will occur.

Further, the example shown in FIG. 16 is an example of another movement path that does not consider the interference of each robot, but the arc connecting the node 19 and the node 20 causes interference (passing) between the robot B and the robot D. In the second step of interference determination, it is determined that the arc connecting the node 19 and the node 20 causes interference between the robot B and the robot D.

Hereinafter, a method for updating the movement route for avoiding interference will be described.

In the second embodiment, when interference occurs, the update unit 1155 updates the movement route so as to avoid the interference without increasing the number of steps, updates the movement route so as to avoid the interference by waiting, and interferes by detouring. Avoid interference by using one of the methods of updating the movement route to avoid.

For example, in the case of the examples shown in FIGS. 14 and 15, as described above, interference (simultaneous approach) between the robot A and the robot B occurs at the node 19. Here, for the robot A having a high priority, interference cannot be avoided without increasing the number of steps. On the other hand, for robot B, which has a low priority, it is currently "17⇒18⇒19⇒20⇒21⇒14⇒21⇒20⇒19⇒18⇒17", but "17⇒10⇒11⇒12⇒13". If the movement route is "⇒ 14 ⇒ 13 ⇒ 12 ⇒ 11 ⇒ 10 ⇒ 17", interference can be avoided without increasing the number of steps.

Therefore, as shown in FIG. 17, the update unit 1155 updates the movement path of the robot B to "17⇒10⇒11⇒12⇒13⇒14⇒13⇒12⇒11⇒10⇒17" and determines. The 1153 is an updated movement path for the movement path of the robot B, and makes an interference determination for each step.

Further, for example, consider the case shown in FIG. In the example shown in FIG. 18, the robot A moves from A to α, and the robot B moves from B to β. The circles indicate nodes and the lines indicate arcs. In this case, as shown in FIG. 19, the movement paths that do not consider the interference of each robot are 6⇒7⇒8⇒9⇒4⇒5 for robot A and 2⇒3⇒4⇒9⇒14 for robot B. Become. In this case, the interference (simultaneous approach) between the robot A and the robot B occurs at the node 9.

Here, neither the robot B having a high priority nor the robot A having a low priority can avoid interference without increasing the number of steps. Therefore, it is determined whether the robot B having a high priority can move in the order of standby, left / right, and rearward with respect to the traveling direction, and the movement route is updated. In this example, since it is possible to update to a movement path that can avoid interference by waiting, the update unit 1155 uses, for example, the Dyxtler method, the A * star method, or the like, as shown in FIG. 20, the movement path of the robot B. Is updated to "2⇒3⇒3⇒8⇒9⇒14", and the determination unit 1153 determines the movement path of the robot B in the updated movement path for each step.

Further, for example, consider the case shown in FIG. In the example shown in FIG. 21, the robot A moves from A to α, and the robot B moves from B to β. The circles indicate nodes and the lines indicate arcs. In this case, as shown in FIG. 22, the movement path that does not consider the interference of each robot is 1⇒2⇒3⇒4⇒ for robot A and 3⇒2 for robot B. In this case, the interference (simultaneous approach) between the robot A and the robot B occurs at the node 2.

Here, neither the robot B having a high priority nor the robot A having a low priority can avoid interference without increasing the number of steps. Therefore, it is determined whether the robot B having a high priority can move in the order of standby, left / right, and rearward with respect to the traveling direction, and the movement route is updated. In this example, interference cannot be avoided by standby, but interference can be updated to a movement path that can be avoided by moving to the left with respect to the traveling direction. As shown in FIG. 23, the movement path of the robot B is updated to "3⇒8⇒7⇒2", and the determination unit 1153 uses the updated movement path for each step. Interference judgment is made.

FIG. 24 is a flowchart showing an example of the movement route determination process performed by the information processing apparatus 1010 of the second embodiment.

First, the generation unit 151 generates a movement path of each robot (however, the occurrence of interference between robots is not considered) for patrolling and collecting a plurality of products existing on the movement path by a plurality of robots. (Step S1010).

Subsequently, the determination unit 1153 sets the priority order for each movement route generated by the generation unit 151 (step S1020).

Subsequently, if the interference determination is not completed in all the movement steps (No in step S1030), the determination unit 1153 updates the movement step of the interference determination target (step S1040). Note that this update is performed by incrementing the movement step.

Subsequently, the determination unit 1153 determines whether or not interference occurs between the robots in the movement step of the determination target (step S1050). If interference does not occur between the robots in the movement step to be determined (No in step S1050), the process returns to step S1030.

On the other hand, when interference occurs between the robots in the movement step to be determined (Yes in step S1050), the determination unit 1153 does not increase the number of steps in descending order of priority among the robots in which the interference occurs. It is determined whether or not the movement route can be updated so as to avoid interference (step S1060).

If the movement route can be updated so as to avoid interference without increasing the number of steps (Yes in step S1060), the update unit 1155 updates the movement route in that way (step S1070), and returns to step S1020. When returning to step S1020, the determination unit 1153 adopts the updated movement route, resets the priority order, and restarts the interference determination for each step from the beginning.

On the other hand, when the movement path cannot be updated so as to avoid the interference without increasing the number of steps (No in step S1060), the update unit 1155 waits for the robot having the higher priority among the robots in which the interference occurs. The node to move next is determined in the order of left, right, rearward with respect to the traveling direction (step S1080), and the movement route to the destination is re-searched (step S1090). Then, when the movement route to the destination can be re-searched, that is, generated (Yes in step S1100), the movement route is updated to the movement route and the process returns to step S1020. When returning to step S1020, the determination unit 1153 adopts the updated movement route, resets the priority order, and restarts the interference determination for each step from the beginning.

That is, in step S1080, if the node to move to the next is first determined by waiting and the movement route to the destination cannot be generated (No in step S1100), then the node moves to the left and right with respect to the traveling direction. If the node cannot be determined and the movement route to the destination cannot be generated, the node to move next is finally determined behind the traveling direction and the movement route to the destination is generated.

As described above, also in the second embodiment, in order to avoid the interference point not only by detouring but also by waiting, interference between the moving bodies is avoided so that the moving path of the entire moving body is more preferred. Can be done.

(Modification example)
In the above embodiment, a case where goods are (picked) collected by using a cart in a warehouse and goods are stored by using a cart has been described as an example.

However, the present invention is not limited to this, and can be applied to human transportation by community bus. In this case, the moving body becomes a community bus, and the plurality of points existing on the moving path become places where humans are or send humans, and the moving path becomes a road.

It can also be applied to disaster response plans such as relief and transportation of supplies. In this case, the moving body becomes a car, the plurality of points existing on the moving path become places where the victims, supplies, hospitals, and shelters are located, and the moving path becomes a road.

It can also be applied to home delivery such as collection and delivery. In this case, the moving body becomes a truck, the plurality of points existing on the moving path become a place or a place where the delivery is located, and the moving path becomes a road.

It can also be applied to patrols of sales staff. In this case, the moving body becomes an automobile, the plurality of points existing on the moving path become places where sales staff are present, places to visit, etc., and the moving path becomes a road.

Further, when the moving body is an automobile, the output device 30 may be a car navigation system or a projector. When the output device 30 is a projector, an embodiment such as projecting a moving path onto the windshield of an automobile can be considered.

(program)
The program executed by the information processing apparatus 10 of the above embodiment and each modification is a file in an installable format or an executable format, and is a CD-ROM, a CD-R, a memory card, a DVD (Digital Versatile Disk), or a flexible file. It is stored and provided in a computer-readable storage medium such as a disk (FD).

Further, the program executed by the information processing apparatus 10 of the above-described embodiment and each modification may be provided by storing it on a computer connected to a network such as the Internet and downloading it via the network. Further, the program executed by the information processing apparatus 10 of each of the above-described embodiments and modifications may be provided or distributed via a network such as the Internet. Further, the program executed by the information processing apparatus 10 of each of the above-described embodiments and modifications may be provided by incorporating it into a ROM or the like in advance.

The program executed by the information processing apparatus 10 of the above-described embodiment and each modification has a modular configuration for realizing each of the above-described parts on a computer. As actual hardware, for example, the CPU reads a program from the ROM onto the RAM and executes the program, so that each of the above functional units is realized on the computer.

The above-described embodiment and each modification are presented as examples, and are not intended to limit the scope of the invention. The new embodiment can be implemented in various other forms, and various omissions, replacements, and changes can be made without departing from the gist of the invention. These embodiments are included in the scope and gist of the invention, and are also included in the scope of the invention described in the claims and the equivalent scope thereof.

1 Information processing system 2 Network 10,1010 Information processing device 20 Terminal device 30-1 to 30-n (30) Output device 151 Generation unit 153, 1153 Judgment unit 155, 1155 Update unit 157 Transmission unit

Japanese Patent No. 4138541

Claims (8)

A generator that generates a movement path for each of multiple moving objects,
A determination unit for determining whether or not interference occurs between at least two or more moving bodies among the plurality of moving bodies as a result of the movement of the plurality of moving paths by the plurality of moving bodies.
When the interference occurs, an update unit that updates the movement path so as to avoid the interference by temporarily making one of the two or more moving bodies wait on the movement path.
Equipped with a,
The generation unit generates the plurality of movement paths on a one-layer network composed of a plurality of nodes and an arc connecting the nodes.
The update unit is a multi-layered network of the one-layer network, and one of the above-mentioned ones so as to avoid the interference on the multi-layered network in which the entry to the node and the arc where the interference occurs is prohibited. Update the movement path of the moving body of
The standby is an information processing device represented by movement between layers in the multi-layer network. The information processing device according to claim 1 , wherein the multi-layer network is a two-layer network. When the moving path of one of the moving bodies cannot be updated so that the interference can be avoided on the multi-layered network, the updating unit increases the number of layers of the multi-layered network to avoid the interference. The information processing device according to claim 1, wherein the movement path of one of the moving bodies is updated. The determination unit determines whether or not interference occurs between at least two or more moving bodies among the plurality of moving bodies for each unit movement amount of the plurality of moving paths.
When the interference occurs, the updating unit updates the moving path so as to avoid the interference by temporarily making one of the two or more moving bodies wait on the moving path. Item 1. The information processing apparatus according to item 1. The fourth aspect of claim 4 in which the updating unit updates the moving route so as to avoid the interference by bypassing one of the two or more moving bodies when the interference cannot be avoided due to the standby. Information processing equipment. An information processing system including an information processing device and a plurality of output devices.
The information processing device
A generator that generates a movement path for each of multiple moving objects,
A determination unit for determining whether or not interference occurs between at least two or more moving bodies among the plurality of moving bodies as a result of the movement of the plurality of moving paths by the plurality of moving bodies.
When the interference occurs, an update unit that updates the movement path so as to avoid the interference by temporarily making one of the two or more moving bodies wait on the movement path.
Each of the plurality of output devices is provided with a transmission unit that transmits movement route information indicating the movement route of the moving body associated with the output device.
Each of the plurality of output devices outputs the movement route indicated by the movement route information transmitted from the information processing device .
The generation unit generates the plurality of movement paths on a one-layer network composed of a plurality of nodes and an arc connecting the nodes.
The update unit is a multi-layered network of the one-layer network, and one of the above-mentioned ones so as to avoid the interference on the multi-layered network in which the entry to the node and the arc where the interference occurs is prohibited. Update the movement path of the moving body of
The standby is an information processing system represented by movement between layers in the multi-layer network. A generation step that generates a movement path for each of multiple moving objects,
A determination step for determining whether or not interference occurs between at least two or more moving bodies among the plurality of moving bodies as a result of the movement of the plurality of moving paths by the plurality of moving bodies.
When the interference occurs, an update step of updating the movement path so as to avoid the interference by temporarily making one of the two or more moving bodies wait on the movement path, and an update step.
Only including,
In the generation step, the plurality of movement paths are generated on a one-layer network composed of a plurality of nodes and arcs connecting the nodes.
In the update step, one of the above so as to avoid the interference on the multi-layered network in which the one-layer network is multi-layered and the entry to the node and the arc where the interference occurs is prohibited. Update the movement path of the moving body of
The standby is a movement route determination method represented by movement between layers in the multi-layer network. A generation step that generates a movement path for each of multiple moving objects,
A determination step for determining whether or not interference occurs between at least two or more moving bodies among the plurality of moving bodies as a result of the movement of the plurality of moving paths by the plurality of moving bodies.
When the interference occurs, an update step of updating the movement path so as to avoid the interference by temporarily making one of the two or more moving bodies wait on the movement path, and an update step.
Let the computer run
In the generation step, the plurality of movement paths are generated on a one-layer network composed of a plurality of nodes and arcs connecting the nodes.
In the update step, one of the above so as to avoid the interference on the multi-layered network in which the one-layer network is multi-layered and the entry to the node and the arc where the interference occurs is prohibited. Update the movement path of the moving body of
The standby is a program for being represented by the movement between layers in the multi-layer network.

Images