KR20150137166A - Method for planning path for avoiding collision between multi-mobile robot - Google Patents

Abstract

The present invention relates to a method to plan a path to avoid a collision between a plurality of mobile robots comprising: (a) a step of registering a traveling map wherein the plurality of mobile robots travel; (b) a step of registering an initial priority, an origin, and a destination of each mobile robot; (c) a step of gradually producing a path for each mobile robot from the origin to the destination based on the traveling map on the initial priority to avoid a collision between the mobile robots; (d) a step of traveling each mobile robot along the path produced in the step (c); (e) a step of predicting a collision between the mobile robots during traveling of the mobile robots; and (f) a step of reproducing a path for a mobile robot with low traveling priority, among a pair of mobile robots based on the traveling priority of the pair of mobile robots which are predicted to collide with each other in step (e). As such, the present invention allows the production of a path without overlaps and collisions by applying a decentralized method to the production of the path for the plurality of mobile robots.

Description

TECHNICAL FIELD [0001] The present invention relates to a path generation method for avoiding collision between a plurality of mobile robots,

The present invention relates to a path generation method for collision avoidance between a plurality of mobile robots, and more particularly, to a path generation method for avoiding collision between mobile robots in generating a path of a plurality of mobile robots traveling in the same traveling space, And more particularly, to a path generation method for collision avoidance between a plurality of possible mobile robots.

When a plurality of mobile robots travel in the same traveling space such as a building or an exhibition, when each mobile robot calculates its shortest distance without considering movement of other mobile robots, There is a possibility.

In such a case, if the mobile robot is stopped to avoid collision with other mobile robots while traveling along the calculated path path, the operation efficiency may be lowered, or a plurality of mobile robots may fall into a deadlock state If you can not achieve the goal, it will come up.

In this multi-object robot system, there are two methods for generating paths of individual mobile robots that can avoid collision. The first is the centralized method and the other is the decoupled method.

The centralized method simultaneously generates the paths of all the mobile robots in one cycle. When generating the path of each mobile robot, the path is generated considering the number of all the other mobile robots. However, the centralized method provides an advantage of generating an optimum path, but the computational complexity increases exponentially as the number of mobile robots increases, which is disadvantageous when a large number of mobile robots are applied .

In addition, the centralized method can be applied to all the mobile robots at any time if the route travel time of the mobile robot is different from the anticipation due to the obstacle or the delay of the operation during the actual travel, In this case, the complexity of the calculation mentioned above also occurs during traveling, which causes the performance of the entire system to deteriorate.

On the other hand, the decentralized method is a method for avoiding collision by individually generating paths of respective mobile robots, detecting a situation in which collision occurs between the mobile robots, and then modifying the collision path or controlling the speed. The distributed method has the advantage of low individual computation amount, but it is difficult to guarantee the optimum path.

For example, the technique disclosed in Korean Patent No. 10-0670565 is a decentralized method, in which a region where a collision occurs is calculated and a speed profile is adjusted according to a priority to avoid a collision. However, the method disclosed in the above-mentioned Korean Patents has a possibility that the mobile robots are put into a deadlock state because they only avoid the collision by adjusting the speed of the mobile robot in a fixed path. For example, when two mobile robots face each other and change their positions, the above method does not provide a method of avoiding collision.

SUMMARY OF THE INVENTION Accordingly, the present invention has been made to solve the above-mentioned problems, and it is an object of the present invention to provide a method and apparatus for generating a path of a plurality of mobile robots by applying a decentralized method, And to provide a path generation method for collision avoidance between robots.

In order to cope with the change of the work plan due to the dynamic obstacle encountered by the mobile robot while driving and the extension of the working time, the collision inspection and the path regeneration are performed to maintain the working efficiency even in the change of the traveling environment occurring during traveling, Another object of the present invention is to provide a path generation method for collision avoidance between a plurality of mobile robots capable of preventing a deadlock state.

