TECHNICAL FIELD

The invention concerns in general the technical field of autonomous vehicles. Especially the invention concerns route generation in an autonomous vehicle environment.

BACKGROUND

Some prior art describes an automated guided vehicle (AGV) that is a computer-controlled vehicle which travels around the facility. AGV systems typically comprise multiple AGVs which are controlled by a control unit. Typical application areas of the AGV systems are for example industrial applications where the loads are moved around the warehouses, manufacturing facilities, or marine container terminals. The use of the AGVs increases the efficiency of the system and reduces costs. The control unit manages the transport orders involving order queueing, assignment of each order to a suitable AGV, monitoring of order progress, and maintain constantly updated order status, for example. Several transport orders can be given simultaneously to the control unit and are placed in the work queue. The work queue is emptied primarily in first-in, first-out (FIFO) order. However, different priority can be given to orders, depending on, for instance, the load station or the production situation.

Further, the control unit manages AGV traffic including route planning, prevention of collisions by using static rules for route determination, and resolution of deadlocks. The routes of multiple AGVs shall be planned so that the route plans made of the other AGVs are not invalidated, and the planned routes are not in conflict with each other. The routing is typically based on time intervals, where certain route positions are reserved for a certain AGV at a certain time intervals. The reserved route position cannot be used by any other AGVs at that same time interval without causing a conflict, or collision. The other AGVs have to wait and use the reserved route position at a later time interval.

Figure 1 describes an example of the route planning for two AGVs based on the prior art. The area 1 10 in which two AGVs are operating is divided to sub- areas P1 -P25 called as positions in the following. To keep the example simple it is assumed that both AGVs operate with the same speed, it takes one time interval to travel through one position and to perform a predetermined task by the AGVs, the AGV may travel either horizontally, vertically or on the slant (i.e. any position around the position in which the AGV is locating are possible for the AGV to move), and the mutual timing of the AGVs is such that the first AGV is configured to initiate the travel in a beginning of a time interval TO and the other AGV in a beginning of a time interval T3.

In Figure 1 on the up-most area 1 10 layout on the left depicts that a first AGV locates in position P6 and area layout on the right depicts that a second AGV locates in position P1 1 . A control unit determines a first task for the first AGV in a position P10 and a second task in a position P21 . It determines a route through the following positions: P6, P7, P8, and P9 to the first destination D1 in position P10 and the second route through the following positions: P14, P18, and P17 to the second destination D2 in a position P21 . Similarly, the control unit determines a first task the second AGV in a position P20 and a second task in a position P17. It determines a route for the second AGV through the following positions: P1 1 , P12, P13, and P14 to the first destination D3 in position P20 and the second route through the following positions: P19 and P18 to the second destination D4 in a position P17. The mentioned routes are marked on the area layouts with arrows.

Next, the routes are taken to a time axis. The time axis refers here to data structure 120 by means of which it is possible to express time based positions of the AGVs in a same time space. The time axis is divided to time intervals T0-T12. The routes, i.e. time based positions, are put to the corresponding time intervals. By comparing the time based positions of the different AGVs in the data structure 120 it is detected that there would be a conflict in the position P14 at time interval T6. In the prior art solution in response to the detection of the conflict the second AGV has to wait and use the position P14 at a later time. In the other words the second AGV waits in the position P13 during time interval T6 so that the position P14 is free and the second AGV can continue its travelling to the position P14 at time interval T7.

Publications of Bennewitz, M. et al. : "Finding and optimizing solvable priority schemes for decoupled path planning techniques for teams of mobile robots", Liu, F. et al. : "Real time replanning based on A ^* for collision avoidance in multi- robot systems", and van den Berg, J. P. et al. : "Prioritized motion planning for multiple robots" disclose solutions for planning routes of multiple robots based on assigning priorities to the robots.

In the prior route planning solutions the planned routes are locked when they are sent to the AGVs either in blocks or as a whole and as a result one or more AGVs need to stop in the conflict situations. This is very inefficient and it takes more time to perform the determined tasks of the AGVs. Thus, there is a need to develop further solutions for providing more sophisticated route generation in the area of AGV systems. SUMMARY