According to another aspect of the present invention, there is provided a path generation method for avoiding collision between a plurality of mobile robots, the method comprising: (a) registering a running map on which the plurality of mobile robots travel; (b) registering the initial priority, the origin and the destination for each of the mobile robots; (c) generating a route from the origin to the destination of each of the mobile robots based on the travel map, sequentially generated in the order of the initial priorities, avoiding collision between the routes of the mobile robot; (d) each of the mobile robots travels according to a path generated in the step (c); (e) predicting a collision between the mobile robots in a traveling process of the mobile robots; (f) when a collision between the mobile robots is predicted in the step (e), a path of the mobile robot having the low driving priority is regenerated based on the traveling priority between the pair of mobile robots in which the collision is predicted And a path generation method for avoiding collision between a plurality of mobile robots.

In the step (a), the driving map may be composed of a plurality of nodes and edges connecting the nodes.

Also, the path generated in the step (c) is generated based on any one of a Djikstra algorithm, an A * algorithm, and a D * algorithm; The path generated in the step (c) includes information on the occupancy time of the node and the edge on the path; In the step (c), whether or not occupancy of the nodes and edges on the path generated earlier according to the occupancy time is stored according to the initial priority, and the occupied nodes and edges in the subsequent occupancy time are stored in the path generation Can be excluded.

In the step (c), when there is a mobile robot in which there is no path capable of avoiding a collision among the plurality of mobile robots, the mobile robot may be kept in a waiting state.

In the step (e), collision between any one of the plurality of mobile robots and the remaining mobile robots is sequentially predicted. Wherein the step (f) comprises the steps of: (f1) comparing the traveling priorities of the two mobile robots when a collision with any one of the mobile robots is predicted during the execution of the step (f) if the traveling priority of one of the mobile robots is low in the step (f1), the path of any one of the mobile robots is regenerated; The steps (e), (f1), and (f2) may be sequentially performed on all mobile robots.

If the traveling priority of any one of the mobile robots is high in step (f1), the steps (e), (f1) and (f2) have.

The path generated in step (c) and the path regenerated in step (f) are generated based on any one of a Djikstra algorithm, an A * algorithm, and a D * algorithm; The paths generated and regenerated in the step (c) and the step (f) include information on occupancy times of nodes and edges on the path; In the step (f), it is stored whether or not occupancy of nodes and edges on the pre-generated path with respect to the plurality of mobile robots according to the occupation time is stored, and nodes and edges occupied in the occupation time at the time of path re- .

If the path regenerated in step (f) satisfies the pre-registered waiting condition, the traveling of the mobile robot may be switched to the waiting state.

Here, the initial priority includes an initial priority registered initially for each of the plurality of mobile robots; The traveling priority includes a priority based on the initial priority, a cost based on a route cost from a current location of the mobile robot to a node or an edge where a collision is predicted, and a mission based priority Based on the regeneration route based priority reflecting the path cost of the path to be regenerated excluding the node where the collision is predicted from the position of the mobile robot at present and the regeneration route based priority reflecting the initial priority level, the cost based priority, And a combination priority based on a combination of at least two of the path-based priorities.

According to the present invention, according to the present invention, there is provided a method for generating a path of a plurality of mobile robots by applying a decentralized method, A path generation method is provided.

In order to cope with the change of the work plan due to the dynamic obstacle encountered by the mobile robot while driving and the extension of the working time, the collision inspection and the path regeneration are performed to maintain the working efficiency even in the change of the traveling environment occurring during traveling, There is provided a path generation method for collision avoidance between a plurality of mobile robots capable of preventing a deadlock state.

FIG. 1 is a diagram illustrating a configuration of a path generation system for collision avoidance between a plurality of mobile robots according to the present invention,
FIGS. 2 and 3 are diagrams for explaining a path generation method for collision avoidance between a plurality of mobile robots,
4 is a diagram showing an example in which a collision is predicted or deadlocked between mobile robots,
5 is a diagram for explaining the Djikstra algorithm,
6 to 8 are diagrams for explaining a route creation process according to priority in a route creation method for collision avoidance between a plurality of mobile robots according to the present invention,
9 is a view for explaining an example of a driving priority in a path generation method for collision avoidance between a plurality of mobile robots according to the present invention.

Hereinafter, embodiments according to the present invention will be described in detail with reference to the accompanying drawings.

1 is a diagram illustrating a configuration of a path generation system for collision avoidance between a plurality of mobile robots 200 according to the present invention. As shown in FIG. 1, the path generation system according to the present invention includes a plurality of mobile robots 200 and a control center 100 for controlling a plurality of mobile robots 200.

The plurality of mobile robots 200 run in the same traveling space. In the present invention, it is assumed that the mobile robot 200 is provided in the form of a two-wheeled mobile robot 200. The control center 100 exchanges data with the mobile robot 200 through wireless communication and can transmit a specific command to the mobile robot 200 as needed.

Here, the control center 100 generates paths of the respective mobile robots 200 by using the path generation method according to the present invention to be described later, and controls the movement of the mobile robot 200, so that the mobile robot 200 Are prevented from colliding with each other and falling into a deadlock state when traveling in the traveling space.

Hereinafter, a path generation method according to the present invention will be described in detail with reference to FIG. 2 and FIG. Here, as shown in FIG. 5 and FIG. 9, the driving map applied to the route generating method according to the present invention may include a navigation map including a plurality of nodes and an edge connecting adjacent nodes For example.

4 is a diagram showing an example in which a collision is predicted or deadlocked between the mobile robots 200. FIG. 4A is a diagram showing a state in which the next destination node of the mobile robot 200 is occupied by another mobile robot 200. FIG. 4B is a diagram showing a state in which two or more mobile robots 200 run one to the other while sharing one edge. 4 (c) is a view showing a state in which one or more mobile robots 200 are trapped at corners.

When two or more mobile robots 200 move along the original path in the deadlock state as shown in FIG. 4, the mobile robots 200 collide with each other. In the example shown in FIG. 4, When the same state occurs, it can be predicted as a collision, and a route regeneration process for collision avoidance is performed through a process to be described later.

Referring again to FIG. 2, the path generation method according to the present invention will be described in detail. First, a driving map is registered in the route creation system according to the present invention (S20). Here, the travel map is composed of a plurality of nodes and edges, as described above, and the travel map can be registered in the control center 100 and each mobile robot 200.

Then, the initial priority is registered for each mobile robot 200 (S21). In the present invention, the initial priority is determined such that priority is determined and registered for each mobile robot 200 uniformly at an initial stage. Here, in addition to the registration of the initial priority, other variables for path generation and running of the mobile robot 200, as well as variables such as the source and destination, the moving speed, and the acceleration / deceleration speed of each mobile robot 200 may be registered together .

As described above, when the values of the initial priority, the destination and the place of departure are registered, a route from the departure point to the destination of each mobile robot 200 is generated based on the travel map. In the present invention, And a path of each mobile robot 200 is sequentially generated in order of initial priority (S22).

Here, in the path generation method according to the present invention, the path of the mobile robot 200 is generated based on any one of the Djikstra algorithm, the A * algorithm, and the D * algorithm.

The Djikstra algorithm, the A * algorithm, and the D * algorithm are applied to generate the shortest path. Referring briefly to FIG. 5, the shortest distance path from the source a to the destination b , All possible paths are generated along the edge connecting the node and the node, and the shortest path is searched by accumulating the distance of the corresponding path.

Here, in the present invention, in the process of generating a route according to the initial priority, the generated route includes the occupation of the node and the edge on the route, and information on the occupancy time.

In the state where occupancy according to the occupancy time of the node and the edge on the path generated first according to the initial priority is stored and the path is generated according to the subsequent initial priority, the node and the edge occupied in the occupancy time Is excluded from the path generation of the mobile robot 200 at present.

6, when the mobile robot 200 is located at the node G2 and the mobile robot 200 is located at the node G1, It is assumed that the robot 200 generates a route that the destination of the robot R1 is the node G1 and the destination of the mobile robot 200 is the node G2 and that the initial priority of the mobile robot 200 is the same as that of the mobile robot 200 It is assumed that the path is created assuming that it is higher than the initial priority.