An objective of the invention is to present a method, a control unit and a system for solving a conflict situation in route generation. Another objective of the invention is that the method, the control unit and the system for solving the conflict situation improve an overall performance of an AGV solution. The objectives of the invention are reached by a method, a control unit and a system as defined by the respective independent claims.

According to a first aspect, a method for solving a conflict situation between route elements in an environment comprising a plurality of AGVs to whom one or more route elements are consecutively generated is provided, wherein the method comprising: generating a route element with priority for an AGV; determining if the generated route element conflicts with at least one existing route element; and in response to a determination of the conflict re-generating the at least one route element being involved in the conflict which is provided with a lower priority. The determination of the conflict may be performed by comparing at least position information of the generated route to position information of the at least one existing route element.

Alternatively or in addition, the determination of the conflict may be performed by comparing a time based position of the AGV on the generated route element to a time based position of at least one other AGV on a route element generated for the at least one other AGV. The route element which is provided with a lower priority may be found by comparing the predetermined priorities of the route elements being involved in the conflict.

The method may further comprise: in response to a detection that the route elements being involved in the conflict comprises a priority with the same value determining the route element which is generated later; and re-generating the route element which is generated later.

The route element may be generated so that the generated route element is allowed to conflict with one or more existing route element having a lower priority than the priority of the route element being generated.

The priority of a route element leading to an idle location may be set lower than the priority of a route element leading to task execution position.

The priority of a first route element in a route generated for the AGV may be set higher than the priority of a later route element generated for the same AGV.

The priority of the route element under execution by an AGV may be set equal to or higher than the priority of any other existing route element.

According to a second aspect, a control unit for solving a conflict situation between route elements in an environment comprising a plurality of AGVs to whom one or more route elements are consecutively generated is provided, wherein the control unit comprising: at least one processor, and at least one memory storing at least one portion of computer program code, wherein the processor being configured to cause the control unit at least to perform: generate a route element with priority for an AGV; determine if the generated route element conflicts with at least one existing route element; and in response to a determination of the conflict re-generate the at least one route element being involved in the conflict which is provided with a lower priority.

The control unit may be configured to determine the conflict by comparing at least position information of the generated route to position information of the at least one existing route element.

Alternatively or in addition, the control unit may be configured to determine the conflict by comparing a time based position of the AGV on the generated route element to a time based position of at least one other AGV on a route element generated for the at least one other AGV.

The control unit may be configured to find the route element which is provided with a lower priority by comparing the predetermined priorities of the route elements being involved in the conflict.

The control unit may further be configured to: determine the route element which is generated later in response to detection that the route elements being involved in the conflict comprises a priority with the same value; and regenerate the route element which is generated later. The control unit may further be configured to generate the route element so that the generated route element is allowed to conflict with one or more existing route element having a lower priority than the priority of the route element being generated.

The control unit may also be configured to set the priority of a route element leading to an idle location lower than the priority of a route element leading to task execution position.

The control unit may also be configured to set the priority of a first route element in a route generated for the AGV higher than the priority of a later route element generated for the same AGV. Moreover, the control unit may be configured to set the priority of the route element under execution by an AGV equal to or higher than the priority of any other existing route element.

According to a third aspect, a system for solving a conflict situation between route elements is provided, wherein the system comprising: a plurality of AGVs to whom one or more route elements are consecutively generated and a control unit, which is configured to: generate a route element with priority for an AGV; determine if the generated route element conflicts with at least one existing route element; and in response to a determination of the conflict regenerate the route element being involved in the conflict, which is provided with a lower priority. In the system the control unit and the AGVs are communicatively coupled to each other and the control unit is configured to deliver the generated route elements to the AGVs. The exemplary embodiments of the invention presented in this patent application are not to be interpreted to pose limitations to the applicability of the appended claims. The verb "to comprise" is used in this patent application as an open limitation that does not exclude the existence of also un-recited features. The features recited in depending claims are mutually freely combinable unless otherwise explicitly stated.

The novel features which are considered as characteristic of the invention are set forth in particular in the appended claims. The invention itself, however, both as to its construction and its method of operation, together with additional objectives and advantages thereof, will be best understood from the following description of specific embodiments when read in connection with the accompanying drawings.

BRIEF DESCRIPTION OF FIGURES