The path of the mobile robot 200 having a high initial priority is firstly generated. According to the Djikstra algorithm for finding the path with the shortest distance, as shown in FIG. 7 (a), the mobile robot 200 The shortest path P1 is generated. At this time, as described above, when the path of the mobile robot 200 is generated, information on the occupancy time of nodes and edges on the path is stored together. FIG. 7 (b) And the occupancy time of the edge.

Then, the path of the mobile robot 200 R2, which is the next priority, is generated through the Djikstra algorithm. As shown in (c) of FIG. 7, the edge of the occupation time 3.5s to 4.5s Since the collision is predicted because the paths overlap in the area A, the edges in the occupation time are excluded from the path generation.

Therefore, in the path generation of the mobile robot 200, the route of the shortest distance is generated in a state in which the edge on the area A is excluded, so that the route P2 as shown in Fig. 8 can be generated.

Herein, in the process of generating paths in the order of the initial priorities for the plurality of mobile robots 200, it is possible to prevent conflicts among the subordinate mobile robots 200 due to nodes and edges occupied by path generation of the previous mobile robot 200 When there exists a mobile robot 200 in which there is no avoidable path, the traveling of the mobile robot 200 can be maintained in a standby state at the present cycle, and path generation in the next cycle, The path generation process is performed again in the path regeneration process. Here, the description of the cycle relating to the path generation will be described later.

Through the above process, when the path creation of each mobile robot 200 is completed (the mobile robot 200 in the standby state may exist), each of the mobile robots 200 starts running along the generated path (S23).

A collision check and a path regeneration process for regenerating a path in the case where a collision is predicted are performed in the traveling process of the mobile robots 200 in step S24, The traveling is proceeding.

Even if a collision-avoided path is generated for each of the mobile robots 200 through the above-described method, the collision inspection and path regeneration process may be performed in accordance with a change in the traveling environment occurring in the traveling process of the mobile robot 200, In the case where a change occurs in the original work plan due to an operation such as changing a path or reducing a speed in order to avoid a dynamic obstacle while driving or extending an operation time, So that a collision with another mobile robot 200 may occur, so that this is reflected.

(Hereinafter, referred to as a 'target mobile robot 200') among a plurality of mobile robots 200 and the rest of the mobile robots 200 A collision between the mobile robot 200 (hereinafter referred to as a "comparison mobile robot 200") is predicted sequentially.

Then, when the comparison mobile robot 200 in which a collision with the target mobile robot 200 is predicted in the prediction process is generated, the mobile robot 200 determines which one of the two mobile robots 200 One path is regenerated. In this case, when the traveling priority of the target mobile robot 200 is low, the path of the target mobile robot 200 is regenerated. This is because the comparison mobile robot 200, which is predicted to collide with the current target mobile robot 200, The path regeneration of the comparison mobile robot 200 can be considered when the comparison mobile robot 200 is in the position of the target mobile robot 200.

When the above process is performed on all the mobile robots 200, a path for avoiding collision can be generated for the mobile robot 200 in which the collision is predicted.

FIG. 3 is a diagram illustrating an algorithm for performing the collision detection and path regeneration process as described above. The collision inspection and path regeneration process according to the present invention will be described in more detail with reference to FIG. Herein, the execution cycle of the collision check and the path regeneration process is performed every time when one of the mobile robots 200 arrives at the next node, but the present invention is not limited thereto. In addition, as described above, in the case of the mobile robot 200 in which no path is generated in the generation of the initial path, the process of generating the shortest path in the path regeneration process is performed.

Steps S30 and S31 represent the initialization process of the variable. n denotes an index of the target mobile robot 200, and m denotes an index of the comparison mobile robot 200. When n and m are set to 1, a collision between the first mobile robot 200 and the first mobile robot 200 is predicted (S32). Here, the collision prediction checks whether a situation as shown in FIG. 4 occurs between the target mobile robot 200 and the comparison mobile robot 200. As described above, in the collision prediction, the paths of the two mobile robots 200 It is possible to predict the collision by comparing the occupation time of the node and the edge on the node and the edge on the node.

If a collision between the current target mobile robot 200 and the comparison mobile robot 200 is predicted in step S32, the traveling priorities between the target mobile robot 200 and the comparison mobile robot 200 are compared in step S33. Here, the driving priority may be set equal to the above-described initial priority.

In addition, the driving priority may be provided in a form different from the initial priority. For example, a task-based priority that reflects the importance of a given task to each mobile robot 200 is applicable. For example, when the mobile robot 200 according to the present invention is applied to transport the goods in the warehouse, the mobile robot 200, which is in the process of transferring the goods, The mobile robot 200 can be set to have a higher priority.

As another example, a regeneration path based priority that reflects the path cost of the path to be regenerated is excluded except for the node where the collision is predicted from the position of the mobile robot 200 at present. 9, when the original path of the mobile robot 200 is P1 (solid line) and the original path of the mobile robot 200 is P2 (dotted line), as shown in Fig. 9A, The two mobile robots 200 are predicted to collide. At this time, the path of the mobile robot 200 is regenerated to generate P1 '(one-dot chain line), the path of the mobile robot 200 is regenerated to generate P2' (chain double-dashed line) After the path cost of P1 'and P2' is compared with the regeneration route based priority, the path P2 'having a smaller path cost is determined as a regeneration path, and the path of the mobile robot 200 R2 can be regenerated.

In addition, the cost based priority in which the path cost from the position of the current mobile robot 200 to the node or the edge where the collision is predicted can be applied. For example, when a collision occurs at an adjacent node or edge at the current position, a path that simply bypasses any one of the paths is generated, and when collision avoidance is possible, the path of the mobile robot 200, May be regenerated.

Here, the driving priority may be provided in a combination priority form based on at least two combinations of the initial priority, the cost based priority, the mission based priority, and the route based priority. For example, it is possible to newly reflect the priority order of the current mobile robot 200 by numerically summing the four priorities with predetermined weights.

In this way, the traveling priority of the mobile robot 200 is reflected in the path regeneration by reflecting the working state and running distance of the current mobile robot 200, thereby making it possible to more efficiently generate the route plan.

Referring again to FIG. 3, if it is determined that the driving priority of the target mobile robot 200 is low through comparison of the driving priority in step S33, the path of the target mobile robot 200 is regenerated S34). Here, similar to the initial path generation method shown in Fig. 2, the path regeneration method is based on any one of the Djikstra algorithm, the A * algorithm, and the D * algorithm, The node and the edge occupied in the occupation time at the time of path regeneration are excluded from the path generation based on the information about the occupation time of the regeneration path so that the regenerated path collides with the existing path again in advance.

On the other hand, after the path is regenerated, it is determined whether the target mobile robot 200 corresponds to an atmospheric condition (S35). Here, the atmospheric condition means a case in which a path capable of collision avoidance is not generated during the path regeneration process.

If the waiting condition is not satisfied in step S35, that is, when the path is regenerated, the regeneration path is determined as a new path of the target mobile robot 200, and the target mobile robot 200 is driven on the regeneration path (step S36) . On the other hand, if the waiting condition is satisfied in step S35, a standby command is transmitted to the target mobile robot 200 so that the target mobile robot 200 is in the standby state in the current period (S37).

As described above, when the current target mobile robot 200 is predicted to collide with any of the comparison mobile robots 200 and the traveling priority of the target mobile robot 200 is lower than that of the comparison target robot 200, It is determined whether or not the collision inspection and the path regeneration process for all the mobile robots 200 are completed at step S38. If the determination of all the mobile robots 200 is not completed, To the target mobile robot 200 (S39), and performs the collision inspection and path regeneration process as described above.

On the other hand, if no collision between the current comparison mobile robot 200 and the current mobile robot 200 is predicted in step S32, collision prediction is performed on all of the mobile robots 200 other than the current target mobile robot 200 (S40). If the comparison with all of the mobile robots 200 is not completed, the mobile robot 200 of the next order is used as a comparison target robot (S41) (Step S32). On the other hand, if the comparison with all of the mobile robots 200 is completed in step S40, it is determined whether the collision prediction and the path regeneration process are completed with all the mobile robots 200 as the target mobile robot 200 (S42) When the remaining mobile robot 200 exists, the mobile robot 200 in the next order is used as the target mobile robot 200 (S43), and the collision inspection and path regeneration process is performed. And when the progress of the path regeneration process is completed, the collision check and path regeneration process in the current period are completed.