The embodiments of the invention are illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings.

Figure 1 illustrates a route planning solution according to a prior art.

Figure 2 illustrates schematically an environment wherein the embodiments of the invention may be implemented.

Figure 3 illustrates schematically an example of the method according to the invention.

Figure 4 illustrates schematically a more detailed example of the method according to the invention.

Figure 5 illustrates schematically an example of the invention when applied in an AGV environment. Figure 6a illustrates schematically an example of a re-generated secondary route element for the first AGV.

Figure 6b illustrates schematically an aspect of advantages of the invention.

Figure 7 illustrates schematically an example of the control unit according to the invention. Figure 8 illustrates schematically an example of an AGV. DESCRIPTION OF SOME EMBODIMENTS

The Figure 2 discloses an environment wherein the embodiments of the invention may be implemented as will be described. The environment comprises at least two automated guided vehicles (AGV) 210, 220 which are at least partly controlled by a control unit 230. The control unit 230 may receive input from one or more external entities, such as from an enterprise resource planning (ERP) system, and in response to the input the control unit may be configured to control and manage the AGVs. Hence, the control unit 230 and each AGV 210, 220 are communicatively coupled to each other in order to deliver information between the entities (communication capability marked with arrows in Figure 2). Moreover, the AGVs may also be communicatively coupled to each other in order to exchange information (not illustrated in Figure 2). Thus, the mentioned entities comprise communication means, such as wired or wireless modems, necessary antennas, and similar known elements for implementing the communication. Furthermore, a navigation system is used in the environment by means of which at least the positions of the AGVs within an area may be determined. The navigation system shall be understood in a broad way covering any technical solutions by means of which at least the positions of AGVs may be determined and the AGVs 210, 220 may be guided in order to travel within the area. The AGVs 210, 220 may be similar to each other or they may differ from each other either physically or operatively or both.

As Figure 2 depicts the control unit may be configured to generate consecutively a route for one or more AGVs in the environment. The first AGV 210 may e.g. be instructed to perform a certain task in a destination D1 , such as to pick up some items from the destination D1 , and to continue to some other destination D2 e.g. in order to perform a next task, and so on. Similarly, the control unit 230 may be configured to generate a route for the second AGV 220. The total route of each AGV may comprise of one or more route elements. In this example it means that for the first AGV 210 it is assigned a route comprising route elements RE1 1 and RE12. Correspondingly, for the second AGV 220 the route comprise only one route element RE21 . Naturally, the number of route elements generated for the routes of each AGV is not limited anyhow and they are dependent on time in a sense that at every time instant the existing number of route elements may be zero or more when the system is operating. Further, the route elements are defined between two points, i.e. positions, and at least one end point of a route element may or may not be a destination wherein the AGV in question may be instructed to perform a predetermined task.

As may be seen from Figure 2 the route elements, and thus the routes, defined for the AGVs may be in conflict. The conflict refers to a situation wherein at least two route elements generated for different AGVs disturb each other in some predetermined manner. Especially, the conflict refers to a situation wherein at least two AGVs end up to the same position in the area they are operating at the same time. In other words, the time based positions of the AGVs are the same. The term position shall be understood broadly and it covers any such positions, wherein an AGV is disturbed to travel in its route due to a position of at least one other AGV. In order to solve the conflict situation at least some route elements are provided with a priority. The priority, or priority information, is assigned to at least some, preferably all, route elements and by comparing the priorities one may conclude the mutual order of the route elements. The mutual order may indicate at least the mutual importance of the route elements to be used for the purposes of the present invention. The priority may be defined for a route element on a basis of a predetermined criterion or predetermined criteria. Advantageously, the priorities are defined for route elements in view of a performance of overall system. This may e.g. refer to such a performance that completion of tasks is optimized or to such a performance that AGVs operate in a desired manner. Alternatively or in addition, the predetermined criteria, or at least some criterion, may originate from a view of individual route. In such a case the priority may be based on e.g. required time needed to travel the route element, or the total route, in question, a consumption of energy by an AGV when traveling the route, predetermined importance of a certain AGV or task, or anything similar. The priority information may be included as a parameter in the same data structure that defines the route element itself, i.e. the positions, or it may be separate and be fetched when necessary e.g. by means of some identifier which identifier is linked some known manner with a generated route element. Next an example of the method according to the invention is described by referring to Figure 3. Figure 3 schematically illustrates the invention as a flow chart. As already discussed the system according to the invention generates and maintains route information of AGVs in the system. At a certain instant of time the system may comprise zero or more route elements in the system. Now, the control unit of the system generates 310 a route of one or more route elements with priorities corresponding to the route element to be generated for an AGV. In other words according to an example of the invention the priorities are predetermined for route elements according to predetermined rules set for priority setting. Next, the one or more generated route elements are compared to existing routes consisting of one or more route elements in order to find conflicts 320 between the route elements. The comparison between the route elements is made at least on the basis of positions defining the route. The positions may be expressed with any known manner, such as a set of coordinates in a coordinate system defined in the environment the invention is applied to. In case one or more conflicts are found the control unit is configured to re-generate 330 the route element which is involved in the conflict and has a priority that fulfills a predetermined criterion set in the system. The predetermined criterion may e.g. be set so that the route being involved in the conflict and having a lower priority than the at least one other route element being involved in the conflict is re-generated 330.