It is to be understood that both the foregoing general description and the following detailed description of the present invention are exemplary and explanatory and are intended to be exemplary and explanatory only and are not to be construed as limiting the scope of the inventive concept. And it is obvious that it is included in the technical idea of the present invention.

100: Control center 200: Mobile robot

Claims (9)

A path generation method for collision avoidance between a plurality of mobile robots,
(a) registering a running map on which the plurality of mobile robots travel;
(b) registering the initial priority, the origin and the destination for each of the mobile robots;
(c) generating a route from the departure location to the destination of each of the mobile robots based on the travel map, sequentially generated in the order of the initial priorities, avoiding collision between the routes of the mobile robot;
(d) each of the mobile robots travels according to a path generated in the step (c);
(e) predicting a collision between the mobile robots in a traveling process of the mobile robots;
(f) when a collision between the mobile robots is predicted in the step (e), a path of the mobile robot having the low driving priority is regenerated based on the traveling priority between the pair of mobile robots in which the collision is predicted Wherein the plurality of mobile robots are connected to the plurality of mobile robots. The method according to claim 1,
Wherein the traveling map comprises a plurality of nodes and an edge connecting the nodes in the step (a). 3. The method of claim 2,
Wherein the path generated in step (c) is generated based on any one of a Djikstra algorithm, an A * algorithm, and a D * algorithm;
The path generated in the step (c) includes information on the occupancy time of the node and the edge on the path;
In the step (c), whether or not occupancy of the nodes and edges on the path generated earlier according to the occupancy time is stored according to the initial priority, and the occupied nodes and edges in the subsequent occupancy time are stored in the path generation Wherein the plurality of mobile robots are excluded from the plurality of mobile robots. The method of claim 3,
Wherein, in the step (c), when there is a mobile robot in which there is no path capable of avoiding a collision among the plurality of mobile robots, the mobile robot is maintained in a running waiting state, A method for generating a route for a route. 3. The method of claim 2,
In the step (e), collision between any one of the plurality of mobile robots and the remaining mobile robots is sequentially predicted;
The step (f)
(f1) comparing the traveling priorities of the two mobile robots when a collision with any one of the mobile robots is predicted during the step (e); and
(f2) when the traveling priority of one of the mobile robots is low in the step (f1), the path of any one of the mobile robots is regenerated;
Wherein the steps (e), (f1), and (f2) are performed sequentially for all mobile robots. 6. The method of claim 5,
The steps (e), (f1), and (f2) are performed for the mobile robot having the higher traveling priority of any one of the mobile robots in the next step (f1) Wherein the plurality of mobile robots are connected to the plurality of mobile robots. 6. The method of claim 5,
Wherein the path generated in step (c) and the path regenerated in step (f) are generated based on any one of a Djikstra algorithm, an A * algorithm, and a D * algorithm;
The paths generated and regenerated in the step (c) and the step (f) include information on occupancy times of nodes and edges on the path;
In the step (f)
Wherein the occupancy of nodes and edges on the pre-created path with respect to the plurality of mobile robots is stored according to the occupancy time, and nodes and edges occupied in the occupying time at the time of path reclamation are excluded from the path creation. A path generation method for collision avoidance between mobile robots. 8. The method of claim 7,
Wherein when the path regenerated in the step (f) satisfies the pre-registered waiting condition, the traveling of the mobile robot is switched to the waiting state. 8. The method of claim 7,
Wherein the initial priority includes an initial priority initially registered for each of the plurality of mobile robots;
The driving priority is
The initial priority,
A cost based priority in which a path cost from a position of the mobile robot to a node or an edge at which a collision is predicted is reflected,
A task-based priority in which the mission importance of the mobile robot is reflected,
Based on a regeneration route based priority in which a path cost of a path to be regenerated is reflected excluding a node for which a collision is predicted from a current position of the mobile robot,
And a combination priority based on at least two combinations of the initial priority level, the cost-based priority, the mission-based priority, and the regeneration path-based priority. A method for generating a route.

Images