Figure 4 schematically discloses the flow chart of Figure 3 in more detailed manner. Especially the step 320 becomes clear from Figure 4. As said the control unit generates 310 a route for an AGV, which route comprises one or more route elements. The analysis of conflicts 320 comprises a comparison 410 of each of the generated route elements to existing route elements generated for other AGVs and maintained in the system. According to an embodiment of the invention the comparison may be based on positions, such as coordinates or set of coordinates, defining belonging to the route elements. According to another embodiment of the invention the comparison is arranged to take into account the real position of an AGV in view of time, when the AGV in question is arranged to travel the corresponding route element. Advantageously, the time based positions of the AGVs are defined in the same time space for the comparison purposes, among others. If the comparison 410 indicates that no conflicts is found the method may be stopped. But if at least one conflict is found, the control unit is configured to compare priorities 420 defined for the conflicting route elements. Moreover, the control unit is configured to select 430 the route element to which a lower priority is defined. Finally, the route element with a lower priority is re-generated 330.

The invention is now described by applying the inventive idea to the situation as already discussed in the background part by referring to the Figure 1 . This is illustrated in the Figure 5. For the purpose of simplicity the following assumptions are made (the same as in the context of the Figure 1 ):

• both AGVs operate with the same speed,

• the AGVs may travel either horizontally, vertically or on the slant (i.e. any position around the position in which the AGV is locating are possible for the AGV to move),

• it takes one time interval to travel through one position by the AGVs,

• it takes one time interval to perform a predetermined task in a corresponding destination, D1 , D2 by the AGVs,

· the mutual timing of the AGVs is such that the first AGV is configured to initiate the travel in a beginning of a time interval TO and the other AGV in a beginning of a time interval T3.

It is clear from the context that the above described assumptions are only made for maintaining the simplicity in describing the invention. The assumptions made do not limit the invention anyhow and the inventive idea is directly applicable in any other setup in the AGV environment.

The AGVs are operating in the area 1 10 and for a first AGV a route is generated. The route starts from position P5 and the destination D1 is in a position P10. Further, the second route element for the first AGV is from the position P10 to the position P21 , referred also D2. Correspondingly, a starting position of the second AGV is P1 1 and a first route element is generated from the position P1 1 to a position P20 (referred with D3) and the second route element is from the position P20 to a position P17 (referred also D4). Priorities are also defined for the route elements. According to the invention the generated routes with the priority information may be implemented in a data structure 510, as depicted in the Figure 5. One may notice that there exists a conflict at a time interval T6. At the time interval T6 the first AGV (AGV1 ) is planned to be on the second route element, which is assigned with a priority 2. The second AGV (AGV2) is at the same time interval T6 on the first route element which is, in this example, assigned with a priority 1 . The control unit is configured to compare the priorities in response to the detection of the time based conflict of the AGVs. As the priority of the first route element of the second AGV is higher than the priority of the conflicting route element, i.e. the second route element, of the first AGV, the control unit is configured to regenerate the second route element of the first AGV.

Figure 6a illustrates as an example a re-generated secondary route element for the first AGV. The re-generated route element goes along the following positions P10-P15-P19-P18-P17-P21 . By taking the re-generated route element to the data structure, as depicted in Figure 6b, one may notice that there exist no conflicts. Moreover, the second AGV (AGV2) now reaches the position P20 sooner than according to prior art solutions, i.e. at the time interval T7. The advantages of the present invention are thus straightforward.

The implementation of the method as described may be based on utilization of time intervals in the route generation, as described in the previous examples. Time intervals may be defined individually for each AGV. The time interval expresses the time the AGV in question uses to travel a certain distance when the AGV is provided with operational parameters to perform the travel or a task in the operational environment. Hence, this takes into account at least some characteristics of AGVs, such as speed. Now, when one or more route elements of a route are generated for an AGV, the travel of the route may be expressed by means of one or more time intervals. In order to take the environment in which the AGVs are traveling into account the time intervals of the AGV may be positioned in a 2D or 3D matrix. The 2D matrix is used in case the motion is to be expressed in 2D area and 3D matrix is used if the motion of the AGVs is to be expressed in three-dimensional space. The matrix represents the environment in which the AGVs reserve time intervals, or slots, when traveling the generated route elements therein. Now, when the routes, or route elements, of the at least two AGVs are positioned in the matrix, or space, it is possible to detect, by e.g. comparing, if both AGVs end to the same position at a same time interval. If this is the case that the time based positions of the AGVs match at least the route element provided with a lower priority is to be re-generated according to the method of the invention. The matrices are only one way to express the travel of AGV in an environment, but the invention is not limited to matrices only. For example, any other way, such as a graph, of expressing the same may be used. Worth mentioning is that it may happen that the generated route element may be assigned with the same priority as the at least one other route element with whom the generated route element is in conflict. In such a case the conflict may be resolved by providing for each generated route element a time stamp, which indicates the instant of time when the route element in question is generated, or re-generated. As the existing route elements are not in conflict it is advantageous to re-generate the new route element which caused the conflict. The route element to be re-generated may thus be selected on the basis of the provided time stamps so that the latest route element being a party of the conflict is re-generated. The time stamp may be included in the data structure 510 of Figure 5 by adding a field for time stamp.

Next it is discussed how the route element is re-generated in case of a conflict is detected. According to an example of the invention the control unit 230 may be configured to generate new route elements so that if one or more conflicts exist, they exist only with route elements that have a lower priority than the route element being generated. This may be achieved by requiring route generation to return only feasible - meaning conflict free - routes with regard to supplied set of existing route elements. Effect of conflicting with only lower priority routes may e.g. be achieved by depriving routing process of information about existence of these lower priority route elements. Moreover, search for feasible route element may be set to simultaneously optimize a selected criterion.

Clearly, by decreasing the amount of existing lower priority route elements to consider, control unit 230 is able to find better solutions with less computation resources needed. If selection of priority is based on significance of a route element to performance of overall system, the method according to an example of the invention yields significant performance improvements when applied.

Criteria for setting priority for route element may comprise, but are not limited to:

• setting high priority for route elements leading to positions where tasks are performed,

• setting low priority for route elements leading to positions where AGVs wait idle, • setting priority based on route elements planned position in AGVs execution queue,

• setting low priority for route elements that are subject to change in the future. An example of such route element would be element that would be replaced if new tasks were given to system before end of current planning horizon, and/or

• setting the priority of the route element under execution by an AGV equal to or higher than the priority of any other existing route element.

As discussed above the control unit 230 is the entity which determines the routes and controls the operation of the AGVs through interaction. According to an example of the invention the control unit 230 may be configured to maintain information on active routes in a memory or a database. The memory or the database may be either internal or external to the control unit 230, but in all cases accessible by the control unit 230. It may be arranged so that the route, or any part of the route, such as route element, may be removed from the memory or database when a corresponding AGV has traveled the route, or the part of the route. This improves the efficiency of the system and the determination of conflicting routes according to the invention. Alternatively or in addition, the control unit may be configured to maintain information on characteristics of one or more AGVs operating in the environment in which the present invention is applied to. The characteristics may comprise, but are not limited to, operational details, such as speed, of each AGV, parameters of AGVs relating to a capability of performing one or more tasks and so on. The characteristics may be taken into account in route generation and in optimization of the performance of the overall system, as discussed.

Figure 7 discloses a schematic example of a control unit 230 according to the invention. The control unit 230 may comprise one or more processors 710, one or more memories 720 being volatile or non-volatile for storing portions of computer program code 721 a-721 n and any data values, a communication interface 730 and possibly one or more user interface units 740. The mentioned elements may be communicatively coupled to each other with e.g. an internal bus. The communication interface provides interface for communication with any external unit, such as AGVs, database and/or external systems, such as ERP. The communication interface may be based on one or more known communication technologies, either wired or wireless, in order to exchange pieces of information as described earlier. Additionally, the control unit may be arranged to maintain and/or control a navigational system applied in the environment by means of which the AGVs may operate within the environment.

The processor 710 of the control unit is at least configured to implement at least some method steps as described. The implementation of the method may be achieved by arranging the processor 710 to execute at least some portion of computer program code 721 a-721 n stored in the memory 720 causing the processor 710, and thus the control unit 230, to implement one or more method steps as described. The processor 710 is thus arranged to access the memory 720 and retrieve and store any information therefrom and thereto. Moreover, the processor 710 is configured to control the communication through the communication interface 730 with any external unit, such as with AGVs. The processor 710 may also be configured to control storing of received and delivered information. For sake of clarity, the processor herein refers to any unit suitable for processing information and control the operation of the control unit, among other tasks. The operations may also be implemented with a microcontroller solution with embedded software. Similarly, the memory 720 is not limited to a certain type of memory only, but any memory type suitable for storing the described pieces of information may be applied in the context of the present invention.

Some non-limiting examples of the control unit may e.g. be a server, personal computer, laptop computer, computing circuit, a network of computing devices.

Figure 8 discloses a schematic example of an AGV 210, 220 operating in the environment. The AGV 210, 220 may comprise one or more processors 810, one or more memories 820 being volatile or non-volatile for storing portions of computer program code 821 a-821 n and any data values or parameters, a communication interface 830, one or more user interface units 840 and vehicle related devices 850. The vehicle related devices may comprise, but are not limited to, one or more power generating entities, such as motor, one or more tools for performing the tasks in the environment, such as a fork with associated apparatuses, and navigation unit, for example. The mentioned elements may be communicatively coupled to each other with e.g. an internal bus. The communication interface provides interface for communication with any external unit, such as with control unit 230 and/or other AGVs. The communication interface may be based on one or more known communication technologies, either wired or wireless, in order to exchange pieces of information as described earlier.

In the description herein it is discussed that the match of time based positions is found by arranging the AGV in question to travel the determined route. This is naturally an operation which is calculated by the control unit prior to signaling the route information to the AGV, or AGVs, in question. Hence, the aim is to avoid a delivery of any such route information to one or more AGVs, which may end up to a conflict.

Even if the present invention is described above in an environment with two AGVs the invention is not limited to this example only, but is applicable in environments comprising more than two AGVs to whom routes may be generated. In such environments the described method is advantageously consecutively applied between route elements of two AGVs so that any possible conflict is found between any AGVs. This naturally applies only to those routes which are active in at least some extent in the control unit, as described.

It is worthwhile to mention here that a route element for any AGV may be generated so that the route continues from a destination to some other destination e.g. in order to perform a chain of tasks in multiple destinations with the AGV in question. Moreover, the control unit may be configured to dynamically generate additional route elements to one or more AGVs. This means that AGVs may receive additional route element during the travel.

The term 'position' shall be understood broadly in this disclosure. The position may e.g. be a single coordinate point in a coordinate system, or a plurality of points within the area. For example, the positions as referred in the context of figures shall be understood as some form of sub-areas of the area in which the AGVs are arranged to operate. The sub-spaces may comprise one or more items defining a position in some accuracy within the area.

Features described in the preceding description may be used in combinations other than the combinations explicitly described. Although functions have been described with reference to certain features, those functions may be performable by other features whether described or not. Although features have been described with reference to certain embodiments, those features may also be present in other embodiments whether described or not.